An Adaptive Route-‐‑
Guidance Algorithm for Intelligent Vehicle
Highway Systems
Kanishak Kataria 100050026 Sonal Chouhan 100050036 Pulkit Piyush 100050037
Overview
• Introduction
• Adaptive Route-Guidance Algorithm
o Map Storage and Scaling o Heuristic Search
o Adaptive Determination of Switching o Real-Time Heuristic Search
o Route-Guidance Algorithm Summary
• Simulation Results
• Conclusion
Introduction
What is route guidance algorithm ?
o Route guidance is the problem of providing drivers with help to plan a route prior to and during their journey
Problem with existing algorithms (eg shortest path algorithm) :
o There is no way to store a detailed road-network map into the internal main memory in order to find an optimal route in an affordable time period on a huge road network, and in order to adjust to quickly changing traffic conditions.
o Road and traffic information is not static, especially during road
construction, accidents or rush hours when a lane blockage occurs. This dynamic behavior of road networks suggests that any route-guidance algorithm must adapt to changing environments.
Assumptions for the algorithm to work
1) Drivers can receive static information from a local travel agency which supplies information from I/O devices or from a Traffic Management Center (TMC) when the vehicle is in operation.
2) Dynamic information can be received from the TMC by an in-vehicle transceiver for acquiring real-time traffic information and updating the information in the device database.
3) During the journey this dynamic information can be filtered so that only information of interest to the route planner is presented to the computer main memory in which a tree (or map) is constructed for searching for the solution.
Characteristics of the algorithm
• represents the road network by different type of nodes, with the information being
extracted from hierarchical layered maps (or files).
• separates the internal working map from the other database and searches only one
layered map at a given time.
• adapts the different algorithms on the same search tree based on computation time
constraints and dynamic road information.
Adaptive Route-‐‑Guidance Algorithm
• This route-guidance algorithm is a combination of two components, i.e., a heuristic-search algorithm used for finding an optimal route, and a real-time heuristic-search algorithm for deriving a near-optimal route while
maintaining a time constraint.
• The route-guidance algorithm achieves its objective by automatically switching between its two components.
• This route guidance algorithm is constructed on top of an internal map whose structure is described below.
1. Map Storage and Scaling (1/2)
• Internal Map is constructed as a tree stored in the main processor of a vehicle, and is used as node-based graph to represent the two-dimensional (2-D) real road network.
• The internal map uses all of the road-network data as its resources stored in the files. These files are denoted as either major node or minor-node files.
• The network data can be updated by a TMC on line, and
relevant traffic information can be filtered into the internal map for navigation.
• Right now the map uses two level hierarchy to represent the road network. However this is not the only map structure possible. Our algorithm can be extended to a multi-layer or a multi-sublayer node-based map, in case the road network is extremely large.
1. Map Storage and Scaling (2/2)
• Maps are divided into an overall summary map of major nodes and several regional maps of minor nodes.
o Each intersection of streets in the road network is denoted as a minor node and major intersections are denoted as both minor and major nodes.
o For interstate travel it uses major cities or major freeway intersections as major nodes, and for urban travel it uses the main street intersections as major nodes.
• Need for Map Hierarchy :
o The internal map has an upper bound, which implies determination of the scale factor of the map. An upper bound for the size of each map is predetermined in order to limit the initial planning time to meet the driver's requirements and to efficiently utilize the limited computer memory.
• The size of each map layer is determined by how long we allow the algorithm to find an optimal route.
• Thus the scale factor of the map is implicitly decided according to the computation time constraints, which is crucial for real-time route guidance.
2. Heuristic Search (1/3)
• The heuristic search is the first of two component algorithms used. It is a modified A* algorithm.
• The heuristic search (or modified A*) algorithm
expands fewer nodes than Dijkstra shortest-distance algorithm if a proper heuristic-evaluation function can be defined.
Dijkstra’s algorithm A* algorithm
2. Heuristic Search (2/3)
• In the implementation, the most promising route is
defined as the route which takes the least travel time.
Thus f'(n) is the sum of the actual travel time g(n) and the estimated travel time h'(n):
f'(n) = g(n) + h'(n)
• The estimated travel time h’(n) is computed by dividing the estimated distance by the average speed:
h'(n) = D'(Lc,Ld) / Vavg
where D'(Lc,Ld) is the Euclidean distance between the current location Lc, and the final destination Ld, and Vavg is the average travel speed on the road.
2. Heuristic Search (3/3)
• Difference between the general A* algorithm and modified A* algorithm
o For each node in the knowledge base forbidden flags has been labeled in order to automatically avoid closed roads. Forbidden flags are
determined from information provided by the TMC.
• The benefits of using modified A* algorithm
o The nodes leading to closed roads are marked as forbidden nodes at the time of receiving the information. These forbidden nodes cannot be
generated by the modified A* algorithm, and therefore closed roads are automatically avoided.
• admissibility property of A* algorithm holds
o This modified A* algorithm is shown to be optimal because it generates the fewest nodes while solving a problem. Since the function h'(n)
underestimates the cost and since all travel times and estimates are positive, it finds an optimal route for the driver, based on the admissibility property and the shortest travel time criteria, provided that one exists.
3. Adaptive Determination of Switching (1/3)
• The route-guidance algorithm allows the internal map to combine both static and dynamic traffic information.
• Therefore it is very likely that after pre-planning, the traffic and road conditions on the network have
changed and online re-planning therefore becomes necessary.
• At this time, the route guidance algorithm will calculate how much time, Tplanning is left to allow it to plan the new path using the following equation:
Tplanning = D(lc, lg)/ Vavg
where D(lc, lg) is the actual distance between the current location lc and the next intermediate goal lg, and Vavg is the average travel speed on this road.
3. Adaptive Determination of Switching (2/3)
• The route-guidance algorithm decides which of its two component algorithms will be used to solve the problem by comparing Tplanning against the system-specified
upper-bound deadline, Tdeadline
• Tdeadline is determined based on the time allowed for the route planner to find a solution.
• If (Tplanning < Tdeadline ) the planner will use the heuristic- search algorithm.
• Otherwise, it will switch to a real-time heuristic-search algorithm.
• Since there is no reason to generate an entire new search tree again, the planner still uses whatever is
available from the old tree to save some computation time.
3. Adaptive Determination of Switching (3/3)
• A list of intermediate goals is generated as the optimal route primarily by the heuristic search algorithm from a starting location to a final destination in a low-resolution map, e.g., among major nodes.
• These intermediate goals are temporary destinations on the route used by the driver to reach a final destination.
• The route-guidance algorithm adaptively selects either the heuristic-search or the real-time heuristic-search
algorithm to find a sub-route in a high-resolution map
using successive intermediate goal pairs as the new start and new destination.
4. Real-‐‑Time Heuristic Search (1/4)
• Need for a real-time heuristic :
o Once we start driving, time constraints will occasionally limit the use of heuristic search. Depending on the available CPU, a time constraint always places a limit on the size of nodes that can be searched, i.e., the search horizon.
• A search horizon is a search depth which is determined by the time available for searching a tree.
• This limited search horizon causes the real-time heuristic search to make a decision based on the local
optimality. The depth of search forward from the current state to a fixed depth is determined by the resources
available for computation, i.e., information provided by recent updating from the TMC or CPU time or time
available for planning.
• When a more powerful CPU is available, the search depth can easily be increased.
4. Real-‐‑Time Heuristic Search (2/4)
• The real-time heuristic search finds a satisfactory route which is the least-travel-time route towards the search horizon.
• The frontier nodes are the nodes at the search horizon.
The nodes between the root node and frontier nodes are interior nodes.
• This least travel- time route is found by applying the same heuristic evaluation function, f’(n), to frontier nodes.
• The cost value of each interior node in the tree is based directly on the minimum of the values of its children. An
"x" in the figure 1 indicates a forbidden node which may be caused by a closed road.
4. Real-‐‑Time Heuristic Search (3/4)
• In the example in Figure 1, one road (a single move) is chosen in the direction of the
immediate child of the current state A with the minimum value.
Since the frontier node L has the minimum value 3, the travel
road should be the direction indicated by node D. Only a single move is made instead of going directly to the frontier node with the minimum value, because the values are based on incomplete information
about the road network.
• Further search from the new current state may suggest
choices for making moves other than originally anticipated.
4. Real-‐‑Time Heuristic Search (4/4)
• In contrast to exploring all the frontier nodes as in the above approach, an approach which explores fewer nodes is called the alpha pruning approach, which is analogous to the alpha- beta pruning used in the two-player game algorithm. It is used to perform a minimum search without evaluating all of the
nodes within the search horizon.
• This approach is based on the heuristic function f'(n) being monotone, i.e., non-decreasing along any path away from the starting location.
• The evaluation function clearly satisfies this condition and thus the search space can be significantly pruned.
• Real-time heuristic search algorithm can be interrupted and resumed with little overhead, and can provide better answers when given more time.
• However it does not give us an optimal solution, but rather usually gives near-optimal solutions which are acceptable for most real world problems.
5. Route-‐‑Guidance
Algorithm Summary(1/3)
• Initially, the route-guidance algorithm pre-plans the route according to the major nodes only.
• Since it cannot guarantee that either the current location or the final destination nodes are always in the same layer as the internal map, sometimes the algorithm needs to extract them from a different
layer file. Then these nodes have to be built into the internal tree before the planning process.
• After this pre-planning, the algorithm proceeds to on-line planning until the final destination is
reached.
5. Route-‐‑Guidance
Algorithm Summary(2/3)
1. Enter the destination Id;
2. If either the current location lc, or the destination ld is not in the major-node file, then construct it in the major-node search tree;
3. Open the major-node file and find a list of intermediate goals as the optimal route by heuristic search;
4. If the destination Id is reached, then exit;
5. Otherwise, use or update the next intermediate goal as a temporary destination and perform the following sub-steps;
o 1) If there is no updated traffic and road information along the planned major-node route, then perform the analogous steps and sub-steps on the minor nodes. Goto step 4;
o 2) Otherwise, compute Tplanning
• * If Tplanning < Tdeadline, then use heuristic search on the old tree to find the optimal route. Goto step 4;
• * Otherwise, use real-time heuristic search to find a satisfactory solution.
5. Route-‐‑Guidance
Algorithm Summary(3/3)
• In sub-step 1), the same procedures as for major nodes are processed except a minor-node tree is constructed instead of expanding the old major- node tree.
• From the above steps, we can see that heuristic search is used for both pre-planning and on-line planning when computation time is sufficient.
• Otherwise, real-time heuristic search is used for on-
line planning.
Simulation Results(1/4)
• Suppose a driver needs to travel from New York city, New York to Ann Arbor, Michigan.
• Since this small town of Ann Arbor is not in the major-node file, the route guidance algorithm switches to the minor-node file denoted by "MI".
From there, it finds this town as well as its connections to major nodes and adds this destination to the internal map.
• The algorithm reopens the major- node file and finds a list of
intermediate goals as the optimal route by applying the heuristic search algorithm which constructs and
searches a tree headed by the root (current location) "New York, NY".
Simulation Results(2/4)
• The optimal route is determined to be: New York => Youngstown =>
Cleveland => Toledo => Ann Arbor. This route is pictured in Figure 4 in the bolder line, on which a minor node Ann Arbor is added to the internal map.
• After obtaining the intermediate goals, the driver starts the car towards the first temporary goal, Youngstown, as in step 5 of
Algorithm. If there are no updates, the algorithm goes to sub-step 1).
It quickly opens the minor-node files for New York and Pennsylvania,
constructs a minor-node search
tree, and advises the driver that the best choice should be: Leonia =>
Park => Lodi … => Youngstown.
Simulation Results(3/4)
• If midway between New York and Youngstown during the journey information from TMC is received that the highway from Youngstown to Cleveland is closed because of a tornado, the route guidance
algorithm quickly goes to sub-step 2) and finds out that before the vehicle reaches Youngstown, enough time Tplanning is left for it to determine a new route. By taking a branch headed by Youngstown in the existing major-node tree, the
heuristic search algorithm expands this branch as shown in Figure 5. the algorithm finds the best alternative : Youngstown => Columbus => Toledo
=> Ann Arbor.
Simulation Results(4/4)
• It can happen that during the journey the road from Youngstown to Cleveland is not closed, but the traffic is
slowed down by a half hour due to construction. Since this is an update, the route-guidance algorithm still can re-plan the route. This time it finds that the previous route choice should be kept intact although a half hour more travel time is
required, since this route is still the fastest to reach Ann Arbor.
• This example does not test the use of real-time heuristic search because each layer file contains less than 1,000 nodes and Tplanning is never greater than Tdeadline in the simulation. Therefore real-time heuristic search is never called upon. Sometime in inner-city travel the route-guidance algorithm has to provide a solution in a very limited time because of the short travel time between two streets, and it is also very hard to decompose city streets into each file under certain limits. At this time real- time heuristic search becomes vital.
Conclusion
• This navigation algorithm combines heuristic-search and real-time
heuristic-search algorithms and makes use of a static and dynamically updated database which consists of hierarchically node-based
decomposition files.
• It extracts only the information useful for navigation into an internal map (or tree) and then adaptively selects either the heuristic search or the real-time heuristic-search algorithms to find a solution, depending on which one is the best.
• The algorithm is fairly efficient and flexible, as demonstrated by simulation results.
• The route-guidance algorithm will be ready for real-world testing when the following systems or components can be implemented:
o a positioning system which can determine the current location of the vehicle,
o a transceiver which can receive on-line information from the TMC, a database which can be updated when the in-vehicle transceiver receives real-time information from the TMC, and
o a filter which can extract the relevant on-line traffic and road information in order to update the internal tree (or map) structure from the database.
