Streamlined A* for Faster Robotic Inspections in Ports
Abstract
Research on automatic port inspections using robots has been carried out in the state-owned company Indonesia Port Corporation, Semarang, Indonesia. However, increasing the efficiency of robotic inspections is critical because robots need to perform these tasks at much higher speeds than humans, while maintaining a high level of accuracy. The robot is equipped with sensors and computer vision technology to detect defects or problems that humans might miss. The aim is to increase overall inspection accuracy at a lower cost. In this research, we introduce an optimized A* path planning algorithm that incorporates the flood algorithm, node reductions process, and linear path planning optimization for an autonomous navigated port inspection robot. Our primary objective is to significantly increase the efficiency of the conventional A* algorithm in guiding robotic systems through complex paths. The proposed algorithm demonstrates exceptional efficiency in generating feasible paths, with success attributed to optimization steps that specifically target reducing node processing and enhancing route finding. The experimentation phase involves a comprehensive assessment of the algorithm using six key parameters: running time, number of nodes, number of turns, maximum turning angle, expansion nodes, and the total distances output. Through rigorous testing, the algorithm's performance is evaluated and compared against seven other current algorithms, namely A*, BestFirst, Dijkstra, BFS, DFS, Bidirectional A*, and Geometric A*. Results from the experiments reveal the algorithm's outstanding running time efficiency, surpassing all other algorithms tested. Notably, it exhibits a remarkable 6.5% improvement over the widely recognized Geometric A* algorithm.
Downloads
References
I. Rusinov, E. Besedina, and N. Shcherbinin, “Global Trends of the Cargo Handling Operations Automatization at Container Terminals,” in International Scientific Siberian Transport Forum TransSiberia - 2021, A. Manakov and A. Edigarian, Eds., in Lecture Notes in Networks and Systems. Cham: Springer International Publishing, 2022, pp. 1492–1508. doi: 10.1007/978-3-030-96380-4_165.
H. Zhang, W. Lin, and A. Chen, “Path Planning for the Mobile Robot: A Review,” Symmetry, vol. 10, no. 10, Art. no. 10, Oct. 2018, doi: 10.3390/sym10100450.
A. Ait Saadi, A. Soukane, Y. Meraihi, A. Benmessaoud Gabis, S. Mirjalili, and A. Ramdane-Cherif, “UAV Path Planning Using Optimization Approaches: A Survey,” Arch Computat Methods Eng, vol. 29, no. 6, pp. 4233–4284, Oct. 2022, doi: 10.1007/s11831-022-09742-7.
W. Chi, Z. Ding, J. Wang, G. Chen, and L. Sun, “A Generalized Voronoi Diagram-Based Efficient Heuristic Path Planning Method for RRTs in Mobile Robots,” IEEE Transactions on Industrial Electronics, vol. 69, no. 5, pp. 4926–4937, May 2022, doi: 10.1109/TIE.2021.3078390.
V. Agarwal, S. Tapaswi, and P. Chanak, “A Survey on Path Planning Techniques for Mobile Sink in IoT-Enabled Wireless Sensor Networks,” Wireless Pers Commun, vol. 119, no. 1, pp. 211–238, Jul. 2021, doi: 10.1007/s11277-021-08204-w.
H. Zhao et al., “Fire evacuation supported by centralized and decentralized visual guidance systems,” Safety Science, vol. 145, p. 105451, Jan. 2022, doi: 10.1016/j.ssci.2021.105451.
J.-S. Chou, M.-Y. Cheng, Y.-M. Hsieh, I.-T. Yang, and H.-T. Hsu, “Optimal path planning in real time for dynamic building fire rescue operations using wireless sensors and visual guidance,” Automation in Construction, vol. 99, pp. 1–17, Mar. 2019, doi: 10.1016/j.autcon.2018.11.020.
P. E. Hart, N. J. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, Jul. 1968, doi: 10.1109/TSSC.1968.300136.
V. Raju and M. F. Selekwa, “On the Mapping Problem in SLAM Approaches for Autonomous Robot Navigation,” presented at the ASME 2021 International Mechanical Engineering Congress and Exposition, American Society of Mechanical Engineers Digital Collection, Jan. 2022. doi: 10.1115/IMECE2021-70452.
K. W. Chiang, G. J. Tsai, H. W. Chang, C. Joly, and N. EI-Sheimy, “Seamless navigation and mapping using an INS/GNSS/grid-based SLAM semi-tightly coupled integration scheme,” Information Fusion, vol. 50, pp. 181–196, Oct. 2019, doi: 10.1016/j.inffus.2019.01.004.
Md. Shafiqul Islam, Md. Tarequl Islam, and M. G. G. Faruque, “A Survey on LiDAR-Based SLAM Technique for an Autonomous Model Using Particle Filters,” in Soft Computing for Security Applications, G. Ranganathan, X. Fernando, F. Shi, and Y. El Allioui, Eds., in Advances in Intelligent Systems and Computing. Singapore: Springer, 2022, pp. 227–240. doi: 10.1007/978-981-16-5301-8_17.
P.-C. Song, J.-S. Pan, and S.-C. Chu, “A parallel compact cuckoo search algorithm for three-dimensional path planning,” Applied Soft Computing, vol. 94, p. 106443, Sep. 2020, doi: 10.1016/j.asoc.2020.106443.
S. A. Eshtehardian and S. Khodaygan, “A continuous RRT*-based path planning method for non-holonomic mobile robots using B-spline curves,” J Ambient Intell Human Comput, vol. 14, no. 7, pp. 8693–8702, Jul. 2023, doi: 10.1007/s12652-021-03625-8.
A.-D. Nguyen, N.-H. Tran, T.-T. Nguyen, A.-T. Nguyen, and T.-P. Tran, “A Hybrid Multi-waypoints Path Planning System for Robots with Minimum Turning Radius Constraint Using GA-B-Spline and Dubins Interpolation,” in Proceedings of the International Conference on Advanced Mechanical Engineering, Automation, and Sustainable Development 2021 (AMAS2021), B. T. Long, H. S. Kim, K. Ishizaki, N. D. Toan, I. A. Parinov, and Y.-H. Kim, Eds., in Lecture Notes in Mechanical Engineering. Cham: Springer International Publishing, 2022, pp. 906–917. doi: 10.1007/978-3-030-99666-6_133.
E. D. Lambert, “Optimization and Mathematical Modelling for Path Planning of Co-operative Intra-logistics Automated Vehicles,” phd, University of Leeds, 2023. Accessed: Sep. 10, 2023. [Online]. Available: https://etheses.whiterose.ac.uk/32528/
C. Zhou, B. Huang, and P. Fränti, “A review of motion planning algorithms for intelligent robots,” J Intell Manuf, vol. 33, no. 2, pp. 387–424, Feb. 2022, doi: 10.1007/s10845-021-01867-z.
S. P. Sahoo, B. Das, B. B. Pati, F. P. Garcia Marquez, and I. Segovia Ramirez, “Hybrid Path Planning Using a Bionic-Inspired Optimization Algorithm for Autonomous Underwater Vehicles,” Journal of Marine Science and Engineering, vol. 11, no. 4, Art. no. 4, Apr. 2023, doi: 10.3390/jmse11040761.
Y. Liang and L. Wang, “Applying genetic algorithm and ant colony optimization algorithm into marine investigation path planning model,” Soft Comput, vol. 24, no. 11, pp. 8199–8210, Jun. 2020, doi: 10.1007/s00500-019-04414-4.
T. Qiuyun, S. Hongyan, G. Hengwei, and W. Ping, “Improved Particle Swarm Optimization Algorithm for AGV Path Planning,” IEEE Access, vol. 9, pp. 33522–33531, 2021, doi: 10.1109/ACCESS.2021.3061288.
G. Yi, Z. Feng, T. Mei, P. Li, W. Jin, and S. Chen, “Multi-AGVs path planning based on improved ant colony algorithm,” J Supercomput, vol. 75, no. 9, pp. 5898–5913, Sep. 2019, doi: 10.1007/s11227-019-02884-9.
Y. Liu, S. Yan, Y. Zhao, C. Song, and F. Li, “Improved Dyna-Q: A Reinforcement Learning Method Focused via Heuristic Graph for AGV Path Planning in Dynamic Environments,” Drones, vol. 6, no. 11, Art. no. 11, Nov. 2022, doi: 10.3390/drones6110365.
A. Zhang, T. Qian, and X. Wu, “An improved ant colony algorithm for path planning of manipulator,” in 2020 IEEE 9th Joint International Information Technology and Artificial Intelligence Conference (ITAIC), Dec. 2020, pp. 1358–1362. doi: 10.1109/ITAIC49862.2020.9339081.
D. Foead, A. Ghifari, M. B. Kusuma, N. Hanafiah, and E. Gunawan, “A Systematic Literature Review of A* Pathfinding,” Procedia Computer Science, vol. 179, pp. 507–514, Jan. 2021, doi: 10.1016/j.procs.2021.01.034.
Q. Wang et al., “Application of A star algorithm in amphibious hull cleaning robot,” in 2022 IEEE International Conference on Mechatronics and Automation (ICMA), Aug. 2022, pp. 269–273. doi: 10.1109/ICMA54519.2022.9855911.
A. Rumaksari et al., “Real world design and implementation of pathfinding sewer inspection robot using A* algorithm,” Jurnal Mantik, vol. 7, no. 1, Art. no. 1, May 2023, doi: 10.35335/mantik.v7i1.3702.
C. Zammit and E.-J. van Kampen, “Comparison Between A* and RRT Algorithms for 3D UAV Path Planning,” Un. Sys., vol. 10, no. 02, pp. 129–146, Apr. 2022, doi: 10.1142/S2301385022500078.
B. Fu et al., “An improved A* algorithm for the industrial robot path planning with high success rate and short length,” Robotics and Autonomous Systems, vol. 106, pp. 26–37, Aug. 2018, doi: 10.1016/j.robot.2018.04.007.
R. Song, Y. Liu, and R. Bucknall, “Smoothed A* algorithm for practical unmanned surface vehicle path planning,” Applied Ocean Research, vol. 83, pp. 9–20, Feb. 2019, doi: 10.1016/j.apor.2018.12.001.
G. Tang, C. Tang, C. Claramunt, X. Hu, and P. Zhou, “Geometric A* Algorithm: An Improved A* Algorithm for AGV Path Planning in a Port Environment,” IEEE Access, vol. 9, pp. 59196–59210, 2021, doi: 10.1109/ACCESS.2021.3070054.
C. Liu, Q. Mao, X. Chu, and S. Xie, “An Improved A* Algorithm Considering Water Current, Traffic Separation and Berthing for Vessel Path Planning,” Applied Sciences, vol. 9, no. 6, Art. no. 6, Jan. 2019, doi: 10.3390/app9061057.
Z. Liu, H. Liu, Z. Lu, and Q. Zeng, “A Dynamic Fusion Pathfinding Algorithm Using Delaunay Triangulation and Improved A* for Mobile Robots,” IEEE Access, vol. 9, pp. 20602–20621, 2021, doi: 10.1109/ACCESS.2021.3055231.
Z. Zhang, J. Wu, J. Dai, and C. He, “A Novel Real-Time Penetration Path Planning Algorithm for Stealth UAV in 3D Complex Dynamic Environment,” IEEE Access, vol. 8, pp. 122757–122771, 2020, doi: 10.1109/ACCESS.2020.3007496.
H. Sang, Y. You, X. Sun, Y. Zhou, and F. Liu, “The hybrid path planning algorithm based on improved A* and artificial potential field for unmanned surface vehicle formations,” Ocean Engineering, vol. 223, p. 108709, Mar. 2021, doi: 10.1016/j.oceaneng.2021.108709.
S. Sedighi, D.-V. Nguyen, and K.-D. Kuhnert, “Guided Hybrid A* Path Planning Algorithm for Valet Parking Applications,” in 2019 5th International Conference on Control, Automation and Robotics (ICCAR), Apr. 2019, pp. 570–575. doi: 10.1109/ICCAR.2019.8813752.
Z. Chen, Y. Zhang, Y. Zhang, Y. Nie, J. Tang, and S. Zhu, “A Hybrid Path Planning Algorithm for Unmanned Surface Vehicles in Complex Environment With Dynamic Obstacles,” IEEE Access, vol. 7, pp. 126439–126449, 2019, doi: 10.1109/ACCESS.2019.2936689.
