This paper deals with the problem of allocating goals to multiple robots with complex dynamics while computing obstacle-free motions to reach those goals. The spectrum of existing methods ranges from complete and optimal approaches with poor scalability, to highly scalable methods which make unrealistic assumptions on the robots and/or environment. We overcome these limitations by using an efficient graph-based method for decomposing the problem into sub-problems. In particular, we reduce the problem to a Minimum-Cost Max-Flow problem whose solution is used by a multi-robot motion planner that does not impose restrictive assumptions on robot kinodynamics or on the environment. We show empirically that our approach scales to tens of robots in environments composed of hundreds of polygons.
|Title of host publication||2021 IEEE 17th International Conference on Automation Science and Engineering (CASE)|
|Number of pages||8|
|ISBN (Electronic)||9781665418737, 9781665418720 (USB)|
|ISBN (Print)||9781665448093 (PoD)|
|Publication status||Published - 5 Oct 2021|
|Event||2021 IEEE 17th International Conference on Automation Science and Engineering - Lyon, France|
Duration: 23 Aug 2021 → 27 Aug 2021
|Name||IEEE International Conference on Automation Science and Engineering|
|Conference||2021 IEEE 17th International Conference on Automation Science and Engineering|
|Abbreviated title||CASE 2021|
|Period||23/08/21 → 27/08/21|
Bibliographical noteFunding Information:
VI. FUTURE WORK We have presented a network flow reduction for solving the Multi-Robot Motion Planning and Goal Allocation problem. In the future, we intend to evaluate our approach on industrially-relevant environments, including underground mines and a bus depot. We also intend to extend our flow-based approach to account for heterogeneous fleets. Finally, we will compare our method with loosely-coupled approaches to goal allocation. Acknowledgments. This work is supported by the EU H2020 programme under grant agreement No. 732737 (IL- Fig. 10: MMP-GA problem example with start/goal configurations and solution trajectories.
© 2021 IEEE.
ASJC Scopus subject areas
- Control and Systems Engineering
- Electrical and Electronic Engineering