Transcript Slide 1

Mike Kofi Okyere
Virtual City: A Heterogeneous System Model of an
Intelligent Road Navigation System Incorporating
Data Mining Concepts
Indiana University - Bloomington
Mentors:
Professor Edward A. Lee
Yang Zhao
http://chess.eecs.berkeley.edu
Disadvantages of Current Route
Planners
Overview
Generating satisfactory directions for
route guidance is a challenging task,
because the effectiveness and advantage
of particular routes depend on various
road specifications and characteristics.
Current route planners, such as
MapQuest.com, Yahoo.com and
Maps.com, present only limited route
options to the drivers of personal or
commercial vehicles. Such directions are
based on static evaluation criteria and do
not consider real-time information
related to traffic conditions, road
construction, road inclination or weather
conditions.
•Calculation of shortest and “fastest” route using static
data:
August 7, 2003
• Calculates routes by taking into account the various
road characteristics in addition to the static data:
•Road Length
•Congestion & Construction Sites
•Constant Travel Speed
•Road Inclination & Weather Condition
•No emphasis is placed on traffic behavior or road
specifications
•Start Location: [A1]
: [P20]
•The DataReader actor executes the Query [Fig. 4] on
the data warehouse and sends result sets to
GraphBuilder actor
•The GraphBuilder actor converts the received result
sets into a directed graph (digraph) and sends the
created digraph to the ShortestPath actor
•Establishes a self-balancing Traffic System
•The ShortestPath actor verifies the validity of the input
nodes and graph, in order to then determine the most
efficient route by applying an extension of Dijkstra’s
Shortest Path Algorithm
Dynamic Road Map
Virtual City
•User Input :
•Destination
•Enables roadways to operate at peak volume levels
Static Road Map
Virtual City
Static Road Map
Real-Time Road Map
WORK
WORK
55 Miles
45 Miles
60 Miles
65 Miles
45 Miles
55 Miles
Highway
Speed Limit
70mph
Speed Limit
65mph
Highway
Speed Limit
65mph
Speed Limit
50mph
Route A
Route B
Route C
Route D
The New Approach
The Intelligent Road Navigation System
consists of a dynamic data warehouse that
contains real-time road information,
ranging from road name and length to
road inclination and traffic density. The
most efficient route is calculated by an
extension of the Dijkstra’s Shortest Path
Algorithm to obtain driving directions
that focus on minimizing either travel
time, gasoline usage, driving mileage or a
combination of all.
Advantages of the Intelligent Road
Navigation System
IRNS Sample Run
40 Miles
60 Miles
Speed Limit
45mph
65 Miles
Highway
Speed Limit
70mph
Rush Hour Traffic
Speed Reduction
20%
Speed Limit
65mph
Road Construction
Speed Reduction
15%
Highway
Speed Limit
65mph
Speed Reduction
0%
Speed Limit
50mph
Speed Reduction
0%
Route A
Route B
Route C
Route D
40 Miles
60 Miles
50 Miles
35 Miles
Speed Limit
50mph
Residential Area
Speed Reduction
5%
Speed Limit
45 mph
Intersection Traffic
Speed Reduction
20%
Speed Limit
45mph
Light Traffic
Speed Reduction
10%
35 Miles
50 Miles
Speed Limit
50mph
60 Miles
Speed Limit
45 mph
Speed Limit
45mph
In-City Traffic
Speed Reduction
15%
Speed Limit
45mph
Figure 3 – Showing the Ptolemy II model of the
Intelligent Route Navigation System
SELECT START, END, [LENGTH]/([SPEED]*[TrafficFactor]*[ConstructionFactor])*60
AS TrafficTime
FROM Construction INNER JOIN (Traffic INNER JOIN RoadRules ON
Traffic.TrafficTypeID = RoadRules.TRAFFIC) ON Construcion.ConstructionSiteTypeID
= RoadRules.CONSTRUCTION;"
HOME
HOME
Street Map
Street Map
City B
END
City C
210 sq. ft.
Figure 4 – Showing the Query used to find the
shortest travel time between road segments
City B
END
City C
210 sq. ft.
15
Dijkstra’s Shortest Path Algorithm
15
City A
City A
10
Shortest Path from (a) to (d) is calculated as follows:
10
Graph G = (V, E):
323 sq. ft.
323 sq. ft.
511 sq. ft.
V = {a, b, c, d}, E = {(a, b, 4), (a, c, 2), (b, c, 3), (b, d, 1),(c, a, 2), (c, b, 1), (c, d, 5)}
511 sq. ft.
1. Init: d(a) = 0, d(b) = INF., d(c) = INF., d(d) = INF.
5
5
835 sq. ft.
835 sq. ft.
2. 0+ [a,b] = 4 < INF.
[set distance from (a)  (b) = 4]
0+ [a,c] = 2 < INF.
[set distance from (a)  (c) = 2]
[Pick [c]]
3. 2 + [b,c] = 3 < 4
2 + [b,d] = 7 < INF.
City D
1
START
[Pick [b]]
City D
1
START
[set distance from (a)  (b) = 3]
[set distance from (a)  (d) = 7]
4. 3+ [b,d] = 4
[set distance from (a)  (d) = 4]
The algorithm stops, since the shortest path has been found.
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
Figure 1 - Showing the “Fastest” Route using a Static Data
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
Figure 2 – Showing the Fastest Route using Dynamic Data
Shortest Path: (a)  (c)  (b)  (d)