Planning routes through uncertain territory

Drew McDermott, Ernest Davis

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)107-156
Number of pages50
JournalArtificial Intelligence
Volume22
Issue number2
DOIs
StatePublished - Mar 1984

ASJC Scopus subject areas

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Planning routes through uncertain territory'. Together they form a unique fingerprint.

Cite this