Multirobot Symbolic Planning under Temporal Uncertainty (2016)
Shiqi Zhang, Yuqian Jiang, Guni Sharon, and Peter Stone
Multirobot symbolic planning aims at computing plans, each in the form of a sequence of actions, for a team of robots to achieve their individual goals while minimizing overall cost. Solving this problem requires to model the limited resources of a working environment (e.g., corridors that allow at most one robot at a time) and the possibility of action synergy (e.g., multiple robots going through a door after a single door-opening action). However, it is a challenge to plan for resource sharing and realizing synergy in a team of robots due to the robots' noisy action durations. This paper, for the first time, focuses on the problem of multirobot symbolic planning under temporal uncertainty (MSPTU). We present an algorithm inspired by simulated annealing for MSPTU problems. The algorithm has been evaluated using multirobot navigation tasks in simulation. We observed significant improvements in reducing overall cost compared to baselines in which robots do not communicate or model temporal uncertainty.
In IJCAI'16 Workshop on Autonomous Mobile Service Robots, New York City, USA, July 2016.

Peter Stone Faculty pstone [at] cs utexas edu
Shiqi Zhang Postdoctoral Alumni szhang [at] cs utexas edu