Dynamic and Distributed Allocation of Resource Constrained Project Tasks to Robots

Abstract

Abstract. In this work, we propose a dynamic task selection scheme for allocating real-world tasks to the members of a multi-robot team. Tasks in our research are subject to precedence constraints and simultaneous execution requirements. This problem is similar to the Resource Constrained Project Scheduling Problem (RCPSP) in operations research. Particularly, we also deal with the missions that may change their forms by introducing new online tasks during execution making the problem more challenging besides the real world dynamism. Unpredictability of the exact processing times of tasks, unstable cost values during runtime and inconsistencies due to uncertain information form the main difficulties of the task allocation problem for robot systems. Since the processing times of the tasks are not exactly known in advance, we propose a dynamic task selection scheme for the eligible tasks instead of scheduling all of them to eliminate the redundant calculations. In our approach, globally efficient solutions are attained by the mechanisms for forming priority based rough schedules by tentative coalition commitments and selecting the most suitable tasks from these schedules. The approach is distributed and computationally efficient. 1