Abstract
The LOP (LOCM with Optimised Plans) system is a novel approach to automated domain modeling that learns "static relations"—the underlying rules or maps of a world—by observing optimal plan traces. By identifying when a learned model produces "shortcuts" that are shorter than the provided optimal examples, LOP successfully induces the hidden constraints that define valid actions in complex planning environments.
Introduction
In the field of automated planning, domain model acquisition is the process of teaching a computer the rules of an environment by observing examples of actions. While previous systems like the LOCM family are effective at learning dynamic changes (e.g., "moving a truck changes its location from A to B"), they often fail to learn static constraints (e.g., "a truck can only move between A and B if there is a road connecting them").
Without these static relations, a learned model becomes "too powerful," assuming it can perform actions that are physically impossible, such as teleporting between disconnected points. This leads to the creation of invalid plans that are significantly shorter than reality allows. The challenge is to infer these hidden "road maps" or "successor rules" using only the sequences of actions found in plan traces, without having access to the internal state of the world.
Methodology
The authors introduce LOP, which builds on the existing LOCM2 algorithm using a "reductio ad absurdum" approach to identify missing constraints:
- Initial Learning: Run LOCM2 to learn the basic dynamics (how objects change state).
- Optimality Testing: Use the learned model to solve the same problems. If the planner finds a solution shorter than the provided optimal example, it indicates a missing static constraint.
- Minimal Static Relation Identification: LOP hypothesizes static predicates by looking at action parameters, seeking the smallest subset that forces the planner to match the length of the original optimal plans.
- Refinement and Splitting: The system uses specialized algorithms (MSR and MSR_Split) to partition these relations into their most efficient forms.
- Universality Check: Finally, it determines if a rule is "universal" (part of the world's physics) or "problem-specific" (unique to a specific instance, like a map).
Experimental Evaluation
The researchers evaluated LOP using standard benchmark domains from the International Planning Competition (IPC), including logistics (Driverlog, Depot, TPP), puzzles (Freecell, Sokoban, Blocks), and grid-based environments (Grid, Visitall). Training data was generated using the Fast Downward planner to ensure input plans were strictly optimal.
Results and Discussion
The results were highly successful across a variety of complex domains. In 9 out of 12 domains where the underlying dynamics were correctly identified, LOP successfully discovered the static relations without errors.
Key findings from the evaluation include:
- Driverlog: The system correctly identified distinct road maps for trucks and walking paths for drivers as separate static relations.
- Zeno Travel: LOP successfully induced the "successor" relationship for fuel levels and even identified redundant parameters in the original hand-coded benchmarks.
- Robustness: The system performed well even when input plans were "satisficing" (good but not strictly optimal), though accuracy is highest with truly optimal data.
Conclusion
The most significant contribution of LOP is the use of plan length as a proxy for model accuracy. By treating static relations as grounding filters, LOP bridges the gap between dynamic action learning and environmental constraints. However, the system remains dependent on the accuracy of the initial dynamic model provided by LOCM2. Future work may explore using the identified "optimality gap" to iteratively fix the dynamic model itself, creating a more holistic learning loop.
Summary updated