We consider multi-agent transport task problems where, e.g. in a factory setting, items have to be delivered from a given start to a goal pose while the delivering robots need to avoid collisions with each other on the floor. We introduce a Task Conflict-Based Search (TCBS) Algorithm to solve the combined delivery task allocation and multi-agent path planning problem optimally. The problem is known to be NP-hard and the optimal solver cannot scale. However, we introduce it as a baseline to evaluate the sub-optimality of other approaches. We show experimental results that compare our solver with different sub-optimal ones in terms of regret.
Genetic Algorithms (GAs) can efficiently produce high quality results for hard combinatorial real world problems such as the Vehicle Routing Problem (VRP). Genetic Vehicle Representation (GVR), a recent approach to solving instances of the VRP with a GA, produces competitive or superior results to the standard benchmark problems. This work extends GVR research by presenting a more precise mathematical model of GVR than in previous works and a thorough comparison of GVR to Path Based Representation approaches. A suite of metrics that measures GVR's efficiency and effectiveness provides an adequate characterization of the jagged search landscape. A new variation of a crossover operator is introduced. A previously unmentioned insight about the convergence rate of the search is also noted that is especially important to the application of a priori and dynamic routing for swarms of Unmanned Aerial Vehicles (UAVs). Results indicate that the search is robust, and it exponentially drives toward high quality solutions in relatively short time. Consequently, a GA with GVR encoding is capable of providing a state-of-the-art engine for a UAV routing system or related application.