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
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.
GPS-Route is being developed by
Stefan Edlekamp and
and by PG 452.
Thanks to Thomas Willhalm for code that improve shortest path
queries on geometric domains