Authors: Ariel Felner, Roni Stern, Asaph Ben-Yair, Sarit Kraus, and Nathan Netanyahu
Abstract
We address the problem of finding the shortest path between two points in an unknown real physical environment, where a traveling agent must move around in the environment to explore unknown territory. We introduce the Physical-A algorithm (PHA) for solving this problem. PHA expands all the mandatory nodes that A would expand and returns the shortest path between the two points. However, due to the physical nature of the problem, the complexity of the algorithm is measured by the traveling effort of the moving agent and not by the number of generated nodes, as in standard A. PHA is presented as a two-level algorithm, such that its high level, A, chooses the next node to be expanded and its low level directs the agent to that node in order to explore it. We present a number of variations for both the high-level and low-level procedures and evaluate their performance theoretically and experimentally. We show that the travel cost of our best variation is fairly close to the optimal travel cost, assuming that the mandatory nodes of A are known in advance. We then generalize our algorithm to the multi-agent case, where a number of cooperative agents are designed to solve the problem. It should be noted that the problem addressed here is not a navigation problem, but rather a problem of finding the shortest path between two points for future usage.
Introduction
In classical pathfinding, algorithms like A* typically operate under the assumption that "expanding a node" is a computationally cheap logical operation. In these scenarios, the map is fully known, or the state space is a logical puzzle where transitions occur instantly in memory. However, real-world applications—such as autonomous robots exploring disaster zones or software agents navigating unknown networks—face a different reality.
In these "physical" environments, an agent must physically travel to a location to discover its neighbors and the costs of outgoing edges. The standard A algorithm, which prioritizes nodes based on a global heuristic, might require an agent to move back and forth across a map, leading to excessive travel costs. The Physical-A (PHA*) framework is designed to find the optimal path for future use while minimizing the total distance traveled during the exploration phase. Crucially, this is a search problem aimed at discovering the guaranteed shortest path for subsequent use, rather than a simple navigation task.
The PHA* Framework
PHA* is structured as a two-level algorithm to decouple the search logic from the physical movement:
- High-Level (Decision Maker): This level maintains the "open list" of candidate nodes, similar to standard A*. It selects the next node to expand based on the $f = g + h$ cost function.
- Low-Level (Navigator): Once a target node is selected by the high level, the low-level navigator determines the physical path the agent takes to reach that node.
Algorithmic Enhancements
To mitigate the "back-and-forth" travel inherent in applying A* to physical spaces, the authors propose two primary enhancements:
- Improved ADFS (I-ADFS): This low-level strategy allows the agent to take intelligent detours. If the agent passes near other "promising" nodes (those with low $f$-values) on its way to the primary target, it visits them opportunistically. This prevents costly return trips to those areas later in the search.
- Window A (WinA): This high-level strategy relaxes the strict requirement of always expanding the node with the absolute lowest $f$-value. Instead, it considers a "window" of the $k$ best nodes and selects the one physically closest to the agent's current position. This trade-off significantly reduces travel overhead without sacrificing the guarantee of finding the shortest path.
Multi-Agent PHA (MAPHA)
The framework extends to multi-agent systems (MAPHA*), where multiple cooperative agents work together. The authors explore two optimization goals:
- Fuel Efficiency: Minimizing the total distance traveled by all agents combined.
- Time Efficiency: Minimizing the time elapsed until the shortest path is found by allowing agents to move simultaneously.
Experimental Evaluation
The algorithms were tested on Delaunay graphs, which serve as realistic models for road networks. Three graph types were used:
- Regular: Standard Delaunay triangulations.
- Sparse: 60% of edges removed to simulate obstacles and dead ends.
- Dense: 400 random edges added to simulate high-connectivity "highways."
Experiments involved graphs with 500 to 8,000 nodes, with results averaged over 250 trials.
Key Insights and Results
The study reveals several critical aspects of physical search:
- Metric Shift: In physical environments, the number of nodes expanded is less important than the total distance traveled. An algorithm that expands more nodes but does so with less travel is more efficient.
- Navigation Performance: I-A*DFS navigation outperformed basic tree-path navigation by more than an order of magnitude in large-scale graphs.
- WinA* Benefits: Implementing WinA logic resulted in an additional 30% reduction in travel costs compared to standard A logic.
- Near-Optimality: PHA* performance was found to be within a small constant factor of the theoretical offline optimal (the Traveling Salesman Problem solution for the set of mandatory nodes).
- Multi-Agent Scaling: In time-efficient mode, the search time asymptotically approached the length of the actual shortest path as the number of agents increased. In fuel-efficient mode, adding too many agents eventually led to diminishing returns due to redundant exploration.
Conclusion
PHA* provides a robust framework for finding shortest paths in unknown physical environments. By prioritizing locality in node expansion and allowing for opportunistic exploration, it bridges the gap between logical search and physical constraints. Future work includes relaxing sensor assumptions and exploring decentralized communication models for multi-agent systems.
Summary updated