X hits on this document

# ABSTRACT - page 8 / 12

46 views

0 shares

8 / 12

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 (d1, . . . , dk) 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 ai, aj respectively will consider at most O(|ai| + |aj | + |bn| + |un|) distinct nodes, where |ai| is the number of nodes in area ai, |aj | is the number of nodes in area aj , |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 Aeven 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

End Area 1:3:5

Area 1:3

1

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.