Chance Constrained Simultaneous Task Allocation and Path Planning for Multi-Robot Systems

In many application scenarios of multi-robot systems including parts transfer, mobility-on-demand, and search and rescue, to execute a task, robots have to move to spatially distributed target destinations in an open environment, i.e., in the presence of uncontrolled mobile agents. In such problems, each robot has to be assigned to a task, as well as a collision-free path has to be planned for each robot for moving to the target destination, so that a team performance objective is optimized. Furthermore, the cost (or value) of performing a task is stochastic, which makes the team performance stochastic. In this talk, I will present an algorithmic approach for solving such simultaneous task allocation and path planning (STAPP) problems with probabilistic performance certificates on the team performance. Technically, the STAPP problems can be formulated as a chance-constrained combinatorial optimization problem, which are hard to solve in general. I will show a two-dimensional geometric interpretation of the problem, which allows us to develop a methodical one-parameter search algorithm for computing the optimal solution. I will show computational experiments demonstrating the scalability of our approach with the number of robots and tasks.