Autonomous Vehicle Navigation Using Harmonic Functions via Modified Arithmetic Mean Iterative Method

Authors: Azali Saudi, Jumat Sulaiman

Abstract:

Harmonic functions are solutions to Laplace’s equation that are known to have an advantage as a global approach in providing the potential values for autonomous vehicle navigation. However, the computation for obtaining harmonic functions is often too slow particularly when it involves very large environment. This paper presents a two-stage iterative method namely Modified Arithmetic Mean (MAM) method for solving 2D Laplace’s equation. Once the harmonic functions are obtained, the standard Gradient Descent Search (GDS) is performed for path finding of an autonomous vehicle from arbitrary initial position to the specified goal position. Details of the MAM method are discussed. Several simulations of vehicle navigation with path planning in a static known indoor environment were conducted to verify the efficiency of the MAM method. The generated paths obtained from the simulations are presented. The performance of the MAM method in computing harmonic functions in 2D environment to solve path planning problem for an autonomous vehicle navigation is also provided.

Keywords: Modified Arithmetic Mean method, Harmonic functions, Laplace’s equation, path planning.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.2643972

References:

[1] A. Saudi and J. Sulaiman. Block Iterative Method for Robot Path Planning. The 2nd Seminar on Engineering and Information Technology, Kota Kinabalu, July 7 8, 2009.
[2] A. Saudi and J. Sulaiman. Numerical Technique for Robot Path Planning using Four Point-EG Iterative Method. In proc. of the Int. Symposium on Information Technology, 2010, pp. 831 836.
[3] A. Saudi and J. Sulaiman. Indoor Path Planning for Mobile Robot using LBBC-EG. Int. J. of Imaging and Robotics, 11(3), 2013, pp. 37-45.
[4] A. Saudi and J. Sulaiman. Hybrid Path Planning for Indoor Robot with Laplacian Behaviour-Based Control via Four Point-Explicit Group. Int. J. of Imaging and Robotics, 12(1), 2014, pp. 12-21.
[5] C. I. Connolly, J. Burns, and R. Weiss. Path planning using Laplace’s equation. In Proceedings of the IEEE International Conference on Robotics and Automation, May 13-18, 1990, Cincinnati, USA, pp. 2102-2106.
[6] C. I. Connolly and R. A. Grupen. The applications of harmonic functions to robotics. Journal of Robotic Systems, 10(7), 1993, pp. 931-946.
[7] D. E. Koditschek. Exact robot navigation by means of potential functions: Some topological considerations. In Proceedings of the IEEE International Conference on Robotics and Automation, March 31 - April 3, 1987, Raleigh, USA, vol. 4, 1987, pp. 1-6.
[8] D. M. Young. Iterative Methods for Solving Partial Difference Equations of Elliptic Type. PhD Thesis. Harvard University, 1950.
[9] D. R. Kincaid and D. M. Young. The modified successive overrelaxation method with fixed parameters. Mathematics and Computations, 119, 1972, pp. 705-717.
[10] I. Galligani and V. Ruggiero. The Arithmetic Mean method for solving essentially positive systems on a vector computer. Int. J. Computer Math., 32, 1990. pp. 113121.
[11] J. Sulaiman, M. Othman and M. K. Hasan. A new Half-Sweep Arithmetic Mean (HSAM) algorithm for two-point boundary value problems. In Proceedings of the International Conference on Statistics and Mathematics and its Application in the Development of Science and Technology, 2004, pp. 169-173.
[12] J. Sulaiman, M. Othman and M. K. Hasan. A new Quarter Sweep Arithmetic Mean (QSAM) method to solve diffusion equations. Chamchuri Journal of Mathematics, 1(2), 2009, pp. 93-103.
[13] M. D. Pedersen and T. I. Fossen. Marine vessel path planning and guidance using potential flow. In Proceedings of the 9th IFAC Conference on Manoeuvring and Control of Marine Craft, Sep 19-21, 2012, Arenzano, Italy, pp. 188-193.
[14] M. S. Muthuvalu and J. Sulaiman. Half-Sweep Arithmetic Mean method with composite trapezoidal scheme for solving linear Fredholm integral equations. Applied Mathematics and Computation, 217(12), 2011, pp. 5442-5448.
[15] M. S. Muthuvalu and J. Sulaiman. An implementation of the 2-point block arithmetic mean iterative method for first kind linear Fredholm integral equations. World Journal of Modelling and Simulation, 8(4), 2012, pp. 293-301.
[16] O. Khatib. Real-time obstacle avoidance for manipulators and mobile robots. In Proceedings of the IEEE International Conference on Robotics and Automation, Mar 25-28, 1985, St. Louis, USA, vol. 2, 1985, pp. 500-505.
[17] P. Szulczynski, D. Pazderski and K. Kozlowski. Real-time obstacle avoidance using harmonic potential functions. Journal of Automation Mobile Robotics and Intelligent Systems, 5: 59-66.
[18] R. Kress. Numerical Analysis. New York: Springer-Verlag, 1998.
[19] S. Akishita, S. Kawamura, and K. Hayashi. Laplace potential for moving obstacle avoidance and approach of a mobile robot. In Japan-USA Symposium on Flexible Automation, July 9-13, 1990, Kyoto, Japan, pp. 139-142.
[20] S. Garrido, L. Moreno, D. Blanco, and M. F. Martin. Robotic motion using harmonic functions and finite elements. Journal of Intelligent and Robotic Systems, 59(1), 2010, pp. 57-73.
[21] X. Liang, H. Wang, D. Li, and C. Liu. Three-dimensional path planning for unmanned aerial vehicles based on fluid flow. In Proceedings of the IEEE Aerospace Conference, March 1-8, 2014, Big Sky, USA, pp. 1-13.