การออกแบบและพัฒนาอัลกอริทึมการวางแผนเส้นทางการเคลื่อนที่สำหรับอากาศยานไร้คนขับสำหรับภารกิจลอบเร้นสู่เป้าหมายในพื้นที่อันตราย
Design and Development Path Planning of Unmanned Aerial Vehicles for Stealth Missions in Dangerous Environments
Abstract
อากาศยานไร้คนขับได้เข้ามามีบทบาทอย่างมากสำหรับภารกิจทางทหารในปัจจุบัน การพัฒนาให้อากาศยานไร้คนขับสามารถปฏิบัติภารกิจที่มีความซับซ้อนและอันตรายได้โดยอัตโนมัติจึงมีความสำคัญมาก การทำให้อากาศยานไร้คนขับสามารถปฏิบัติภารกิจตามที่ได้กล่าวมาข้างต้นนั่น คือ การออกแบบพัฒนาอัลกอริทึมการวางแผนเส้นทางการเคลื่อนที่ ในงานวิจัยนี้ได้นำเสนอการออกแบบอัลกอริทึมการวางแผนเส้นทางการเคลื่อนที่สำหรับอากาศยานไร้คนขับสำหรับภารกิจลอบเร้นสู่เป้าหมายในพื้นที่อันตรายโดยมุ่งเน้นประยุกต์ใช้ในพื้นที่ในร่ม การออกแบบอัลกอริทึมการวางแผนหาเส้นทางการเคลื่อนที่ในงานวิจัยนี้ใช้พื้นฐานจากอัลกอริทึมการวางแผนหาเส้นทางการเคลื่อนที่แบบ A* ของ Ren และทำการปรับปรุงให้สามารถหลบหลีกได้ทั้งสิ่งกีดขวางและภัยคุกคามทั้งในรูปแบบหยุดนิ่งและรูปแบบพลวัต โดยประยุกต์ใช้อัลกอริทึม Lifelong Planning A* และ D*lite ของ Sven Koenig และ Maxim Likhachev จากนั้นทำการทดสอบเพื่อประเมินประสิทธิภาพเปรียบเทียบอัลกอริทึมการวางแผนหาเส้นทางการเคลื่อนที่ทั้ง 3 แบบ ด้วยการจำลองผ่านโปรแกรม Python ผลการทดสอบแสดงให้เห็นว่าอัลกอริทึมที่พัฒนาจาก D*lite จะให้ผลลัพธ์ระยะทางในการเคลื่อนที่ (Path Length) ที่สั้นกว่าอัลกอริทึมที่พัฒนาจาก Lifelong Planning A* เฉลี่ย 4% แต่ให้ผลลัพธ์ระยะทางในการเคลื่อนที่เฉลี่ยยาวกว่าเมื่อเทียบกับอัลกอริทึม A* ของ Ren 1.5% เช่นเดียวกันเวลาที่ใช้ในการหาเส้นทางที่เหมาะสม (Execute Time) ที่เมื่อเทียบกับอัลกอริทึม Lifelong Planning A* จะใช้เวลาเฉลี่ยน้อยกว่า 530.8% แต่เมื่อเทียบกับอัลกอริทึม A* ของ Ren จะใช้เวลามากกว่า 14.7% อย่างไรก็ตามเมื่อพิจารณาความสามารถในการหลบหลีกสิ่งกีดขวางและภัยคุกคามที่เปลี่ยนแปลงตามเวลาของอัลกอริทึม A* ของ Ren ไม่สามารถหลบหลีกได้ แตกต่างจากอัลกอริทึมที่พัฒนาจาก D*lite และ Lifelong Planning A* ที่สามารถหลบหลีกสิ่งกีดขวางและภัยคุกคามที่เปลี่ยนแปลงตามเวลาได้เป็นอย่างดี ดังนั้นอัลกอริทึมที่ประยุกต์จาก D*lite จึงมีความเหมาะสมมากที่สุดในการนำไปต่อยอดประยุกต์ใช้สำหรับภารกิจลอบเร้นสู่เป้าหมายในพื้นที่อันตรายที่อากาศยานไร้คนขับต้องสามารถเคลื่อนที่โดยอัตโนมัติและตอบสนองต่อสิ่งกีดขวางและภัยคุกคามที่เปลี่ยนแปลงตามเวลาได้
Today, unmanned aerial vehicles (UAVs) play an important role in military applications. The development of UAVs to perform complex and dangerous missions is critical. Effective design and path planning are essential for enabling UAVs to undertake such missions. This research proposes a path-planning algorithm for UAVs to automatically perform stealth missions in hazardous environments. The proposed algorithm is intended for indoor applications. The design of the path-planning algorithm in this research is based on the A* algorithm developed by Ren Tianzhu. This algorithm was modified using elements from the Lifelong Planning A* and D* Lite algorithms, developed by Prof. Sven Koenig and Prof. Maxim Likhachev, to address both static and dynamic obstacles and threats. All three path-planning algorithms were evaluated through simulations using a Python program. The results show that the D* Lite-based algorithm typically results in a path length that is 4% shorter on average compared to the Lifelong Planning A* algorithm, but 1.5% longer on average compared to the A* algorithm developed by Ren. Additionally, the execution time for the D* Lite-based algorithm is on average 530.8% less than that of the Lifelong Planning A* algorithm, but 14.7% more compared to the A* algorithm developed by Ren. Despite this, the A* algorithm developed by Ren cannot find paths that avoid dynamic obstacles or threats. In contrast, both the D* Lite and Lifelong Planning A* algorithms can effectively navigate around such dynamic obstacles and threats. Overall, the D* Lite-based path planning demonstrates superior performance compared to both the A* and Lifelong Planning A* algorithms. It is well-suited for stealth missions in hazardous environments that require autonomous operation and the ability to avoid both static and dynamic threats.
Keywords
[1] I. Oz, H. R. Topcuaglu, and M. Ermis, “A meta-heuristic based three-dimensional path planning environment for unmanned aerial vehicles,” Simulation: Transactions of the Society for Modeling and Simulation International, vol. 89, no. 8, pp. 903–920, 2012.
[2] B. Alsadik and F. Nex. (2021, Jun. 24). The rise in UAV inspections for civil infrastructure. [Online]. Available: https://www.gim-international.com/ content/article/the-rise-in-uav-inspections-forcivil- infrastructure
[3] S. B. Amarat and P. Zong, “3D path planning, routing algorithms and routing protocols for unmanned air vehicles: A review,” Aircraft Engineering and Aerospace Technology, vol. 91, no. 9, pp. 1245–1255, 2019.
[4] A. K. Guruji, H. Agarwal, and D. K. Parsediya, “Time-efficient A* algorithm for robot path planning,” Procedia Technology, vol. 23, pp. 144–149, 2016.
[5] K. Karur, N. Sharma, C. Dharmatti, and J. E. Siegel, “A survey of path planning algorithms for mobile robots,” Vehicles, vol. 3, no. 3, pp. 448–468, 2021.
[6] J. Chen, C. Du, Y. Zhang, P. Han, and W. Wei, “A clustering-based coverage path planning method for autonomous heterogeneous UAVs,” IEEE Transactions on Intelligent Transportation System, vol. 23, no.12, pp. 25546–25556, 2022.
[7] J. N. Yasin, S. A. S. Mohamed, M. H. Haghbayan, J. Heikkonen, H. Tenhunen, and J. Plosila, “Unmanned aerial vehicles (UAVs): Collision avoidance systems and approaches,” IEEE Access, vol. 8, pp. 105139–105155, 2020.
[8] G. F. Caballero, A. R. Molina, M. A. Perez, and M. G. V. Cervantes, “Optimized path-planning in continuous spaces for unmanned aerial vehicles using meta-heuristics” IEEE Access, vol. 8, pp. 176774–176788, 2020.
[9] X. Zhou, F. Gao, X. Fang, and Z. Lan, “Improved bat algorithm for UAV path planning in threedimensional space,” IEEE Access, vol. 9, pp. 20100–20116, 2021.
[10] N. Ozalp and O. K. Sahingoz, “Optimal UAV path planning in a 3D threat environment by using parallel evolutionary algorithms,” in Proceedings of 2013 International Conference on Unmanned Aircraft Systems (ICUAS), Atlanta, GA, USA, 2013, pp. 308–317.
[11] F. Duchon, A. Babinec, M. Kajan, P. Beno, M. Florek, T. Fico, and L. Jurisica, “Path planning with modified A star algorithm for a mobile robot,” Procedia Engineering, vol. 96, pp. 59–69, 2014.
[12] L. D. Filippis, G. Guglieri, and F. Quagliotti, “Path planning strategies for UAVS in 3D environments,” Journal of Intelligent & Robotic Systems, vol. 65, no. 1–4, pp. 247–264, 2012.
[13] 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.
[14] H. Wang, X. Qi, S. Lou, J. Jing, H.He, and W. Liu, “An efficient and robust improved A* algorithm for path planning,” Symmetry, vol. 13, no. 11, Article ID 2213, 2021.
[15] S. Karaman, M. R. Walter, A. Perez, E. Frazzoli, and S. Teller, “Anytime motion planning using the RRT*,” in Proceedings of 2011 International Conference on Robotics and Automation (ICRA), Shanghai, Chaina, 2011, pp. 1478–1483.
[16] K. Danancier, D. Ruvio, I. Sung, and P. Nielsen, “Comparison of path planning algorithms for an unmanned aerial vehicle,” IFAC-PapersOnLine, vol. 52, no. 13, pp. 1978–1983, 2019.
[17] Y. Guo, X. Liu, X. Liu, Y. Yang, and W. Zhang, “FC-RRT*: An improved path planning algorithm for UAV in 3D complex environment,” ISPRS International Journal of Geo-Information, vol. 11, no. 2, Article ID 112, 2022.
[18] Z. Zhang, J. Wu, J. Dai, and C. He, “Rapid penetration path planning method for stealth UAV in complex environment with BB treats,” International Journal of Aerospace Engineering, vol. 2020, pp. 15, Article ID 8896357, 2020.
[19] R. Tianzhu, Z. Rui, X. Jie, and D. Zhuoning, “Three-dimensional path planning of UAV based on an improved A* algorithm*,” in Proceedings of 2016 IEEE Chinese Guidance, Navigation and Control Conference (CGNCC), Nanjing, China, 2016, pp. 140–145.
[20] Md. A. K. Niloy, A. Shama, R. K. Chakrabortty, M. J. Ryan, F. R. Badal, Z. Tasneem, Md. H. Ahamed, S. I. Moyeen, S. K. Das, Md. F. Ali, Md. R. Islam, and D. K. Saha, “Critical design and control issues of indoor autonomous mobile robots: A review,” IEEE Access, vol. 9, pp. 35338–35370, 2021.
[21] S. Koenig, M. Likhachev, and D. Furcy, “Lifelong Planning A*,” Artificial Intelligence, vol. 155, no. 1–2, pp. 93–146, 2004.
[22] S. Koenig and M. Likhachev, “D*lite,” AAAI/IAAI, pp. 476–483, 2002.
DOI: 10.14416/j.kmutnb.2024.10.016
ISSN: 2985-2145
Email this article 
Hide
Show all