Using Connectivity Graphs for Path Planning in Digitized Maps

摘要

The paper describes the results of a first phase of research involving spatial reasoning within digitized maps. The work focusses upon techniques for 2-D route planning in the presence of obstacles. Two alternative approaches to route planning are discussed here: one heuristic and knowledge-based, one algorithmic. Both systems employ A* search over a connectivity graph -- a graph generated by abstracting the original map information. The type of output produced by each system is quite different. The algorithmic system produces a simple list of coordinate positions, while the heuristic system generates a symbolic description of the planned route. The heuristic system achieves this capability through the use of inference rules which can analyze and classify spatial relationships within the connectivity graph. In other words, the connectivity graph acts as a knowledge structure upon which spatial reasoning may be performed. The paper also describes extensions of this methodology which exploit a hierarchical data structure; here, the hierarchy reflects different levels of map resolution.