A network-flow reduction for the multi-robot goal allocation and motion planning problem

João  Salvado; Masoumeh Mansouri; Federico Pecora

doi:10.1109/CASE49439.2021.9551640

A network-flow reduction for the multi-robot goal allocation and motion planning problem

João Salvado, Masoumeh Mansouri, Federico Pecora

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

119 Downloads (Pure)

Abstract

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.

Original language	English
Title of host publication	2021 IEEE 17th International Conference on Automation Science and Engineering (CASE)
Publisher	IEEE
Pages	2194-2201
Number of pages	8
ISBN (Electronic)	9781665418737, 9781665418720 (USB)
ISBN (Print)	9781665448093 (PoD)
DOIs	https://doi.org/10.1109/CASE49439.2021.9551640
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

Publication series

Name	IEEE International Conference on Automation Science and Engineering
ISSN (Print)	2161-8070
ISSN (Electronic)	2161-8089

Conference

Conference	2021 IEEE 17th International Conference on Automation Science and Engineering
Abbreviated title	CASE 2021
Country/Territory	France
City	Lyon
Period	23/08/21 → 27/08/21

Bibliographical note

Funding 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.

Publisher Copyright:
© 2021 IEEE.

ASJC Scopus subject areas

Control and Systems Engineering
Electrical and Electronic Engineering

Access to Document

10.1109/CASE49439.2021.9551640

SalvadoJ2021network
J. Salvado, M. Mansouri and F. Pecora, "A Network-Flow Reduction for the Multi-Robot Goal Allocation and Motion Planning Problem," 2021 IEEE 17th International Conference on Automation Science and Engineering (CASE), 2021, pp. 2194-2201, doi: 10.1109/CASE49439.2021.9551640. © 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Accepted author manuscript, 787 KBLicence: Other (please specify with Rights Statement)

Cite this

Salvado, J., Mansouri, M., & Pecora, F. (2021). A network-flow reduction for the multi-robot goal allocation and motion planning problem. In 2021 IEEE 17th International Conference on Automation Science and Engineering (CASE) (pp. 2194-2201). Article 9551640 (IEEE International Conference on Automation Science and Engineering). IEEE. https://doi.org/10.1109/CASE49439.2021.9551640

@inproceedings{d6528dfb86e0469c9478541286c0c693,

title = "A network-flow reduction for the multi-robot goal allocation and motion planning problem",

abstract = "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. ",

author = "Jo{\~a}o Salvado and Masoumeh Mansouri and Federico Pecora",

note = "Funding 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. Publisher Copyright: {\textcopyright} 2021 IEEE.; 2021 IEEE 17th International Conference on Automation Science and Engineering, CASE 2021 ; Conference date: 23-08-2021 Through 27-08-2021",

year = "2021",

month = oct,

day = "5",

doi = "10.1109/CASE49439.2021.9551640",

language = "English",

isbn = "9781665448093 (PoD)",

series = "IEEE International Conference on Automation Science and Engineering",

publisher = "IEEE",

pages = "2194--2201",

booktitle = "2021 IEEE 17th International Conference on Automation Science and Engineering (CASE)",

}

Salvado, J, Mansouri, M & Pecora, F 2021, A network-flow reduction for the multi-robot goal allocation and motion planning problem. in 2021 IEEE 17th International Conference on Automation Science and Engineering (CASE)., 9551640, IEEE International Conference on Automation Science and Engineering, IEEE, pp. 2194-2201, 2021 IEEE 17th International Conference on Automation Science and Engineering, Lyon, France, 23/08/21. https://doi.org/10.1109/CASE49439.2021.9551640

A network-flow reduction for the multi-robot goal allocation and motion planning problem. / Salvado, João; Mansouri, Masoumeh; Pecora, Federico.
2021 IEEE 17th International Conference on Automation Science and Engineering (CASE). IEEE, 2021. p. 2194-2201 9551640 (IEEE International Conference on Automation Science and Engineering).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A network-flow reduction for the multi-robot goal allocation and motion planning problem

AU - Salvado, João

AU - Mansouri, Masoumeh

AU - Pecora, Federico

N1 - Funding 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. Publisher Copyright: © 2021 IEEE.

PY - 2021/10/5

Y1 - 2021/10/5

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85116987358&partnerID=8YFLogxK

U2 - 10.1109/CASE49439.2021.9551640

DO - 10.1109/CASE49439.2021.9551640

M3 - Conference contribution

SN - 9781665448093 (PoD)

T3 - IEEE International Conference on Automation Science and Engineering

SP - 2194

EP - 2201

BT - 2021 IEEE 17th International Conference on Automation Science and Engineering (CASE)

PB - IEEE

T2 - 2021 IEEE 17th International Conference on Automation Science and Engineering

Y2 - 23 August 2021 through 27 August 2021

ER -

A network-flow reduction for the multi-robot goal allocation and motion planning problem

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this