An iterative technique for solving path planning in identified environments by using a skewed block accelerated algorithm

A'qilah Ahmad Dahalan; Azali Saudi; A'qilah Ahmad Dahalan; Azali Saudi

doi:10.3934/math.2023288

AIMS Mathematics

2023, Volume 8, Issue 3: 5725-5744. doi: 10.3934/math.2023288

Previous Article Next Article

Research article

An iterative technique for solving path planning in identified environments by using a skewed block accelerated algorithm

A'qilah Ahmad Dahalan ^{1,2,3
,
,},
Azali Saudi ⁴

1.
CONFIRM Centre for SMART Manufacturing, University of Limerick, Limerick, Ireland
2.
MACSI, Department of Mathematics and Statistics, University of Limerick, Limerick, Ireland
3.
Department of Mathematics, Universiti Pertahanan Nasional Malaysia, Kuala Lumpur, Malaysia
4.
Faculty of Computing and Informatics, Universiti Malaysia Sabah, Kota Kinabalu, Malaysia

Received: 26 August 2022 Revised: 18 October 2022 Accepted: 26 October 2022 Published: 22 December 2022
MSC : 35A35, 65F10, 68T40

Currently, designing path-planning concepts for autonomous robot systems remains a topic of high interest. This work applies computational analysis through a numerical approach to deal with the path-planning problem with obstacle avoidance over a robot simulation. Based on the potential field produced by Laplace's equation, the formation of a potential function throughout the simulation configuration regions is obtained. This potential field is typically employed as a guide in the global approach of robot path-planning. An extended variant of the over-relaxation technique, namely the skewed block two-parameter over relaxation (SBTOR), otherwise known as the explicit decoupled group two-parameter over relaxation method, is presented to obtain the potential field that will be used for solving the path-planning problem. Experimental results with a robot simulator are presented to demonstrate the performance of the proposed approach on computing the harmonic potential for solving the path-planning problem. In addition to successfully validating pathways generated from various locations, it is also demonstrated that SBTOR outperforms existing over-relaxation algorithms in terms of the number of iterations, as well as the execution time.
- rotated iterative scheme,
- numerical analysis,
- Laplace's equation,
- accelerated method,
- path finding,
- obstacle avoidance
Citation: A'qilah Ahmad Dahalan, Azali Saudi. An iterative technique for solving path planning in identified environments by using a skewed block accelerated algorithm[J]. AIMS Mathematics, 2023, 8(3): 5725-5744. doi: 10.3934/math.2023288

Related Papers:

Abstract

Currently, designing path-planning concepts for autonomous robot systems remains a topic of high interest. This work applies computational analysis through a numerical approach to deal with the path-planning problem with obstacle avoidance over a robot simulation. Based on the potential field produced by Laplace's equation, the formation of a potential function throughout the simulation configuration regions is obtained. This potential field is typically employed as a guide in the global approach of robot path-planning. An extended variant of the over-relaxation technique, namely the skewed block two-parameter over relaxation (SBTOR), otherwise known as the explicit decoupled group two-parameter over relaxation method, is presented to obtain the potential field that will be used for solving the path-planning problem. Experimental results with a robot simulator are presented to demonstrate the performance of the proposed approach on computing the harmonic potential for solving the path-planning problem. In addition to successfully validating pathways generated from various locations, it is also demonstrated that SBTOR outperforms existing over-relaxation algorithms in terms of the number of iterations, as well as the execution time.

References

[1]	B. Patle, B. Ganesh, A. Pandey, D. Parhi, A. Jagadeesh, A review: On path planning strategies for navigation of mobile robot, Def. Technol., 15 (2019), 582–606. https://doi.org/10.1016/j.dt.2019.04.011 doi: 10.1016/j.dt.2019.04.011
[2]	N. Buniyamin, N. Sariff, W. Wan Ngah, Z. Mohamad, Robot global path planning overview and a variation of ant colony system algorithm, International Journal of Mathematics and Computers in Simulation, 5 (2011), 9–16.
[3]	S. Sasaki, A practical computational technique for mobile robot navigation, Proceedings of the IEEE International Conference on Control Applications, 1998, 1323–1327. https://doi.org/10.1109/CCA.1998.721675 doi: 10.1109/CCA.1998.721675
[4]	H. Chou, P. Kuo, J. Liu, Numerical streamline path planning based on log-space harmonic potential function: a simulation study, Proceedings of IEEE International Conference on Real-time Computing and Robotics, 2017,535–542. https://doi.org/10.1109/RCAR.2017.8311918 doi: 10.1109/RCAR.2017.8311918
[5]	Y. An, S. Wang, C. Xu, L. Xie, 3D path planning of quadrotor aerial robots using numerical optimization, Proceedings of the 32nd Chinese Control Conference, 2013, 2305–2310.
[6]	M. Silva, W. Silva, R. Romero, Performance analysis of path planning techniques based on potential fields, Proceedings of Latin American Robotics Symposium and Intelligent Robotics Meeting, 2010,115–119. https://doi.org/10.1109/LARS.2010.33 doi: 10.1109/LARS.2010.33
[7]	C. Connolly, R. Gruppen, The applications of harmonic functions to robotics, Journal of Robotic Systems, 10 (1993), 931–946. https://doi.org/10.1002/rob.4620100704 doi: 10.1002/rob.4620100704
[8]	O. Khatib, Real-time obstacle avoidance for manipulators and mobile robots, Proceedings of IEEE International Conference on Robotics and Automation, 1985,500–505. https://doi.org/10.1109/ROBOT.1985.1087247 doi: 10.1109/ROBOT.1985.1087247
[9]	H. Ghassemi, S. Panahi, A. Kohansal, Solving the Laplace's equation by the FDM and BEM using mixed boundary conditions, American Journal of Applied Mathematics and Statistics, 4 (2016), 37–42. https://doi.org/10.12691/ajams-4-2-2 doi: 10.12691/ajams-4-2-2
[10]	A. Dahalan, A. Saudi, Pathfinding algorithm based on rotated block AOR technique in structured environment, AIMS Mathematics, 7 (2022), 11529–11550. https://doi.org/10.3934/math.2022643 doi: 10.3934/math.2022643
[11]	K. Al-Khaled, Numerical solutions of the Laplace's equation, Appl. Math. Comput., 170 (2005), 1271–1283. https://doi.org/10.1016/j.amc.2005.01.018 doi: 10.1016/j.amc.2005.01.018
[12]	K. Shivaram, H. Jyothi, Finite element approach for numerical integration over family of eight node linear quadrilateral element for solving Laplace equation, Mater. Today: Proc., 46 (2021), 4336–4340. https://doi.org/10.1016/j.matpr.2021.03.437 doi: 10.1016/j.matpr.2021.03.437
[13]	C. Connolly, J. Burns, R. Weiss, Path planning using Laplace's equation, Proceedings of IEEE International Conference on Robotics and Automation, 1990, 2102–2106. https://doi.org/10.1109/ROBOT.1990.126315 doi: 10.1109/ROBOT.1990.126315
[14]	J. Barraquand, B. Langlois, J. Latombe, Numerical potential field techniques for robot path planning, IEEE T. Syst. Man. Cy., 22 (1992), 224–241. https://doi.org/10.1109/21.148426 doi: 10.1109/21.148426
[15]	M. Karnik, B. Dasgupta, V. Eswaran, A comparative study of Dirichlet and Neumann conditions for path planning through harmonic functions, In: Lecture notes in computer science, Berlin: Springer, 2002,442–451. https://doi.org/10.1007/3-540-46080-2_46
[16]	A. Abdullah, The four point explicit decoupled group (EDG) method: a fast Poison solver, Int. J. Comp. Math., 38 (1991), 61–70. https://doi.org/10.1080/00207169108803958 doi: 10.1080/00207169108803958
[17]	J. Sulaiman, M. Hassan, M. Othman, The half-sweep iterative alternating decomposition explicit (HSIADE) method for diffusion equation, In: Computational and information science, Berlin: Springer, 2004, 57–63. https://doi.org/10.1007/978-3-540-30497-5_10
[18]	A. Saudi, J. Sulaiman, Block iterative method for robot path planning, Proceedings of the 2nd Seminar on Engineering and Technology, 2009, 1–4.
[19]	A. Saudi, J. Sulaiman, Half-Sweep Gauss-Seidel (HSGS) iterative method for robot path planning, Proceedings of the 3rd International Conference on Informatics and Technology, 2009, 34–39.
[20]	A. Saudi, J. Sulaiman, Robot path planning using Laplacian Behaviour-Based Control (LBBC) via half-sweep SOR, Proceedings of the International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, 2013,424–429. https://doi.org/10.1109/TAEECE.2013.6557312 doi: 10.1109/TAEECE.2013.6557312
[21]	S. Matsui, H. Nagahara, R. Taniguchi, Half-sweep imaging for depth from defocus, Image Vision Comput., 32 (2014), 954–964. https://doi.org/10.1016/j.imavis.2014.09.001 doi: 10.1016/j.imavis.2014.09.001
[22]	J. Chew, J. Sulaiman, A. Sunarto, Solving one-dimensional porous medium equation using unconditionally stable half-sweep finite difference and SOR method, Mathematics and Statistics, 9 (2021), 166–171. https://doi.org/10.13189/ms.2021.090211 doi: 10.13189/ms.2021.090211
[23]	F. Musli, J. Sulaiman, A. Saudi, Numerical simulations of agent navigation via half-sweep modified two-parameter over-relaxation (HSMTOR), Journal of Physics Conference Series, 1988 (2021), 012035. https://doi.org/10.1088/1742-6596/1988/1/012035 doi: 10.1088/1742-6596/1988/1/012035
[24]	A. Saudi, A. Dahalan, An efficient red-black skewed modified accelerated arithmetic mean iterative method for solving two-dimensional Poisson equation, Symmetry, 14 (2022), 993. https://doi.org/10.3390/sym14050993 doi: 10.3390/sym14050993
[25]	A. Dahalan, A. Saudi, Pathfinding algorithm based on rotated block AOR technique in structured environment, AIMS Mathematics, 7 (2022), 11529–11550. https://doi.org/10.3934/math.2022643 doi: 10.3934/math.2022643
[26]	M. Othman, A. Abdullah, An efficient four points modified explicit group Poisson solver, Int. J. Comput. Math., 76 (2000), 203–217. https://doi.org/10.1080/00207160008805020 doi: 10.1080/00207160008805020
[27]	D. Evans, Group explicit iterative methods for solving large linear systems, Int. J. Comput. Math., 17 (1985), 81–108. https://doi.org/10.1080/00207168508803452 doi: 10.1080/00207168508803452
[28]	G. Dahlquist, Å. Björck, Numerical Methods, New Jersey: Prentice Hall, 1974.
[29]	W. Yousif, D. Evans, Explicit group over-relaxation methods for solving elliptic partial differential equations, Math. Comput. Simulat., 28 (1986), 453–466. https://doi.org/10.1016/0378-4754(86)90040-6 doi: 10.1016/0378-4754(86)90040-6
[30]	D. Young, Iterative methods for solving partial difference equations of elliptic type, T. Am. Math. Soc., 76 (1954), 92–111. https://doi.org/10.2307/1990745 doi: 10.2307/1990745
[31]	D. Young, Iterative methods for solving partial difference equations of elliptic type, Ph. D. Thesis, Harvard University, 1950.
[32]	A. Hadjidimos, Accelerated overrelaxation method, Math. Comput., 32 (1978), 149–157. https://doi.org/10.2307/20006264 doi: 10.2307/20006264
[33]	J. Kuang, J. Ji, A survey of AOR and TOR methods, J. Comput. Appl. Math., 24 (1988), 3–12. https://doi.org/10.1016/0377-0427(88)90340-8 doi: 10.1016/0377-0427(88)90340-8
[34]	N. Ali, F. Pin, Modified explicit group AOR methods in the solution of elliptic equations, Applied Mathematical Sciences, 6 (2012), 2465–2480.
[35]	M. Martins, W. Yousif, D. Evans, Explicit group AOR method for solving elliptic partial differential equations, Neural, Parallel and Scientific Computations, 10 (2002), 411–422.
[36]	N. Ali, L. Chong, Group accelerated OverRelaxation methods on rotated grid, Appl. Math. Comput., 191 (2007), 533–542. https://doi.org/10.1016/j.amc.2007.02.131 doi: 10.1016/j.amc.2007.02.131
[37]	A. Saudi, Robot path planning using family of SOR iterative methods with Laplacian behavior-based control, Ph. D. Thesis, University Malaysia Sabah, 2015.
[38]	S. Chen, Collision-free path planning, Ph. D. Thesis, Iowa State University, 1997. https://doi.org/10.31274/rtd-180813-10480
[39]	J. Sanchez-Ibanez, C. Perez-del-Pulgar, A. Garcia-Cerezo, A path planning for autonomous mobile robots: a review, Sensors, 21 (2021), 7898. https://doi.org/10.3390/s21237898 doi: 10.3390/s21237898
[40]	T. Iwashita, M. Shimasaki, Block red-black ordering: a new ordering strategy for parallelization of ICCG method, Int. J. Parallel Prog., 31 (2003), 55–75. https://doi.org/10.1023/A:1021738303840 doi: 10.1023/A:1021738303840
[41]	N. Saad, A. Sunarto, A. Saudi, Accelerated red-black strategy for image composition using Laplacian operator, IJCDS, 10 (2021), 1085–1095. https://doi.org/10.12785/ijcds/100198 doi: 10.12785/ijcds/100198
[42]	A. Dahalan, A. Saudi, J. Sulaiman, Pathfinding for mobile robot navigation by exerting the quarter-sweep modified accelerated overrelaxation (QSMAOR) iterative approach via the Laplacian operator, Mod. Simul. Eng., 2022 (2022), 9388146. https://doi.org/10.1155/2022/9388146 doi: 10.1155/2022/9388146

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)