Multirobot Simultaneous Path Planning and Task Assignment on Graphs with Stochastic Costs

Multi-robot task allocation problems where robots have to move to target destinations arises in a number of applications including search and rescue, goods or parts transfer in warehouses. The problem of task allocation, i.e., allocation of robots to target destinations is coupled with the problem of computing a path for the robots to the destination. We consider a situation, where there are static obstacles as well as dynamic obstacles in the environment. We assume that each robot is equipped with a local reactive collision detector and planner to avoid collision with dynamic obstacles. There could be multiple paths that may be available between a robot-destination pair [7]. The cost of travel (like energy consumed, time taken, etc.) is non-deterministic because the robot may have to slow down or stop to avoid moving obstacles.