|
Project Group Application
Dagstuhl-Seminar
Intermediate Report
Final Report
PDA-Group
Route-Planning Group
Map-Generation Group
Simulation Group
Publications
|
GPS-ROUTE:
A Domain-Independent Trajectory Planner
Route planning is one of the most important application areas of
computer science in general and graph search in particular. Current
technology like hand-held computers, car navigation and GPS
positioning systems ask for a suitable combination of mobile computing
and course selection for moving objects, but
- most maps come on external storage devices and are by far larger
than main memory capacity. This is especially true for on-board and
hand-held computer systems.
- most available digital maps are expensive, since exhibiting and
processing road information e.g. by surveying methods or by
digitizing satellite images is very costly.
- maps are likely to be inaccurate and to contain systematic
errors in the input sources or inference procedures.
- it is costly to keep map information up-to-date, since road
geometry continuously changes over time.
- maps only contain information on road classes and travel
distances, which is often not sufficient to infer travel time. In
rush hours or on bank holidays, the time needed for driving deviates
significantly from the one assuming usual travel speed.
- in some regions of the world digital maps are not available at
all.
Therefore, we develop a domain-independent route planning system
that takes a set of traces as an input precomputes an according
graph structure and quickly answers different on-line queries.
|
|