area that is below or at same level of the lowest common ancestor, and we are in a Descending phase otherwise.

4.

At each iteration we look at the neighbors of the node currently being examined. If we are ascending, we only consider neighbors that are connected through edges that have an edge class lower or equal to the previous edge (bigger road) in the path. If we are descending, we only take edges with class greater or equal to the previ- ous edge (smaller road) in the path. The class of each edge is dynamically computed by calling the function get edge class (edge id, t, F (edge id, t)), where F is the predictor function that returns the tuple (d

_{1}, . . . , d_{k}) of expected driving conditions (e.g., weather, road construc- tion, etc) for the edge at time t, t is the projected time at which the edge will be taken. The set of neighbors of a node are all those nodes directly reachable through a sin- gle edge, or indirectly reachable through a pre-computed path.5.

Whenever we insert a new path into the priority queue, we update its g(n) value by adding to the path’s total travel time the time to traverse the new edge, which is computed by dividing the edge distance by the expected edge speed retrieved with the function get edge speed (edge id, t, F (edge id, t)). h(n) is also updated for the path by using a conservative estimate of the total travel time from the current node to the goal node. Several different estimation policies are possible, more accurate ones can significantly speed up the search [6]. In our implementation we used the simple heuris- tic h(n) = distance(n, end)/max speed, but any other heuristic could be plugged into the algorithm.

Lemma 7.1. The adaptive fastest path algorithm, when computing a path between (start, end) nodes, in areas a_{i}, a_{j }respectively will consider at most O(|a_{i}| + |a_{j }| + |bn| + |un|) distinct nodes, where |a_{i}| is the number of nodes in area a_{i}, |a_{j }| is the number of nodes in area a_{j }, |bn| is the total number of border nodes in all areas, and |un| is the number of nodes connected to upgraded edges in all areas.

Proof Sketch. The worst case for path finding is when no pre-computed path is available. In this case we need to examine all nodes in the starting area until border nodes are reached, and all nodes in the ending area until we reach the destination. Once we have reached the border nodes of the first area, the algorithm only goes through border nodes, or upgraded nodes until the destination area is reached.

The implication of lemma 7.1 is that our search algorithm will need to consider significantly fewer nodes than tradi- tional A∗ even in the case when no area pre-computation is possible. We verify this result running the search algo- rithm on real road networks for the United States where we observed an order of magnitude savings in the number of nodes examined by the algorithm.

Example 3 (Search). Figure 3 presents a road network, there are 3 levels of roads, and we have partitioned the graph along the first 2 levels. The first level gives us the large grid, and the second level the finer grid (shown only for two areas). The size of nodes indicate the level at which they are, larger nodes are associated with edges at higher level. The graph also shows edges that have been upgraded by painting them with dotted lines. The name of an area indicates its position

801

## Area 1

End Area 1:3:5

Area 1:3

## Area 1:7

## Start Area 1:7:5

# Figure 3: Example Hierarchical Search

1

Class 1 roads

... Class 2 roads

1:3

...

...

1:3:1

1:3:5

Descending Phase

...

1:1:9

1:7

...

...

...

1:7:1

1:7:5

Ascending Phase

1:7:9

# Figure 4: Example Area Hierarchy

in the area tree, i.e., area 1 : 7 : 5 is a child of area 1 : 7 which in turn is a child of area 1 (more clearly seen in Figure 4). The total number of nodes in this graph is 28×28 = 784.

We would like to find the fastest path between a starting node in area 1 : 7 : 5, and an ending node in area 1 : 3 : 5. Figure 4 presents the area hierarchy, in this case see that the lowest common ancestor of the start and end nodes is area 1. The algorithm will proceed in two phases: First, it ascends from area 1 : 7 : 5 to area 1, and then it descends to area 1 : 3 : 5. We first expand nodes in area 1 : 7 : 5 by following roads of level 3, until we reach edges in the border of the area which are at level 2, and are inside area 1 : 7. At this point we are still ascending, as we have not reached the lowest common ancestor, and we will not look at roads of level 3 any more. We now move along edges of level 2 until we reach the borders of area 1 : 7, which are roads of level 1. At this point we will consider only roads of level 1, and roads of level 2 upgraded to level 1 (the dotted ones) until we reach area 1 : 3, at which point we enter the descending phase of the algorithm and the order of road classes to follow is reversed. We follow roads of level 2 to area 1 : 3 : 5, and finally roads of level 3 to the destination node.

In this example, in order to simplify the explanation we