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.
1. Point Generation and Graph Search
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.
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.
Navigation as Reasoning
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