Introduction
Traditional search algorithms like A* assume deterministic environments where actions have predictable outcomes. However, real-world domains—such as robotics or scheduling—are often non-deterministic. While off-line methods can plan for contingencies, they suffer from exponential complexity. Real-time search addresses this by interleaving planning and execution, but its performance in non-deterministic settings remained poorly understood until this work.
The Min-Max LRTA* Algorithm
The authors propose min-max LRTA, which adapts Korf’s LRTA to handle uncertainty by adopting a minimax perspective. The agent treats the environment as a "vicious nature" that selects the least favorable outcome for any given action.
The algorithm follows these core rules:
- Action Selection: The agent chooses the action $a$ that minimizes the maximum estimated distance to the goal among all possible successor states $s' \in succ(s, a)$.
- Value Update: Upon selecting an action, the agent updates the heuristic value of the current state $s$ to $V(s) = 1 + \max_{s' \in succ(s,a)} V(s')$. This learning rule ensures the agent accounts for the worst-case outcomes it encounters.
Complexity Analysis
A key contribution of this paper is the derivation of tight complexity bounds. The authors prove that in "safely explorable" domains—where a goal is reachable from any state the agent can reach—a zero-initialized min-max LRTA* agent will reach the goal in at most $2 \sum_{s \in S} gd(s)$ actions, where $gd(s)$ is the goal distance of state $s$.
This result highlights that the difficulty of a search problem for LRTA is determined by the average goal distance* across all states, rather than just the total number of states. The worst-case complexity is $O(n^2)$, where $n$ is the number of states. Interestingly, this bound is identical for both deterministic and non-deterministic domains, suggesting that non-determinism does not necessarily increase the worst-case search effort for this class of algorithms. Additionally, the authors show that "identity actions"—moves that might leave the agent in the same state—can at most double the search complexity.
Experimental Evaluation
The algorithm was evaluated on several domains, including synthetic graphs and the 8-puzzle. A particularly illustrative application is Moving Target Search, where a hunter must capture a prey.
In this scenario, the prey's moves are treated as the non-deterministic component of the environment. The minimax approach guarantees that the hunter will eventually capture the prey, provided the domain allows for it.
Conclusion
Min-max LRTA* provides a robust framework for real-time search under uncertainty. While the minimax assumption is pessimistic, it offers strong theoretical guarantees. Future work includes exploring deeper lookahead strategies and integrating probabilistic outcome models to reduce the inherent pessimism of the minimax approach.
Summary updated