In context-aware route planning, vehicles (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. The infrastructure is modeled as a graph of resources, each with a capacity to hold a certain number of vehicles simultaneously. Agents place reservations on the resources along their path, in such a way that the capacity of a resource is never exceeded. Given a set of reservations from previous agents that may not be violated, finding an optimal route plan for a single agent can be done in polynomial time, as described in this paper.

A planning agent that encounters a reservation of another agent has two choices to avoid a conflict: first, it can decide to circumvent the resource; second, it can use the resource at a later time. If, during the execution of a route plan, an agent is delayed, care must be taken to avoid a collision, especially if the latter conflict-avoidance choice was made. Moreover, small delays can be quite common, for instance in an automated manufacturing setting, where vehicles have to slow down for humans walking on the factory floor. The robustness of the route plans, and the plan repair options open to the agents, are therefore of crucial importance in context-aware routing. A paper on dealing with unexpected incidents can be found here.

Context-aware route planning is relevant in many areas of robotics and production research, and in our research we tackle the following problem domains:

• Airport taxi route planning: efficient taxi routes are not only desirable for passengers eager to leave the plane or enter the sky, but it also important to waste as little fuel as possible. The presence of other aircraft is important to take into account when planning a taxi route, since aircraft cannot overtake each other on a taxiway, and must even maintain a safe distance so as not to get into a leading plane's exhaust. In our simulator, as described below, we have experimented on Amsterdam Airport Schiphol.
• Container terminal operations: marine container terminals are an important link in the global transportation chain. Large ships may carry thousands of containers destined either for further transportation in the hinterland, or for loading onto a different ship. Immediate transfer to the next transportation mode is often not possible, so containers are temporarily stored on the terminal grounds, where transportation of containers is partly achieved by either Automated Guided Vehicles (AGVs) or by Straddle Carriers (SCs). For both types of vehicles, efficient conflict-free route planning is vital, and moreover interfaces with other optimization problems at the terminal such as ship loading and container stacking.
• Avoiding congestion on the motorway: for vehicles on the motorway it makes less sense to reserve patches of road for particular time intervals, but it is possible to aggregate intended route choices to obtain expected traffic densities in the near future; using existing time-dependent path planning algorithms, a quickest-time route can be found in polynomial time. We intend to combine such algorithms with (currently time-independent) multi-criteria route planning algorithms, so we can reason about the best route in time if e.g. road pricing schemes are in effect. We collaborate on this research with our colleagues from the Network Architectures and Services group.
• Avoiding waiting time for charging electrical vehicles en-route, as described in our paper entitled "Intention-Aware Routing of Electric Vehicles".

To evaluate both the efficiency and the robustness of our algorithms, we are developing an open source simulation environment, in which agents make route plans, execute them, and revise them if necessary. The simulator can be viewed and downloaded from http://casimir.sourceforge.net. The name 'Casimir' derives from the name of the project in which this research was started, a collaboration between the algorithmics group and Rotterdam-based Almende B.V. The simulator is built on top of the Emerge agent platform.