Using connectivity graphs to support map-related reasoning

Sammanfattning: This thesis describes how connectivity graphs can be used to support automated as well as human reasoning about certain map-related problems. Here, the term "map" intends to denote the representation of any two-dimensional, planar surface which can be partitioned into regions of free vs. obstructed space. This thesis presents two methods for solving shortest path problems within such maps. One approach involves the use of heuristic rules of inference, while the other is purely algorithmic. Both approaches employ A' search over a connectivity graph -- a graph abstracted from the map’s 2-D surface information. This work also describes how the algorithmic framework has been extended in order to supply users with graphical replies to two other map- related queries, namely visibility and localization. The technique described to solve these latter two queries is unusual in that the graphical responses provided by this system are obtained through a process of synthetic construction. This thesis finally offers outlines of proofs regarding the computational complexity of all algorithmic methods employed.