Parallel Hierarchical Composition Conflict-Based Search for Optimal Multi-Agent Pathfinding
| Autor: | Nancy M. Amato, Hannah Lee, Marco Morales, James Motes |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Mathematical optimization
Control and Optimization Computer science Mechanical Engineering Biomedical Engineering Parallel algorithm Extension (predicate logic) Computer Science Applications Human-Computer Interaction Set (abstract data type) Task (computing) Artificial Intelligence Control and Systems Engineering Path (graph theory) Task analysis Computer Vision and Pattern Recognition Motion planning Pathfinding |
| Zdroj: | IEEE Robotics and Automation Letters. 6:7001-7008 |
| ISSN: | 2377-3774 |
| DOI: | 10.1109/lra.2021.3096476 |
| Popis: | In this letter, we present the following optimal multi-agent pathfinding (MAPF) algorithms: Hierarchical Composition Conflict-Based Search, Parallel Hierarchical Composition Conflict-Based Search, and Dynamic Parallel Hierarchical Composition Conflict-Based Search. MAPF is the task of finding an optimal set of valid path plans for a set of agents such that no agents collide with present obstacles or each other. The presented algorithms are an extension of Conflict-Based Search (CBS), where the MAPF problem is solved by composing and merging smaller, more easily manageable subproblems. Using the information from these subproblems, the presented algorithms can more efficiently find an optimal solution. Our three presented algorithms demonstrate improved performance for optimally solving MAPF problems consisting of many agents in crowded areas while examining fewer states when compared with CBS and its variant Improved Conflict-Based Search. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|