Navigation is one of the main applications in location based systems. In order to navigate to a destination, a shortest path analysis has to be calculated. Shortest path analyses are commonly based on vector maps and calculate the shortest path (or route) between two points in a network. Fundamental research has been done in shortest path analysis for vehicle navigation in street networks, but the algorithms for vehicle navigation are only of limited use for pedestrian navigation. In this paper, an approach based on raster maps is described that calculates shortest paths for pedestrians. It will be shown that the algorithm can be extended very easily in order to support various kinds of applications.

Artikelauszug / Extract:

1. Introduction
Vehicle navigation systems have become a high market penetration. Especially mobile vehicle navigation systems, based on Personal Digital Assistants (PDA), are getting more and more popular. The typical data bases of these systems are vector data, which are acquired in the Geographic Data Files (GDF) format [ISO 2002]. The price of such systems, including PDA, Software, GPS and street data, starts in the range of about $300. Vehicle navigation on street network data is a robust process and the software has become very user-friendly. However, the navigation with such systems has only limited use for pedestrian navigation. There are two main reasons that existing navigation systems are not suitable for pedestrian navigation. First, the movement behavior of pedestrians can only be inadequately described with vector maps, because unlike cars, pedestrians are not moving along the middle axis of street lanes, but typically use the shortest distance between their actual position and the next visible target of their path, especially when crossing places or in indoor areas.