Exploratory Digraph Navigation Using A

Fabrice Mayran de Chamisso, Laurent Soulier, Michaël AupetitIJCAI 2015

Introduction

Standard pathfinding algorithms like A* typically operate under the assumption that the environment is either fully known or that unknown regions are impassable. However, in real-world scenarios—such as a robot exploring a building for the first time—an agent often possesses a known, albeit potentially long, "safe" route while observing "boundary vertices" that might lead to more efficient shortcuts.

The authors define this challenge as Exploratory Digraph Navigation (EDN). The core problem is a decision-making trade-off: should the agent follow a guaranteed long path or risk encountering a dead end by exploring a potential shortcut? Existing solutions often fail to optimize for immediate navigational efficiency, either by underestimating costs or focusing primarily on map-building.

Conceptual diagram of Exploratory Digraph Navigation (EDN) showing the trade-off between a known safe path and an unknown shortcut.

Methodology: The EDNA* Algorithm

To address the EDN problem, the authors propose EDNA (Exploratory Digraph Navigation with A), a generalization of the standard A algorithm. EDNA introduces several key innovations to manage the exploration-exploitation trade-off:

  1. Dual Heuristics:
    • Standard Heuristic ($\mathcal{H}$): An admissible estimate of the distance from a vertex to the goal.
  2. Shortcut Risk Heuristic ($\mathcal{R}$): An estimate of the cost associated with a shortcut at a boundary vertex, incorporating the risk of dead ends or sub-optimal paths.
  3. Early Stopping Criterion: Unlike A, which continues until the goal is reached, EDNA can terminate the search early if the estimated cost of a known path exceeds the "best distance" found so far, including potential exploratory shortcuts.
  4. Two-Phase Execution: The algorithm alternates between a Planning phase (computing a path to the goal or a promising boundary vertex) and a Navigation phase (physical movement and exploration of unknown edges).

Experimental Evaluation

The performance of EDNA* was evaluated using synthetic benchmarks, including random planar digraphs with approximately 9,000 vertices and "Square-Shaped Possibly-Overlapping" (SSPO) obstacles to simulate complex environments like road networks. To force exploration decisions, a fraction of edges were removed from the agent's initial map.

Visual comparison of EDNA* navigation, highlighting the discovery of a shortcut through an unexplored zone.

Key Results

  • Navigational Efficiency: EDNA achieved navigational cost reductions of 3.9% on random graphs and up to 20% on grid-like graphs compared to standard A.
  • Significant Shortcuts: In specific scenarios, the algorithm identified shortcuts up to 14 times shorter than the known safe path.
  • Computational Performance: Despite the added complexity of managing exploration risks, the computational overhead remained comparable to A. In some instances, the early stopping criterion allowed EDNA to expand fewer vertices than standard A*.

Discussion and Future Work

EDNA treats exploration as a planning variable with an associated (uncertain) cost, prioritized by the risk heuristic $\mathcal{R}$. This allows for tuning the agent's "adventurousness" through parameters like total penalty and angular penalty toward the goal. A significant advantage is knowledge reinforcement*: even failed shortcuts provide valuable map updates that improve future navigation.

However, the algorithm's performance is highly dependent on the quality of the risk heuristic. An overly optimistic heuristic can lead to "stubbornness," where the agent wastes excessive effort exploring dead ends. Future research aims to develop a "non-stubbornness criterion" to help agents decide when to abandon a shortcut and return to the safe path, as well as incorporating dynamic "energy budgets" to adjust risk tolerance based on remaining resources.

Summary updated

BibTeX
@inproceedings{chamisso2015exploratory,
  author = {Fabrice Mayran de Chamisso and Laurent Soulier and Michaël Aupetit},
  title = {{Exploratory Digraph Navigation Using A}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure