Constraint-based multi-robot path planning

Malcolm Ryan*

*Corresponding author for this work

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

26 Citations (Scopus)

Abstract

Planning collision-free paths for multiple robots traversing a shared space is a problem that grows combinatorially with the number of robots. The naive centralised approach soon becomes intractable for even a moderate number of robots. Decentralised approaches, such as prioritised planning, are much faster but lack completeness. Previous work has demonstrated that the search can be significantly reduced by adding a level of abstraction [1]. We first partition the map into subgraphs of particular known structure, such as cliques and halls, and then build abstract plans which describe the transitions of robots between the subgraphs. These plans are constrained by the structural properties of the subgraphs used. When an abstract plan is found, it can easily be resolved into a complete concrete plan without further search. In this paper, we show how this method of planning can be implemented as a constraint satisfaction problem (CSP). Constraint propagation and intelligent search ordering further reduce the size of the search problem, allowing us to solve large problems significantly more quickly. Empirical evaluation on a realistic planning problem shows the clear superiority of the constraint-based approach, but the value of abstraction is mixed: it allows us to solve more problems at the cost of a time-overhead on simple problems. This implementation also opens up opportunities for the application of a number of other search reduction and optimisation techniques, as we will discuss.

Original languageEnglish
Title of host publication2010 IEEE International Conference on Robotics and Automation, ICRA 2010
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages922-928
Number of pages7
ISBN (Print)9781424450381
DOIs
Publication statusPublished - 2010
Externally publishedYes
Event2010 IEEE International Conference on Robotics and Automation, ICRA 2010 - Anchorage, AK, United States
Duration: 3 May 20107 May 2010

Other

Other2010 IEEE International Conference on Robotics and Automation, ICRA 2010
CountryUnited States
CityAnchorage, AK
Period3/05/107/05/10

Fingerprint Dive into the research topics of 'Constraint-based multi-robot path planning'. Together they form a unique fingerprint.

Cite this