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

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.

Authors:

• Azali Saudi
• Jumat Sulaiman

Keywords:

• Modified Arithmetic Mean method
• Harmonic functions
• Laplace’s equation
• path planning.

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.