AAAI Publications, Twenty-Sixth AAAI Conference on Artificial Intelligence

Font Size: 
Coordinated Multi-Robot Exploration Under Communication Constraints Using Decentralized Markov Decision Processes
Laetitia Matignon, Laurent Jeanpierre, Abdel-Illah Mouaddib

Last modified: 2012-07-14


Recent works on multi-agent sequential decision making using decentralized partially observable Markov decision processes have been concerned with interaction-oriented resolution techniques and provide promising results. These techniques take advantage of local interactions and coordination. In this paper, we propose an approach based on an interaction-oriented resolution of decentralized decision makers. To this end, distributed value functions (DVF) have been used by decoupling the multi-agent problem into a set of individual agent problems. However existing DVF techniques assume permanent and free communication between the agents. In this paper, we extend the DVF methodology to address full local observability, limited share of information and communication breaks. We apply our new DVF in a real-world application consisting of multi-robot exploration where each robot computes locally a strategy that minimizes the interactions between the robots and maximizes the space coverage of the team even under communication constraints. Our technique has been implemented and evaluated in simulation and in real-world scenarios during a robotic challenge for the exploration and mapping of an unknown environment. Experimental results from real-world scenarios and from the challenge are given where our system was vice-champion.


Motion planning; Navigational planning; Multi-robot planning; Nonlinear control and decision making; mobile robotics

Full Text: PDF