A Hybrid Routing Approach Using Two Searching Layers
DOI:
https://doi.org/10.2478/ecce-2021-0007Keywords:
Motion control, Optimization, Path planning, Shortest path problemAbstract
This paper considers SUB_GOALs by using basic A* algorithm and Subgoal Graphs in a hybrid approach to execute optimal route. SUB_GOALs identified with pre-searching from basic A* at break points and Subgoal Graphs at corners of obstacles are added to SUB_TABLE to expedite the final searching in the hybrid approach. Map to work on is divided to subregions with decision-making process by using line-of-sight to avoid redundant searching. In the final searching layer, all feasible SUB_GOALs gained from decision-making process in the same subregion are connected to find final solutions of routes. Solutions achieved in the divided subregions are evaluated and combined to discover the final optimal route. The proposed hybrid approach is applied to three different scenarios in various dimensions of maps. In these three scenarios, the shortest route without hitting obstacles is calculated as 46.67, 57.76 and 124.7 units, respectively, and compared with other search algorithms. Simulation results of route planning are demonstrated to exhibit the effectiveness of the proposed hybrid approach.References
Y. Fernando, M. A. Mustaqov and A. D. Megawaty, “Penerapan Algoritma A-Star Pada Aplikasi Pencarian Lokasi Fotografi Di Bandar Lampung Berbasis Android,” Jurnnal Teknoinfo, vol. 14, no. 1, 2020, pp. 27–34. https://doi.org/10.33365/jti.v14i1.509.
H. Yusnita, “Kinerja Dynamic Programming, Algoritma A Star dan Dijkstra Dalam Menentukan Rute Terpendek,” Universitas Sumatera Utara, Master thesis, 2020. http://repositori.usu.ac.id/handle/123456789/28221
R. F. Oktanugraha and S. R. Nudin, “Implementasi Algoritma A* (A Star) Dalam Penentuan Rute Terpendek Yang Dapat Dilalui Non Player Character Pada Game Good Thief,” Journal of Informatics and Computer Science, vol. 2, no. 1, 2020, pp. 74–85.
A. R. Soltani, H. Tawfik, J. Y. Goulermas and T. Fernando, “Path planning in construction sites: performance evaluation of the Dijkstra, A* and GA search algorithms,” Adv. Engineering Informatics, vol. 16, no. 4, pp. 291–303, 2002. https://doi.org/10.1016/S1474-0346(03)00018-1.
N. Delanoue, L. Jaulin and B. Cottenceau, “Counting the Number of Connected Components of a Set and its Application to Robotics,” in J. Dongarra, K. Madsen, J. Waśniewski (eds) Applied Parallel Computing. State of the Art in Scientific Computing. PARA 2004. Lecture Notes in Computer Science, vol. 3732, pp. 93–101, 2006. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11558958_11.
W. Zeng and R. L. Church, “Finding shortest paths on real road networks: the case for A*,” International Journal of Geographical Information Science, vol. 23. no. 4, pp. 531–543, 2009. https://doi.org/10.1080/13658810801949850.
K. Kimura and A. Lipeles, “Fuzzy controller component,” U. S. Patent 14,860,040, December 14, 1996.
A. Stentz, “Optimal and efficient path planning for partially-known environments,” in M. H. Hebert, C. Thorpe, A. Stentz (eds) Intelligent Unmanned Ground Vehicles. The Springer International Series in Engineering and Computer Science (Robotics: Vision, Manipulation and Sensors), vol. 388. Springer, 1997. https://doi.org/10.1007/978-1-4615-6325-9_11.
S. Koenig and M. Likhachev, “Fast Replanning for Navigation in Unknown Terrain,” Transactions on Robotics, vol. 21, no. 3, pp. 354–363, 2005. https://doi.org/10.1109/TRO.2004.838026.
S. Yetkin, “Application of two-dimensional path planning algorithms for the robot fish,” Fırat Üniversitesi, Master thesis, 2016. http://hdl.handle.net/11508/17991.
L. Liu, S. Luo, F. Guo and S. Tan, “Multi-point shortest path planning based on an improved discrete bat algorithm,” Applied Soft Computing, vol. 95, 2020, 106498. https://doi.org/10.1016/j.asoc.2020.106498.
E. Masehian and D. Sedighizadeh, “Multi-objective PSO-and NPSO-based algorithms for robot path planning,” Advances in Electrical and Computer Engineering, vol. 10, no. 4, pp. 69–76, 2010. https://doi.org/10.4316/aece.2010.04011.
N. A. Elkhateeb and R. I. Badr, “Novel PID Tracking Controller for 2DOF Robotic Manipulator System Based on Artificial Bee Colony Algorithm,” Electrical, Control and Communication Engineering, vol. 13, no. 1, 2017, pp. 55–62. https://doi.org/10.1515/ecce-2017-0008.
T. Uras, S. Koenig and C. Hernandez, “Subgoal graphs for optimal pathfinding in eight-neighbor grids,” ICAPS, pp. 224–232, 2013.
T. Uras and S. Koenig, “Identifying hierarchies for fast optimal search,” Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, pp. 878–884, 2014.
D. Nussbaum and A. Yörükçü, “Moving target search with subgoal graphs,” Twenty-Fift International Conference on Automated Planning and Scheduling, Jerusalem, Israel, pp. 179–187, 2015.
K. Xu, Y. Hu, Y. Zeng, Q. Yin and M. Yang, “Improving the Scalability of the Magnitude-Based Deceptive Path -Planning Using Subgoal Graphs,” Entropy, vol. 22, no. 2, 2020. https://doi.org/10.3390/e22020162.
L. Zuo, Q. Guo, X. Xu and H. Fu, “A hierarchical path planning approach based on A* and least-squares policy iteration for mobile robots,” Neurocomputing, vol. 170, pp. 257–266, 2015. https://doi.org/10.1016/j.neucom.2014.09.092.
J. Peng, Y. Huang and G. Luo, “Robot path planning based on improved A* algorithm,” Cybernetics and Information Technologies, vol 15, no. 2, pp. 171–180, 2015. https://doi.org/10.1515/cait-2015-0036.
F. Duchon, et. al. “Path planning with modified A star algorithm for a mobile robot,” Procedia Engineering, vol. 96, pp. 59–69, 2014. https://doi.org/10.1016/j.proeng.2014.12.098
I. S. AlShawi, L. Yan, W. Pan and B. Luo, “Lifetime enhancement in wireless sensor networks using fuzzy approach and A-star algorithm,” IEEE Sensors Journal, vol. 12, no. 10, pp. 3010–3018, 2012. https://doi.org/10.1109/JSEN.2012.2207950
Downloads
Published
Issue
Section
License
Copyright (c) 2021 Gonca Ozmen Koca et al., published by Sciendo
This work is licensed under a Creative Commons Attribution 4.0 International License.
How to Cite
