Real-Time Multi-Robot Mission Planning in Cluttered Environment
Addressing a collision-aware multi-robot mission planning problem, which involves task allocation and path-finding, poses a significant difficulty due to the necessity for real-time computational efficiency, scalability, and the ability to manage both static and dynamic obstacles and tasks within a...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-02-01
|
| Series: | Robotics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2218-6581/13/3/40 |
| _version_ | 1827305107269615616 |
|---|---|
| author | Zehui Lu Tianyu Zhou Shaoshuai Mou |
| author_facet | Zehui Lu Tianyu Zhou Shaoshuai Mou |
| author_sort | Zehui Lu |
| collection | DOAJ |
| description | Addressing a collision-aware multi-robot mission planning problem, which involves task allocation and path-finding, poses a significant difficulty due to the necessity for real-time computational efficiency, scalability, and the ability to manage both static and dynamic obstacles and tasks within a complex environment. This paper introduces a parallel real-time algorithm aimed at overcoming these challenges. The proposed algorithm employs an approximation-based partitioning mechanism to partition the entire unassigned task set into several subsets. This approach decomposes the original problem into a series of single-robot mission planning problems. To validate the effectiveness of the proposed method, both numerical and hardware experiments are conducted, involving dynamic obstacles and tasks. Additionally, comparisons in terms of optimality and scalability against an existing method are provided, showcasing its superior performance across both metrics. Furthermore, a computational burden analysis is conducted to demonstrate the consistency of our method with the observations derived from these comparisons. Finally, the optimality gap between the proposed method and the global optima in small-size problems is demonstrated. |
| first_indexed | 2024-04-24T17:50:22Z |
| format | Article |
| id | doaj.art-4471c4ad8edf40b88efe5f10b9f52d8a |
| institution | Directory Open Access Journal |
| issn | 2218-6581 |
| language | English |
| last_indexed | 2024-04-24T17:50:22Z |
| publishDate | 2024-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Robotics |
| spelling | doaj.art-4471c4ad8edf40b88efe5f10b9f52d8a2024-03-27T14:03:09ZengMDPI AGRobotics2218-65812024-02-011334010.3390/robotics13030040Real-Time Multi-Robot Mission Planning in Cluttered EnvironmentZehui Lu0Tianyu Zhou1Shaoshuai Mou2School of Aeronautics and Astronautics, Purdue University, West Lafayette, IN 47907, USASchool of Aeronautics and Astronautics, Purdue University, West Lafayette, IN 47907, USASchool of Aeronautics and Astronautics, Purdue University, West Lafayette, IN 47907, USAAddressing a collision-aware multi-robot mission planning problem, which involves task allocation and path-finding, poses a significant difficulty due to the necessity for real-time computational efficiency, scalability, and the ability to manage both static and dynamic obstacles and tasks within a complex environment. This paper introduces a parallel real-time algorithm aimed at overcoming these challenges. The proposed algorithm employs an approximation-based partitioning mechanism to partition the entire unassigned task set into several subsets. This approach decomposes the original problem into a series of single-robot mission planning problems. To validate the effectiveness of the proposed method, both numerical and hardware experiments are conducted, involving dynamic obstacles and tasks. Additionally, comparisons in terms of optimality and scalability against an existing method are provided, showcasing its superior performance across both metrics. Furthermore, a computational burden analysis is conducted to demonstrate the consistency of our method with the observations derived from these comparisons. Finally, the optimality gap between the proposed method and the global optima in small-size problems is demonstrated.https://www.mdpi.com/2218-6581/13/3/40multi-robot systemsmission planningtask allocation |
| spellingShingle | Zehui Lu Tianyu Zhou Shaoshuai Mou Real-Time Multi-Robot Mission Planning in Cluttered Environment Robotics multi-robot systems mission planning task allocation |
| title | Real-Time Multi-Robot Mission Planning in Cluttered Environment |
| title_full | Real-Time Multi-Robot Mission Planning in Cluttered Environment |
| title_fullStr | Real-Time Multi-Robot Mission Planning in Cluttered Environment |
| title_full_unstemmed | Real-Time Multi-Robot Mission Planning in Cluttered Environment |
| title_short | Real-Time Multi-Robot Mission Planning in Cluttered Environment |
| title_sort | real time multi robot mission planning in cluttered environment |
| topic | multi-robot systems mission planning task allocation |
| url | https://www.mdpi.com/2218-6581/13/3/40 |
| work_keys_str_mv | AT zehuilu realtimemultirobotmissionplanninginclutteredenvironment AT tianyuzhou realtimemultirobotmissionplanninginclutteredenvironment AT shaoshuaimou realtimemultirobotmissionplanninginclutteredenvironment |