Empirical evaluation of multi-agent routing approaches

In multi-agent route planning, there is a set of autonomous vehicles (agents), each with their own start and destination locations. Agents want to reach their destinations as quickly as possible while avoiding conflicts with other agents. We present a single-agent route planning algorithm that finds an optimal conflict-free route plan given a set of reservations from higher-priority agents. We also present an approach that constructs a conflict-free schedule along a fixed path. In order to obtain low-cost multi-agent plans, the fixed paths must provide the agents with sufficiently different alternatives in case certain parts of the infrastructure are more congested than others. We tried both a k shortest paths algorithm, and an algorithm for node-disjoint paths, and compared both approaches to the routing algorithm, and investigated how performances depend on characteristics of the infrastructure.