A Hybrid Routing Approach Using Two Searching Layers

Gonca Ozmen Koca; Seda Yetkin

doi:10.2478/ecce-2021-0007

.blurhash-client-img { display: none !important; }

A Hybrid Routing Approach Using Two Searching Layers

Electrical, Control and Communication Engineering

Volume 17 (2021): Issue 1 (June 2021)

By: Gonca Ozmen Koca and Seda Yetkin

Open Access

|Sep 2021

Read online

Abstract

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.

[1] 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.10.33365/jti.v14i1.509
Open DOI Search in Google Scholar Back to article
[2] 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
Search in Google Scholar Back to article
[3] 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.10.26740/jinacs.v2n01.p74-85
Open DOI Search in Google Scholar Back to article
[4] 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.10.1016/S1474-0346(03)00018-1
Open DOI Search in Google Scholar Back to article
[5] 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.10.1007/11558958_11
Open DOI Search in Google Scholar Back to article
[6] 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.10.1080/13658810801949850
Open DOI Search in Google Scholar Back to article
[7] K. Kimura and A. Lipeles, “Fuzzy controller component,” U. S. Patent 14,860,040, December 14, 1996.
Search in Google Scholar Back to article
[8] 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.10.1007/978-1-4615-6325-9_11
Open DOI Search in Google Scholar Back to article
[9] 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.10.1109/TRO.2004.838026
Open DOI Search in Google Scholar Back to article
[10] 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.
Search in Google Scholar Back to article
[11] 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.10.1016/j.asoc.2020.106498
Open DOI Search in Google Scholar Back to article
[12] 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.10.4316/aece.2010.04011
Open DOI Search in Google Scholar Back to article
[13] 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.10.1515/ecce-2017-0008
Open DOI Search in Google Scholar Back to article
[14] T. Uras, S. Koenig and C. Hernandez, “Subgoal graphs for optimal pathfinding in eight-neighbor grids,” ICAPS, pp. 224–232, 2013.10.1609/icaps.v23i1.13568
Open DOI Search in Google Scholar Back to article
[15] 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.10.1609/aaai.v28i1.8845
Open DOI Search in Google Scholar Back to article
[16] 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.10.1609/icaps.v25i1.13709
Open DOI Search in Google Scholar Back to article
[17] 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.10.3390/e22020162751658033285937
Open DOI Search in Google Scholar Open in PubMed Back to article
[18] 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.10.1016/j.neucom.2014.09.092
Open DOI Search in Google Scholar Back to article
[19] 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.10.1515/cait-2015-0036
Open DOI Search in Google Scholar Back to article
[20] 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.09810.1016/j.proeng.2014.12.098
Open DOI Search in Google Scholar Back to article
[21] 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.220795010.1109/JSEN.2012.2207950
Open DOI Search in Google Scholar Back to article

Articles in this issue

DOI: https://doi.org/10.2478/ecce-2021-0007 | Journal eISSN: 2255-9159 | Journal ISSN: 2255-9140

Journal RSS Feed

Language: English

Page range: 59 - 66

Published online: Sep 13, 2021

Published in print: Jun 1, 2021

Published by: Riga Technical University

In partnership with: Paradigm Publishing Services

Publication frequency: 2 issues per year

Keywords:

Motion control,

Optimization,

Path planning,

Shortest path problem

Related subjects:

Engineering,

Introductions and overviews,

Engineering, other

© 2021 Gonca Ozmen Koca, Seda Yetkin, published by Riga Technical University
This work is licensed under the Creative Commons Attribution 4.0 License.

Volume 17 (2021): Issue 1 (June 2021)