Context-Aware Multi-Stage Route Planning

Context-Aware Multi-Stage Route Planning

Van Belle, J.P.

Witteveen, C. (mentor)

Electrical Engineering, Mathematics and Computer Science

Software Technology

2010-05-25

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.

routing
agents
collision
infrastructure

http://resolver.tudelft.nl/uuid:9e4a7ce2-4259-4816-930d-522008aff9b4

Student theses

master thesis

(c) 2010 Van Belle, J.P.