THE APPLICATION OF LINGUISTIC GEOMETRY
TO THE ROUTING OF EMERGENCY VEHICLES
by
Richard James Turek, Jr.
B.S., Towson State University, 1984
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Computer Science
1996
Copyright 1996 by Richard James Turek, Jr.
All
rights reserved.
This thesis for the Master of Science
degree by
Richard James Turek, Jr.
has been approved
by
Tom Altman
Mike Radenkozic
2&:
Date
Turek. Richard James. Jr. (M.S., Computer Science)
The Application of Linguistic Geometry to the Routing of Emergency Vehicles
Thesis directed by Professor Boris Stilman
I
I
ABSTRACT
The objective of this research project is to explore the feasibility of applying Linguistic
Geometry (LG) to the dynamic generation of either optimal or nearoptimal routes for E911
emergency vehicles. A prototype developed to simulate a Computer Aided Dispatch (CAD)
system, routes vehicles on a street network with a sufficient density to represent the target
operating environment. The prototype network contains over 800 street miles of road with
greater than 6,700 nodes and 9,000 arcs in a density representative of a municipal
streetscape. Analysis of the CAD complex system allows for the reduction of the problem
space for the prototype to the generation of an optimal path between two points on the
network within 0.5 seconds. Routes where determined to be typically under four miles in
length, but the prototype assumes no route length limitations.
LG, in particular, the Language of Trajectories (LT) was applied to generate the
optimal paths. LT was extended to introduce aggressive pruning of the search space during
the costing calculation without compromising the generation of an optimal path. As a further
study, nearoptimal path generation was introduced by arbitrarily bounding the search space
through a simple distance equation.
The conclusion is that applying LG is a viable approach to routing emergency
vehicles. The prototype met or exceeded all performance criteria.
This abstract accurately represents the content of the candidate's thesis. I recommend its
publication.
Signed
Boris Stilman
IV
DEDICATION
I dedicate this thesis to my wife, Anna, without her enduring support my work could
not have been completed.
ACKNOWLEDGMENTS
My thanks to Dr. Stilman for his support and understanding when the duties of life
periodically interrupted my research.
CONTENTS
Chapter
1. Introduction......................................................................1
2. Problem Definition...............................................................3
2.1 Current Dispatch System.......................................................3
2.1.1 Phone Subsystem...............................................................4
2.1.2 Dispatch Subsystem............................................................4
2.1.3 Communications Subsystem......................................................4
2.1.4 Mobile Unit Subsystem.........................................................5
2.2 System Augmented with Computer Aided Routing..................................5
2.2.1 Phone Subsystem...............................................................6
2.2.2 Dispatch Subsystem............................................................6
2.2.3 Communications Subsystem......................................................6
2.2.4 Mobile Unit Subsystem.........................................................6
2.2.5 Approach......................................................................7
3. Description of Prototype........................................................11
4. Prototype History...............................................................15
5. Description of Algorithm........................................................16
5.1 Formal Definition............................................................17
5.2 Algorithm Implementation.....................................................18
5.2.1 Redundant Path Pruning.......................................................19
5.2.2 Partial SUM Pruning..........................................................20
5.2.3 Nearoptimal Pruning.........................................................21
5.3 Algorithm Walk Through.......................................................21
5.4 Comparison to Language of Trajectories.......................................26
6. Contrast to Dijkstra's Algorithm...............................................27
6.1 Dijkstra's Algorithm.........................................................27
6.2 Comparison...................................................................28
7. Results.........................................................................29
7.1 Optimal Path Generation......................................................29
vii
7.2 Nearoptimal Path Generation...............................................36
7.3 Analysis of Results and Conclusions........................................43
References .......................................................................44
viii
FIGURES
Figure
1.1 Street Centerline Database for the City of Aurora, Colorado.......................1
2.1 E911 Emergency Response System...................................................4
2.2 Augmented E911 Emergency Response System.........................................5
2.3 Dispatch System Architecture.....................................................10
3.1 Graphically Displayed Route......................................................11
3.2 Prototype Architecture...........................................................12
3.3 Prototype Network Object Design..................................................13
5.1 Formal Definition of Language of Trajectories Adaptation.........................16
5.2 Redundant Path Pruning...........................................................19
5.3 Partial SUM Pruning..............................................................20
5.4 Nearoptimal Pruning.............................................................21
5.5 LTA Example......................................................................22
7.1 Distribution Over Time of Optimal Routes Generated (10,000 Samples)..............31
7.2 Distribution Over Time of Optimal Routes Generated (4,000 Samples)...............31
7.3 Distribution Over Distance of Optimal Routes Generated (10,000 Samples)..........32
7.4 Distribution Over Distance of Optimal Routes Generated (4,000 Samples)...........32
7.5 Scatter Plot of Distance Over Time for Optimal Route Generation..................33
7.6 Scatter Plot of Arcs per Route Over Time for Optimal Route Generation............34
7.7 Scatter Plot of Nodes Searched Over Time for Optimal Route Generation............35
7.8 Distribution Over Number of Attempts to Generate a Near Optimal Route............36
7.9 Distribution Over Time of Nearoptimal Routes Generated (10,000 Samples).........38
7.10 Distribution Over Time of Nearoptimal Routes Generated (4,000 Samples)..........38
7.11 Distribution Over Distance of Nearoptimal Routes (10,000 Samples)...............39
7.12 Distribution Over Distance of Nearoptimal Routes (4,000 Samples)................39
7.13 Scatter Plot of Distance Over Time for Nearoptimal Route Generation.............40
7.14 Scatter Plot of Arcs per Route Over Time for Nearoptimal Route Generation......41
7.15 Scatter Plot of Nodes Searched Over Time for Nearoptimal Routes.................42
TABLES
Table
5.1 Pass 1 Results..............................................................24
5.2 Pass 1 Search Queue.........................................................24
5.3 Pass 2 Results..............................................................25
5.4 Pass 2 Search Queue.........................................................25
7.1 Optimal Route Generation Statistics (10,000 Routes).........................29
7.2 Optimal Route Generation Statistics (4,000 Routes)..........................30
7.3 Nearoptimai Route Generation Statistics (10,000 Routes)....................36
7.4 Nearoptimal Route Generation Statistics (4.000 Routes).....................37
x
1. Introduction
While studying Linguistic Geometry (Stilman, 1996) under Dr. Stilman, I started
exploring the feasibility of applying commercially available technology to the automation of
the emergency vehicle dispatch process. It became obvious that the critical weakness in
commercial Geographic Information System (GIS) technology, was the rapid optimal
generation of paths. For example, ARC/INFO executed on a Sun SPARCstation 10
generated routes (ESRI, 1996) with an elapsed time in the five to ten second range per
route. This latency was clearly unacceptable for routing emergency vehicles to an incident in
which several routes need to be generated in order to determine the closest vehicle(s) to
route to the emergency.
Fascinated with the significant reduction in the search space obtainable using
Linguistic Geometry, I set out to determine if the Language of Trajectories (Stilman. 1993)
could be applied to optimal path planning on a complex street network. Another highly
desirable characteristic of the Language of Trajectories was the guaranteed generation of an
optimal route. For obvious reasons, this is important in routing emergency vehicles while
trying to minimize response time.
Figure 1.1, Street Centerline Database for the City of Aurora, Colorado
The objective of this research project is to explore the feasibility of applying the
Language of Trajectories into the dynamic generation of either optimal or nearoptimal routes
for emergency vehicles. Figure 1.1 shows a representative street network used to evaluate
1
the potential of this approach. In order for the results to be meaningful, the E911 emergency
vehicle dispatch problem is defined and evaluation criteria is assigned to the route
generation aspect of the problem.
2
2. Problem Definition
An important objective of every local government is to ensure reliable and
predictable emergency vehicle dispatching. Computer Aided Dispatch (CAD) systems assist
the human dispatcher to pick which emergency vehicles to send to an emergency and then
to monitor these dispatched emergency vehicles. They do little, however, to determine which
vehicle is closest, based on network connectivity, nor to help determine the best route for the
vehicle to take to the emergency. The dispatcher typically chooses a vehicle either by line
ofsight distance or by the proximity of the vehicles station. The vehicles driver must, at the
time of dispatch, determine the best route to the scene of the emergency using his or her
own knowledge of the city street network and traffic patterns. These requirements, placed on
humans with severe time constraints, allow for major variance in the time required for an
emergency vehicle to arrive at the scene. The loss of human life or extreme property damage
can result.
The typical E911 dispatch system is analyzed to determine the feasibility of
subdividing the system into standalone subsystems. The objective is to simplify the problem
into one subsystem containing only the dynamic routing algorithm with a specific set of
evaluation criteria or requirements. An example follows on how current systems respond to a
call for help.
2.1 Current Dispatch System
The current E911 system is a partially automated, but mostly a human intensive
system. The following scenario indicates where in the process humans are performing the
most critical work.
A citizen dials 911 on the telephone and the phone system automatically forwards
the call to the appropriate 911 operator. The 911 operator questions the caller to extract and
transcribe relevant information. This information, along with the address of the emergency, is
electronically forwarded to the appropriate public safety dispatcher. The dispatcher, using
the CAD system, then selects the vehicle(s) to send to the emergency. The dispatcher radios
each unit to be dispatched and verbally relays situation information. Each driver determines
the best route to the emergency and drives to the scene. Information updates, from either the
dispatcher or driver, are communicated via radio while the vehicle(s) are in transit. The
unit(s) arrive at the scene and attempt to control the situation. Critical information is radioed
between the unit and the dispatcher. If an emergency transport is required, as with
paramedics, the driver chooses a hospital and then chooses a route to get to that hospital.
The situation is closed when all units have completed their relevant tasks.
After analyzing the scenario, four major activities present themselves. These
activities define the major subsystems for the E911 System. Figure 2.1 depicts these
subsystems and how they interact at a high level. A more detailed discussion of each
subsystem follows.
3
2.1.1 Phone Subsystem
The Phone Subsystem receives the 911 call and automatically forwards it to the
appropriate 911 operator. In most cases, the appropriate operator is determined by the
geographic location of the caller, or more exactly, the location of the telephone the caller is
using. The operator solicits information from the caller and produces a transcription. Once
the operator determines the type of emergency and the address, a notice is sent to the
appropriate dispatcher. As more information is gleaned from the caller, updates are sent to
the dispatcher.
2.1.2 Dispatch Subsystem
The Dispatch Subsystem receives the emergency notification from the Phone
Subsystem and displays it to the dispatcher. For a police emergency, the dispatcher then
verbally polls the units for availability and dispatches a vehicle. For a fire emergency, the
address of the emergency is forwarded to the CAD system which selects the unit based on
the location of the units fire station. The dispatcher then verbally dispatches the unit. The
dispatcher maintains verbal communications with dispatched units using the
Communications Subsystem.
2.1.3 Communications Subsystem
The Communications Subsystem transports all message traffic between the
dispatcher and the mobile unit. The communications medium is typically radio frequency and
supports both voice and digital data transmissions. This subsystem usually has multiple
frequencies with a small number of vehicles sharing a frequency.
4
2.1.4 Mobile Unit Subsystem
The Mobile Unit Subsystem consists of the driver and the emergency vehicle. The
driver receives notification of the emergency by voice message over the radio. The driver
then determines the route to the emergency and drives to the scene. Currently, this
subsystem is completely autonomous.
2.2 System Augmented with Computer Aided Routing
The emergency dispatch and routing automation is a complex problem. It integrates
mobile units with the base dispatch system through a realtime RF communications
mechanism (see Figure 2.2). The mobile units utilize the Global Positioning System (GPS) to
maintain their current location. The dispatch station utilizes Geographic Information System
(GIS) technology to graphically display mobile units and associate them to the street
network. The following is the above scenario augmented with the automated routing
capability.
A citizen dials 911 on the telephone with the phone system automatically forwarding
the call to the appropriate 911 operator. The 911 operator questions the caller to extract and
transcribe relevant information. This information, along with the address of the emergency, is
forwarded to the appropriate public safety dispatcher. The system automatically determines
the closest appropriate vehicles and presents them to the dispatcher. The dispatcher selects
the vehicle(s) to send to the emergency. The system automatically forwards the directions to
all dispatched vehicles. The dispatcher radios each unit to be dispatched and verbally relays
situation information. Each driver drives to the scene using the forwarded directions.
Updates in the vehicles location are automatically forwarded periodically to the base.
Changes to the directions are also automatically forwarded to the vehicle when necessary.
Information updates, from either the dispatcher or driver(s), are radioed while the vehicle(s)
are in route. The unit(s) arrive at the scene and alleviate the situation. As needs arise,
critical information is radioed between the unit(s) and the dispatcher. If an emergency
transport is required, as with paramedics, the system automatically generates directions to
GPS
Receiver
Dnver
notification,
routes
notification \ / voice.
________/ vehicles to dispatch
^ Dispatcher
<
Figure 2.2, Augmented E911 Emergency Response System
5
the nearest appropriate hospital and forwards it to the vehicle. The driver follows the route to
the hospital. The situation closes when all units have completed their relevant tasks.
Now that the E911 dispatch scenario is altered to add dynamic tracking, the system
architecture is evaluated to determine where modifications are required.
2.2.1 Phone Subsystem
This subsystem requires no modifications to support automatic routing. It already
forwards the notification of the emergency electronically to the dispatcher.
2.2.2 Dispatch Subsystem
This dispatch subsystem requires the most modifications. It requires the integration of
several new components: Differential GPS (DGPS), a GIS, and the route generator. The
interface with the dispatcher is significantly altered to allow for the graphical display of
vehicles, the presentation of candidate vehicles to be routed, and the graphical presentation
of the dispatched routes.
Adding the DGPS component allows for a more accurate location (+/15 feet) of the
vehicles to be reported to the GIS. The reduced error is extremely useful to correctly
correlate the vehicle(s) to the street network. The vehicle(s) must be mapped to the correct
street segment for any generated directions to be meaningful.
The GIS component graphically displays the street network to the dispatcher while
displaying the location of all vehicles being monitored. The GIS must also spatially associate
the vehicles to the street network. When it is time to determine the proximity of the vehicles
to an emergency, the GIS forwards the network locations of all appropriate vehicles and the
emergency to the route generator. After the route generation is complete, the GIS graphically
displays the possible routes to the dispatcher while presenting an ordered list of the
vehicles, starting with the closest vehicle and ending with the furthermost vehicle from the
emergency. The dispatcher chooses the vehicle(s) to dispatch, and the GIS coordinates the
forwarding of the directions to the mobile units. Throughout the dispatch process, the GIS
tracks the vehicles relative to the projected route and alerts the dispatcher of any deviations.
The Route Generator implements a routing algorithm based on the Language of
Trajectories. It receives start and stop locations relative to the street network for each vehicle
potentially being dispatched and generates the optimal route for the defined network and
search space. A more detailed discussion of the algorithm is presented in the Description of
the Algorithm section.
2.2.3 Communications Subsystem
This subsystem requires little if any modification. The only additions, if any, are
equipment to support digital data transmissions and any extra bandwidth to support the new
data transmissions.
2.2.4 Mobile Unit Subsystem
This mobile unit subsystem requires two key modifications: The first is the addition of
a GPS receiver to receive location updates from the GPS satellites and the second is a small
6
computer to coordinate the forwarding of the units location to the Dispatch Subsystem. The
new computer must also receive routing directions from the Dispatch Subsystem and display
the directions.
2.2.5 Approach
This section determines the new system level performance requirements and
allocates them to the appropriate subsystems. After the requirements have been allocated,
each subsystem is evaluated for its risk of successfully meeting the requirements. The
objective is to prove that the only major risk to successfully implementing this system is in
the dispatch subsystem. The dispatch subsystem is then further analyzed to isolate risk to
the smallest component. This component is then prototyped to alleviate the risk and prove
that computerized emergency vehicle routing is feasible.
2.2.5.1 Performance Requirements
This section first identifies the system level performance requirements then flows
them down to the subsystems.
2.2.5.1.1 System Performance Requirements
Now that the required changes to the E911 system have been identified and the key
subsystems determined, performance requirements are isolated to determined the
requirements of a useful system. The following represent the key timing and performance
requirements for the dispatch system.
The system shall complete the dispatch cycle within 30 seconds. A dispatch cycle is
defined to start when an emergency notice is generated by the 911 operator and
completed when the route directions are displayed in the mobile unit being routed.
Defining the dispatch cycle this way removes the operator interacting with the caller from
the timing requirements, which can be quite variable in duration. The allocation of 30
seconds to the dispatch process is somewhat arbitrary. The ultimate goal is to have the
time from emergency notification to the arrival of unit(s) be a maximum of four minutes.
Four minutes is critical, in particular, for emergency medical teams responding to an
emergency in which the victim has stopped breathing. After discussions with public
safety officials, 30 seconds was agreed upon as a requirement for dispatch.
The system shall send the emergency notice from the 911 operator to the dispatcher
within one second.
A sufficient reaction time shall be allocated to the dispatcher. For this problem, 15
seconds is appropriate for the human dispatcher to interact with the system to dispatch
vehicles.
The system shall route a maximum of 10 units at one time. This is an arbitrary upper
bound based on analysis of the City of Aurora dispatch process. It represents the worst
case scenario of a several alarm fire emergency in which several fire stations are
responding with full complements of vehicles.
7
The system shall present the dispatcher with the list of candidate vehicles within 10
seconds of receiving the emergency notice. The vehicles are ordered by their distance
from the emergency, starting with the closest vehicle.
The system shall transmit and display the directions in all dispatched vehicles within four
seconds. A large amount of time is allocated to account for multiple vehicles sharing the
same communications frequency and, therefore, serializing some of the directions being
forwarded.
The mobile units shall transmit their location to the home base at the minimum rate of
once every five seconds during normal operation.
The mobile units shall transmit their location to the home base at the minimum rate of
once every second while in transit to the scene of an emergency.
2.2.5.1.2 Subsystem Performance Requirements
The system level requirements are now allocated to the subsystems. Any
requirements that transgress subsystem boundaries are rewritten to represent only the
portion allocated to an individual subsystem. The following represent the key timing and
performance requirements allocated to the subsystems.
Phone Subsystem
The phone system shall forward the emergency notice to the communications subsystem
within 0.1 seconds of the 911 operator authorizing its transmission.
Dispatch Subsystem
The dispatch subsystem shall display the emergency notice to the dispatcher within 0.1
seconds of receipt.
The dispatch subsystem shall route a maximum of 10 units at one time.
The dispatch subsystem shall present the dispatcher with the list of candidate vehicles
within 10 seconds of receiving the emergency notice.
15 seconds is allocated for the human to view the list of possible vehicles to route,
selecting the vehicles to dispatch, and authorizing the dispatch of the vehicles. Note that
this is not so much of a requirement as a marker for the allocation of time to an
uncontrollable event.
The dispatch subsystem shall forward directions to the communications subsystem
within 0.1 seconds of the dispatcher authorizing the dispatch.
Communications Subsystem
The communications subsystem shall transmit the emergency notice from the phone
subsystem to the dispatch subsystem within 0.8 seconds.
The communications subsystem shall transmit the directions from the dispatch
subsystem to the designated mobile unit within 3.4 seconds.
8
Mobile Unit Subsystem
The mobile unit shall display the directions to the driver within 0.5 seconds of receipt of
the directions from the communications subsystem.
The mobile unit shall transmit its location to the home base at the minimum rate of once
every five seconds during normal operation.
The mobile unit shall transmit its location to the home base at the minimum rate of once
every second while in transit to the scene of an emergency.
2.2.5.2 System Risk Assessment
This section isolates and identifies the critical risks, if any, associated with the four
subsystems and then attempts to mitigate those risks.
The phone subsystem has no critical risks. It is an existing, operational system, that
is used in the augmented E911 system without modification.
The dispatch subsystem has two critical risks: 1) correlating vehicles to the street
network in realtime, and 2) generating the routes within the required time constraint on a
large dense street network.
Correlating vehicles to the street network in realtime, particularly when dealing with
a large number of vehicles, is pushing current commercial GIS technology. However, its
feasibility has been proven with current proprietary research on dynamic vehicle tracking. As
for dynamic routing, I am unaware of any products or prototypes that mitigate this risk. I
consider this capability to be the only critical risk for the E911 system.
The communications subsystem does not harbor any critical risks. It encapsulates
standard communications medium and technologies. The only potential risk, which is easily
mitigated with good systems engineering and network modeling, is having too many mobile
units on the same RF frequency.
The mobile unit subsystem has no critical risks. Current mobile computing
technology easily supports the required capabilities. The main issue with this suosystem is to
meet the requirements with the most cost effective solution possible, since it is replicated in
each vehicle routed.
2.2.5.3 The Isolation of Dynamic Vehicle Routing
The system risk assessment reduced the problem to one critical risk, can a system
be built that routes a vehicle in one second on a large dense street network? Therefore, the
problem can easily be reduced to the dispatch subsystem with only the requirements levied
against it.
Figure 2.3 depicts an architecture for the dispatch subsystem. This subsystem has
two components: the GIS Display Server (GDS) and the route server. The GDS component
interacts with the communications subsystem to receive the emergency notice from the
phone subsystem and location updates from the mobile units. This component also forwards
directions to the mobile units through the communications subsystem. The dispatcher only
interacts with GDS when dispatching the vehicles. The route server is completely isolated
from the rest of the system. Its interface is defined with two messages with the GIS display
9
server. It receives a message requesting it to generate a route and sends a message
containing the route information.
Figure 2.3 shows that the problem can be further reduced to the route server
component. By showing that the dynamic route generation can be accomplished within the
one second time constraint on commercially available hardware proves that the E911
system can be augmented with automated routing using current technology. The route server
component has a very simple external interface and thus lends itself to be easily prototyped
to determine feasibility.
10
3. Description of Prototype
The objective of this prototype is to implement a minimum architecture to explore the
feasibility of using a hybrid of the Language of Trajectories to generate optimal routes within
one second using a realworld street network. The Problem Definition section systematically
reduces the problem space to the generation of an optimal route within one second. The
prototype further reduces the problem to generating routes between two intersections on the
street network. It is simple enough to determine the directions from the vehicle to the starting
intersection and from the destination intersection to the incident address. Therefore, this final
simplification does not detract from a feasibility study using the prototype. A preliminary
version of this prototype was demonstrated at the 1995 Goddard Conference on Space
Applications of Artificial Intelligence and Emerging Information Technologies.
Two key areas of study relative to the prototype are: 1) what is the optimal way to
model the street network, and 2) what adaptations to the Language of Trajectories is
required to support this problem domain. This section focuses on the first question as well as
other prototype architecture issues and defers discussion of the second question until the
Description of Algorithm section. Since these studies where iterative, the current incarnation
of the prototype is discussed in this section with previous versions summarized in the
Prototype History section. As a margin of error, timing requirements for the generation of an
optimal route was shortened to 0.5 seconds (from one second). I felt this was necessary
since more research needs to be placed on a better model for the street network. I felt it was
also reasonable to assume that the required enhancements would not slow the routing down
by a factor of two.
The prototype, in summary, generates its
network model from two publicly available data
sources. Once the network model is built, the
prototype runs in one of two modes: interactive or
batch. Interactive mode allows for a user to select
the start and destination intersections from a
graphical display, generates a route, and graphically
displays the route with statistics and textual
directions. Figure 3.1 shows an example of a
graphically displayed route. Batch mode, while
visually unimpressive, benchmarks the behavior or
the prototype. It follows a test script defining pairs of
intersections for which it generates routes. This
mode computed all the statistics analyzed in the
Results section.
The prototype is comprised of five parts
(processes) as defined by circles in Figure 3.2. Data
stores are represented by the parallel bars (lines). The flow of data is indicated by the
arrowed lines. Lines with labels identify the data being transferred between the two
processes. Lines without a label are only between a data store and a process and indicate
11
I
that the store holds homogeneous data, and the flow migrates a complete data item of which
the store holds.
The Network Generator builds the Network Database by importing data from either
an Arc/lnfo Coverage (ESRI, 1992) or from Tiger/Line Data (Census Bureau, 1993). The
Network is streamlined and optimized for path planning and is intended to be memory
resident during routing activities. A detailed discussion of the network is presented in the
object model discussion.
The Benchmark Manager coordinates the execution of a benchmark test. The
Benchmark Manager randomly generates a specified number of start / destination
intersection pairs and serially feeds them to the Route Server for route generation. Statistics
collected from the route generation results are stored to disk. The randomly generated
intersection pairs are also saved to disk to support baselining versions of the prototype.
The Display Manager coordinates the interactive generation of routes. It simulates
the Dispatch Subsystem's graphical display. The Display Manager currently allows the user
to graphically select start and destination intersections and forwards the route generation
request to the Route Server. The route is graphically displayed along with textual directions
and statistical information.
The three processes discussed above are all implemented in the Avenue
programming language and executed in the ArcView commercial application.
The Statistics Generator is simply a commercial spreadsheet program that imports
raw statistics generated by the routing requests and builds summary plots and distribution
analysis. A summary of the results from this analysis is included in the Results section.
The Route Server is a single threaded, object oriented C++, dynamic link library
(DLL) (Borland, 1993) which fully encapsulates the routing function for the prototype. The
Route Server is called as a DLL function with a routing request and returns the routing
12
results. Figure 3.3 identifies the key classes involved in the routing process with their
relationships in Booch notation.
The Grammar class completely encapsulates the routing algorithm with the rest of
the classes modeling the network. The routing algorithm is discussed in the Description of
Algorithm section. As the notation indicates, there exists only one Grammar object at
execution time.
The Map class is the smart container class for the street network. It coordinates
retrieval of the persistent node and arc objects from file and the memory management of
these objects. At execution time, one Map object coordinates from one to n arcs and nodes
where n is the number of objects required to model the street network.
The networK is a set of persistent objects loaded into memory at DLL initialization. It
is modeled with five classes of which only three are concrete (exist as objects). The Map
class, as indicated, manages the network. The Node and Arc classes are the critical
elements of the network. These classes model the network topology in a fashion that
supports the routing algorithm in an optimal fashion.
The GISEntity class is a base class that implements a unique identifier for all
network objects. Both Node and Arc inherit from this class for its uniqueness capability.
The Coordinate base class implements a Cartesian coordinate. It is inherited by the
Node class to support nearoptimal routing (see the Nearoptimal Pruning discussion) when
enabled.
The Node class represents a street intersection. It maintains network topology by
keeping a set of Arcs connected to it. The Node class also maintains the statistics required
for the routing algorithm. See the Algorithm Implementation section for a discussion of those
statistics.
13
The Arc class models a street segment. It supports network topology by maintaining
the nodes to which it is connected. The Arc class also maintains the cost of traversing it.
The network impedance or cost equation is run as a batch preprocess on the
network. It leaves a residual impedance value for each Arc and Node. This has a twofold
advantage: it decouples the routing algorithm from the cost equation: and it keeps the route
generation algorithm fast and simple. For the prototype, distance is used for impedance and
only the Arcs impedance is used.
The prototype utilizes the street network for City of Aurora, Colorado (see Figure
1.1). The network has over 800 street miles with 6,711 nodes (intersections) and 9,050 arcs
(street segments). This network is based on the actual street network for Aurora and is
distilled from their GIS database.
Currently, the network is modeled as a undirected cyclic graph. Further research is
required to explore alternative representations that better represent phenomena such as
oneway streets and other peculiarities of real world street networks.
14
4. Prototype History
The prototype has had many revisions over the time spanning this research project.
Each revision was attempting to either improve the correctness of the street network model
or the performance of the routing algorithm. The prototype has undergone three major
revisions from its initial concept.
A commercially available object oriented database management system (ODBMS)
was initially used to implement the persistent objects in the street network. Significant effort
and time was spent on optimizing this implementation for performance, but to no avail.
ODBMS products on Windows 3.1. at that time, could not meet the required performance.
This implementation was producing optimal routes within minutes. This approach had the
appeal of transparently implementing the persistence of the network objects and simplifying
their memory management. But obviously, this implementation was had totally unacceptable
performance characteristics.
The next generation of the prototype migrated from an ODBMS implementation to
memory resident network with the prototype managing the persistence of the objects. This
approach has the appeal of promoting rapid access to the network objects. Optimal route
generation now occurs in seconds. There were two significant deficiencies with this version:
double indirect addressing was used and the prototype was a 16 bit application. Each Node
and Arc has a unique identifier, as provided by the GISEntity class. Network topology was
implemented using the identifiers and lookup tables. Arcs and Nodes each had their own
lookup table. This approach was an easy solution for implementing the object persistence,
but added extra overhead for network traversals. A rather troublesome aspect to this
approach was the limitations imposed by the 16 bit architecture. Special coding was required
to implement the lookup tables when they spanned more than 64 KB in size. This version of
the prototype also used dynamic data exchange (DDE) as the communications mechanism to
the Route Server. This version did not. as of yet, have a graphical display.
This version of the prototype added the ArcView commercial product as the
graphical front end. ArcView graphically displayed the street map and allowed for the user to
interactively select Node pairs for route generation. Routes were graphically displayed along
with textual descriptions. This was the version of the prototype that was demonstrated at
Goddard.
The current version of the prototype is a 32 bit dynamic link library (DLL) that is
called strictly from the ArcView front end. Substantial optimizations where performed during
the port from 16 bit to 32 bit. The lookup tables are removed and instead Arcs and Nodes
use pointers to directly address each other. The cost coefficient was migrated from a floating
point number to a 32 bit integer. By changing the communications mechanism from DDE to
DLL, Windows messaging overhead was removed and replaced with the overhead of a
standard function call. This version is currently ported to Windows 95 only.
15
5. Description of Algorithm
This algorithm produces all optimal paths between two nodes on a cyclic graph
based on predetermined traversal costs. The algorithm is derived from the Language of
Trajectories (Stilman, 1993). This section formally describes the algorithm, its
implementation, and walks through an example of the algorithm building an optimal path
between two nodes on a defined graph.
The Language of Trajectories Adaptation in summary, performs the following steps:
determines the cost from the start and destination nodes to all nodes in the search space
and applies the three rules from its context free grammar. These rules search the problem
space for optimal paths by applying the intersection of the SUM, STk, and STr sets.
L Q Kernel Ff
1 Q1 S (xo, yo, so) *> A (x, y, s) two 0
2i q2 A (x, y, s) > a (x) A (nextj (x, s), y, f (s)) two 3
3 Q3 A (x, y, s) > a (y) 0 0
VT = {3}
Vn = {S.A}
vPR = {q1' q2 q3>
Qi (X. y) = (map (x, y) = c. c >= 0)
Q2 (s) = (s >= 1)
Q3 = t
L = {1, 3} U two. two = {2,. 22...2}
VAR = {xo, yo. So, x. y, s}
FN = {f, next,, .... nextn, map, step}
f (s) = s 1, D (f) = 2* {0}
next (x) is the intersection of the following sets:
STi, ST(Sos*i), and SUM where
SUM = {v  v from X, map (xo, v) + map (yo, v) = map (x, y)>
STk (x) = {v  v from X, step (x, v) = k}
D (next,) = X
map (x. y) = MIN (cost of traversing the graph from x to y), D (map) = Z
step(x, v) = MIN (number of steps traversing the graph from x to v), D (step) = Z
Figure 5.1, Formal Definition of Language of Trajectories Adaptation
16
5.1 Formal Definition
Figure 5.1 contains the formal definition of Language of Trajectories Adaptation
(LTA). The figure is divided into two parts. The first part is the definition of the contextfree
grammar. The algorithm has three rules represented by L(1) through L(3). Rule 2 fires
multiple times and has multiple concurrent branches. These multiple branches are
represented by the subscript i. Column Q" identifies the predicate for each rule. These
predicates must test true for the associated rule to fire. The Kemer column defines the
actual rule. Columns FT and "Fp define which rule to execute next when the associated
predicate passes or fails respectively. When a predicated tests positive, its associated rule is
executed before jumping to the rule indicated by FT.
Rule 1 starts the algorithm, it transitions from the start state by seeding x. y\ and
s with the starting values. xo" is the starting node. y0 is the destination node. So is the
minimum number of steps between the nodes. Rule 2" builds the string of terminals for all
possible optimal paths. Each terminal is a node in the graph. Rule 3 appends the terminal
for the destination node to the end of the optimal path string.
The second part of Figure 5.1 defines the notation used in the contextfree grammar.
Vj* identifies the set of terminals.
VN identifies the set of nonterminals.
VPR" identifies the set of predicates and then proceeds to define them.
Predicate Qt" tests for the existence of a path between x" and /* Rule 1" will not
fire if a path does not exist between the two nodes. Predicate Q2" tests for the end
of the path and predicate Q3" is always true. If the algorithm is generating a path,
there is always an end to it.
L is the set of all rule numbers. Since rule 2" can have multiple concurrent
branches, it has a subscript to represent each branch.
VAR" is the set of ail variables used by the grammar, {xo, y0, so} are the initial
variables. is the starting node, y0" is the destination node. s0 is the number of
steps (arcs) between the nodes. During the execution of the algorithm. V represents
the current node, y" represents the destination node, and s is the remaining
number of steps to the destination.
FN" is the set of all functions employed by the grammar. Each function is explained
separately.
Function T simply decrements the number of steps remaining.
Function next" determines the next possible moves by calculating the intersection
of STr, STk, and SUM". Elements of this set are returned by assigning a value to
i". For example, next,1 returns the first element of the intersection set and next2
returns the second element, and so forth. ST,0 is the set of all nodes connected by
an arc to the current node. STk is the set of all nodes k arcs (steps) away from the
start node. SUM" is the set of all nodes guaranteed to be on an optimal path. SUM
is populated with all nodes that have a cost from the starting node plus the cost from
17
the destination node equal to the cost of getting from the start node to the
destination node.
X is the set of all nodes in the graph.
Function map" returns the minimum cost of traversing the graph between two
nodes. This function is discussed more in the Algorithm Implementation section.
Function "step" returns the minimum number of arcs (steps) required to traverse the
graph between two nodes.
The proof that the Language of Trajectories computes all possible optimal paths
between two points was completed by Dr. Stilman in his research (Stilman, 1993). The only
changes I performed to this grammar where simplifications with the extraction of the concept
of pieces with different behaviors, changes to STk to support a graph, and a shift in the
notation toward my problem domain. Therefore, Dr. Stilmans proof that the grammar
produces all optimal paths still holds true and will not be repeated here. Whereas, I made
significant changes to the map function as part of implementing the algorithm ana. thus,
need to prove that it still contributes to the production of optimal routes.
5.2 Algorithm Implementation
The Language of Trajectories algorithm focuses on a grid (raster) based system and
needs to be augmented to operate on a vector (network topology) system. This derivation,
the Language of Trajectories Adaptation (LTA), is encapsulated in the calculation of "map",
ST*, and STi. Another significant deviation is limiting the search space to a subset of the
network without losing the ability to generate optimal routes.
What is not intuitively obvious from the formal representation of LTA is how the
computational cost is distributed. The algorithm, as defined by the grammar, looks
computationally inexpensive. In fact, after the costs required by the "map" function are
derived, the computational cost is negligible. The significant computational cost of this
approach is completely within the calculation of map", or more specifically, in deriving the
costs from the start and destination nodes for each relevant node in the search space.
Therefore, the greatest computational savings are to be gained by optimizing the calculation
of map.
As identified in the Description of Prototype section, the Grammar object
encapsulates LTA's implementation. The graph is encapsulated in the Map, Node, and Arc
objects. Critical statistics required for SUM and STk are maintained in the Node objects.
The algorithm first generates the costs required for the "map function. It requires
two passes to calculate the "map" function. The first pass calculates the cost from the
starting node while the second pass calculates the cost from the destination node. Costs are
only calculated for relevant nodes as defined later in the pruning discussion. Both passes
are blind breadthfirst ordered searches to keep it fast and simple. As part of the first pass,
STk" is calculated as well. At the completion of the second pass, SUM has been
calculated, since the SUM" value for a given node is simply the smallest cost from the start
node added to the smallest cost from the destination node.
18
Throughout the calculations, each Node object maintains the statistics for SUM and
STk". The node knows what its cost from the start and destination nodes are, what its SUM*
value is: and how many steps it is from the start node.
A key data structure embedded in the grammar object is the Search Queue. It
maintains the list of nodes to be evaluated. This represents the paths still being expanded. A
significant cost savings for this approach is the minimal overhead required to represent
paths as only the last node found and its predecessor for the path. To maintain a breadth
first search, nodes are added to the tail of the queue while the next node to evaluate is taken
from the front of the queue. Pruning, when called out, is simply not adding the next node for
a path to the Search Queue. Therefore, in the following discussion, when pruning a path, the
to" node is simply not added to the Search Queue causing the evaluation of the path to be
terminated.
Pruning, during the first two passes, can only occur by taking advantage of
calculating ST/ and SUM information during the map generation. The precalculation, of
the required information for these two sets, allows insight into which nodes and arcs have
the potential for being in an optimal path. The pruning of a path is performed for two
reasons:
1. The path is more costly than an already calculated path to the to node, or
2. The SUM for the to node" is greater than the SUM for the destination node.
The third pass, the application of the grammar, searches the problem space for an
optimal path by applying the intersection of SUM, STk, and ST/. Two of the sets. SUM"
and ST/ are calculated in the first two passes and one set, ST/ is implicit in the network
topology. The prototype, currently, only expands one optimal path out of the set of all optimal
paths. For this problem domain, only one optimal path is required.
5.2.1 Redundant Path Pruning
The first prune, the Redundant Path prune,
removes the longer redundant paths throughout the
network from the search space. It has the desirable
characteristic of pruning from the very beginning of
computation. Figure 5.2 highlights how the prune
affects the network. Nodes are labeled with lower
case letters. For this example, there are four nodes
{a. b, c, d}. The start and destination nodes are
identified by a square surrounding the node. Each
arc is labeled with its cost. For this example, all
arcs have a uniform cost of one. A pruned path is
indicated with a slash mark across it. In the
following discussion, arcs are identified by the
nodes they connect. For example, the arc
connecting nodes a" and b is identified as arc
ab".
Assuming the first pass (calculate the cost
from the start node) and a breadthfirst search, the
prune works as follows. Node a is the start node
Before Pruning
After Pruning
Figure 5.2, Redundant Path Pruning
19
and node c" is the destination node. Node a is set as the current node and assigned a cost
of 0. Arc ab is traversed and node b is assigned a cost of 1. Arc ad is next traversed and
node d is assigned a cost of 1. Node ab" is now the current node. Arc be is now traversed
and node c is assigned a cost of 2. Arc bd" is traversed and an attempt is made to update
node d with a cost of 2. Node d is already assigned a cost of 1 and, therefore, already
has a shorter path to it. Therefore the path represented by arc bd" is redundant and pruned
from the search space. Node d is now the current node. Arc bd is traversed and an
attempt is made to update node b with a cost of 2. Node b is already assigned a cost of 1
and, therefore, already has a shorter path to it. Therefore, the path represented by arc 'bd" is
redundant and pruned from the search space. The first pass is complete. It is obvious that
the paths pruned were redundant and more costly and, therefore, had no meaningful
participation in the search. This example proves that performing the Redundant Path prune
does not hinder the production of optimal paths while reducing the search space.
5.2.2 Partial SUM Pruning
The second prune, the partial SUM prune,
removes nodes from the search space with a path to
them greater in cost than the current leastcost path to
the destination node. It has the negative characteristic
of not starting to prune until the first path to the stop
node has been found. But, once started, it is quite
aggressive. Figure 5.3 highlights how the prune
affects the network. Nodes are labeled with lower
case letters. For this example, there are nine nodes
{a, b, .... i}. The start and destination nodes are
identified by a square surrounding the node. Each arc
is labeled with its cost. For this example, all arcs have
a uniform cost of one. In the following discussion, arcs
are identified by the nodes they connect. For example,
the arc connecting nodes a and b is identified as
arc ab". A pruned path is indicated witn a slash mark
across the last arc traversed. Nodes that are no
longer part of the search space, based on Partial SUM
pruning, are highlighted by being circled.
Assuming the first pass (calculating the cost
from the start node) and a breadthfirst search, the
prune works as follows. Node a" is the start node and
node c is the destination node. Node a is set as the
current node and assigned a cost of 0. Arc ab" is
traversed and node b is assigned a cost of 1. Arc
ad" is next traversed and node d is assigned a cost of 1. Node b is now the current node.
Arc be is now traversed and node c is assigned a cost of 2. We now have a preliminary
SUM for the destination node. All optimal paths are guaranteed to have a cost less than or
equal to the destination node's SUM value. The SUM value is preliminary since we have
not yet determined if there are any less costly paths to the destination node. Arc be is
traversed and the cost assigned to node e" is 2. Node d" is now the current node. Arc de
is traversed and node e is assigned a cost of 2. Arc dg is next traversed and node g is
20
assigned a cost of 2. Node c is the destination node and is no longer evaluated. Node e
is now the current node. Arc ef is now traversed and the cost to node T is 3 which is
greater than the current destination SUM value. Therefore, path ef is pruned, node T will
be evaluated no further. Arc eh is traversed and the cost to node h" is 3 which is greater
than the current destination SUM value. Therefore, path eh is pruned, node h will be
evaluated no further. Node g is now the current node. Arc gh is now traversed and the
cost to node h is 3 which is greater than the current destination SUM value. Therefore,
path gh is pruned, node IT will be evaluated no further. We are now done, there are no
other paths to evaluate. The circled nodes indicate all of the nodes removed from the search
space by the partial SUM pruning without detracting from the production of optimal paths.
The proof of this rests in the principles of the Language of Trajectories. The SUM
set contains the nodes in all optimal paths. Membership in the SUM set is determined by
each node having the same SUM value as the destination node. The SUM value for a
node is the cost from the start node plus the cost from the destination node for that node.
Therefore, it follows that if a node is not the destination node and it has a SUM' value
greater than the destination s SUM" value, it cannot possibly be in an optimal path.
It also follows that a preliminary calculation of the SUM value for the destination
node is greater than or equal to its final SUM" value. Since an optimal path to the
destination is guaranteed to be less than or equal to the cost of any path to that destination.
With this, any node with a SUM value greater than the destination node's preliminary
SUM value cannot be part of an optimal path to that destination node and can be removed
from the search space.
5.2.3 Nearoptimal Pruning
A third level of pruning can be applied to
artificially bound the search space, as shown in
Figure 5.4 by the rectangle. When this level of
pruning is enabled, the algorithm produces near
optimal routes, since it is artificially bounding the
search space. The pruning is performed by
testing for inclusion in an arbitrary bounding
rectangle. Since this prune arbitrarily dismisses
potential routes, ail solutions must be considered
nearoptimal. The prototype runs with or without
the artificial bounding to study the performance
characteristics of both optimal and nearoptimal
solutions.
5.3 Algorithm Walk Through
Figure 5.5 depicts the graph used in the walk through example. Nodes are labeled
with lower case letters. For this example, there are Fifteen nodes {a, b, ..., o}. The start and
destination nodes are identified by a square surrounding the node. Each arc is labeled with
its cost. For this example, all arcs have a uniform cost of one, except for one arc, it has a
cost of three. In the following discussion, arcs are identified by the nodes they connect. For
example, the arc connecting nodes a and b is identified as arc ab".
Figure 5.4, Nearoptimal Pruning
21
Pass 1, which computes the cost from the
start node to all valid nodes in the search space is as
follows. Each step is summarized in an enumeration.
The current (from) node is specified first followed by a
colon. The arc being traversed follows with an arrow
pointing to the connected (to) node. The statistics and
any pruning follow the comma. The results of first pass
are summarized following all of the steps.
1. a is the start node, costfromstart = 0, steps
ffomstart = 0
2. a": af > T, costfromstart = 3, stepsfromstart
= 1, f is added to Search Queue
3. a: ab > b, costfromstart = 1, stepsfrom
start = 1. b" is added to Search Queue
4 T: fi > T, costfromstart = 4, stepsfromstart =
2, i is the destination node, i has SUM" of 4, i
is not added to Search Queue since it is
destination
5 ep > e, costfromstart = 4. stepsfromstart
= 2, e is added to Search Queue
6. T: af > "a", back to predecessor, pruned
7. b: be > c, costfromstart = 2, stepsfromstart = 2, c is added to Search Queue
8. b": be" > e; costfromstart = 2, stepsfromstart = 2, e is added to Search Queue
9. b": bd > d", costfromstart = 2, stepsfromstart = 2, d" is added to Search Queue
10. b: ab" > a", back to predecessor, pruned
11. e": ef > P, back to predecessor, pruned
12. e: ei > T, costfromstart = 3, stepsfromstart = 3, "i" is the destination node. i has
SUM of 3, T is not added to Search Queue since it is destination
13. e: eh > h, costfromstart = 3, stepsfromstart = 3, h is added to Search Queue
14. e": de" > d", costfromstart = 3, d already has a costfromstart = 2. Redundant Path
prune applied
15. e": be > b, costfromstart = 3; b already has a costfromstart = 2, Redundant Path
prune applied
16. e: ce > c, costfromstart = 3, b already has a costfromstart = 2, Redundant Path
prune applied
17. c: ce > e, costfromstart = 3, e already has a costfromstart = 2, Redundant Path
prune applied
18. c: be > b", back to predecessor, pruned
22
19. "e": ef > T, costfromstart = 3; f already has a costfromstart = 3, Redundant Path
prune applied
20. e": ei > i, costfromstart = 3, T already has a costfromstart = 3, Redundant Path
prune applied
21. e: "eh" > h", costfromstart = 3, h" already has a costfromstart = 3, Redundant Path
prune applied
22. e": de" > d, costfromstart = 3, "d already has a costfromstart = 2. Redundant Path
prune applied
23. e: "be" > "b", back to predecessor, pruned
24. e: ce" > "c, costfromstart = 3, c already has a costfromstart = 2, Redundant Path
prune applied
25. d": de" > e", costfromstart = 3, e already has a costfromstart = 2, Redundant Path
prune applied
26. d": dg" > "g", costfromstart = 3, stepsfromstart = 3. g is added to Search Queue
27. d: bd > b\ back to predecessor, pruned
28. h hi > i", costfromstart = 4, destination SUM = 3, Partial SUM prune applied
29. h": hk > k", costfromstart = 4, destination "SUM = 3, Partial SUM prune applied
30. h": gh" > g", costfromstart = 4. g already has a costfromstart = 3. Redundant Path
prune applied
31. h: eh" > e", back to predecessor, pruned
32. g": gh" > h, costfromstart = 4, h" already has a costfromstart = 3, Redundant Path
prune applied
33. g: gj > j", costfromstart = 4, destination SUM = 3, Partial SUM prune applied
34. g": dg" > "d, back to predecessor, pruned
A summary of the statistics gathered during Pass 1 are found in Table 5.1. The two
required statistics gathered are displayed in columns for each node in the graph. If a graph
was pruned from the search space, a question mark was left as an indicator that no statistics
were gathered for that node. Table 5.2 depicts all of its entries during pass 1 in the order
they were appended to the end of the queue. If there was no predecessor node for an entry,
the column was left blank.
23
Table 5.1, Pass 1 Results
Node Cost(start) Steps(start)
a 0 0
b 1 1
c 2 2
d 2 2
e 2 2
f 3 1
9 3 3
h 3 3
i 3 3
i 4 4
k 4 4
1 9 ?
m 9 ?
n ? ?
o 9 ?
Table 5.2, Pass 1 Search
Queue
Predecessor Node
a
a f
a b
f e
b c
b e
b d
e h
d 3
Pass 2, which computes the cost from the destination node to all valid nodes in the
search space is as follows. Each step is summarized in an enumeration. The current (from)
node is specified first followed by a colon. The arc being traversed follows with an arrow
pointing to the connected (to) node. The statistics and any pruning follow the comma. The
results of second pass are summarized following all of the steps.
1. i": il > I, costfromdestination = 1, T has an unknown costfromstart, which is a
large number guaranteed to be larger than any cost, therefore i has a SUM greater
than the destination SUM of 3, Partial SUM prune applied
2. i: hi > h, costfromdestination = 1, costfromstart = 3, SUM = 4, destination
SUM" = 3. Partial SUM prune applied
3. i": ei > e", costfromdestination = 1. costfromstart = 2. SUM = 3, e is added to
Search Queue
4. i": fi > f, costfromdestination = 1, costfromstart = 3, SUM = 4. destination SUM"
= 3, Partial SUM prune applied
5. e: ef > T, costfromdestination = 2, f already has a costfromdestination =
Redundant Path prune applied
6. e: ei" > i", back to predecessor, pruned
7. e": eh > h, costfromdestination = 2, hn already has a costfromdestination = 1.
Redundant Path prune applied
8. e": de" > d, costfromdestination = 2, costfromstart = 2, SUM = 4, destination
SUM" = 3, Partial SUM prune applied
9. e": be > b, costfromdestination = 2. costfromstart = 1, SUM = 3, destination
SUM" = 3, b is added to Search Queue
24
10. e: ce" > c, costfromdestination = 2, costfromstart = 2, SUM" = 4, destination
SUM = 3. Partial SUM prune applied
11. b: be > c, costfromdestination = 3, c already has a costfromdestination = 2.
Redundant Path prune applied
12 b; be _> e* back to predecessor, pruned
13. b: bd" > d, costfromdestination = 3, d already has a costfromdestination = 2.
Redundant Path prune applied
14. b: ab > a", costfromdestination = 3, costfromstart = 0, SUM = 3, destination
SUM = 3, a is not added to Search Queue since it is the start
A summary of the statistics gathered during Pass 2 are found in Table 5.3. The three
required statistics gathered are displayed in columns for each node in the graph. If a graph
was pruned from the search space, a question mark was left as an indicator ihat no statistics
were gathered for that node. Table 5.4 depicts all of its entries for the Search Queue during
pass 2 in the order they were appended to the end of the queue. If there was no predecessor
node for an entry, the column was left blank.
Table 5.3, Pass 2 Results
Node Cost(start) Steps( start) Cost(dest.)
a 0 0 3
b 1 1 2
c 2 2 2
d 2 2 2
e 2 2 1
f 3 1 1
g 3 3 ?
h 3 3 1
i 3 3 0
J 4 4 ?
k 4 4 ?
I ? ? 1
m ? ? ?
n ? 9 ?
o ? ? ?
Table 5.4, Pass 2 Search
Queue
Predecessor Node
i
i e
e b
Pass 3, which applies the contextfree grammar, is as follows. Each enumeration
summarizes the production of the intersection set. The current (from) node is specified first,
followed by a colon. The elements of ST/, STk", and SUM are shown followed by an
arrow pointing to the intersection of the three sets.
1. (a}
2. a: ST1(a) = {T, b}, ST,(a) = (Y, b}, SUM = {a, b", e, "i"} > fb}
3. b": ST,(b) = fc, "e, d}, ST2fa") = {c, d. e}, SUM = fa, b, e\ i} > fe}
25
4. "e": ST,(e) = {T, T, h". d, c"}, ST3(a) = {g", h", i"}, SUM = {a, b, e, T} > {i"}
The results of pass 3 are as follows: a > ab" > b > be" > e > ei" > T.
There is only one optimal path between nodes a" and i.
5.4 Comparison to Language of Trajectories
The major differences between the Language of Trajectories (LT) and the Language
of Trajectories Adaptation (LTA) are summarized with the following points.
1. The LT algorithm is searches a grid where as LTA searches a graph,
2. For LTA, the number of steps from the start node to a given node is independent
from the cost of getting from the start node,
3. LTA migrated from distance as the cost to a more generic cost function,
4. LTA substantially optimizes the calculation of map, STk, & SUM, and
5. LTA generates ail optimal paths, as does LT, but without an exhaustive search.
26
6. Contrast to Dijkstras Algorithm
Dijkstra's algorithm (Dijkstra. 1959) is the current standard of comparison for single
source shortest path algorithms. This section first describes Dijkstra's algorithm then
compares the Language of Trajectories Adaptation to Dijkstras algorithm.
6.1 Dijkstras Algorithm
Dijkstra's algorithm in its unaltered form, computes the cost of the shortest path to all
vertices in the graph. It does not. however, generate the shortest path (Stacey, 1996). A
second pass is added to generate the shortest path based on residual statistics generated
by Dijkstras algorithm in the first pass (Cheng, 1986). The algorithm is as follows:
Inputs to the algorithm:
connected, nondirected weighted graph
all weights are positive
start vertex is a and destination vertex is z
Output from each pass:
Pass 1: L(z), the length of a shortest path from a to z
Pass 2: P, where P is the set of vertices in the shortest path.
Pseudocode for Dijkstra's algorithm:
rPass 1 7
T is the set of all vertices in the graph
L(a) = 0
for each vertex x in T where x != a
L(x) = INFINITY
while T is not empty
choose v in T with minimum L(v)
T = T {v}
for each x in T adjacent to v
L(x) = min (L(x), L(v) + w (v, x))
r Pass 2 7
P = 0
V = z
while v != a
P = {v} + P
v = vertex with smallest L value adjacent to v
P = {a} + P
Pass 1 first initializes the length (L) for all vertices. The L for the start vertex is set to
zero, all other vertices have L set to infinity. Pass 1 next loops through all vertices in the
graph, selecting one at a time, the one with the smallest L value. The vertex v is removed
from the set of vertices in the graph. The L value for all adjacent vertices, still in the set T, is
updated if the new cost to get to the vertex is less than the old cost. In this case, w(vi, v2) is
27
the cost of traversing between two adjacent vertices. When pass 1 is complete, the cost of
the shortest path to all vertices in the graph from vertex a has been computed and is
represented in L.
Pass 2 simply starts at the destination vertex z and walks the graph choosing the
adjacent vertex with the least cost from the source vertex. This generates a shortest,
between a and z, represented in set P.
6.2 Comparison
The fundamental difference between Dijkstra's algorithm and the Language of
Trajectories Adaptation (LTA) is that Dijkstras algorithm produces one shortest path and
LTA produces all shortest paths between two vertices. Another significant difference is that
Dijkstra's algorithm is an exhaustive search where as LTA prunes away unnecessary parts of
the graph., using the Partial SUM prune, while still producing all shortest paths. Empirical
data, from the Results section, shows that on average LTA searches less than half of the
vertices in the graph while performing ail three passes.
Dijkstra's algorithm requires two passes to compute an optimal path. Pass 1
computes the shortest paths cost from a source vertex to all vertices in the graph. Pass 2
generates the optimal path. The Language of Trajectories Adaptation (LTA) requires three
passes to compute optimal routes. Pass 1 computes the cost from the source vertex to all
vertices deemed pertinent to the solution. Pass 2 computes the cost from the destination
vertex to ail vertices deemed pertinent to the solution. Pass 3 generates the route.
Pass 1 for both algorithms are very comparable. Both algorithms are determining the
least cost to each node in the search space. LTA differentiates itself by reducing the search
space from the entire graph.
An analogy to further clarify the differences between LTA and Dijkstras algorithm is:
Dijkstras algorithm build a gradient with the source vertex being the low point. Dijkstras
algorithm searches the gradient for the path of steepest descent. LTA builds a trough
between the source and destination vertices with the SUM set. LTA searches for a path
between the two vertices while remaining at the lowest point in the trough.
LTA, even though it is a three pass algorithm, is more efficient at finding optimal
paths on a graph than Dijkstra's algorithm. Reducing the search space while still producing
optimal paths is the key separator for LTA.
28
7. Results
The prototype was executed on the street centerline database for the city of Aurora,
Colorado (see Figure 1.1). The network has over 800 street miles with 6,711 nodes and
9,050 arcs. A sample set of 10,000 randomly generated node pairs was generated and used
as the primary benchmark set. Due to a limitation in Microsoft Excel, a secondary sample set
of 4,000 node pairs was generated to produce the scatter plots. The benchmark was
executed on a Pentium Pro 200 MHz PC with 64 MB of RAM running the Windows 95
operating system. Statistics were generated for both optimal and nearoptimal route
generation. Due to a limitation with the time measurement function used to collect statistics,
elapsed time has a granularity of 1/100th of a second.
7.1 Optimal Path Generation
Table 7.1 contains a summary of the 10,000 sample benchmark results. This
benchmark only produced optimal routes. The key extraction is that the algorithm optimally
routed vehicles in an average of 0.07 seconds with a standard deviation of 0.04. No route
generation required more than 0.19 seconds. The average length of the paths generated
was 5.29 miles with a standard deviation of 2.73.
Table 7.1, Optimal Route Generation Statistics (10,000 Routes)
Average Maximum Minimum Standard Deviation
Elapsed Time (s) 0.07 0.19 0.00 0.04
Length of Path (mi) 5.29 14.63 0.04 2.73
Segments per Path 48.83 149.00 1.00 23.68
Nodes Searched 4,038.12 8.172.00 6.00 2.251.11
Elapsed time is measured from the time the Route Server receives the routing
request until the time the response is formatted for return. The elapsed time measurement
does suffer from the 1/100lh of a second tick described above. With this granularity, a
skewing of the results downward has occurred. A conservative deskewing would be to add
1/100th of a second to all the results. This would restate the results as: the elapsed time
average is 0.08 seconds with a maximum of 2/10th of a second and a minimum of 1/100th of a
second. The standard deviation would remain the same since all that is happening is 1/100th
of a second shift in the results.
Length and the number of segments per path gives insight into the complexity of
produced routes which on average were 5.29 mile long and had 49 arc in them.
The number of nodes searched ranged from 6 to 8,172 with an average of 4,038.
This is deceiving because this count includes numerous repeat visits. I had no easy way of
determining how many unique nodes where searched. But the above number is still very
useful since it gives insight into a computational cost per node.
29
Table 7.2, Optimal Route Generation Statistics (4,000 Routes)
Average Maximum Minimum Standard Deviation
Elapsed Time (s) 0.07 0.18 0.00 0.04
Length of Path (mi) 5.25 14.58 0.05 2.74
Segments per Path 48.39 147.00 1.00 23.74
Nodes Searched 3,986.08 8,143.00 9.00 2,259 48
Table 7.2 contains the summary of the 4,000 sample benchmark results. Again, this
benchmark produced only optimal routes. The key extraction is that the algorithm optimally
routed vehicles in an average of 0.07 seconds with a standard deviation of 0.04. No route
generation required more than 0.18 seconds. Again, a conservative deskewing of elapsed
time adds 1/100th of a second to the results. The average length of the paths generated were
5.25 miies with a standard deviation of 2.74. A comparison of Table 7.1 and Table 7.2 reveal
that both sample sets have similar characteristics with only minor perturbations. The average
distance for the 4,000 sample set was 4/100* of a mile shorter than the average for the
10,000 sample set. All other deviations can be attributed to the on average shorter routes.
Figure 7.1 and Figure 7.2 depict the distribution of generated routes over elapsed time for
both the 10,000 and 4,000 sample sets. Figure 7.3 and Figure 7.4 show the distribution of
generated routes over distance for both the 10,000 and 4,000 sample sets. But again, the
differences where very minor and the 4,000 sample set is very representative of the larger
set and will be used for further analysis.
Figure 7.3 and Figure 7.4 show a good normal distribution over distance. The
randomly generated node pairs did not produce an excessive clustering of trivially short or
overly long paths.
Figures 7.5. 7.6, and 7.7 are scatter plots of the 4,000 sample benchmark set. Each
isolates a statistic gathered in the above tables and plots it verses elapsed time. All show an
increase in elapsed time relevant to an increase in their value but with various degrees of
magnitude and clustering. Figure 7.5 show a definite trend with the increase in the length of
a path with an increase in the time required to generate it. But, it is not clustering very well.
So, it seems to be a loose association at best. The same assessment is true for the number
of arcs in a route. Figure 7.6 shows a trend for elapsed time to increase with the number of
arcs but it is not clustering well. Figure 7.7 on the other hand, shows a more significant trend
for elapsed time to increase with the number of nodes searched with much better clustering.
30
Elapsed Time (seconds)
Figure 7.1, Distribution Over Time of Optimal Routes Generated (10,000 Samples)
600
500
 400
c
O 300
u>
 200
tc
100
0
525
96
401
398
408
394
417
316
45
SL
308
82
259'
468
n 130
44
JL
3 4 0
o CM T
O O o o o , T *
o' o' o' o' o o o o'
Elapsed Time (seconds)
Figure 7.2, Distribution Over Time of Optimal Routes Generated (4,000 Samples)
31
800
700
O 600
f
2 500
9
c
<Â§ 400
 300
0
K 200
100
0
Figure 7.3, Distribution Over Distance of Optimal Routes Generated (10,000 Samples)
300
250
o
~ 200
2
5 150
(0
9
1 100
tc
50
0 
Figure 7.4, Distribution Over Distance of Optimal Routes Generated (4,000 Samples)
o^cscoTiouji^coooTcMco^rm
Distance (miles)
Distance (miles)
32
)
I
i
I
Elapsed Time (seconds)
Figure 7.5, Scatter Plot of Distance Over Time for Optimal Route Generation
33
Elapsed Time (seconds)
Figure 7.6, Scatter Plot of Arcs per Route Over Time for Optimal Route Generation
34
Nodes Searched
I
t
9000
8000
7000
I
l
6000
5000
4000
i
I
o
3000
2000
1000
I
0
0.05 0.1 0.15
Elapsed Time (seconds)
0.2
Figure 7.7, Scatter Plot of Nodes Searched Over Time for Optimal Route Generation
35
7.2 Nearoptimal Path Generation
All the benchmark sample sets
used for nearoptimal route generation
are the same as the sets used in the
optimal route benchmarks. The only
difference is the mode in which the
routing algorithm executes. Table 7.3
contains a summary of the 10,000
sample benchmark results. This
benchmark only produced nearoptimal
routes. The key extraction is that the
algorithm routed vehicles in an average
of 0.03 seconds with a standard
deviation of 0.02. No route generation
required more than 0.23 seconds. The
average length of the paths generated
were 5.29 miles with a standard
deviation of 2.73. Figure 7.8 shows the
distribution of the number of attempts
required to successfully generate a
route. The objective, in generating the
nearoptimal routes, was to successfully
generate a route on the first attempt
90% of the time. Figure 7.8 shows that that goal was accomplished with about a 96%
success rate. The search space was bounded by rectangle whose dimensions are relative to
the start and destination nodes. The following enumeration indicates the dimensions of the
bounding rectangle for each attempt by identifying the rectangles opposing comers. XMIN
is smallest X coordinate from either the start or destination nodes. YMIN MIN is smallest Y
coordinate from either the start or destination nodes. XMAX and YMAX are maximums from
the node pair.
1. (XMIN  2,000 ft. YMIN 2.000 ft), (XMAX + 2,000 ft, YMAX + 2,000 ft)
2. (XMIN  4,000 ft. YMIN 4,000 ft), (XMAX + 4,000 ft. YMAX + 4,000 ft)
3. (XMIN  8,000 ft. YMIN 8,000 ft), (XMAX + 8,000 ft. YMAX + 8,000 ft)
Elapsed time is measured from the time the Route Server receives the routing
request until the time the response is formatted for return. The elapsed time measurement
does suffer from the 1/100th of a second tick described above. With this granularity, a
skewing of the results downward has occurred. A conservative deskewing would be to add
Table 7.3, Nearoptimal Route Generation Statistics (10,000 Routes)
Average Maximum Minimum Standard Deviation
0.02
2.73
23.71
1,330.26
Elapsed Time (s) 0.03 0.23 0.00
Length of Path (mi) 5.29 14.63 0.04
Segments per Path 48.88 149.00 1.00
Nodes Searched 1,728.06 8,094.00 6.00
10000
9000
"Â§ 8000
2 7000
S 6000
3 5000
4000
5 3000
,Â§ 2000
1000
0
Figure 7.8, Distribution Over Number of
Attempts to Generate a Near Optimal Route
9592
345 i.
63 Â£=3
1 2 3
Number of Tries
36
1/100lh of a second to all the results. This would restate the results as: the elapsed time
average is 0.04 seconds with a maximum of 0.24 seconds and a minimum of 0.01 seconds.
The standard deviation would remain the same since all that is happening is 1/100 of a
second shift in the results.
The length and the number of segments per path gives insight into the complexity of
produced routes which on average were 5.29 mile long and had 49 arcs in them. The paths
are slightly longer than those generated optimally.
The number of nodes searched ranged from 6 to 8,094 with an average of 1,728.
This is a significant reduction from the optimal route results.
Table 7.4 contains the summary of the 4,000 sample benchmark results. Again, this
benchmark produced only nearoptimal routes. The key extraction is that the algorithm
routed vehicles in an average of 0.03 seconds with a standard deviation of 0.02. No route
generation required more than 0.19 seconds. The average length of the paths generated
were 5.25 miles with a standard deviation of 2.74. A comparison of Table 7.3 and Table 7.4
reveal that both sample sets have similar characteristics with only minor perturbations.
Figure 21 and Figure 7.10 depict the distribution of generated routes over elapsed time for
both the 10,000 and 4,000 sample sets. Figure 7.11 and Figure 7.12 show the distribution of
Table 7.4, Nearoptimal Route Generation Statistics (4,000 Routes)
Average Maximum Minimum Standard Deviation
Elapsed Time (s) 0.03 0.19 0.00 0.02
Length of Path (mi) 5.25 14.58 0.05 2.74
Segments per Path 48.39 147.00 1.00 23.73
Nodes Searched 1,698.82 7,488.00 9.00 1,331.58
generated routes over distance for both the 10,000 and 4,000 sample sets. But again, the
differences where very minor and the 4,000 sample set is very representative of the larger
set and are used for further analysis.
Figure 7.11 and Figure 7.12 show a good normal distribution over distance. The
randomly generated node pairs did not produce an excessive clustering of trivially short or
overly long paths.
Figures 7.13, 7.14, and 7.15 are scatter plots of the 4,000 sample benchmark set for
nearoptimal routes. Each isolates a statistic gathered in the above tables and plots it verses
elapsed time. All show an increase in elapsed time relevant to an increase in their value but
with various degrees of magnitude and clustering. Figure 7.13 show a definite trend with the
increase in the length of a path with an increase in the time required to generate it. But, it is
not clustering very well. So, it seems to be a loose association at best. The same
assessment is true for the number of arcs in a route. Figure 7.14 shows a trend for elapsed
time to increase with the number of arcs but it is not clustering well. Figure 7.15 on the other
hand, shows a more significant trend for elapsed time to increase with the number of nodes
searched with much better clustering.
37
4000
3500
a 3000
V
I 2500
e
5 2000
1 1500
3
a 1000
500
o
o CM (0 co T* CM CO CO CM CM
o o o o o T" X o CM
o' o' o o o' o o' o O
Elapsed Time (seconds)
3 53 12
21 34 12
urn
 1012
12 447502
1 74 21 10 4 0 4 1 0 1 0 0 0 0 21 IjUj.nu., i
Figure 7.9, Distribution Over Time of Nearoptimal Routes Generated (10,000 Samples)
1600
1400
1200
o
2 1000
a
c
$ 800
(A
 600
o
OS
400
200
0
Figure 7.10, Distribution Over Time of Nearoptimal Routes Generated (4,000 Samples)
r 15
10 56
369
175 199
7 n 75 52 n 1 4 0 1 0 1 1 2 0 1 J L . J.3 Q; n,i ... : = i :
o CM CO 00 r CM CO CO
O O o O o . T
O o' o' o O o o o'
Elapsed Time (seconds)
38
Distance (miles)
Figure 7.11, Distribution Over Distance of Nearoptimal Routes (10,000 Samples)
Distance (miles)
Figure 7.12, Distribution Over Distance of Nearoptimal Routes (4,000 Samples)
39
I
j
j
i
01
o
u
c
3
Elapsed Time (seconds)
Figure 7.13, Scatter Plot of Distance Over Time for Nearoptimal Route Generation
40
Arcs in Route
Elapsed Time (seconds)
Figure 7.14, Scatter Plot of Arcs per Route Over Time for Nearoptimal Route
Generation
41
Nodes Searched
Elapsed Time (seconds)
Figure 7.15, Scatter Plot of Nodes Searched Over Time for Nearoptimal Routes
42
7.3 Analysis of Results and Conclusions
The average and standard deviation for the time required to generate an optimal
route support that a route is generated in under 0.16 seconds for 95% of the routes
generated. This includes deskewing for the 1/100m of a second timer tick. The 0.16 seconds
is well under the required 0.5 seconds to route a vehicle.
The average route length of 5.3 miles is also a worst case length for emergency
vehicle routing. Typically, emergency vehicles are not routed across an entire city.
The statistics gathered for both optimal and nearoptimal route generation indicate
that the amount of time required to generate a route is directly correlated to the number of
nodes searched during the process. The scatter plots for elapsed time verses the number of
nodes searched clusters quite well, where as, other scatter plots show less clustering. It is
also obvious that a ceiling was encountered relative to the Aurora data set. A larger network
would be useful to better predict how the network wiil scale to any street network.
Intuitively, the use of a breadthfirst search should scale poorly to tremendously
large networks. This is mainly due to the fact that the Partial SUM prune does not participate
until a path is found between the start and destination nodes. The nearoptimal route
generation, with its artificial bounding of the search space, should scale much better to the
larger networks. Clearly, more data needs to be collected in this area. But, for the problem
domain to which this research was aimed, the Aurora network is very representative and the
results of this research are useful.
The preliminary conclusion is that the application of the LTA algorithm to the E911
problem domain is quite feasible and useful. The amount of time required to generate an
optimal route was far less than anticipated and surprisingly stable. The predictability of the
algorithm lends itself to applications where human life depends on rapid predictable
response. The results are preliminary because statistics have been gathered on only one
sample, the City of Aurora, Colorado. But, further sample networks need to be analyzed to
draw further conclusions.
43
REFERENCES
Borland, (1993), Borland C++ Programmer's Guide Version 4.0, Borland International, Inc.,
Scotts Valley, CA, Chap. 9, 265270.
Cheng, P (1986), The Pixel Planner for the Autonomous Vehicle Test Bed (AVTB), Central
Engineering Laboratories, FMC Corp., Sunnyvale, CA.
Census Bureau, (1993), TIGERAJne Files 1992 Technical Documentation, United States.
Department of Commerce, Bureau of the Census. Washington, D. C.
Dijkstra, E., (1959), A Note on Two Problems in Connexion with Graphs, Numerishe
Mathematik 1, 269271.
ESRI, (1992), Understanding GIS The ARC/INFO Method Revision 6, Environmental
Systems Research Institute, Inc., Redlands, CA, Chap. 2,131.
ESRI, (1996), Advanced topic: the pathfinding algorithm, ARC/INFO Online Help,
Environmental Systems Research Institute. Inc., Redlands, CA.
Stacey, D., (1996), Graph Theory (part 4), World Wide Web Page,
httpJ/hebb. cis. uoguelph. ca/~deb/27190/graph4. html.
Stilman, B., (1993), A Linguistic Approach to Geometric Reasoning. International Journal of
Computers and Mathematics with Applications, Vol. 26 No. 7, 2957.
Stilman, B., (1996), Linguistic Geometric, World Wide Web Page,
http://www. cudenver. edu/~bsti Iman/boris. html.
[
I
44
