Network-guided multi-robot path planning in discrete representations

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 collision-free, 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.

I. Introduction

This paper discusses an interesting variant of path coordination problems, where a static wireless network is responsible for the high-level path planning of multiple robots (see Figure 4). In this setup, the robots can divert their computation to tasks such as local obstacle avoidance and localization. This is beneficial in cases where robots are resource constrained and have a limited time to compute a path, such as planetary exploration [1] or warehouse management [2]. Moreover, the network may compute better quality paths for the robots because it has access to more information, as in the scenario of Figure 2(a). Similarly, static nodes can often take advantage of wired communication for coordination, which is more reliable compared to wireless communication. This could be the case in future cyber-physical systems for transportation, which can employ a networked infrastructure to guide automobiles in an urban environment to control traffic.