Network-Guided Multi-Robot Path Planning in Discrete Representations

TitleNetwork-Guided Multi-Robot Path Planning in Discrete Representations
Publication TypeConference Paper
Year of Publication2010
AuthorsLuna, R, Bekris, KE
Conference NameIEEE/RSJ International Conference on Intelligent Robots and Systems (IROS'10)
Date PublishedOct. 2010
Conference LocationTaipei, Taiwan

This work deals with problems where multiple robots move on a roadmap guided by wireless nodes that form a communication network. The nodes compute paths for the robots within their communication range given information about robots only in their vicinity and communicating only with neighbors. The objective is to compute paths that are collisionfree, minimize the occurrence of deadlocks, as well as the time it takes to reach the robots’ goals. This paper formulates this challenge as a distributed constraint optimization problem. This formulation lends itself to a message-passing solution that guarantees collision-avoidance despite only local knowledge of the world by the network nodes. Simulations on benchmarks that cannot be solved with coupled or simple decoupled schemes are used to evaluate parameters and study the scalability, path quality and computational overhead of the approach.

Refereed DesignationRefereed