1. bookVolumen 17 (2021): Heft 1 (June 2021)
Zeitschriftendaten
License
Format
Zeitschrift
eISSN
2255-9159
Erstveröffentlichung
31 Jan 2013
Erscheinungsweise
2 Hefte pro Jahr
Sprachen
Englisch
access type Uneingeschränkter Zugang

A Hybrid Routing Approach Using Two Searching Layers

Online veröffentlicht: 13 Sep 2021
Volumen & Heft: Volumen 17 (2021) - Heft 1 (June 2021)
Seitenbereich: 59 - 66
Zeitschriftendaten
License
Format
Zeitschrift
eISSN
2255-9159
Erstveröffentlichung
31 Jan 2013
Erscheinungsweise
2 Hefte pro Jahr
Sprachen
Englisch
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 Search in Google Scholar

[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

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[7] K. Kimura and A. Lipeles, “Fuzzy controller component,” U. S. Patent 14,860,040, December 14, 1996. Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[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

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[14] T. Uras, S. Koenig and C. Hernandez, “Subgoal graphs for optimal pathfinding in eight-neighbor grids,” ICAPS, pp. 224–232, 2013. Search in Google Scholar

[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 Search in Google Scholar

[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. Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

Empfohlene Artikel von Trend MD

Planen Sie Ihre Fernkonferenz mit Scienceendo