PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Partially Observable Deterministic Action Models

Eyal Amir, Allen Chang

arXiv:1401.3437v1cs.AI

TL;DR

Learning action effects and preconditions from partial observations is difficult because familiar conditional-independence structures can fail. The paper introduces SLAF, an online logical approach for tracking action models and possible states. For several common deterministic-action settings, it reports exact learning with polynomial-time guarantees and polynomially many traces to convergence.

  • Problem

    Learning action effects and preconditions under partial observability is difficult because conditional-independence structures useful for tractability may fail when intervening states are unobserved.

    Source: §1 · p. 2

  • Method

    SLAF updates a logical formula online to represent the transition relations and world states consistent with actions and partial observations.

    Source: §1 · p. 2

  • Results

    For several common deterministic-action settings, the consistent action models can be found exactly in polynomial, sometimes linear, time in the number of steps and features, with polynomially many traces needed for convergence.

    Source: §9 · p. 32

  • Takeaways & Limitations

    Transition-belief states are already being used to guide exploration by autonomous agents in adventure games.

    Source: §9 · p. 32

    For nondeterministic actions, representations using poly(|P|) propositions can grow exponentially; whether flat formulas require this growth for deterministic actions remains open.

    Source: USING THE OUTPUT OF SLAF0 · p. 12

Abstract

from arXiv · show

We present exact algorithms for identifying deterministic-actions effects and preconditions in dynamic partially observable domains. They apply when one does not know the action model(the way actions affect the world) of a domain and must learn it from partial observations over time. Such scenarios are common in real world applications. They are challenging for AI tasks because traditional domain structures that underly tractability (e.g., conditional independence) fail there (e.g., world features become correlated). Our work departs from traditional assumptions about partial observations and action models. In particular, it focuses on problems in which actions are deterministic of simple logical structure and observation models have all features observed with some frequency. We yield tractable algorithms for the modified problem for such domains. Our algorithms take sequences of partial observations over time as input, and output deterministic action models that could have lead to those observations. The algorithms output all or one of those models (depending on our choice), and are exact in that no model is misclassified given the observations. Our algorithms take polynomial time in the number of time steps and state features for some traditional action classes examined in the AI-planning literature, e.g., STRIPS actions. In contrast, traditional approaches for HMMs and Reinforcement Learning are inexact and exponentially intractable for such domains. Our experiments verify the theoretical tractability guarantees, and show that we identify action models exactly. Several applications in planning, autonomous exploration, and adventure-game playing already use these results. They are also promising for probabilistic settings, partially observable reinforcement learning, and diagnosis.

1. Introduction

Partially observable action learning is difficult because the conditional-independence structures that support tractable learning often fail. The paper introduces SLAF to identify exactly the action models consistent with partial observations and gives tractable algorithms for selected deterministic action classes.

1. Introduction

  • Partial observability can make the next state depend on earlier states because the intervening state is unobserved, undermining useful conditional-independence structures.The paper contrasts this with fully observable settings where structures such as the Markov property support tractable learning and decision-making.Source: §1 · p. 2
  • SLAF tracks, online, the possible transition relations and world states consistent with an action-and-partial-observation sequence.It updates a propositional Transition Belief Formula representing those possibilities.Source: §1 · p. 2
  • The algorithms range from a deduction-based method for nondeterministic problems with worst-case exponential time in fluents to polynomial-time updates for special deterministic action classes.One polynomial-time setting covers ADL actions without conditional effects when preconditions are known and failures observable, or when executions always succeed; another assumes injective actions.Source: §1 · pp. 2–3
  • Case (b) takes O(T^2 · n) time for T action-observation steps; under the stated observation-frequency condition, case (a) and case (b) take polynomial time.The condition is that every feature is observed at least once every fixed k steps in expectation; the representation can then be kept in k-CNF.Source: §1 · p. 3
  • The authors report exact, efficient learning of some ADL action effects in domains with more than 100 features, alongside faster and qualitatively better results than related approaches.They contrast their polynomial scaling with approaches described as inexact or requiring Ω(2^(2n)) time.Source: §1 · p. 3
  • Unlike explicit planning-operator design, learning seeks models compatible with observed trajectories and sound states; the resulting knowledge can support changing goals and applications such as autonomous exploration.The paper also identifies virtual worlds and games as applications, and deterministic models as possible approximations for robotics, interfaces, and diagnosis.Source: §1 · pp. 2–4

2. Simultaneous Learning and Filtering (SLAF)

SLAF represents uncertainty about both the current world state and the action model while tracking a system with unknown dynamics. It updates that representation as actions occur and partial observations arrive.

2. Simultaneous Learning and Filtering (SLAF)

  • A transition belief state collects possible pairs of world states and transition relations, thereby retaining uncertainty about both the state and the dynamics.A solution includes possible transition models and their associated possible states.Source: §2 · p. 4
  • SLAF processes action-observation sequences recursively, progressing possible states through an action and then filtering them by the observation.The formal semantics defines progression, observation filtering, and their repeated application across time steps.Source: §2 · pp. 4–5
  • In the locked-door example, trying a key and observing the door unlock eliminates transition-model possibilities inconsistent with that outcome.The example starts with three candidate key models and filters to the model in which key 1 opens the door.Source: §2 · p. 5
  • The observations are logical sentences over fluents, and SLAF can generalize both version spaces of action models and belief states conditioned on a transition relation.The paper describes the generalizations relative to Wang (1995) and Logical Filtering.Source: §2 · p. 6

3. Learning by Logical Inference

This section develops a propositional-reasoning view of SLAF, representing transition belief states with formulas and characterizing filtering as consequence finding. It establishes the correctness of a formula-based algorithm while noting limits on compact representation and tractable computation, and open representation-growth questions for deterministic actions.

3. Learning by Logical Inference

  • Directly representing transition-state pairs can require space Ω(2^(2|P|)), motivating a compact propositional representation for structured cases.The passage attributes the cost to explicitly representing the very large set of possible transition-state pairs.Source: §3 · pp. 6–7

3.1 Representing Transition Relations in Logic

  • Transition relations and belief states are represented with propositional formulas encoding conditional effects and preconditions, whose models correspond to transitions or state-transition pairs.The encoding treats an effect as holding in the successor state when its condition holds in the current state.Source: §3.1 · p. 7, TRANSITION BELIEF STATES CORRESPOND TO… · p. 9

3.2 Transition-Formula Filtering

  • SLAF filtering can be computed by consequence finding, and the SLAF0 formula algorithm is correct and equivalent to SLAF.SLAF0 combines a transition-belief formula with transition axioms and applies consequence finding; the characterization supports proofs of specialized algorithms’ correctness.Source: §3.2 · pp. 9–11
  • Existentially quantifying variables from a formula is equivalent to finding its consequences restricted to the remaining vocabulary.The section states this equivalence for one variable and extends it to any set of variables.Source: §3.2 · p. 10
  • Checking whether a particular state and transition model are possible takes time linear in the output formula’s size, while possibility and universal-property queries can use SAT solvers.A particular interpretation can be checked by evaluating the formula; SAT supports queries about possible models or states and whether all possible models satisfy a property.Source: USING THE OUTPUT OF SLAF0 · p. 11
  • The zeroth-level algorithm may enable compact representation, but guarantees neither compactness nor tractable computation; no algorithm can ensure both in general.Source: USING THE OUTPUT OF SLAF0 · p. 12
  • Deciding whether a clause follows from SLAF is coNP-hard, since the analogous Logical Filtering decision problem is coNP-hard even for deterministic actions.Source: USING THE OUTPUT OF SLAF0 · p. 12
  • With nondeterministic actions, transition-belief representations using poly(|P|) propositions can grow exponentially; whether this occurs for deterministic actions with flat formulas is open.Logical circuits avoid this growth for deterministic actions when represented using fluents at time 0 (Shahaf et al., 2006).Source: USING THE OUTPUT OF SLAF0 · p. 12

4. Factored Formula Update

Factoring SLAF updates along logical connectives can make computation tractable by separating formula components. Factored-SLAF is exact under stated action and formula conditions, but the general representation may still require exponential computation.

4. Factored Formula Update

  • Connective-based decomposition addresses the cost of handling interactions across a whole representation by allowing independent pieces to be processed separately.Computation then scales linearly with the number of pieces.Source: §4 · p. 12
  • When SLAF distributes over ∧ or ∨, its computation can be split across formula parts; the paper gives a linear-time exact algorithm when distribution is guaranteed.When distribution is not possible, the same algorithm returns a weaker transition belief formula.Source: §4 · p. 12
  • Factored-SLAF returns an exact solution for known 1:1 actions; a modified version is exact for actions without conditional effects when success or failure is observed.The general distribution conditions also permit decomposition when formula components include their joint prime implicates and the action meets the stated simplicity condition.Source: §4 · p. 13
  • With Literal-SLAF responses cached, each step takes time linear in the transition belief formula’s representation size.Step-SLAF takes O(|ϕ|c) when each Literal-SLAF run takes time c, and is exact under the stated Corollary 4.3 assumptions.Source: §4 · p. 13
  • The prescribed form of SLAF’s result reduces the task to simple computations, but its representation can still be exponential in size.In general, m can reach 2|P|, and finding the corresponding G_i terms may take exponential time in |P|.Source: §4 · p. 14

5. Compact Model Representation

This section develops compact representations and efficient algorithms for deterministic actions without conditional effects, covering effect and precondition learning as well as action failures when preconditions are known. The guarantees depend on action and observation conditions, including bounded precondition width, successful execution, and sufficiently frequent observations.

5. Compact Model Representation

  • The paper provides efficient algorithms for learning non-conditional deterministic action effects and preconditions, and for learning effects when actions may fail.This action class generalizes STRIPS and applies to a large part of the AI-planning literature.Source: §5 · p. 15

5.1 Actions of Limited Effect

  • When an action has at most k precondition literals, the limited-effect algorithm checks combinations in O(exp(k)) iterations.The restricted language reduces the terms that need checking compared with Theorem 4.5.Source: §5.1 · p. 15

5.2 Actions of No Conditional Effects: Revised Language

  • The revised axiomatization is equivalent to SLAF within the restricted action models, whose vocabulary represents unconditional STRIPS actions but not deterministic models in general.The representation uses propositions for action effects, unchanged fluents, and preconditions.Source: §5.2 · pp. 16–17

5.3 Always-Successful Non-Conditional Actions

  • For always-successful non-conditional actions, AS-STRIPS-SLAF allows unknown preconditions but cannot effectively learn them.The method assumes that the actions in the observed sequence all succeeded.Source: §5.3 · p. 17
  • AS-STRIPS-SLAF exactly matches SLAF and runs in linear time per action-observation pair; with each fluent observed within every k steps, k-CNF is preserved indefinitely.The output also remains fluent-factored when the input is fluent-factored.Source: §5.3 · pp. 18–19

5.4 Learning Actions Which May Fail

  • PRE-STRIPS-SLAF handles observed action failures for non-conditional effects when preconditions are known, returning a safe approximation that is exact under Corollary 4.3 conditions.It maintains a conjunction of disjunctions of fluent-factored formulas.Source: §5.4 · pp. 20–21
  • PRE-STRIPS-SLAF runs in linear time per action-observation pair and preserves m·k-CNF when every fluent is observed within every k steps and the input is m·k-CNF.Here m is the maximum number of literals in any action precondition.Source: §5.4 · p. 21

6. Building on Our Results

The paper sketches extensions to SLAF for richer observations, action schemas, and preference or probabilistic bias. Some extensions preserve the existing fluent-factored structure and time complexity under stated conditions.

6.1 Expressive Observation Model

  • A more expressive observation model can relate observation propositions to fluents, with observation propositions conditionally independent of adjacent states given the current fluents.The paper’s simpler baseline assumes an observed fluent’s value is its value in the current state.Source: §6.1 · p. 22
  • When the observation model is in k-CNF and at most one variable is unobserved per step, the update preserves fluent-factored form and the algorithms’ time complexity.The observation is incorporated through prime implicates of the observation and model sentences, with subsumed clauses removed.Source: §6.1 · p. 22
  • Preference models or probabilistic priors can be applied after SLAF, yielding an exact solution when their combination with the logical formula can be computed efficiently.The resulting formula can also be queried with a SAT solver; its variable count is independent of sequence length and linear in the number of fluents for some algorithms.Source: §6.1 · p. 22
  • A complete treatment of parameterized actions is outside the paper’s scope; it offers generalization guidelines instead.The example is move(b, x, y), which moves object b from x to y.Source: §6.1 · p. 23
  • Parameterized actions can be handled by grounding predicates and actions, then adding axioms that join information across instantiations.The authors expect further treatment could make time complexity depend on the number of action schemas rather than instantiated actions.Source: §6.1 · p. 23

7. Experimental Evaluation

Experiments examined SLAF on four IPC domains and found that per-step runtime stayed relatively constant as sequences grew, with computation scaling to moderate domain sizes. The results also illustrate conditions for theoretical guarantees and practical limits in extracting and using learned models.

7. Experimental Evaluation

  • Polynomial time and space guarantees rely on simple logical action structure and bounded-from-zero observation frequency; determinism alone is insufficient.The experiments assumed deterministic actions with few preconditions but did not enforce observing every fluent within a fixed number of steps.Source: §7 · pp. 23, 29, 30
  • Experiments used random 5000-step sequences, observed 10 randomly selected fluents per step, and gave SLAF no domain or starting-state information.The sequences were generated from PDDL descriptions for four IPC domains; computation time and space were recorded every 200 steps.Source: §7 · pp. 23–24
  • About 1 ms per SLAF step for 200-fluent domains; per-step time stayed relatively constant, so total runtime grew linearly with sequence length.The figures compare time and space across domain sizes for Blocksworld, Depots, Driverlog, and Zeno-Travel.Source: §7 · p. 24, Figure 6 · p. 25, Figure 7 · p. 26
  • Replacing ground propositions with schema propositions reduced the SAT solver’s variable load and sped model finding, while the 1:1 precondition heuristic often produced inaccurate preconditions.The heuristic was added because, without action failures in the sequences, blank preconditions were not eliminated by the algorithm.Source: §7 · p. 29
  • If a fluent never changes during an action sequence, the algorithm may infer that an arbitrary action causes it to hold.The learned action model is therefore not necessarily the correct model for planning.Source: §7 · pp. 29–30
  • Chang and Amir (2006) describe interleaving planning, execution, and learning; with detectable plan failure, their procedure reaches the goal in bounded time.The stated bound is linear in the longest plan needed to reach the goal and exponential in the complexity of the action model to be learned.Source: §7 · p. 30

8. Comparison with Related Work

The paper contrasts exact, feature-based SLAF with prior approaches that use approximations, explicit state representations, or less tractable model-learning procedures. It emphasizes retaining all models consistent with observations while scaling with features rather than enumerating states.

8. Comparison with Related Work

  • HMMs require explicit state-space representations, while RL approaches are described as highly intractable in partially observable domains and practical approximations as limited to small domains and horizons.The paper says its smallest HMM comparison domain, with 31 features, would require a transition matrix of (2^31)^2 entries.Source: §8 · pp. 30–31
  • SLAF represents features rather than states, is more compact than the Looping Prediction Suffix Tree approach, and retains all possible models when evidence is insufficient.Holmes and Charles Lee Isbell (2006) focus on the limit case where enough information determines a single consistent model; SLAF does not model stochasticity in the belief state.Source: §8 · pp. 30–31
  • SLAF learns deterministic transition models in polynomial time in state features, described as O(poly(log n)) in the number of states.The comparison is with PSR learning, whose discovery of tests requires matrices of size Ω(n^2) for state spaces of size n.Source: §8 · p. 31
  • The paper characterizes its algorithms as exact and tractable in domains with more than 300 features, using determinism, limited action effects, and observed failure.By contrast, DBN methods using EM and approximations are described as limited to small domains and as having unbounded errors in discrete deterministic domains.Source: §8 · pp. 30–31
  • Earlier weighted-MaxSAT learning of candidate STRIPS models is approximate, whereas SLAF identifies the exact set of action models consistent with traces.The cited approach also uses heuristic rules to rule out models considered unlikely.Source: §8 · p. 32
  • Compared with Shahaf and Amir (2006), SLAF’s transition-belief formula has bounded size independent of tracked time steps, though their circuit encoding handles more general deterministic models.The cited approach uses circuit SAT solvers, which the paper says were less optimized than CNF SAT solvers at the time.Source: §8 · p. 32

9. Conclusions

The paper concludes that exact learning of deterministic action effects and preconditions is polynomial-time in several common settings. It also identifies potential applications and extensions of this framework.

9. Conclusions

  • In several common settings, exact identification takes polynomial time, sometimes linear, and the number of traces needed for convergence is polynomial in the number of features.The framework can also compute exact solutions for large domains with hundreds of features in many cases.Source: §9 · p. 32
  • The results are already being applied to adventure-game agents, with exploration guided by the computed transition belief state; future work would extend them to stochastic and continuous-feature domains.The authors also identify reinforcement learning, virtual-domain agents, and HMMs as promising applications.Source: §9 · pp. 32–33

Appendix A. Our Representation and Domain Descriptions

  • A domain description consists of effect rules whose heads specify effects and whose conditions specify preconditions; a rule is active when its condition holds in the state.An unconditional rule is written as “a causes F.”Source: Appendix A · p. 33
  • A domain description determines a unique transition relation, applying inertia to unaffected fluents; explicit “keeps” rules are shorthand for paired positive and negative effect rules.An effect of FALSE makes an action unable to execute in that state.Source: Appendix A · p. 33
  • Under the example’s deterministic, no-conditional-effects assumption, each action affects every fluent positively, negatively, or not at all, yielding rules of the form “a causes l” or “a keeps l.”The example also assumes actions must meet their preconditions to execute successfully.Source: Appendix A · p. 34

B.1 Proof of Lemma 3.1: Consequence Finding and Existential Quantification

  • The proof eliminates a variable by adding its resolvents and retaining the resulting consequences, establishing equivalence to existentially quantifying that variable.The proof establishes both necessity and sufficiency of this equivalence.Source: §B.1 · p. 35

B.2 Proof of Theorem 3.3

The proof establishes an equality between two ways of updating state-transition-relation pairs: applying SLAF to a formula or filtering the pairs it describes.

B.2 Proof of Theorem 3.3

  • The proof targets equality between the sets of state-transition-relation pairs produced by the two update formulations.It establishes the equality by showing containment in both directions.Source: §B.2 · pp. 35–36
  • For the reverse direction, a pair produced by filtering has a preceding state satisfying the input formula and the required action transition.The proof takes such a state from the definition of filtering.Source: §B.2 · p. 35
  • For one direction, a pair satisfying the SLAF update has a preceding state that satisfies the input formula and transitions to the updated state under the relation.The proof uses a witness state and the effective-transition constraints.Source: §B.2 · p. 36

B.3 Proof of Theorem 4.1: Distribution of SLAF Over Connectives

The proof shows that SLAF distributes over disjunction by equating the update of a disjunction with the disjunction of the separate updates.

B.3 Proof of Theorem 4.1: Distribution of SLAF Over Connectives

  • SLAF of a disjunction has the same models as the disjunction of the separate SLAF updates.The proof establishes the equality by showing both model-set containments.Source: §B.3 · p. 36
  • A model of the SLAF update of a disjunction comes from an input model of one disjunct, so it satisfies that disjunct’s update.This establishes one containment in the model-set equality.Source: §B.3 · p. 36
  • Conversely, a model of either separate disjunct update comes from an input model that also satisfies the original disjunction.The proof notes that a similar argument applies to conjunctions.Source: §B.3 · p. 36

B.4 Proof of Theorem 4.5: Closed form for SLAF of a belief state formula

The appendix derives a closed form for SLAF by eliminating time-indexed literals, then shows how assumptions about action effects restrict the resulting clauses and their representation size.

B.4 Proof of Theorem 4.5: Closed form for SLAF of a belief state formula

  • The closed-form proof resolves out time-t literals from the belief, action, and transition formulas to obtain equivalent consequences over the next time step.The resolution is guaranteed to yield the corresponding consequence set.Source: §B.4 · p. 36
  • Resolving clauses with matching state terms produces the equivalent clause representation in the theorem.The proof considers clauses associated with the complete terms that satisfy the input formula.Source: §B.4 · p. 36
  • The proof uses complete fluent assignments satisfying the belief formula as state terms when constructing the resulting clauses.A complete term characterizes exactly one state.Source: §B.4 · p. 37

B.5 Proof of Theorem 5.1: Closed form when k affected fluents

  • Under a deterministic action with one term-precondition case, the proof replaces literals in the precondition terms while preserving the relevant effect condition.The assumption is that when the case does not hold, nothing changes.Source: §B.5 · pp. 37–38
  • The intermediate clause representation takes O(n^2) space, while encoding all preconditions for all effects would require O(2^n n) new propositions.The latter count motivates restricting which clauses need to be represented.Source: §B.5 · p. 38
  • When an action affects at most k fluents, each resulting clause has at most 2k literals and requires 2kn space.This bound follows after restricting attention to clauses with at most k relevant effect propositions.Source: §B.5 · pp. 38–39
  • With dependence on at most k other fluents, a no-change proposition can be represented through the possible k preconditions that could affect the fluent.The proof expresses no change as a conjunction excluding those possible preconditions.Source: §B.5 · p. 39

B.6 Proof of Theorem 5.3: Equivalent Restricted Definition of Action Axioms

The proof equates the action update with existentially projecting the old-state fluents from the prior belief and action-transition constraints. This follows because those constraints encode exactly the transition relation for a successful action.

B.6 Proof of Theorem 5.3: Equivalent Restricted Definition of Action Axioms

  • For a successful action, SLAF[a](ϕ) is equivalent to ϕ′, formed by existentially projecting P from ϕ ∧ τeff(a).The proof identifies P as the old-state fluents and P′ as the successor-state fluents.Source: §B.6 · p. 39
  • A model of ϕ′ supplies a prior state and transition relation whose successor valuation satisfies the projected formula.The proof obtains the transition relation from S_f and the successor state from P′.Source: §B.6 · p. 39
  • τeff(a) holds exactly when the action preconditions are met and the successor state matches the action’s effects.This is the condition that ⟨s, a, s′⟩ belongs to the transition relation.Source: §B.6 · p. 39

B.7 Proof of Theorem 5.4: AS-STRIPS-SLAF is Correct

The proof establishes AS-STRIPS-SLAF correctness by resolving away old-state fluents in the action update and then incorporating the observation. It also bounds formula growth under regular fluent observation and gives polynomial-time steps.

B.7 Proof of Theorem 5.4: AS-STRIPS-SLAF is Correct

  • The action update is equivalent to C(ϕ ∧ τeff(a)), where C resolves out the old-state fluents P and renames successor fluents P′ as P.The proof constructs the equivalent formula from fluent-factored ϕ.Source: §B.7 · p. 39
  • Because each clause contains at most one P-literal, the factored components generate all consequences obtainable by resolving out P.The proof then computes component consequences by resolution.Source: §B.7 · pp. 39–40
  • The observation update conjoins o with the action-filtered formula, and unit resolution makes the result fluent-factored.These are the operations performed by steps 1.(d)–(e).Source: §B.7 · p. 40

B.8 Proof of Theorem 5.5: AS-STRIPS-SLAF Complexity

  • Each filtering step increases clause width by at most one, while observing a fluent resets its belief-state component to 1-CNF.If every fluent is observed within at most k steps, the transition belief formula stays in k-CNF indefinitely; each algorithm step is polynomial time.Source: §B.8 · pp. 40–41

B.9 Proof of Theorem 5.7: PRE-STRIPS-SLAF is Correct

PRE-STRIPS-SLAF handles failed actions by retaining worlds that violate the precondition, and successful actions by filtering executable worlds with AS-STRIPS-SLAF. Its filtering is linear-time and its formula remains bounded in width under regular observation.

B.9 Proof of Theorem 5.7: PRE-STRIPS-SLAF is Correct

  • On action failure, the filtered worlds are those that violate the action precondition, which the algorithm represents by conjoining its negation.The negated precondition is converted to a logically equivalent disjunction of fluent-factored formulas.Source: §B.9 · p. 41
  • On action success, the algorithm first removes worlds violating the precondition, then filters the remaining worlds with AS-STRIPS-SLAF.It filters each subformula separately; equality with SLAF holds when a condition of Corollary 4.3 applies.Source: §B.9 · p. 41
  • The algorithm’s final simplification steps preserve a logically equivalent belief formula.Source: §B.9 · p. 41

B.10 Proof of Theorem 5.8: PRE-STRIPS-SLAF Complexity

  • Each AS-STRIPS-SLAF call and the remaining steps take linear time in the formula size; if fluents are observed within k steps and preconditions have at most m literals, the formula stays in m · k-CNF indefinitely.Each fluent-factored subformula is in k-CNF, and each disjunction contains at most m disjuncts.Source: §B.10 · p. 41

Appendix C. Experiments And Their Outputs

The appendix presents generating models and one satisfying learned model for four IPC domains. These examples accompany experiments the authors describe as tractable and exact, with reported problem sizes and solver timings.

Appendix C. Experiments And Their Outputs

  • The appendix gives one satisfying learned model per domain as an example of the models represented by the learned formula, across Driverlog, Zeno-Travel, Blocksworld, and Depots.The experiments are described as showing tractable, exact learning.Source: Appendix C · p. 41

C.1 Driverlog Domain

  • 2.469 SLAF time and 8.406 inference time were reported for Driverlog with 231 fluents, 1,000 actions, and 10 observed fluents per step.The displayed satisfying model includes learned needs, causes, and keeps relations for the domain’s actions.Source: §C.1 · pp. 42–44

C.2 Zeno-Travel Domain

  • 1.109 SLAF time and 11.015 inference time were reported for Zeno-Travel with 91 fluents, 21,000 possible actions, 1,000 sampled actions, and 5 observations per step.The displayed model includes learned fuel-level effects for FLY and ZOOM and passenger effects for BOARD and DEBARK.Source: §C.2 · p. 45

C.3 Blocks-World Domain

  • 2.203 SLAF time and 42.312 inference time were reported for Blocksworld with 209 fluents, 1,000 actions, and 10 observed fluents per step.The displayed learned model lists needs, causes, and keeps relations for UNSTACK, STACK, PUTDOWN, and PICKUP.Source: §C.3 · pp. 46–47

C.4 Depot Domain

  • 2.797 SLAF time and 8.062 inference time were reported for Depots with 250 fluents, 1,000 actions, and 10 observed fluents per step.The displayed satisfying model includes learned relations for UNLOAD, LOAD, DROP, LIFT, and DRIVE.Source: §C.4 · pp. 48–50
Loading 1401.3437v1…