On-line Learning of Planning Domains from Sensor Data in PAL: Scaling up to Large State Spaces

Leonardo Lamanna, Alfonso Emilio Gerevini, Alessandro Saetti, Luciano Serafini, Paolo TraversoAAAI 2021 · DOI

Introduction

Autonomous robots often face a significant hurdle: the "gap" between raw, continuous sensor data (like GPS or RFID signals) and the discrete symbolic representations (like PDDL) required for classical AI planning. While previous iterations of the Plan-Act-Learn (PAL) algorithm attempted to bridge this gap, they often hit a "scalability wall." In large state spaces, random exploration is insufficient; a robot wandering aimlessly in a complex environment will rarely encounter its goal, making model learning nearly impossible.

This paper presents an enhanced PAL framework designed to scale to massive state spaces. The core innovation is the use of a flawed "draft" model to guide exploration, allowing the agent to incrementally correct its internal map through real-world experience.

The PAL Architecture

The authors propose a hybrid architecture that interleaves symbolic planning with graph-based learning. This system consists of three primary components: the Learning, Modeling, and Planning components.

The PAL hybrid architecture interleaves learning, modeling, and planning components to bridge the gap between raw sensor data and symbolic planning.

Modeling and Planning

The agent maintains two distinct types of models:

  • The "Draft" (Intensional) Model: An initial PDDL model that serves as a "best guess." It provides a "compass" for exploration, even if it contains inaccuracies or missing constraints.
  • The Learned (Extensional) Map: A state-transition graph built on-the-fly as the agent moves. Nodes are linked to sensor observations via a Perception Function, modeled as a set of normal distributions.

Planning follows a dual-track approach. The Extensional Planner first searches through verified states. If no path is found, the Exploration Planner utilizes the draft PDDL model to hypothesize a route to the goal.

Failure-Driven Refinement

Learning is driven by execution failures. When an action suggested by the draft model fails in the real world, the agent updates its internal model with new constraints. This ensures the agent avoids repeating specific mistakes, gradually aligning its internal representation with the ground truth.

Experimental Evaluation

The approach was tested using three classic International Planning Competition (IPC) benchmarks: Logistics, Grid, and Rovers. To simulate real-world complexity, the authors introduced discrepancies between the initial PDDL model and the actual environment (e.g., forbidden air routes in Logistics).

Key Results

The enhanced PAL algorithm demonstrated significant improvements in scalability and efficiency:

  • Scalability: The system successfully solved 30 out of 37 large-scale Logistics instances, a feat impossible for previous versions reliant on random exploration.
  • Learning Rate: In repeated tasks, action-execution failures typically dropped to nearly zero by the fifth attempt, indicating rapid convergence to an accurate model.
  • Efficiency: As shown in the performance metrics, planning within the learned extensional state graph becomes increasingly efficient as the environment is explored, as the search space is restricted to reachable states.
Computational performance across Logistics, Grid, and Rover benchmarks, showing the breakdown of plan computation and state determination times.

Discussion and Future Work

A key insight of this work is the "Compass Effect": a perfect map is unnecessary for goal-directed exploration if a rough guide is available. To handle high-dimensional data, the authors also introduced Factorized Perception, treating sensor variables independently to reduce the computational overhead of state identification.

Current limitations include the simplicity of model updates (currently "banning" failed actions) and the assumption of a static environment. Future research will explore more sophisticated learning techniques, such as updating general action preconditions, and adapting the framework for dynamic worlds where environmental rules may change over time.

Summary updated

BibTeX
@inproceedings{lamanna2021line,
  author = {Leonardo Lamanna and Alfonso Emilio Gerevini and Alessandro Saetti and Luciano Serafini and Paolo Traverso},
  title = {{On-line Learning of Planning Domains from Sensor Data in PAL: Scaling up to Large State Spaces}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i13.17409},
}
Figure