Symbolic and geometric connectivity graph methods for route planning in digitized maps

The results of research involving spatial reasoning within digitized maps are reported, focusing on techniques for 2D route planning in the presence of obstacles. Two alternative approaches to route planning are discussed, one involving heuristic symbolic processing and the other employing geometric calculations. Both techniques employ A* search over a connectivity graph. The geometric system produces a simple list of coordinate positions, whereas the symbolic system generates a symbolic description of the planned route. The symbolic system achieves this capability through the use of inference rules that can analyze and classify spatial relationships within the connectivity graph. The geometric method calculates an exact path from the connectivity information in the graph. Thus, the connectivity graph acts both as a knowledge structure on which spatial reasoning can be performed and as a data structure supporting geometrical calculations. An extension of the methodology that exploits a hierarchical data structure is described