Simultaneous Task Allocation and Planning Under Uncertainty

In many service robot applications, such as intra-logistics, surveillance or stock monitoring, it is desirable for a collection of tasks to be allocated to a team of robots. In this paper, we address applications such as these where tasks are independent (there are no inter-task dependencies) and each task only requires a single robot to complete it. Most existing approaches for solving this class of problems divide the problem into separate task allocation (TA) and planning processes. TA determines which robot should complete which tasks, and planning determines how each task, or conjunction of tasks, should be completed. This separation is made to reduce the computational complexity of the problem. It allows each robot to plan separately for its own task set, avoiding the need for a joint planning model which is typically exponential in the number of team members. This separation also allows specialised algorithms to be used for the TA and planning parts, increasing the efficiency with which the task-directed behaviour of the team can be generated. When doing this, TA usually assumes a greatly simplified model of planning in order to be able to efficiently compute allocations. However, this separation also means that the TA process cannot be informed by the plans of the individual robots, which prevents it from exploiting opportunities, or avoiding hindrances, that are only evident once planning has been performed.