Qualitative Landmark-based Path Planning and Following

Tod S. Levitt, Daryl T. Lawton, David M. Chelberg, Philip C. NelsonAAAI 1987

Abstract

This paper presents a robust framework for robotic navigation that prioritizes qualitative visual landmarks over precise metric measurements. By representing the environment as a network of "viewframes" and "orientation regions," the authors enable autonomous agents to plan paths, correct errors, and discover opportunistic shortcuts without the need for absolute coordinate data.

Introduction

In the late 1980s, robot navigation relied heavily on brittle metric techniques like dead reckoning and triangulation, which were susceptible to cumulative sensor errors. This research proposes a "common sense" alternative inspired by biological navigation: using landmarks. The goal is to formalize a mathematical framework that allows a robot to determine its location and navigate effectively using only relative visual information.

Methodology: Qualitative Spatial Representation

The authors propose a hierarchical spatial representation based on visual events rather than coordinates:

  • Viewframes: Panoramic snapshots from a single location recording relative angles between landmarks.
  • Landmark-Pair-Boundaries (LPBs): Virtual lines connecting pairs of landmarks that divide the world into distinct regions.
  • Orientation Regions: Topological "cells" created by the intersection of multiple LPBs, providing a coordinate-free map.
Geometric representation of Landmark-Pair-Boundaries (LPBs) and orientation regions.

By identifying which side of an LPB it occupies, a robot can localize itself without range estimates. Paths are defined as sequences of visual events, such as crossing specific LPBs.

Experimental Evaluation

The theory was evaluated using simulated landmark data based on the Martin Marietta Autonomous Land Vehicle (ALV) site and 30-meter U.S. Army ETL terrain grid data.

Comparison of real-world path and simulated terrain grid used for evaluation.

Synthetic viewframes were generated by placing virtual sensors within these simulated environments to test landmark recognition and the calculation of orientation regions.

Key Insights and Results

A core strength of this approach is the "shortcut" phenomenon. Because paths are stored as landmark sequences, a robot can recognize a destination landmark from a distance even if it is on a different path, allowing for immediate, opportunistic route optimization.

Results using an A* search algorithm over the visual memory graph showed that qualitative routes were significantly smoother than metric plans. The system demonstrated the ability to perform "dramatic replanning" at runtime, successfully calculating direct shortcuts when goal-related landmarks were observed mid-route.

Conclusion

The qualitative landmark-based approach offers a robust alternative to error-prone metric navigation. However, it relies on the significant assumption of reliable landmark recognition—a major computer vision challenge at the time of publication. Future research will focus on integrating traversability constraints and managing the quadratic computational complexity associated with increasing landmark density.

Summary updated

BibTeX
@inproceedings{levitt1987qualitative,
  author = {Tod S. Levitt and Daryl T. Lawton and David M. Chelberg and Philip C. Nelson},
  title = {{Qualitative Landmark-based Path Planning and Following}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure