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

João Salvado, Masoumeh Mansouri, Federico Pecora

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 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 languageEnglish
Title of host publication2021 IEEE 17th International Conference on Automation Science and Engineering (CASE)
PublisherIEEE
Pages2194-2201
Number of pages8
ISBN (Electronic)9781665418737, 9781665418720 (USB)
ISBN (Print)9781665448093 (PoD)
DOIs
Publication statusPublished - 5 Oct 2021
Event2021 IEEE 17th International Conference on Automation Science and Engineering - Lyon, France
Duration: 23 Aug 202127 Aug 2021

Publication series

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

Conference

Conference2021 IEEE 17th International Conference on Automation Science and Engineering
Abbreviated titleCASE 2021
Country/TerritoryFrance
CityLyon
Period23/08/2127/08/21

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'A network-flow reduction for the multi-robot goal allocation and motion planning problem'. Together they form a unique fingerprint.

Cite this