In classical planning, an agent knows exactly where it is. Finding a path to a goal is like navigating a well-lit map: you simply find the shortest sequence of moves from point A to point B. But in the real world, sensors are noisy, maps are incomplete, and actions have unpredictable side effects.
When an agent is unsure of its current state, it must plan in belief space. Instead of being at a single point, the agent occupies a "belief state"—a set or distribution of all possible worlds it might currently be in. This shift from points to sets creates a massive computational hurdle: the number of possible belief states is exponentially larger than the number of physical states.
The Exponential Wall of Uncertainty
The fundamental challenge, as identified by Michael R. Genesereth and Illah Reza Nourbakhsh, is that a planner must account for every potential reality simultaneously. If you aren't sure if a door is locked, your plan must work whether it is or isn't.
Early attempts like Cassandra, developed by Gregg Collins and Louise Pryor, handled this by building explicit contingency branches for every possible outcome. While this solved classic puzzles like the "keys and boxes" problem, the search tree exploded. Every unknown bit of information doubled the number of branches, making complex missions impossible to solve through brute force.
Compressing Knowledge with Symbolic Logic
To scale, researchers realized they couldn't simply list every possible world in a belief set. They needed a way to represent "what we know" compactly.
Eyal Amir and Stuart Russell introduced Logical Filtering, a symbolic method that uses logic to update an agent's knowledge. Instead of tracking a thousand possible locations, the agent tracks a single logical formula that describes its constraints. Similarly, Son Thanh To and colleagues showed that using prime implicates—a specific mathematical way of structuring knowledge—allows planners to find a "sweet spot" between memory efficiency and the speed of reasoning.
Estimating Distance in the Fog
In classical search, heuristics like "as the crow flies" distance help guide the agent. In belief space, estimating distance is much harder because you are measuring the distance from a set of states to a goal.
Jussi Rintanen pioneered methods for calculating these distance estimates in discrete belief spaces. A major breakthrough came with the State Agnostic Planning Graph (SAG) by William Cushing and Daniel Bryce. Rather than building a new reachability graph for every possible state, SAG uses boolean labels to track which goals are reachable from any state in the current belief set. This allows their planner, POND, to prune useless actions without the redundant work of traditional heuristics.
Focusing on the Reachable and the Risky
If the belief space is an infinite ocean, most of it is irrelevant to the task at hand. Modern algorithms succeed by ignoring the "useless" parts of the uncertainty.
- Sampling the Essentials: The SARSOP algorithm, developed by Hanna Kurniawati, David Hsu, and Wee Sun Lee, focuses only on the "optimally reachable" belief spaces. By sampling points that are likely to lead to the goal and aggressively pruning suboptimal paths, it solves problems with thousands of states that were previously intractable.
- Learning from Failure: In conformant planning—where you must find a plan that works without any sensors—Xiaodi Zhang and Enrico Scala developed SUPERB. This system finds "superior counter-examples"—specific initial states where a plan fails—and uses them to refine the plan until it is robust against all possible starting conditions.
- Safety Shields: When resources are tight, Michal Ajdarów and others use "shields" to pre-calculate safe boundaries. These shields act as filters, blocking any action that might lead to a belief state where the agent runs out of power or hits an obstacle.
Compilation: Leveraging Classical Success
Perhaps the most pragmatic direction is compilation. Instead of inventing entirely new solvers, researchers like Ran Taig and Shirin Sohrabi translate probabilistic or uncertain problems into the language of classical planning. By "compiling" uncertainty into additional state variables or temporal logic preferences, they allow high-performance classical planners to solve complex tasks like explanation generation and probabilistic navigation without starting from scratch.