Learning Generalized Policies for Fully Observable Non-Deterministic Planning Domains

Till Hofmann, Hector GeffnerIJCAI 2024

Abstract

This paper introduces a method to learn generalized policies for Fully Observable Non-Deterministic (FOND) planning domains. By reducing the complex FOND problem to a combination of generalized classical planning and automated dead-end detection, the authors enable the discovery of transparent, provably correct strategies that solve infinite families of non-deterministic problems using only a few small training examples. The approach leverages description logic for feature learning and Answer Set Programming (ASP) for policy synthesis, ensuring both generalization and safety.

Introduction

In automated planning, classical domains assume deterministic actions where outcomes are certain. However, real-world scenarios often involve non-determinism, modeled as Fully Observable Non-Deterministic (FOND) planning. FOND planning is computationally intensive (EXP-hard) because policies must account for multiple possible outcomes and avoid "dead-ends"—states from which the goal becomes unreachable.

Traditional FOND solvers address specific problem instances from scratch. In contrast, generalized planning seeks a single policy capable of solving any instance within a domain (e.g., clearing a stack of blocks of any height). This paper addresses the challenge of learning such generalized policies for non-deterministic domains, ensuring they are both goal-reaching and safe from dead-ends.

Methodology

The proposed approach treats policy learning as a combinatorial optimization problem, built upon three main pillars:

  1. FOND-to-Classical Reduction: The authors prove that a general FOND policy can be derived from a generalized classical policy by adding a safety requirement: the policy must never select an action that could lead to a dead-end.
  2. Feature Learning: Instead of raw state descriptions, the system utilizes a description logic grammar to learn abstract features (e.g., "distance to goal"). These features allow the policy to generalize across problems of varying sizes.
  3. Min-Cost SAT Formulation: The search for the simplest set of rules and features is encoded as a Boolean Satisfiability (SAT) problem, specifically using Answer Set Programming (ASP). The resulting policy is designed to be dead-end free, goal-tracking (using a learned ranking function), and simple to prevent overfitting.

The authors also explore a variation using transition constraints (identifying "bad moves") rather than just "bad states," which enhances performance in domains with complex safety requirements.

Experimental Evaluation

The method was evaluated on 12 standard FOND benchmark domains, including navigation tasks (Acrobatics, Beam-walk), stacking tasks (Blocks-world variants), and resource-constrained navigation (Tireworld, Miner). Training sets consisted of small instances (e.g., 3-4 objects), while testing was conducted on significantly larger, unseen instances.

Experimental results using state-based constraints. Bold values in the |S| column indicate instances where the method failed to find a general policy or hit resource limits.

Results and Discussion

The experimental results highlight the trade-offs between different constraint formulations. As shown in Figure 1, the state-based constraint method successfully learned general policies for 7 out of 12 domains. However, it struggled with domains like Tireworld and Triangle-Tireworld, where identifying safe states is more complex than identifying safe transitions.

Experimental results using transition-based constraints. This method successfully solves the Tireworld and Triangle-Tireworld domains, which were problematic for the state-based approach.

By employing transition constraints (Figure 2), the system successfully solved the notoriously difficult Tireworld variants. Key insights from the results include:

  • FOND = Classical + Safety: Non-determinism is effectively managed by filtering classical policies through a safety lens.
  • Transparency: The method produces human-readable rules, offering a clear advantage over black-box neural networks.
  • Efficiency: For many domains, the solver found optimal policies in less than a second, though complex domains like Miner required significantly more computation time (exceeding 1,000 seconds in some cases).

Conclusion

This work demonstrates that generalized policies for FOND domains can be synthesized efficiently using combinatorial optimization. While the method is highly effective and produces provably correct, transparent policies, it remains dependent on the expressivity of the feature grammar and the scalability of the underlying ASP solver. Future research may explore hybrid approaches combining this symbolic method with deep learning to handle larger feature spaces while maintaining formal guarantees.

Summary updated

BibTeX
@inproceedings{hofmann2024learning,
  author = {Till Hofmann and Hector Geffner},
  title = {{Learning Generalized Policies for Fully Observable Non-Deterministic Planning Domains}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure