Rapid Deployment of Mobile Robots Under Temporal, Performance, Perception, and Resource Constraints

Abstract

We consider the problem where a team of mobile robots is tasked with collecting information about a set of stationary targets. There is a temporal deadline to complete the task, and the objective is to determine a control policy maximizing the probability of successfully completing the task within the assigned deadline. In addition, robots use imprecise sensors, and are subject to noisy dynamics. Furthermore, there are more targets than robots, so load sharing between robots is necessary. We model this problem using the theory of constrained Markov decision processes and split the solution into two steps. First, policies to observe small subsets of targets are computed, and the proposed model and algorithm allow one to extract accurate information characterizing the performance of the computed control policies. In the second stage, a subset of the computed policies is assigned to the robots for execution with the objective of maximizing a collective team performance function. To this end, we introduce a submodular objective function and a greedy approximation algorithm to solve this nonlinear assignment problem. Simulations demonstrate how these models can be used in practice to appropriately tune the parameters characterizing this problem and show how the approach favorably scales with the complexity of the problem.