Evaluating heuristics for prioritizing context-aware route planning agents

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 respective destinations as quickly as possible while avoiding collisions and deadlocks with other agents. Finding an optimal set of conflict-free route plans is an NP-hard problem, so we have developed a polynomial-time, single-agent route planning algorithm that finds an optimal (shortest-time) conflict-free route plan given a set of reservations from higher-priority agents. The cost of the multi-agent route plan that results from the sequential application of our single-agent algorithm depends on the order in which the agents plan. We therefore present a number of agent ordering heuristics, and evaluate them on different types of infrastructures and according to different measures of multi-agent plan cost. If we wish to minimize the makespan of a multi-agent route plan, then the best heuristic is to let agents plan first that have to cover the greatest distances; if we are optimizing for the sum of individual agent plan costs, then the best approach is a greedy heuristic that prioritizes agents that are least affected by the reservations of others.