Terrain Navigation Through Knowledge-based Route Planning

John F. Gilmore, Antonio C. Semeco

Introduction

In the mid-1980s, autonomous ground vehicle (AGV) navigation faced a significant scale discrepancy. High-level planners could navigate global maps to avoid large geographic features like mountains but remained blind to local obstacles such as rocks or trees. Conversely, local reactive systems could avoid immediate hazards but lacked the context of a broader mission or destination.

The TREK (Tech Route Execution Kaleidoscope) system was developed to bridge this gap. It provides a unified architecture that integrates global pathfinding, local sensor-based navigation, and high-level knowledge-based reasoning to allow a vehicle to navigate complex environments while adhering to tactical mission goals.

The TREK Architecture

The TREK system processes navigation through four distinct phases, moving from geometric point generation to symbolic validation.

To construct a navigable path, the system identifies three types of critical points:

  • Two-sweep points: A heuristic approach where the system scans forward and "walks" around obstacle contours, mimicking human navigation.
  • Convex terrain points: Geometric vertices of obstacles used to define a navigation polygon.
  • Crossover exposure points: Tactical points representing areas of high visibility or traffic.

These points are connected into a graph, and the A* algorithm is employed to find the optimal path. The search uses a weighted cost function that balances distance, terrain difficulty, known threats, and mission constraints: $F(c) = (Distance \cdot W1) + (Terrain \cdot W2) + (Threats \cdot W3) + (Constraints \cdot W4)$.

2. Scene Matching

To maintain global positioning, TREK performs "image-to-image" mapping. It utilizes a perspective-invariant graph matching technique to align local sensor observations with a global altitude map, ensuring the vehicle remains localized even when terrain features appear differently from a ground-level perspective.

3. Knowledge-Based Validation

Built in LISP on a Symbolics 3600 machine, the expert system is the "brain" of TREK. It uses symbolic reasoning to validate paths against three rule sets:

  • Scene Rules: Identifying objects based on context (e.g., a moving object on a road is classified as a vehicle).
  • Mission Rules: Prioritizing high-level objectives such as patrolling specific zones versus engaging intruders.
  • Survivability Rules: Calculating risk-reward trade-offs, such as whether a detour to avoid a threat is worth the mission delay.
Example of prioritized mission goals within the TREK expert system.

Evaluation and Key Insights

Because standardized benchmarks for autonomous navigation did not exist in 1984, the TREK system was evaluated using high-resolution digitized terrain maps (12.5m to 100m resolution) and video imagery. The system was tested against simulated military and search-and-rescue scenarios.

A core insight of the TREK project was the shift from treating navigation as a purely geometric problem to treating it as a symbolic reasoning problem. By using "if-then" logic, the vehicle could hypothesize about its environment. For example, the "Two-Sweep" heuristic simplified complex calculus into a manageable scanning method that prioritized practical movement over mathematical perfection.

Multi-Level Integration

The system successfully demonstrated that an unbiased route graph could be generated by merging defensive paths (obstacle avoidance) with offensive tactical options. The local-to-global matching algorithm proved robust against terrain permutations and sensor obscurations, a significant precursor to modern feature-based registration.

Conclusion and Future Work

While TREK represented a leap forward in integrated navigation, it faced limitations in sensor modality and temporal reasoning. The original tests relied heavily on video imagery, with the authors noting that infrared (IR) integration would be necessary for all-weather operations. Furthermore, the mission rules were relatively static, requiring more sophisticated temporal reasoning to handle dynamic, moving threats over long durations. Subsequent research aimed to port the TREK architecture onto physical mobile robot prototypes for real-world material handling and field tests.

Summary updated

BibTeX
@inproceedings{gilmore1985terrain,
  author = {John F. Gilmore and Antonio C. Semeco},
  title = {{Terrain Navigation Through Knowledge-based Route Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1985},
}
Figure