SixthSense: Fast and Reliable Recognition of Dead Ends in MDPs

Andrey Kolobov, Mausam, Daniel S. Weld

Introduction

Probabilistic planning often relies on Markov Decision Processes (MDPs) to model complex environments. However, a persistent challenge in solving large-scale MDPs is the presence of "dead ends"—states from which the goal is unreachable. While some dead ends are explicit and easy to identify, many are implicit, requiring deep search to uncover. SixthSense is a machine learning algorithm designed to bridge this gap by learning compact logical rules, known as "nogoods," to identify these states efficiently.

The Challenge of Implicit Dead Ends

In MDP solvers, dead ends consume significant computational resources. "Explicit" dead ends, where no actions are possible, are trivial to detect. In contrast, "implicit" dead ends allow for actions but offer no path to the goal. Existing heuristics often fail to detect these, leading solvers to explore vast, useless search spaces. Conversely, more sensitive methods that use classical planners for verification are often too slow for real-time applications.

The SixthSense Approach

SixthSense employs a "generate-and-test" methodology to discover nogoods—logical conjunctions that guarantee a state is a dead end.

  1. Generation: The algorithm identifies "basis functions" from successful trajectories. Candidate nogoods are then formed by selecting literals that negate these functions, ensuring the conditions for success cannot be met.
  2. Soundness Testing: To maintain reliability, candidates are verified using a planning graph-based procedure. This ensures that if SixthSense labels a state as a dead end, it is guaranteed to be one, preventing the accidental pruning of valid paths.
  3. Optimization: Confirmed nogoods are pruned to their most general form, allowing a single rule to cover millions of potential states.
  4. Adaptive Scheduling: Learning rounds are triggered based on the discovery of new dead ends, with an exponential back-off strategy to maintain efficiency.

Experimental Evaluation

The effectiveness of SixthSense was tested on benchmarks from the International Probabilistic Planning Competition (IPPC), including the Drive and Exploding Blocks World domains.

Memory and time savings in the Drive domain.

In the Drive domain, as shown in the figure above, SixthSense consistently achieved memory savings of approximately 50%. While initial time savings were negative due to the overhead of learning, they quickly became positive, reaching up to 60% as the problem complexity increased.

Performance gains in the Exploding Blocks World-08 domain.

The impact was even more pronounced in the Exploding Blocks World domain. In several large-scale problems, standard solvers reached their memory limits and failed. SixthSense enabled these solvers to succeed by pruning dead-end branches, achieving near 100% savings in memory and time for the most challenging instances.

Key Insights

  • Compact Explanations: A few logical rules can explain millions of dead-end states, drastically reducing the state space the planner must store.
  • Soundness: By guaranteeing that pruned states are truly dead ends, SixthSense maintains the integrity of the planning process.
  • Efficiency: Once learned, nogoods are extremely fast to evaluate, often occupying less than 0.5% of total planning time in large problems.

Conclusion

SixthSense provides a powerful "hunch" for MDP solvers, allowing them to avoid the pitfalls of implicit dead ends. By combining machine learning with formal verification, it offers a scalable solution for complex probabilistic planning tasks, significantly reducing both memory and time requirements. Future work aims to extend this approach to first-order logic to further improve the generality of the learned rules.

Summary updated

Abstract

The results of the latest International Probabilistic Planning Competition (IPPC-2008) indicate that the presence of dead ends, states with no trajectory to the goal, makes MDPs hard for modern probabilistic planners. Implicit dead ends, states with executable actions but no path to the goal, are particularly challenging; existing MDP solvers spend much time and memory identifying these states. As a first attempt to address this issue, we propose a machine learning algorithm called SIXTHSENSE. SIXTHSENSE helps existing MDP solvers by finding nogoods, conjunctions of literals whose truth in a state implies that the state is a dead end. Importantly, our learned nogoods are sound, and hence the states they identify are true dead ends. SIXTHSENSE is very fast, needs little training data, and takes only a small fraction of total planning time. While IPPC problems may have millions of dead ends, they may typically be represented with only a dozen or two no-goods. Thus, nogood learning efficiently produces a quick and reliable means for dead-end recognition. Our experiments show that the nogoods found by SIXTHSENSE routinely reduce planning space and time on IPPC domains, enabling some planners to solve problems they could not previously handle.
BibTeX
@inproceedings{kolobov2010sixthsense,
  author = {Andrey Kolobov and Mausam and Daniel S. Weld},
  title = {{SixthSense: Fast and Reliable Recognition of Dead Ends in MDPs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7752},
}
Figure