Planning routes through uncertain territory

摘要

Planning routes and executing them requires both topological and metric information. A natural implementation of a ‘cognitive map’ might therefore consist of an assertional data base for topological information and a ‘fuzzy map’ for the metric information. A fuzzy map captures facts about objects by recording their relative positions, orientations, and scales in convenient frames of reference. It is fuzzy in the sense that coordinates are specified to lie in a range rather than having fixed values. The fuzzy map allows easy retrieval of information. The same information is also represented in a discrimination tree, which allows an object to be retrieved given its location and other attributes. The problem of constructing a fuzzy map is more difficult; we present a partial solution, an algorithm that assimilates a fact first by imposing constraints on the fuzzy coordinates of the objects involved, then by rearranging or growing the tree of frames of reference. Route planning is modelled as a process of finding the overall direction and topology of the path, then filling in the details by deciding how to go around barriers. It uses the retrieval algorithms. Our program SPAM carries out all these processes.