Decentralized mission planning for heterogeneous robotic teams based on hierarchical task representation : doctoral thesis - Barbara Arbanas Pascoal Ferreira (B. Arbanas Pascoal Ferreira ; Faculty of electrical engineering and computing, 2022)
This thesis focuses on the planning and coordination of cooperative missions for heterogeneous MRS. This complex problem consists of mission decomposition selection (the question what do we do?), task allocation (the question who does what?), and task scheduling (the question how do we arrange tasks in time?), which are often summarized under the common term mission (task) planning. Mission planning can be viewed as an optimization problem that attempts to find the most appropriate way to execute a mission, given certain criteria. Overlaid on this process is a set of coordination mechanisms that ensure timely and coordinated planning and execution of tasks between multiple individual robots. This thesis proposes a distributed, multi-stage optimization method for planning complex missions for heterogeneous multi-robot teams. This class of problems includes tasks that can be executed in different ways and are associated with cross-schedule dependencies that constrain the schedules of the different robots in the system. In nature, these are NP-hard problems, and obtaining exact solutions is computationally intractable. The approach proposed in this thesis involves a multi-objective heuristic search of the mission model, represented as a hierarchical tree that defines the mission goal. This process identifies multiple favorable ways to accomplish the mission (task decomposition selection), which feed directly into the next phase of the method - task allocation and scheduling. For task allocation and scheduling, a distributed algorithm is proposed for missions where the tasks of different robots are tightly coupled with temporal and precedence constraints. The approach is based on representing the problem as a variant of the Vehicle Routing Problem (VRP). The solution is found using a distributed metaheuristic algorithm based on evolutionary computation (CBM-pop). Such an approach allows for fast and near-optimal allocation and can therefore be used for online rescheduling in case of task changes. Simulation results show that the approach has better computational speed and scalability without loss of optimality compared to state-of-the-art distributed methods. Finally, this work defines a decentralized coordination framework for heterogeneous multi-robot systems (GEM). The framework includes coordination mechanisms that ensure coordinated mission planning and execution. It also implements a complete software infrastructure that interacts with the specified hierarchical task model. It is domain-independent and supports different missions for heterogeneous multi-robot systems, as long as they conform to the mission specification model. The proposed solutions are thoroughly tested in a realistic simulation environment as well as in real experiments using heterogeneous multi-robot systems. The proposed algorithms are directly compared with similar methods in the literature and the results show that our method can handle more complex missions with good scaling properties. We provide suboptimal solutions in fast computation times, which makes the proposed solutions particularly suitable for real-world robotics applications. The following original scientific contributions are achieved in this thesis: • A framework for decentralized task allocation, scheduling, and coordination of heterogeneous robotic teams based on hierarchical task representation. • A method for distributed task allocation and scheduling for heterogeneous robotic team missions with cross-schedule task dependencies. • A method for distributed mission decomposition selection for heterogeneous robotic team missions with complex task dependencies. Keywords: Multi-Robot Planning, Multi-Robot Coordination, Task Allocation, Task Scheduling, Distributed Optimization, Multi-Robot Systems