Abstract:
In context-aware route planning, agents have to plan their route on a common infrastructure in such a way that plans made by other agents are not invalidated, and no conflicts are introduced. Previous research on context-aware routing, mostly in the domain of automated guided vehicle (AGV) routing, has reported on an O(n^4v^2) (n the number of vehicles, v the number of infrastructure resources) algorithm. In this paper we present an improved algorithm with a complexity of only O(nv log(nv) + nv^2). Our free path routing approach is based on a search through the graph of free time windows on the resources, rather than a search through the infrastructure itself. Our algorithm can be used to find a set of conflict-free routes for a number of agents by finding the route for a single agent at a time. As a consequence, the order in which agents plan their route will determine the quality not only of the individual agent plans, but also of the global plan. Our experimental results confirm that for an individual agent, its position in the planning queue can make a significant difference; for the total throughput of the airport, however, the order in which the agents make their plans is not highly significant. Also the experiments compare our free path routing approach to fixed path scheduling approaches. We show that for a reasonable amount of extra computation time (required to investigate alternative routes), a free path routing approach finds more efficient plans, because it manages to avoid bottlenecks in the infrastructure.