Incremental multi-robot task selection for resource constrained and interrelated tasks

When the tasks of a mission are interrelated and subject to several resource constraints, more efforts are needed to coordinate robots towards achieving the mission than independent tasks. In this work, we formulate the Coordinated Task Selection Problem (CTSP) to form the basis of an efficient dynamic task selection scheme for allocation of interrelated tasks of a complex mission to the members of a multi-robot team. Since processing times of tasks are not exactly known in advance, the incremental task selection scheme for the eligible tasks prevents redundant efforts as, instead of scheduling all of the tasks, they are allocated to robots as needed. This approach results in globally efficient solutions through mechanisms that form priority based rough schedules and select the most suitable tasks from these schedules. Since our method is targeted at real world task execution, communication requirements are kept limited. Empirical evaluations of the proposed approach are performed on the Webots simulator and the real robots. The results validate that the proposed approach is scalable, efficient and suitable to the real world safe mission achievement.