Scheduling of Missions with Constrained Tasks for Heterogeneous Multi-Robot Systems

Applications of multi-robot systems (MRS) have been widely considered in domains ranging from healthcare and manufacturing to search-and-rescue. These applications involve the execution of complex missions comprising interdependent tasks with complicated constraints and conflicting optimisation objectives. One of the most challenging MRS problems is therefore the synthesis of robot plans that comply with these complexities. Despite significant research, existing solutions do not provide end-to-end methodologies capable of addressing this MRS planning problem for realistic sets of complex constraints and optimisation objectives. Furthermore, current solutions rarely employ formal methods to provide guarantees on the compliance of their MRS plans with such requirements.
This thesis addresses the limitations summarised above by proposing an end-to-end, tool-supported MRS task allocation and scheduling approach (KANOA). KANOA tackles the allocation of mission tasks to, and the synthesis of plans (i.e., task schedules) for, the heterogeneous robots of an MRS by using a combination of formal methods over several stages. To that end, KANOA comes with a domain-specific language (DSL) for the high-level description of MRS planning problems with: (i) realistic constraints on the sequencing of tasks, and on permitted robot workloads and areas of operation; and (ii) conflicting optimisation objectives (maximising the probability of successful mission completion, minimising the robot idling time, and/or minimising the mission duration).