Technical Summary: Learning Lifted Action Models from Traces with Minimal Information

Problem Statement

Recent work has demonstrated that lifted STRIPS models can be learned efficiently from action traces alone (SIFT algorithm), and that STRIPS+ models (which allow implicit action arguments) can be learned from fully observable state-action traces (SYNTH algorithm). However, these approaches face practical limitations:

1. SIFT requires full STRIPS action traces where arguments are explicit, which often includes unnecessary parameters not needed for action selection (e.g., in sliding-tile puzzles, the current position of a tile must be explicitly passed even if the action is "move left").
2. SYNTH assumes full observability of all state predicates, which is unrealistic for agents operating in partially observable environments.

This paper addresses the problem of learning STRIPS+ action domains from traces where both action arguments and state information are partially observable. Specifically, the authors investigate the conditions under which an equivalent domain can be learned when traces carry minimal information: some action arguments are omitted, and state predicates are either fully unobservable, fully observable, or only locally observable (observable only for objects relevant to the current state).

Methodology

The proposed solution, SYNTH+, is a unified algorithm that extends and combines the capabilities of SIFT and SYNTH. It operates on extended traces (sequences of actions and partial state observations) and relies on two core mechanisms:

1. Mutex Features (Extension of SIFT)

To handle missing action arguments without state observability, the authors introduce mutex features.

• Concept: A mutex feature $f = \langle k, A, D \rangle$ represents a predicate of arity $k$ where the $k$-th argument is implicitly determined by the first $k-1$ arguments.
• Mechanism: Unlike standard features where add and delete patterns have the same arity, mutex features allow delete patterns to have arity $k-1$. This captures the constraint that an action (e.g., drop()) deletes a predicate (e.g., holding(o)) based on the object currently held, without explicitly naming that object in the action trace.
• Consistency: A mutex feature is consistent if, across the trace graph, every ground atom $f(o)$ receives a single truth value, and for any two true atoms $f(o)$ and $f(o')$ in the same state, if the last arguments differ ($o_k \neq o'_k$), then at least one preceding argument must also differ ($o_i \neq o'_i$ for some $i < k$).

2. Query Synthesis and Integration (Extension of SYNTH)

SYNTH+ integrates the "invention" of predicates (via SIFT) with the inference of implicit arguments (via SYNTH) in an iterative loop:

1. Input: A labeled graph of extended traces and a set of fully observable predicates $P_\omega$.
2. Iteration:
   • SIFT+ Step: Uses action patterns over explicit and currently known implicit arguments to invent new mutex features and plain features. These features represent new predicates and their effects.
   • SYNTH Step: Uses the newly invented predicates (and any observable predicates) to define queries (subqueries $Q_i$) that bind implicit variables ($z_i$) to unique objects in the state.
   • Update: The graph is updated with the new implicit arguments and their defining queries.
3. Termination: The process continues until a fixed point is reached or a maximum depth bound ($d_{max}$) is exceeded.

3. Local Observability

The framework is extended to LOCAL SYNTH+, which handles local observability. In this setting, a predicate is observable only for "local" objects (those appearing as arguments in the current action). The algorithm modifies the consistency testing procedure (TEST*) to assume non-local atoms are false when testing preconditions, ensuring that unobserved parts of the state do not invalidate the learning of implicit arguments.

Key Contributions

1. SYNTH+ Algorithm: A general algorithm for learning STRIPS+ domains from traces with partial observability of both actions and states. It unifies the predicate invention of SIFT with the implicit argument resolution of SYNTH.
2. Mutex Features: A novel formalism allowing the learning of predicates where the last argument is functionally dependent on the others, enabling the recovery of omitted action arguments without full state observation.
3. Completeness Results: Theoretical conditions are established for when the algorithms are complete:
   • SIFT+ (No state observability): Requires the hidden STRIPS+ domain to be well-formed, strongly connected, and acyclic in its dependency graph (where nodes are predicates and implicit variables).
   • SYNTH+ (Partial state observability): Requires the dependency graph restricted to non-observable predicates to be acyclic.
   • LOCAL SYNTH+: Proven complete under local observability for key predicates (predicates in preconditions involving only implicit arguments) if they are fully observable, and other predicates are locally observable.
4. Generalization: The work demonstrates that SIFT and SYNTH are special cases of SYNTH+ (where $P_\omega = \emptyset$ and $P_\omega = P$, respectively).

Experimental Results

The authors evaluated SIFT+ and SYNTH+ on a suite of standard planning domains (e.g., Blocks, Delivery, Grid, Sokoban, Logistics) using extended traces generated from hidden STRIPS+ models.

• SIFT+ Performance: Successfully learned correct domains (100% verification rate) from action traces alone across all tested domains, recovering an average of 55% of the action arguments that were omitted from the traces.
• SYNTH+ Performance: Learned correct domains using significantly fewer observable predicates than SYNTH.
  • In Delivery, SYNTH+ learned the domain observing only the agent's position (at(x)) and static adjacency, whereas SYNTH required all fluent predicates.
  • In Sokoban and Logistics*, SYNTH+ learned domains with only static predicates observed, a scenario where neither SYNTH nor SIFT+ could succeed.
• Efficiency: The algorithms ran efficiently (seconds to minutes) on standard hardware, scaling to domains with thousands of trace steps.

Significance and Claims

The paper claims that SYNTH+ provides a practical, lifted alternative to model-based reinforcement learning by enabling the learning of dynamic models from "natural" traces. These traces require minimal information:

• They do not need to list every argument required by a formal STRIPS encoding (e.g., the current position of a block being unstacked).
• They do not require full state observability; partial or local observability of specific predicates is sufficient.

The authors emphasize that their approach bridges the gap between theoretical model learning (which often assumes full observability) and practical application (where agents have limited perception). By characterizing the exact conditions (acyclicity of dependency graphs) under which learning is possible, the work establishes a rigorous scope for lifted action model learning in partially observable settings. The results suggest that complex domains can be reconstructed from traces that convey only the information necessary to select actions, rather than the full state description.