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.
- 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.
- 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.
- Optimization: Confirmed nogoods are pruned to their most general form, allowing a single rule to cover millions of potential states.
- 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.
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.
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