Context-Aware Multi-Stage Route Planning

Abstract

One way to prevent collisions and deadlocks between agents on infrastructures with capacity constraints is to use context-aware route planning algorithms. In context-aware route planning, there is a set of agents each planning a conflict-free route from a start location to a destination location on a common infrastructure. If a sequential approach is used for route planning, finding an optimal conflict-free route for a single agent can be done in polynomial time by allowing agents to place reservations on infrastructure resources for the intended periods of occupation. In the multi-stage variant of the context-aware route planning problem, there is a sequence of locations to be visited by an agent instead of just a start and destination location as in single-stage route planning. A straightforward approach to the multi-stage route planning problem would be concatenating subsequent routes found by a single-stage algorithm. However, this solution is incomplete and sub-optimal in case of context-aware route planning. Therefore, we developed three multi-stage route planning algorithms that always return an optimal route for a single agent, given a set of reservations made by previous agents. The results of our experiments show that one of the multi-stage algorithms is suitable for use in practice, since the cpu-time needed to make a route is at most a few tenths of a second.