Online Learning of Action Models for PDDL Planning

1 Introduction

Automated planning techniques require the specification of planning domains through action models (a set of preconditions and a set of effects for each domain action). However, the manual specification of the action models is often an inaccurate, time consuming, and error-prone task. The automated learning of action models is widely recognised as a key and compelling challenge to overcome these difficulties. Several works have addressed the task of learning action models, and have provided important results from different perspectives and according to different assumptions, see, e.g., [Yang et al., 2007; Amir and Chang, 2008; Xu and Laird, 2010; Rodrigues et al., 2011; Mour˜ao et al., 2012; Zhuo and Kambhampati, 2013; Cresswell et al., 2013; Certicky, 2014; Aineto et al., 2018; Aineto et al., 2019].

However, most of the recent and state-of-the-art methods perform learning offline, and require as input a set of plan traces generated by previously executed actions. This has two major drawbacks. First, often agents need to learn the model of the domain online, because they need to explore an unknown environment, acquire information, and learn a model by experimenting the execution of their actions incrementally, step by step. This is the case of many applications in robotics, e.g., in SLAM [Stachniss et al., 2016], where the robot tries to build a map of the environment by exploration, or in the Robocup Rescue [Kitano and Tadokoro, 2001], where the robot needs to explore the environment to perform a rescue task. Second, previous work on learning action models does not deal with the problem of generating informative plan traces. As stated in the conclusions of [Aineto et al., 2019], generating informative plan traces for learning planning action models is still an open issue. Indeed, if the available set of plan traces does not contain informative examples, there is little chance to learn all action preconditions, since some preconditions can be only discovered by specific plans that can unlikely be generated randomly [Fern et al., 2004].

In this paper, we propose a new approach that does not suffer from these drawbacks, focusing on the case of learning STRIPS action schema expressed in PDDL, and under the assumption of full observability of the states reached by the agent. We propose an algorithm, called OLAM algorithm (Online Learning of Action Models), for learning action models online, incrementally during the execution of plans. A key aspect of OLAM is that it combines and interleaves the activity of learning action preconditions and effects with an exploration phase that selects which plan to execute. In this way, OLAM generates plan traces to reach certain goal states, decided online, which are useful for the learning task.

Beyond proving termination, we analyse our algorithm to show some important theoretical properties that are defined according to the state transitions of the models learned by the algorithm. In particular we prove that OLAM is correct, i.e., it learns action models which generate only the state transitions generated by the planning domain modelling the true environment where the agent acts. Moreover OLAM is "integral", i.e., it learns action models that generate all the transitions of the true environment with respect to the states that can be reached by the algorithm.

We also provide substantial empirical evidence of the good learning performance of OLAM using a large set of benchmarks from the International Planning Competitions (IPCs). Finally we experimentally compare OLAM with a recent and state-of-the-art method for learning action models offline, showing that the online learning can be much more effective.

2 RelatedWork

Recent offline approaches address the problem of model learning with different assumptions on the observability of states and actions, see, e.g., [Amir and Chang, 2008; Bonet and Geffner, 2020; Cresswell et al., 2013; Mour˜ao et al., 2012; Newton et al., 2007; Yang et al., 2007; Zhuo et al., 2010; Zhuo and Kambhampati, 2013]. A prominent system among these is Fama [Aineto et al., 2019], which learns action models offline from examples by transforming the learning task into a classical planning task. It works with different kinds of inputs, from a set of plans to just a pair of initial and final states, without intermediate actions or states. Moreover, it accepts in input partially specified action models.

On the one hand, the aforementioned approaches to offline learning can deal with partial observability of states and actions, and some of them even with noisy states and noisy actions. OLAM requires instead full observability of states, it does not deal with noisy sensors, and actions are decided by OLAM itself. On the other hand, differently from OLAM, all these approaches are offline, require in input plan traces that in some cases might be not available, and hence do not deal with the issue of selecting informative plan traces.

Since the seminal work on online learning of operators [Gil, 1994b; Gil, 1994a; Wang, 1996], and the first approaches to learning action models by integrating learning, planning, and execution [Garc´ıa-Mart´ınez and Borrajo, 2000], some recent approaches have addressed the problem of online and incremental learning of action models. Walsh and Littman (2008) propose an approach to online learn action models which can be used in web-service planning problems. Their approach requires the use of an external "teacher" providing plan traces on demand. 3SG [Certicky, 2014] is an online algorithm that learns probabilistic action models with conditional effects and deals with action failures, sensory noise, and incomplete information. Xu and Laird (2010) describes an instance-based online method for learning action models in relational domains. The work is extended to deal with both discrete and continuous action models [Xu and Laird, 2011; Xu and Laird, 2013]. Rodrigues et al. (2010a; 2010b) propose a technique based on relational reinforcement learning to learn deterministic action models, and Rodrigues et al. (2011) extend the approach to deal with nondeterministic actions. These approaches are based on important technical differences with respect to our work. Most important, the main conceptual and practical difference is that all these approaches assume that the action to be executed is randomly selected or given in input, and therefore do not deal with the problem of guiding the exploration phase towards informative states, a key and promising feature of OLAM. The work by Lamanna et al. (2021) proposes an online method to learn planning domains by mapping continuous observations to deterministic state transition systems. It uses a given PDDL planning domain and a classical planner to heuristically explore the state space towards the problem goal. However, it focuses on learning the final state machine of the planning domain rather than PDDL action models like OLAM.

Our approach shares some similarities with the work on planning by reinforcement learning (RL) [Sutton and Barto,

1998]. However, RL focuses on learning policies rather than PDDL action models. Moreover, most often, in RL, actions are represented as (probabilistic) state transitions, rather than with symbolic action models.

3 Problem

Let P be a set of predicates with associated arity, of a first order language, and O be a finite set of operator names with associated arity. Predicates and operators of arity n are called n-ary predicates and n-ary operators. Given an n-tuple x = 〈x1, . . . , xn〉 of distinct symbols (constants or variables), let P(x) be the set of atomic formulas p(xi1 , . . . , xim ) obtained by applying the m-ary predicate p ∈ P to any m-tuple of symbols 〈xi1 , . . . , xim 〉 in x (with 1 ≤ i1, . . . , im ≤ n). For instance, if P contains the single binary predicate on, and x = 〈x1, x2, x3〉. Then, P(x) = {on(xi, xj) | 1 ≤ i, j ≤ 3}.

Definition 1 (Action schema). An action schema for an nary operator name op ∈ O on the set of predicates P is a tuple 〈par(op), pre(op), eff +(op), eff -(op)〉, where par(op) is a tuple of variables, pre(op), eff +(op), and eff -(op) are three sets of atoms on P(par(op)).

Essentially, pre(op), eff +(op), and eff -(op) represent the preconditions, positive, and negative effects of operator op. Without loss of generality, we assume that operators have no negative precondition. We also assume that the description of the effects is consistent, i.e., eff +(op) ∩ eff -(op) = ∅.

Definition 2 (Ground action). The ground action a = op(c1, . . . , cn) of an n-ary operator name op ∈ O w.r.t. the constants c1, . . . , cn is the triple 〈pre(a), eff +(a), eff -(a)〉, where pre(a) (resp. eff +(a), eff -(a)) is obtained by replacing the i-th parameter of par(op) in pre(op) (resp. eff +(op), eff -(op)) with ci.

We use the term lifted, as the opposite of grounded, to refer to expressions and actions where constants have been replaced with parameters.

Definition 3 (Planning domain). A planning domain M is a triple 〈P,O,H〉 where P is a set of predicates, O is a set of operator names with their arity and, for every op ∈ O, H is a function mapping an operator name op into an action schema.

Definition 4 (Finite-State Machine of a planning domain). The Finite-State Machine (FSM) of a planning domain M = 〈P,O,H〉 for the set C of constants is the triple M(C) = 〈S,A, δ〉 where S = 2P(C) is the set of all possible subsets of facts; A is the set of all possible ground actions of each n-ary operator name in O on any n-tuple of constants in C; δ ⊆ S ×A×S is a transition relation such that (s, a, s′ ) ∈ δ if pre(a) ⊆ s and s′ = s ∪ eff +(a) \ eff -(a).

A plan π inM(C) is a finite sequence of actions. A state sn ∈ S is reachable from a state s0 ∈ S in M(C) if there is a plan π = 〈a1, . . . , an〉 such that (si-1, ai, si) ∈ δ for i = 1 . . . n.

Assuming that the sets P, O and C are known by the agent, its task is to learn a planning domain by executing the actions available in O over constants in C, observing, and determining what are their preconditions and effects on the environment described in terms of the properties in P. In formal terms, the agent has to build an action model M = 〈P,O,H〉, i.e., the preconditions and effects of every action schema in the domain of H. We assume that the dynamics of the environment where the agent acts, which is unknown by the agent, is fully described by the finite state machine M′ (C), where M′ = 〈P, O, H′ 〉 is an action model called Ground-Truth Model (GTM).

The following definitions state the notions of correctness and integrity for the learned planning domain M = 〈P,O,H〉 w.r.t. the GTM.

Definition 5 (Correctness). Let M and M′ be two action models and M(C) = 〈S,A, δ〉 and M′ (C) = 〈S,A, δ′ 〉 be their FSMs with respect to a set of constants C. We say that

1. M(C) correctly approximates M′ (C) from a state s0 ∈ S if, for every state sn reachable from s0 in M(C), 〈sn, a, s〉 ∈ δ implies 〈sn, a, s′ 〉 ∈ δ′ for some s′ ⊇ s.
2. M(C) correctly approximatesM′ (C) ifM(C) correctly approximates M′ (C) from every state in S;
3. M correctly approximates M′ if M(C) correctly approximatesM′ (C) for every set of constants C.

A plan is valid when the actions in the plan are "executable" and the plan achieves a given set of (positive) goals. Therefore, when the learned model correctly approximates the GTM, any valid plan computed by using the learned model is also valid for the GTM.

Definition 6 (Integrity). LetMandM′ be two action models and M(C) = 〈S,A, δ〉 and M′ (C) = 〈S,A, δ′ 〉 be their FSMs with respect to a set of constants C. We say that

1. M(C) integrally approximatesM′ (C) from a state s0 ∈ S if, for every state sn reachable from s0 in M(C), 〈sn, a, s′ 〉 ∈ δ′ implies 〈sn, a, s〉 ∈ δ for some s ⊇ s′ ;
2. M(C) integrally approximates M′ (C) if M(C) integrally approximates M′ (C) from every state in S;
3. M integrally approximates M′ if M(C) integrally approximatesM′ (C) for every set of constants C.

Therefore, when the learned model integrally approximates the GTM, any valid plan for the GTM is also a valid plan for the learned model.

4 Learning Algorithm

In the proposed approach, the agent constructs and executes informative plan traces for learning the planning domain. Algorithm 1 shows the pseudocode of the OLAM (Online Learning of Action Models). The input of the algorithm are the same sets of predicates and operator names (with their associated arity) of the GTM, and a set C of constants representing the objects of the environment explored by the agent. OLAM produces in the output two planning domains M and M-? . The former is such that M(C) correctly and integrally approximates M′ (C) from the state of the environment when OLAM terminates. The latter correctly approximates M′ .

We adopt the following notations. Let x = 〈x1, . . . , xn〉 and c = 〈c1, . . . , cn〉 two n-tuple of distinct parameters and constants. If p is an m-ary predicate, p(x) denotes an atom p(xi1 , . . . , xim ) for some m-tuple of indexes 1 ≤ i1, . . . , im ≤ n; and p(c) the atom obtained by replacing xi with ci in p(x). In the following the indexing will be left implicit. OLAM incrementally builds the following sets:

1. pre(op), which contains the preconditions of the operator op; it is initialized to the whole set of lifted atoms (line 2); an atom p(x) is removed from pre(op) whenever an instance op(c) of op is executed successfully in a state s and p(c) ̸∈ s (line 19).
2. eff +! (op) and eff -! (op), which contains the set of lifted positive and negative effects of op learned by the agent; they are initially empty (line 3); a lifted atom p(x) is added to eff +! (op) (resp. eff -! (op)) if the execution of an instance op(c) of op in state s makes p(c) become true (resp. false) in the resulting state (lines 20-21).
3. eff +? (op) and eff -? (op), which are sets of lifted atoms that could become part of the positive or negative effects of op; they are initialized to the entire set of lifted atoms (line 2); a lifted atom p(x) is removed from eff +? (op) (resp. eff -? (op)) if p(x) is discovered to be a positive or negative effect or if the atom p(c) is false (resp. true) in a state s and remains false (resp. true) after executing successfully an instance op(c) of op in s (lines 22-23).
4. pre⊥(op), which is a set of sets of lifted preconditions for op such that in every non empty set in pre⊥(op) there is at least one precondition of op; pre⊥(op) is initialized to a set including only the empty set (line 4); pre⊥(op) is augmented by the set formed by any lifted fact p(x) such that p(c) is false in a state s, if the execution of an instance op(c) of op fails in s (line 26).
5. eff +!? (op) and eff -!? (op), which are derived sets denoting eff +! (op) ∪ eff +? (op) and eff -! (op) ∪ eff -? (op).

Let denote the sets of preconditions and positive/negative effects of any operator op of M′ by pre′ (op) and eff ′+/-(op), respectively. The update of the sets built by OLAM guarantees that pre(op) is a superset of pre′ (op), eff +/- ! (op) are subsets of eff ′+/-(op), and eff +/- !? (op) are superset of eff ′+/- !? (op).

At each iteration of the external loop (lines 7-31), the agent selects a state s′ and a ground action op′ (c′ ). s′ is reachable from the current state with the model M learned so far; the ground action op′ (c′ ) is such that its execution in s′ could provide to the agent some additional information about the preconditions, the positive, or the negative effects of op′ . This condition is formalised by (2)-(4). In particular, if condition (2) holds, the preconditions of op′ could be refined by executing op′ (c′ ) in s′ , because s′ does not contain all the preconditions of op′ (c′ ). Indeed if op′ (c′ ) will succeed, then the preconditions which are false in s′ can be eliminated. If condition (3) (resp. (4)) holds, some positive (resp. negative) effects of op′ could be learned, because op′ (c′ ) is executable in s′ and s′ does not contain all the facts in eff +? (op′ (c′ )) (resp. contains at least a fact in eff -? (op′ (c′ ))). Indeed, the facts in eff +? (op′ (c′ )) but not in s′ which become true can be added to the positive effects. Similarly, the facts that are in eff -? (op′ (c′ ))) and in s′ which become false can be added to the negative effects. The selection of such a state s′ and action op′ (c′ ) is done by constructing a plan from the current state s to a state s′ which satisfies conditions (2)-(4) for an op′ (c′ ) (line 8). If there is more than one action op′ (c′ ) that satisfies conditions (2)-(4) in s′ , one of them is randomly selected. The choice of s′ , op′ (c′ ) and the associated plan is obtained by invoking PLAN with the following goal:

Each disjunct in (1) describes a set of states from which the agent can potentially learn something by executing op(c). P + and P - partition the preconditions of op(c) so that the atoms in P + are true in s′ , the atoms in P - are false in s′ , and set P - has not already been checked to be necessary for successfully executing op(c). E+ is a subset of possible positive effects of op(c) which are false in s′ and can become true by executing op(c); similarly for E-. Notice that for every state s′ that contains P + and E- and does not contain P - and E+, and every action op′ (c′ ) such that (iv) and (v) and (vi) hold, when condition (2) is satisfied by s′ and op′ (c′ ), P - is not empty; when condition (3) is satisfied by s′ and op′ (c′ ), E+ is not empty; finally, when condition (4) is satisfied by s′ and op′ (c′ ), E- is not empty.

In the internal loop (lines 9-30), OLAM executes π and if it manages to successfully complete the execution of π (i.e., π = 〈〉, line 10) the ground action op′ (c′ ) will be executed in the environment where the agent acts (line 17). The dynamics of such an environment is unknown by the agent, and it determines the result returned by call EXECUTE(op(c)). When a ground action op(c) is successfully executed, OLAM observes the state of the environment snext resulting from the execution (line 18), and updates sets pre(op), eff +/- ! (op) and eff +/- ? (op) according to the criteria defined above (lines 1923). If the op(c) execution fails in the environment, pre⊥(op) is extended as described above, and π is reset to nil since its execution deviates from the expected trajectory computed according to the domain M learned so far (lines 26-27).

Theorem 1 (Termination). Algorithm OLAM terminates.

Proof sketch. The algorithm terminates because at every iteration of the external loop (7-31) one of the following facts holds for some operator op: the size of pre(op), eff +? (op), or eff -? (op) is reduced; the size of pre⊥(op), eff +! (op), or eff -! (op) is increased. Moreover, pre⊥(op) cannot be larger than 2P(par(op)) , all the other sets cannot be larger than P(par(op)), and the number of operators is equal to |O|.

In the rest of the section, we study the properties of correctness and integrity for the learned modelsMandM-? .

Theorem 2 (Correctness of M-? ). M-? correctly approximates M′ .

Algorithm 1 OLAM

Require: M = 〈P, O, {par(op), ∅, ∅}op∈O〉, C 1: s ← OBSERVE() 2: ∀op ∈ O, eff -? (op) ← eff +? (op) ← pre(op) ←P(par(op)) 3: ∀op ∈ O, eff -! (op) ← eff +! (op) ← ∅ 4: ∀op ∈ O, pre⊥(op) ← {∅} 5: M← 〈P,O, {par(op), pre(op), eff +! (op), eff -! }op∈O 〉 6: π ←nil 7: while ∃s′ , op′ (c′ ) such that s′ is reachable from s byM(C) and (2) ∨ (3) ∨ (4) holds do 8: π ← PLAN(M(C), s, s′ ) 9: while π ̸= nil do 10: if π ̸= 〈〉 then 11: op(c) ← POP(π) 12: else 13: op(c) ← op′ (c′ ) 14: π ← nil 15: end if 16: x ← par(op) 17: if EXECUTE(op(c)) does not fail then 18: snext ← OBSERVE() 19: pre(op) ← {p(x) ∈ pre(op) | p(c) ∈ s} 20: eff +! (op) ← eff +! (op) ∪ {p(x) | p(c) ∈ snext \ s} 21: eff -! (op) ← eff -! (op) ∪ {p(x) | p(c) ∈ s \ snext} 22: eff +? (op) ← eff +? (op) \ {p(x) | p(c) /∈ s ∩ snext} 23: eff -? (op) ← eff -? (op) \ {p(x) | p(c) ∈ s ∪ snext} 24: s ← snext 25: else 26: pre⊥(op)←pre⊥(op) ∪ {{p(x)∈pre(op)|p(c)̸∈s}} 27: π ← nil 28: end if 29: M← 〈P,O, {par(op), pre(op), eff +! (op), eff -! }op∈O 〉 30: end while 31: end while 32: M-? ← 〈P,O, {par(op), pre(op), eff +! (op), eff -!? }op∈O 〉 33: returnM,M-? Conditions in line 7: pre(op′ (c′ )) \ s′ ̸∈ pre⊥(op′ (c′ )) (2) pre(op′ (c′ )) ⊆ s′ and eff +? (op′ (c′ )) ̸⊆ s′ (3) pre(op′ (c′ )) ⊆ s′ and eff -? (op′ (c′ )) ∩ s′ ̸= ∅ (4)

Proof sketch. The correctness of M-? derives from the fact that at every execution step of OLAM, the set of preconditions of every operator op inM-? is a superset of pre′ (op), the set of positive effects of op is a subset of eff ′+(op), and finally the set of negative effects of op is a superset of eff ′-(op).

Theorem 3 (Correctness of M). M(C) correctly approximates M′ (C) from the final state of OLAM.

Proof sketch. The learned model M is the same as M-? but the set of negative effects of every operator op of M is eff -! (op). The statement of the theorem derives from the fact that op cannot have any missing negative effect that is true in some state s reachable from the final state of OLAM. Indeed, by construction, eff -! (op) ⊆ eff ′-(op) ⊆ eff -!? (op), and since condition (4) is false, eff -? (op(c)) ∩ s = ∅ is true.

Theorem 4 (Integrity of M). M(C) integrally approximates

M′ (C) from the final state of OLAM.

Proof sketch. The statement of the theorem derives from the fact that (i) every operator op cannot have any missing positive effect that is false in some state s reachable from the final state of OLAM, and (ii) if an instance op(c) of op is executable from s via M′ (C) then it is also executable from s via M(C). Statement (i) derives from the facts that, by construction, eff +! (op) ⊆ eff ′+(op) ⊆ eff +!? (op), and since condition (3) is false, eff +? (op(c)) ⊆ s is true. Statement (ii) derives from the fact that, since condition (2) is false, pre(op(c)) \ s ∈ pre⊥(op(c)), and at any execution step, if φ ∈ pre⊥(op) and φ ̸= ∅ then φ ∩ pre′ (op) ̸= ∅.

The learned model M approximates the GTM from the final state sf of OLAM both correctly and integrally. This implies that all and only the valid plans computed from sf via M are valid plans from sf via the GTM. Therefore, if a complete algorithm fails to reach a given set of goals from sf viaM, then the goals cannot be reached also via the GTM.

5 Experiments

We evaluate the effectiveness of OLAM for online learning planning domains on 23 planning domains, including the domains from the learning tracks of the past IPCs and the domains used by Aineto et al. (2019). For each domain, using an available problem generator, we randomly generated 10 small or middle-size instances with a number of objects ranging from 3 to 241 and consequently a number of potential grounded actions ranging from 12 to about 3.16 · 106 . For every domain OLAM is run on all the generated problem instances, from the smallest to the largest. On the first instance, OLAM takes as input the empty set of preconditions, positive and negative effects; for the successive runs, OLAM takes as input the planning domainM learned at the previous run. In OLAM, the calls EXECUTE and OBSERVE (lines 17-18) are implemented by a simulator of the IPC domain. The transition function of such a model is not known by the agent, who can only ask to execute actions and observe the current state. For function PLAN of Algorithm 1 (line 8), we adopt FASTDOWNWARD [Helmert, 2006] with a 60 seconds timeout. All experiments were run on an Intel Xeon Skylake 2.3 GHz with 8 cores and 64 GB of RAM.

The learned planning domain is compared with the GTM, as done by Aineto et al. (2019), by precision and recall measures. Given a learned model M and GTMM′ , we define precision and recall for preconditions (Ppre, Rpre), positive and negative effects (Peff-, Peff +, Reff-, Reff +). Specifically, Ppre and Rpre are defined as follows:

Intuitively, they measure the (relative) amount of extra learned preconditions w.r.t. the GTM, and the (relative) amount of missing preconditions w.r.t. the GTM, respectively. The lower these amounts, the greater the measures. Similarly we define precision and recall for eff - and eff +. If the precision and recall measures for pre, eff - and eff + is 1, then the learned model is exactly the same as in the GTM for pre, eff and eff +, respectively. The overall precision P and recall R are defined considering pre, eff -, eff + together. I.e.,

and similarly for R.

Table 1 summarizes the efficacy of Mw.r.t. the GTM in terms of precision and recall. By construction of sets pre(op) and eff +/- ! (op) of every operator op, Rpre, Peff +, and Peffof Mmust be equal to 1, i.e., there is no missing precondition and extra effect in the learned model Mw.r.t. the GTM. This is confirmed by the results in Table 1. Moreover, Ppre is always quite high, although usually lower than 1, i.e., there are few extra preconditions in the learned model w.r.t. the GTM. The extra learned preconditions are static predicates such that, when the action is grounded, the corresponding grounded preconditions are true in all the states reachable from the initial state. This prevents the remotion of these extra preconditions from a correct learned model, likeM. The recall over the positive/negative effects is always equal to 1 for every domain but ROVER, i.e., there are no missing effects (except for ROVER) in the learned model w.r.t. the GTM.

The results in Table 1 also show that domain M can be learned using very few problems, often using only a single problem. Note that such a domain is learned by few small problems, and it does not mention their constants, i.e., it is general and hence suitable even for much larger problems. This shows that overall OLAM is able to effectively generalize between the experience derived from small environments and the future experience in large environments.

We also study the efficacy of M-? w.r.t. the GTM. The difference between the learned models M andM-? consists in the fact that M-? also includes set eff -? (op) as negative effects of an operator op. Therefore, the precision and the recall over the preconditions and the positive effects ofM-? are the same as in Table 1. Table 2 gives the precision and recall over the negative effects of M-? and over all domain M-? . For this study we consider M-? with and without assuming eff ′-(op) ⊆ pre′ (op), i.e., when this assumption is made, the atoms in eff -? (op) that are not in the preconditions of an operator are removed. By construction of set eff -!? , Reff- must be equal to 1. Surprisingly, this is false for domains GOLDMINER and ROVER. The reason why this happens is that for these domains an assumption of ours does not hold: ROVER is a special domain including operators with inconsistent effects, i.e., eff ′+(op)∩eff ′-(op) ̸= ∅, for some operators. For GOLD-MINER, the assumption eff ′-(op) ⊆ pre′ (op) does not hold. This assumption is violated also in domains PARKING, SATELLITE and MATCHING-BW, but for these domains there is no missing negative effect inM-? , since OLAM on line 21 learns eff -! regardless of this assumption. Interestingly, P - eff with this assumption is always equal to 1, while without the assumption it is almost always quite low. This gap gives evidence that such an assumption can be very useful for removing extra negative effects from the learned domain.

We compare OLAM with a version of the algorithm that explores the world randomly. The random strategy reaches an average precision and recall of 0.45 and 0.63, against the average precision and recall of 0.99 and 0.92 obtained by OLAM, which shows that the generation of informative plan traces is extremely helpful.

In the last experiment we compare the online learning of OLAM with the offline learning method proposed by Fama [Aineto et al., 2019]. Fama takes as input a set of plans with their state trajectories. Since OLAM does not support partial observability, we set Fama for working in a fully observable environment, and considered the same sets of plan traces and planning domains (but VISITALL and ZENOTRAVEL) as in [Aineto et al., 2019]. The set of plan traces consists of 10 traces with 10 states; the set of planning domains does not contain ZENOTRAVEL and VISITALL, because the distributed version of Fama finds no solution for ZENOTRAVEL, and there is no problem generator available for VISITALL. Since Fama adopts the assumption eff ′-(op) ⊆ pre′ (op) for any operator op, we compared the planning domain derived from Fama with M-? using the same assumption. We obtained similar results from the comparison between Fama and the other learned domainM.

Table 3 compares OLAM and Fama. OLAM obtains better or equal precision and recall, and generally it is also much faster. In all the domains but ROVER, OLAM executes less actions than Fama. We think that the difference for ROVER is related to the consistent-effects assumption made in OLAM that in ROVER does not hold. Overall, learning the planning domain online is much more effective than learning it offline. In our online approach, indeed, the agent selects the goals to reach and actions to execute to optimize learning, while in offline approaches actions are provided in the input traces.

6 Conclusions

The paper proposes an online algorithm, OLAM, for learning PDDL planning domain under the assumption of full observability. OLAM incrementally learns an action model by selecting goals to reach and actions to execute that allow to acquire useful information about the operators. The paper shows some important theoretical properties of OLAM concerning the completeness and integrity of the learned models. An implementation of OLAM shows good learning performance on a large set of benchmarks from the IPCs, and outperforms a state-of-the-art method for learning action models offline. OLAM works with full observability; extension to partial observability is part of the future work.

Acknowledgements

This work is partially supported by the EU ICT-48 2020 project TAILOR (No. 952215).