Print Email Facebook Twitter Context-Aware Multi-Stage Route Planning Title Context-Aware Multi-Stage Route Planning Author Van Belle, J.P. Contributor Witteveen, C. (mentor) Faculty Electrical Engineering, Mathematics and Computer Science Department Software Technology Date 2010-05-25 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. Subject routingagentscollisioninfrastructure To reference this document use: http://resolver.tudelft.nl/uuid:9e4a7ce2-4259-4816-930d-522008aff9b4 Part of collection Student theses Document type master thesis Rights (c) 2010 Van Belle, J.P. Files PDF mscthesis.pdf 680.35 KB Close viewer /islandora/object/uuid:9e4a7ce2-4259-4816-930d-522008aff9b4/datastream/OBJ/view