Artificial potential field path length reduction using Kenneth-Nnanna-Saleh algorithm

Kenneth Christopher Ugwoke; Nnanna Nwojo Agwu; Saleh El-Yakub Abdullahi

doi:10.46481/jnsps.2025.2659

Authors

Kenneth Christopher Ugwoke
[email protected]
Department of Computer Science, Nile University of Nigeria, Plot 681, Cadastral Zone C, Airport Road, Jabi, Abuja, Nigeria
Nnanna Nwojo Agwu Department of Computer Science, Nile University of Nigeria, Plot 681, Cadastral Zone C, Airport Road, Jabi, Abuja, Nigeria
Saleh Abdullahi Department of Computer Science, Nile University of Nigeria, Plot 681, Cadastral Zone C, Airport Road, Jabi, Abuja, Nigeria

Keywords:

Path planning, Artificial potential field, Obstacle avoidance

Abstract

The artificial potential field (APF) is one of the famous path planning algorithms. It creates a virtual force field that attracts a robot to the goal or repels it from an obstacle, forcing it to move along the direction of the resultant forces toward the goal. The repulsive force pushes the robot away from the obstacle, causing a large displacement from the straight path, increasing the path length. This paper presents the Kenneth-Nnanna-Saleh (KNS) algorithm that can shorten the length of an APF path by reducing its waypoints. The algorithm takes an APF path that is generated from the problem domain as input, evaluates angles at each point, and compares the angle with a pre-defined threshold angle to remove or retain the point in the resultant KNS path. Simulation environments, each with varying complexity in obstacle arrangement, were designed for various simulations of the proposed algorithm. A Python-based computer simulation program was implemented and used to simulate the KNS, APF, and a similar waypoint reduction algorithm -Ramer-Douglas-Peucker (RDP) and the results were analyzed. The results show that KNS can yield a shorter path than APF and RDP and retain the obstacle avoidance feature of the path. The shortened path maintains the geometry of the APF path and leads to reduced energy cost for the deployment of robots.

Dimensions

REFERENCES

[1] H. Qin, S. Shao, T. Wang, X. Yu, Y. Jiang & Z. Cao, “Review of autonomous path planning algorithms for mobile robots”, Drones 7 (2023) 211. https://doi.org/10.3390/drones7030211.

[2] Y. Benjmaa & D. Duvivier, “A review of path planning algorithms”, in Intelligent systems design and applications, A. Abraham, A. Bajaj, T. Hanne, P. Siarry & K. Ma (Eds.), Springer Nature Switzerland, Cham, 2024, pp. 119–130. https://doi.org/10.1007/978-3-031-64850-2_11.

[3] A. N. A. Rafai, N. Adzhar & N. I. Jaini, “A review on path planning and obstacle avoidance algorithms for autonomous mobile robots”, J. Robot. 2022 (2022) 2538220. https://doi.org/10.1155/2022/2538220.

[4] S. Dian, J. Zhong, B. Guo, J. Liu & R. Guo, “A smooth path planning method for mobile robot using a BES-incorporated modified QPSO algorithm”, Expert Syst. Appl. 208 (2022) 118256. https://doi.org/10.1016/j.eswa.2022.118256.

[5] K. S. Suresh, R. Venkatesan & S. Venugopal, “Mobile robot path planning using multi-objective genetic algorithm in industrial automation”, Soft Comput. 26 (2022) 7387. https://doi.org/10.1007/s00500-022-07300-8.

[6] D. Han, Q. Yu, H. Jiang, Y. Chen, X. Zhu & L. Wang, “Three-dimensional path planning for post-disaster rescue UAV by integrating improved grey wolf optimizer and artificial potential field method”, Appl. Sci. 14 (2024) 4461. https://doi.org/10.3390/app14114461.

[7] L. Liu, X. Wang, X. Yang, H. Liu, J. Li & P. Wang, “Path planning techniques for mobile robots: review and prospect”, Expert Syst. Appl. 227 (2023) 120254. https://doi.org/10.1016/j.eswa.2023.120254.

[8] A. S. Abdel-Rahman, S. Zahran, B. E. Elnaghi & S. F. Nafea, “Enhanced hybrid path planning algorithm based on APF and A-star”, Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci. 48 (2023) 867. https://doi.org/10.5194/isprs-archives-XLVIII-1-W2-2023-867-2023.

[9] J. Yang, H. Zhang & P. Ning, “Path planning and trajectory optimization based on improved APF and multi-target”, IEEE Access 11 (2023) 139121. https://doi.org/10.1109/ACCESS.2023.3338683.

[10] M. Wakchaure, B. K. Patle & A. K. Mahindrakar, “Artificial intelligence in the life sciences application of AI techniques and robotics in agriculture: a review”, Artif. Intell. Life Sci. 3 (2023) 100057. https://doi.org/10.1016/j.ailsci.2023.100057.

[11] G. Huang & Q. Ma, “Research on path planning algorithm of autonomous vehicles based on improved RRT algorithm”, Int. J. Intell. Transp. Syst. Res. 20 (2022) 170. https://doi.org/10.1007/s13177-021-00281-2.

[12] F. Method, “Research on autonomous vehicle path planning based on improved A* algorithm and improved DWA algorithm”, Sensors 24 (2024) 3899. https://doi.org/10.3390/s24123899.

[13] L. Cao, L. Wang, Y. Liu & S. Yan, “3D trajectory planning based on the rapidly-exploring random tree–connect and artificial potential fields method for unmanned aerial vehicles”, Int. J. Adv. Robot. Syst. 19 (2022) 1. https://doi.org/10.1177/17298806221118867.

[14] J. Fan, X. Chen & X. Liang, “UAV trajectory planning based on bi-directional APF-RRT* algorithm with goal-biased”, Expert Syst. Appl. 213 (2023) 119137. https://doi.org/10.1016/j.eswa.2022.119137.

[15] M. Li, B. Li, Z. Qi, J. Li & J. Wu, “Optimized APF-ACO algorithm for ship collision avoidance and path planning”, J. Mar. Sci. Eng. 11 (2023) 1177. https://doi.org/10.3390/jmse11061177.

[16] J. Luo, Z. Wang & K. Pan, “Reliable path planning algorithm based on improved artificial potential field method”, IEEE Access 10 (2022) 108276. https://doi.org/10.1109/ACCESS.2022.3212741.

[17] L. Liu & B. Wang, “Research on path-planning algorithm integrating optimization a-star algorithm and artificial potential field method”, Electronics 11 (2022) 3660. https://doi.org/10.3390/electronics11223660.

[18] G. Hao, Q. Lv, Z. Huang, H. Zhao & W. Chen, “UAV path planning based on improved artificial potential”, Aerospace 10 (2023) 562. https://doi.org/10.3390/aerospace10060562.

[19] X. Lv, W. Li & J. Wang, “Safety-field-based path planning algorithm of lane changing for autonomous vehicles”, Int. J. Control Autom. Syst. 20 (2022) 564. https://doi.org/10.1007/s12555-020-0942-3.

[20] A. Gültekin, S. Diri & Y. Becerikli, “Simplified and smoothed rapidly-exploring random tree algorithm for robot path planning”, Teh. Vjesn. 30 (2023) 891. https://doi.org/10.17559/TV-20221015080721.

[21] B. Dergisi, “Effective solutions for common problems of artificial potential field based path planning algorithms for mobile robots mobil robotlar için yapay potansiyel alan tabanli yol planlama mixed integer linear programming approach artificial potential fields vec”, Bujse 15 (2022) 105. https://doi.org/10.20854/bujse.1214752.

[22] R. Raj & A. Kos, “A comprehensive study of mobile robot: history, developments, applications, and future research perspectives”, Appl. Sci. 12 (2022) 6951. https://doi.org/10.3390/app12146951.

[23] A. A. Nippun Kumaar & S. Kochuvila, “Mobile service robot path planning using deep reinforcement learning”, IEEE Access 11 (2023) 100083. https://doi.org/10.1109/ACCESS.2023.3311519.

[24] M. Jones, S. Djahel & K. Welsh, “Path-planning for unmanned aerial vehicles with environment complexity considerations: a survey”, ACM Comput. Surv. 55 (2023) 1. https://doi.org/10.1145/3570723.

[25] H. Han, Z. Xi, J. Cheng & M. Lv, “Obstacle avoidance based on deep reinforcement learning and artificial potential field”, in 2023 9th International Conference on Control, Automation and Robotics (ICCAR), 2023, pp. 215–220. https://doi.org/10.1109/ICCAR57134.2023.10151771.

[26] J. M. Jayoma, G. P. Navales, F. A. M. Bustamante & L. R. Tradio, “Enhanced Ramer-Douglas-Peucker algorithm for efficient 2D line simplification”, in 2023 IEEE 15th International Conference on Humanoid, Nanotechnology, Information Technology, Communication and Control, Environment, and Management (HNICEM), 2023, pp. 1–6. https://doi.org/10.1109/HNICEM60674.2023.10589058.

[27] B. Dergisi, “Effective solutions for common problems of artificial potential field based path planning algorithms for mobile robots mobil robotlar için yapay potansiyel alan tabanli yol planlama mixed integer linear programming approach artificial potential fields vec”, Bujse 15 (2022) 105. https://doi.org/10.20854/bujse.1214752.

[28] M. Kara, “Evaluation of popular path planning algorithms”, Int. J. Electron. Telecommun. 70 (2024) 13. https://doi.org/10.24425/ijet.2023.147699.

[29] R. Raza, A. T. Ab Ghani & L. Abdullah, “Extension of hesitant fuzzy weight geometric (HFWG)-VIKOR method under hesitant fuzzy information”, J. Niger. Soc. Phys. Sci. 6 (2024) 2157. https://doi.org/10.46481/jnsps.2024.2157.