Planning for actively synchronized multi-robot systems

We describe an approach for planning under uncertainty for multiple robots when robots must proactively plan perception and communication acts, and decide whether the cost needed to obtain a state estimate is justified by the benefit of the information obtained. The approach is suitable for settings where observations are of high quality and they —either alone or along with communication— recover the system’s joint state, but that happens only infrequently owing to the costs incurred. Such cases allow one to sidestep the construction of the full joint belief space, a well known source of intractability in planning. After formulating the multi-robot problem as a class of MDP to be solved over joint states, albeit specific structure allowing decentralized execution, we give a suitable Bellman recurrence using macro-actions which points to a means of direct solution. We solve for plans which can, after appropriate projection, be executed effectively by individual robots. We provide a simulation-based case study and report on our a physical robot implementation. On the basis of our experience with hardware, we examine enhancements of the model that address nonidealities we have identified in practice.