TL;DR
This paper introduces OLAM, an algorithm that learns PDDL action models online by actively exploring an environment and generating informative plan traces. Unlike previous offline methods, OLAM's active exploration allows it to learn effectively even in unknown environments and significantly outperforms offline approaches in terms of learning speed and accuracy.
What Problem Does This Paper Address?
Automated planning relies on accurate "action models" that describe how actions change the environment. Manually creating these models is tedious and error-prone. While learning action models from existing plan traces (offline learning) has seen progress, it faces two major hurdles: 1) plan traces might not be readily available for new, unknown environments, and 2) existing methods don't actively generate informative traces. This means that if the initial traces don't cover specific scenarios, crucial action preconditions might never be learned. This paper tackles these limitations by proposing an online learning approach that actively seeks out informative experiences.
Methods
The core of the paper is the OLAM (Online Learning of Action Models) algorithm. OLAM operates by interleaving planning, execution, and learning.
- Online Learning: Instead of learning from a fixed dataset of plans, OLAM learns incrementally as it interacts with the environment.
- Active Exploration: A key innovation is OLAM's ability to decide which goals to pursue and which actions to execute. It uses a planner (FAST-DOWNWARD) to generate a plan to reach a state that is predicted to yield the most information about the action models. This is guided by specific conditions that identify states where learning about preconditions, positive effects, or negative effects is most likely.
- Model Representation: OLAM learns STRIPS action schemas expressed in PDDL. It maintains and updates sets of learned preconditions, positive effects, and negative effects for each action.
- Correctness and Integrity: The paper formally defines and proves theoretical properties of OLAM, showing that its learned models "correctly approximate" (don't over-generalize preconditions or under-specify effects) and "integrally approximate" (learn all necessary preconditions and effects) the true, unknown environment dynamics.
Datasets
The authors evaluated OLAM on 23 benchmark planning domains, including those from the International Planning Competitions (IPCs) and domains used in prior work (e.g., Aineto et al., 2019). For each domain, they generated small to medium-sized instances. They also compared OLAM against the offline learning method Fama, using similar problem instances.
Key Insights and Ideas
- Active exploration is crucial for learning: The paper strongly suggests that simply having plans isn't enough; actively seeking out informative experiences is key to learning robust action models, especially in unknown environments.
- Online learning can be more effective than offline: By dynamically choosing what to learn, OLAM significantly outperforms offline methods, even when the offline method is given the same underlying problem structure.
- The importance of informative plan traces: The paper highlights that random exploration is inefficient. OLAM's guided exploration, which targets states likely to reveal new information, is a major advantage.
- Theoretical guarantees matter: Proving correctness and integrity provides confidence that the learned models are not just accurate on the training data but generalize well and capture the true dynamics.
Key Results
- High Precision and Recall: OLAM achieved very high precision and recall for learned preconditions and effects across a wide range of IPC domains, often close to 1.
- Efficiency: OLAM was significantly faster than the offline method Fama, often executing fewer actions to achieve comparable or better learning results.
- Generalization: OLAM demonstrated good generalization capabilities, learning effectively from small instances and applying that knowledge to larger ones.
- Outperforms Offline: In direct comparisons, OLAM consistently outperformed Fama, especially in terms of learning efficiency and overall accuracy.
Limitations and Future Work
- Full Observability Assumption: OLAM currently assumes full observability of the environment's state. This is a significant limitation for real-world applications where sensors are often noisy or incomplete.
- Noisy Sensors/Actions: The current algorithm does not explicitly handle noisy sensor readings or actions that might fail unexpectedly (though it does have mechanisms for handling action failures during learning).
- Future Work: The authors explicitly mention extending OLAM to handle partial observability and noisy sensors as key directions for future research. They also suggest exploring more complex action representations beyond STRIPS.
Summary updated