Extending Conflict-Based Search for Optimal and Efficient Quadrotor Swarm Motion Planning
Multi-agent pathfinding has been extensively studied by the robotics and artificial intelligence communities. The classical algorithm, conflict-based search (CBS), is widely used in various real-world applications due to its ability to solve large-scale conflict-free paths. However, classical CBS as...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-11-01
|
| Series: | Drones |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2504-446X/8/12/719 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850042267988918272 |
|---|---|
| author | Zihao Wang Zhiwei Zhang Wenying Dou Guangpeng Hu Lifu Zhang Meng Zhang |
| author_facet | Zihao Wang Zhiwei Zhang Wenying Dou Guangpeng Hu Lifu Zhang Meng Zhang |
| author_sort | Zihao Wang |
| collection | DOAJ |
| description | Multi-agent pathfinding has been extensively studied by the robotics and artificial intelligence communities. The classical algorithm, conflict-based search (CBS), is widely used in various real-world applications due to its ability to solve large-scale conflict-free paths. However, classical CBS assumes discrete time–space planning and overlooks physical constraints in actual scenarios, making it unsuitable for direct application in unmanned aerial vehicle (UAV) swarm. Inspired by the decentralized planning and centralized conflict resolution ideas of CBS, we propose, for the first time, an optimal and efficient UAV swarm motion planner that integrates state lattice with CBS without any underlying assumption, named SL-CBS. SL-CBS is a two-layer search algorithm: (1) The low-level search utilizes an improved state lattice. We design emergency stop motion primitives to ensure complete UAV dynamics and handle spatio-temporal constraints from high-level conflicts. (2) The high-level algorithm defines comprehensive conflict types and proposes a motion primitive conflict detection method with linear time complexity based on Sturm’s theory. Additionally, our modified independence detection (ID) technique is applied to enable parallel conflict processing. We validate the planning capabilities of SL-CBS in classical scenarios and compare these with the latest state-of-the-art (SOTA) algorithms, showing great improvements in success rate, computation time, and flight time. Finally, we conduct large-scale tests to analyze the performance boundaries of SL-CBS+ID. |
| format | Article |
| id | doaj-art-bf71e6e0a1b64c01bcf60ae188a3c25c |
| institution | DOAJ |
| issn | 2504-446X |
| language | English |
| publishDate | 2024-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Drones |
| spelling | doaj-art-bf71e6e0a1b64c01bcf60ae188a3c25c2025-08-20T02:55:36ZengMDPI AGDrones2504-446X2024-11-0181271910.3390/drones8120719Extending Conflict-Based Search for Optimal and Efficient Quadrotor Swarm Motion PlanningZihao Wang0Zhiwei Zhang1Wenying Dou2Guangpeng Hu3Lifu Zhang4Meng Zhang5Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100085, ChinaAerospace Information Research Institute, Chinese Academy of Sciences, Beijing 100093, ChinaSchool of Electronics and Information Engineering, Beihang University, Beijing 100191, ChinaSchool of Computer Science, Northwestern Polytechnical University, Xi’an 710072, ChinaAerospace Information Research Institute, Chinese Academy of Sciences, Beijing 100093, ChinaInstitute of Information Engineering, Chinese Academy of Sciences, Beijing 100085, ChinaMulti-agent pathfinding has been extensively studied by the robotics and artificial intelligence communities. The classical algorithm, conflict-based search (CBS), is widely used in various real-world applications due to its ability to solve large-scale conflict-free paths. However, classical CBS assumes discrete time–space planning and overlooks physical constraints in actual scenarios, making it unsuitable for direct application in unmanned aerial vehicle (UAV) swarm. Inspired by the decentralized planning and centralized conflict resolution ideas of CBS, we propose, for the first time, an optimal and efficient UAV swarm motion planner that integrates state lattice with CBS without any underlying assumption, named SL-CBS. SL-CBS is a two-layer search algorithm: (1) The low-level search utilizes an improved state lattice. We design emergency stop motion primitives to ensure complete UAV dynamics and handle spatio-temporal constraints from high-level conflicts. (2) The high-level algorithm defines comprehensive conflict types and proposes a motion primitive conflict detection method with linear time complexity based on Sturm’s theory. Additionally, our modified independence detection (ID) technique is applied to enable parallel conflict processing. We validate the planning capabilities of SL-CBS in classical scenarios and compare these with the latest state-of-the-art (SOTA) algorithms, showing great improvements in success rate, computation time, and flight time. Finally, we conduct large-scale tests to analyze the performance boundaries of SL-CBS+ID.https://www.mdpi.com/2504-446X/8/12/719multi-agent pathfindingconflict-based searchquadrotor swarm motion planning |
| spellingShingle | Zihao Wang Zhiwei Zhang Wenying Dou Guangpeng Hu Lifu Zhang Meng Zhang Extending Conflict-Based Search for Optimal and Efficient Quadrotor Swarm Motion Planning Drones multi-agent pathfinding conflict-based search quadrotor swarm motion planning |
| title | Extending Conflict-Based Search for Optimal and Efficient Quadrotor Swarm Motion Planning |
| title_full | Extending Conflict-Based Search for Optimal and Efficient Quadrotor Swarm Motion Planning |
| title_fullStr | Extending Conflict-Based Search for Optimal and Efficient Quadrotor Swarm Motion Planning |
| title_full_unstemmed | Extending Conflict-Based Search for Optimal and Efficient Quadrotor Swarm Motion Planning |
| title_short | Extending Conflict-Based Search for Optimal and Efficient Quadrotor Swarm Motion Planning |
| title_sort | extending conflict based search for optimal and efficient quadrotor swarm motion planning |
| topic | multi-agent pathfinding conflict-based search quadrotor swarm motion planning |
| url | https://www.mdpi.com/2504-446X/8/12/719 |
| work_keys_str_mv | AT zihaowang extendingconflictbasedsearchforoptimalandefficientquadrotorswarmmotionplanning AT zhiweizhang extendingconflictbasedsearchforoptimalandefficientquadrotorswarmmotionplanning AT wenyingdou extendingconflictbasedsearchforoptimalandefficientquadrotorswarmmotionplanning AT guangpenghu extendingconflictbasedsearchforoptimalandefficientquadrotorswarmmotionplanning AT lifuzhang extendingconflictbasedsearchforoptimalandefficientquadrotorswarmmotionplanning AT mengzhang extendingconflictbasedsearchforoptimalandefficientquadrotorswarmmotionplanning |