Representation, organization, and use of topographic models of physical spaces for route planning

Abstract

ROUTER 1 is a new route-planning system. The focus is on knowledge and its processing-more specifically, on the representation and organization of topographic models of physical Spaces and their use for route planning. The route-planning task is decomposed into the subtasks of direction-finding and route-finding. In direction-finding, ROUTER 1 finds the neighborhoods of the initial and goal locations and the direction of the goal location relative to the initial location. In route-finding, ROUTER 1 uses knowledge of the relative direction as a heuristic for selecting pathways. It first selects a high-level pathway from the neighborhood of the initial location to the neighborhood of the goal location, and, then, progressively adds more details to the growing route until a complete legal route is synthesized. This organizational scheme and reasoning method enables ROUTER 1 to solve nontrivial route-planning tasks efficiently and effectively.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>