New complexity results and performance-guaranteed algorithms for multirobot navigation of communication-restricted environments

Jacopo Banfi, Cornell University


Exploiting a team of mobile robots can provide a valid alternative to the employment of human operators in carrying out different kinds of information-gathering tasks, like environmental monitoring, exploration, and patrolling. Frequently, the proposed coordination mechanisms work under the assumption that communication between robots is possible between any two locations of the environment. However, real operational conditions may require to deploy robots only equipped with local limited-range communication modules. In this talk, I will first present a general graph-based framework for planning multirobot missions subject to different kinds of communication constraints. Then, I will focus on a few selected problems taken from the literature that can be framed in such planning framework (like computing a set of joint paths ensuring global connectivity at selected times), and present either new complexity results or performance-guaranteed algorithms to compute good quality solutions to these problems in reasonable time.