Download pdf
Development of a Multi-target Search-and-rescue Robot Based on Improved Algorithms
- 1 St. Johnsbury Academy, St. Johnsbury, VT, United States
* Author to whom correspondence should be addressed.
Abstract
Nowadays more and more natural disasters and accidents happen around us, resulting in situations where people are trapped in danger. These areas often have complex terrains or high-risk environments. Rescue robots are becoming increasingly important in disaster relief and complex environment exploration. The use of rescue robots significantly improves search and rescue efficiency and reduces risk of casualties during rescue operations in hard-to-access or dangerous areas like earthquake ruins or fire scenes. This research develops an efficient rescue robot system that integrates advanced path planning and rapid map-building technologies for multi-target rescue tasks in complex environments. The system's core consists of two main modules: one is a multi-target path planning and obstacle avoidance module that combines A* and TSP algorithms, aimed at generating the shortest path covering all rescue points; the other is a map building module based on SLAM technology, for quickly and accurately drawing environmental maps. Comprehensive validation in computer simulation environments and real miniature car testing environments has shown that the path planning module combining A* and TSP algorithms can successfully plan the shortest rescue routes. Meanwhile, SLAM technology demonstrates its high accuracy and real-time performance in map building. The real miniature car's test results further confirm the system's feasibility and stability. This project offers a method to optimize the path planning of traditional rescue robots, potentially improving the efficiency of multi-target rescue missions. Additionally, the experimental results provide guidance and suggestions for the design, development, and deployment of actual rescue robots in the future.
Keywords
search-and-rescue robots, path planning, multi-target
[1]. J. Zibulewsky, “Defining disaster: The Emergency Department perspective,” Baylor University Medical Center Proceedings, vol. 14, no. 2, pp. 144–149, Apr. 2001. doi:10.1080/08998280.2001.11927751.
[2]. S. Bhatia, H. S. Dhillon, and N. Kumar, "Alive human body detection system using an autonomous mobile rescue robot," International Journal of Robotics Research, vol. 28, no. 2, pp. 1-7, Feb. 2024. [Online]. Available: [IEEE Xplore].
[3]. A. Denker and M. Caneri, "Design and implementation of a semi-autonomous mobile search and rescue robot: SALVOR," IEEE International Conference on Robotics and Automation, 2017. [Online]. Available: [IEEE Xplore].
[4]. Y. V. Bangalkar and S. M. Kharad, "Review paper on search and rescue robot for victims of earthquake and natural calamities," International Journal on Recent and Innovation Trends in Computing and Communication, vol. 3, no. 4, pp. 2037-2040, Apr. 2015. [Online]. Available: [IJRITCC].
[5]. Z. Zhang and Z. Zhao, "A multiple mobile robots path planning algorithm based on A-star and Dijkstra algorithm," International Journal of Smart Home, vol. 8, no. 3, pp. 75-86, Mar. 2014. [Online]. Available: https://doi.org/10.14257/ijsh.2014.8.3.07.
[6]. E. W. Dijkstra, "A note on two problems in connection with graphs," Numerische Mathematik, vol. 1, no. 1, pp. 269, 1959.
[7]. H. I. Kang, B. Lee, and K. Kim, "Path planning algorithm using the particle swarm optimization and the improved Dijkstra algorithm," IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application, 2008, pp. 1002-1007. [Online]. Available: [IEEE Xplore].
[8]. M. Noto, "A method for the shortest path search by extended Dijkstra algorithm," IEEE International Conference on Communication Technology Proceedings (ICCT), 2000, pp. 2316-2320. [Online]. Available: [IEEE Xplore].
[9]. 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 SSC, vol. 4, no. 2, pp. 100, 1968.
[10]. G. Grisetti, R. Kümmerle, C. Stachniss, and W. Burgard, "A tutorial on graph-based SLAM," IEEE Intelligent Transportation Systems Magazine, vol. 2, no. 4, pp. 31-43, Winter 2010. [Online].
[11]. S. Kuswadi, J. W. Santoso, M. Nasyir Tamara, and M. Nuh, “Application slam and path planning using A-star algorithm for mobile robot in Indoor Disaster Area,” 2018 International Electronics Symposium on Engineering Technology and Applications (IES-ETA), pp. 270–274, Oct. 2018. doi:10.1109/elecsym.2018.8615555
[12]. Q. Qiu, X. Chen, Z. Zeng, J. Xiao, and H. Zhang, "Target-based robot autonomous exploration in rescue environments," IEEE International Conference on Information and Automation, Wuyi Mountain, China, 2018, pp. 609-615. [Online]. Available: [IEEE Xplore].
[13]. D. Calisi, A. Farinelli, L. Iocchi, and D. Nardi, “Autonomous Exploration for search and Rescue Robots,” WIT Transactions on The Built Environment, Vol 94, vol. I, pp. 305–314, Jun. 2007. doi:10.2495/safe070301
[14]. M. Kairanbay and H. M. Jani, "A review and evaluations of shortest path algorithms," International Journal of Scientific & Technology Research, vol. 2, no. 6, pp. 99-104, Jun. 2013. [Online]. Available: https://www.researchgate.net/publication/310594546_A_Review_and_Evaluations_of_Shortest_Path_Algorithms.
[15]. B. Jin, "Multi-objective A* algorithm for the multimodal multi-objective path planning optimization," IEEE Congress on Evolutionary Computation (CEC), Shenzhen, China, 2021, pp. 1704-1711. [Online]. Available: [IEEE Xplore].
[16]. N. Mohd Razali and J. Geraghty, "Genetic algorithm performance with different selection strategies in solving TSP," Proceedings of the World Congress on Engineering (WCE), London, U.K., 2011. [Online]. Available: [IEEE Xplore].
[17]. B. Jin, "Multi-objective A* algorithm for the multimodal multi-objective path planning optimization," IEEE Congress on Evolutionary Computation (CEC), Shenzhen, China, 2021, pp. 1704-1711. [Online]. Available: [IEEE Xplore].
[18]. G. Frare, "Dijkstra algorithm & TSP," Dijkstra-TSP Report, 2018. [Online]. Available: [IEEE Xplore].
[19]. C. Chen, J. Frey, P. Arm, and M. Hutter, "SMUG Planner: A safe multi-goal planner for mobile robots in challenging environments," IEEE International Conference on Intelligent Robots and Systems (IROS), Tokyo, Japan, 2013. [Online]. Available: [IEEE Xplore].
[20]. M. N. Kiyani and M. U. M. Khan, "A prototype of search and rescue robot," IEEE International Conference on Mechatronics and Automation, 2016. [Online]. Available: [IEEE Xplore].
[21]. F. Colas, S. Mahesh, F. Pomerleau, M. Liu, and R. Siegwart, "3D path planning and execution for search and rescue ground robots," IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Tokyo, Japan, 2013. [Online]. Available: [IEEE Xplore].
[22]. Y. Deng, Y. Liu, and D. Zhou, "An improved genetic algorithm with initial population strategy for symmetric TSP," Mathematical Problems in Engineering, vol. 2015, pp. 1-6, Aug. 2015. [Online]. Available: https://doi.org/10.1155/2015/212794.
[23]. A. Candra, M. A. Budiman, and K. Hartanto, “Dijkstra’s and A-star in finding the shortest path: A tutorial,” 2020 International Conference on Data Science, Artificial Intelligence, and Business Analytics (DATABIA), Jul. 2020. doi:10.1109/databia50434.2020.9190342
[24]. A. Ko and H. Y. K. Lau, "Robot assisted emergency search and rescue system with a wireless sensor network," International Journal of Advanced Science and Technology, vol. 3, pp. 69-75, Feb. 2009. [Online]. Available: [IEEE Xplore].
[25]. G. Reinelt, “Introduction,” in The traveling salesman computational solutions for TSP applications Gerhard Reinelt, Berlin: Springer, 1994, pp. 1–3
[26]. R. R. Murphy, "Marsupial and shape-shifting robots for urban search and rescue," IEEE Intelligent Systems, vol. 14, no. 2, pp. 14-19, Mar. 2000. [Online]. Available: [IEEE Xplore].
Cite this article
Zhang,Y. (2025). Development of a Multi-target Search-and-rescue Robot Based on Improved Algorithms. Applied and Computational Engineering,147,56-70.
Data availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
Disclaimer/Publisher's Note
The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.
About volume
Volume title: Proceedings of the 3rd International Conference on Mechatronics and Smart Systems
© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and
conditions of the Creative Commons Attribution (CC BY) license. Authors who
publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons
Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this
series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published
version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial
publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and
during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See
Open access policy for details).