Agent Navigation based on Boundary Value Problem using Iterative Methods
Keywords:KSOR, KAOR, Harmonic function, navigation, boundary value problem, Laplace's equation
This paper presents the simulation of numerical solutions to the navigational problem of an agent traveling safely in its environment. The approach is based on the numeric solutions of the boundary value problem (BVP) that generate harmonic potential fields through a differential equation whose gradient represents navigation routes to the destination. Two methods, namely KSOR and KAOR, were tested to solve the BVP. KSOR and KAOR are variants of the standard SOR and AOR methods, respectively. In this work, the KSOR and KAOR methods were used to solve the BVP by applying Laplace's equation to obtain harmonic functions. The generated harmonic functions are then utilized by the searching algorithm to find a smooth navigational route for an agent to travel in its environment without colliding with any obstacles. The numerical results from the solutions of BVP demonstrate that the KAOR provides a faster execution time with fewer iterations compared to the KSOR method.
Akishita S, Kawamura S, Hayashi KI. (1990). Laplace potential for moving obstacle avoidance and approach of a mobile robot. In Japan-USA Symposium on Flexible Automation, A Pacific RIM Conference, p. 139-142.
Al-Taweel A, Dong Y, Hussain S, Wang X. (2021). A weak galerkin harmonic finite element method for laplace equation. Communications on Applied Mathematics and Computation, 3(3), 527-543.
Chou HJ, Kuo PL, Liu JS. (2017). Numerical streamline path planning based on log-space harmonic potential function: a simulation study. In Proc. of the 2017 IEEE International Conference on Real-time Computing and Robotics (RCAR), p. 535-542.
Connolly CI, Burns JB, Weiss R. (1990). Path planning using Laplace's equation. In Proc. of the IEEE International Conference on Robotics and Automation, p. 2102-2106.
Constantinescu R, Poenaru RC, Pop F, Popescu PG. (2019). A new version of KSOR method with lower number of iterations and lower spectral radius. Soft Computing, 23(22), 11729-11736.
Dahalan AA, Saudi A, Sulaiman J, Din WRW. (2017). Numerical evaluation of mobile robot navigation in static indoor environment via EGAOR Iteration. In Journal of Physics: Conference Series, IOP Publishing, p. 012064.
Daily R, Bevly DM. (2008, June). Harmonic potential field path planning for high speed vehicles. In Proc. of the 2008 American Control Conference, p. 4609-4614.
de Silva Jr EP, Engel PM, Trevisan M, Idiart MA. (2002). Exploration method using harmonic functions. Robotics and Autonomous Systems, 40(1), 25-42.
Grontas PD, Vlantis P, Bechlioulis CP, Kyriakopoulos KJ. (2020). Computationally Efficient Harmonic-Based Reactive Exploration. IEEE Robotics and Automation Letters, 5(2), 2280-2285.
Hadjidimos A. (1978). Accelerated Overelaxation Method. Mathematics of Computation, 32, 149-157, 1978.
Hadjidimos A. (2000). Successive overrelaxation (SOR) and related methods. Journal of Computational and Applied Mathematics, 123(1-2), 177-199.
Mohammed F, Rivaie M. (2017). Jacobi-Davidson, Gauss–Seidel and successive over-relaxation for solving systems of linear equations. Applied Mathematics and Computational Sciences, 6, 41-52.
Montiel O, Orozco-Rosas U, Sepúlveda R. (2015). Path planning for mobile robots using Bacterial Potential Field for avoiding static and dynamic obstacles. Expert Systems with Applications, 42(12), 5177-5191.
Muhiddin FA, Sulaiman, J., and Sunarto, A. (2020). Grünwald implicit solution of one-dimensional time-fractional parabolic equations using HSKSOR iteration. In Journal of Physics: Conference Series, IOP Publishing, p. 2025.
Musli FA, Saudi A. (2019). Agent Navigation via Harmonic Potentials with Half-Sweep Kaudd Successive Over Relaxation (HSKSOR) Method. In Proc. of the 2019 IEEE 9th Symposium on Computer Applications & Industrial Electronics (ISCAIE), p. 335-339.
Nguyen T, Pham B, Nguyen TT, Nguyen BT. (2020). A deep learning approach for solving Poisson’s equations. In Proceeding of 12th International Conference on Knowledge and Systems Engineering, p. 213-218.
Prestesy E, Idiartz M. (2010). Computing navigational routes in inhomogeneous environments using bvp path planner. In Proceeding of IEEE/RSJ International Conference on Intelligent Robots and Systems, p. 1427-1432.
Radzuan NZFM, Suardi MN, Sulaiman J. (2017). KSOR iterative method with quadrature scheme for solving system of Fredholm integral equations of second kind. Journal of Fundamental and Applied Sciences, 9, 609-623.
Sabudin EN, Omar R, Ckan H, Melor CK. (2016). Potential field methods and their inherent approaches for path planning. ARPN Journal of Engineering and Applied Sciences, 11(18), 10801-10805.
Suardi MN, Radzuan NZFM, Sulaiman J. (2017). Cubic B-spline solution of two-point boundary value problem using HSKSOR iteration. Global Journal of Pure and Applied Mathematics, 13(11), 7921-7934.
Wray KH, Ruiken D, Grupen RA, Zilberstein S. (2016). Log-space harmonic function path planning. In Proc. of the 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 1511-1516.
Young DM. (1971). Iterative Solution of Large Linear Systems. Academic Press, New York.
Youssef IK, Farid MM. (2015). On the accelerated overrelaxation method. Pure and Applied Mathematics Journal, 4(1), 26-31.
Youssef IK, Taha AA. (2013). On the modified successive overrelaxation method. Applied Mathematics and Computation, 219(9), 4601-4613.
Youssef IK. (2012). On the successive overrelaxation method. Journal of Mathematics and Statistics, 8, 176-184.
How to Cite
Copyright (c) 2023 Farhah Athirah Musli, Azali Saudi
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.