Robot Navigation in Unknown Terrains of Convex Polygonal Obstacles Using Learned Visibility Graphs

B. John Oommen, S. Sitharama Iyengar, Nageswara S. V. Rao, Rangasami L. KashyapAAAI 1986

Abstract

This paper presents a formal framework for autonomous robot navigation and simultaneous mapping in unknown environments populated by convex polygonal obstacles. By incrementally constructing a "Learned Visibility Graph" (LVG) over successive traversals, the robot transitions from reactive, sensor-based local navigation to globally optimal path planning. The authors provide mathematical proofs for the convergence of this learning process, demonstrating that the robot eventually acquires a complete map of its environment, rendering its sensors unnecessary for future navigation between known points.

Introduction

In the mid-1980s, robot navigation research was largely divided between "find-path" problems in known environments and heuristic-based exploration for mapping. This paper addresses the gap between these two domains: how can a robot perform functional tasks—moving from a source to a destination—in an entirely unknown world while systematically improving its internal model of that world?

The proposed solution is a rigorous mathematical treatment for navigation in unknown terrains that guarantees pathfinding (if a path exists) and ensures the internal model converges to the true geometry of the environment.

The Learned Visibility Graph (LVG) Framework

The core of the proposed system is the Learned Visibility Graph (LVG). In a standard Visibility Graph (VG), edges connect all obstacle vertices that have a clear line of sight to one another. The LVG starts as an empty graph and is incrementally populated as the robot's sensors detect new vertices and edges during its travels.

The robot employs a multi-layered algorithmic approach to navigate and learn:

  1. NAVIGATE-LOCAL: When the environment is unknown, the robot uses a hill-climbing strategy. It moves directly toward the destination until it encounters an obstacle. It then uses a local optimization criterion—maximizing the projection of its movement onto the goal vector—to decide the direction for circumnavigation.
  2. BACKTRACK: To ensure robustness, a backtracking procedure allows the robot to escape "dead-ends," such as narrow corners between obstacles and terrain boundaries, by intelligently retracing its steps.
  3. NAVIGATE-GLOBAL: As the LVG grows, the robot uses a hybrid strategy. It plans optimal paths through known regions using graph-search algorithms and resorts to local, sensor-based navigation only when entering unmapped "dark" areas.
Local navigation strategies: (a) moving along an obstacle edge and (b) approaching an obstacle from free space.

Learning and Convergence

The learning component, UPDATE-VGRAPH, is triggered whenever a new vertex is reached. The robot performs a 360-degree sensor scan to identify all visible vertices, updating the LVG edges accordingly. This "on-the-job" training ensures that the robot learns while performing useful work, rather than exploring aimlessly.

The authors prove that if source and destination points are chosen randomly, the LVG will converge to the true Visibility Graph with a probability of one. Once the graph is complete, the robot can switch entirely to classical algorithms like Dijkstra’s, achieving sensor obsolescence for navigation.

A robot's path from source S to destination D through a terrain of convex polygonal obstacles.

Key Results and Performance

The theoretical framework is backed by formal proofs and simulations:

  • Guaranteed Pathfinding: NAVIGATE-LOCAL is mathematically proven to find a path in finite time if one exists.
  • Efficiency: The number of sensor operations required to learn the complete graph is bounded at $O(|V|^2)$, where $V$ is the number of obstacle vertices.
  • Simulation Success: In a primary simulation involving a rectangular terrain with multiple obstacles, the robot successfully learned 31 out of 39 total visibility edges (approximately 80% of the map) in just five random trips.

Limitations and Future Directions

While foundational, the model has several constraints:

  • Convexity: Obstacles must be convex polygons; concave obstacles would require more complex visibility logic.
  • Point Robot: The robot is treated as a single point, ignoring physical dimensions and clearance requirements.
  • Static World: The environment is assumed to be static, with no moving obstacles or dynamic changes.

Future work suggests extending these principles to non-convex obstacles, non-point robots, and relaxing the interior restrictions regarding obstacle placement relative to terrain boundaries.

Summary updated

BibTeX
@inproceedings{oommen1986robot,
  author = {B. John Oommen and S. Sitharama Iyengar and Nageswara S. V. Rao and Rangasami L. Kashyap},
  title = {{Robot Navigation in Unknown Terrains of Convex Polygonal Obstacles Using Learned Visibility Graphs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure