Domain Model Acquisition in the Presence of Static Relations in the LOP System

1 Introduction

Modelling is well known as a bottleneck in the development of solutions to difficult combinatorial problems. The research field of automated modelling focuses on the task of constructing formal descriptions of problems automatically, often using solution data as input. Automated model acquisition is an active research area in constraint programming, general game playing and computer security (e.g. [O'Sullivan, 2010; Bessiere et al., 2014; Bj¨ornsson, 2012; Aarts et al., 2013]).

Domain model acquisition is automated modelling in a planning context: it is the problem of learning planning domain models from example data. The LOCM family of domain model acquisition systems [Cresswell et al., 2009; Cresswell and Gregory, 2011; Cresswell et al., 2013] learn planning domain models from collections of plans. For example, given the following two plans, a planning domain model acquisition system should learn operator schema of the type shown in Figure 1:

(drive-truck truck2 driver1 loc3 loc1) (load-truck truck2 loc1 pkg1) (drive-truck truck2 driver1 loc1 loc3) (unload-truck truck2 loc1 pkg1) (load-truck truck2 loc6 pkg3) (drive-truck truck2 driver2 loc6 loc2) (drive-truck truck1 driver1 loc6 loc4)

The LOCM family of algorithms only learn the dynamic aspects of the domain (i.e. state changes that occur due to action application). This is problematic since many domains

Stephen Cresswell

The Stationery Office St. Crispins, Duke Street, Norwich, NR3 1PD, UK stephen.cresswell@tso.co.uk

(:action drive-truck-benchmark :parameters (?t - truck ?d - driver ?l1 - loc ?l2 - loc) :precondition (and (at ?t ?l1) (conn ?l1 ?l2) (driving ?d ?t)) :effect (and (not (at ?t ?l1)) (at ?t ?l2))) (:action drive-truck-locmii :parameters (?t - truck ?d - driver ?l1 - loc ?l2 - loc) :precondition (and (at ?t ?l1) (driving ?d ?t ?l1)) :effect (and (not (at ?t ?l1)) (at ?t ?l2) (not (driving ?d ?t ?l1)) (driving ?d ?t ?l2)))

use static relations to restrict the possible actions. Consider the Driverlog domain, where the road map is encoded as a binary static predicate. Figure 1 shows both the benchmark and LOCM2 versions of the drive action. The conn predicate encodes the road map in the hand coded benchmark. This is not modelled in the induced drive action. Some of these static relations could be inferred given extra information about intermediate states. However, it is more desirable to be able to infer these static relations using only the minimal information available to the LOCM system, since intermediate state information may not always be available. In this paper, we extend the LOCM2 system in order to detect static relations. The key assumption in our approach is that the input is drawn from optimal goal-directed plans. Assuming that LOCM2 has detected the dynamics of the problem correctly, then if the induced plan is shorter, then this is a good clue to the fact that some static relation has gone undetected. Static conditions supporting the length of the input plans can then be hypothesised. We call our system LOP [Gregory and Cresswell, 2015] (standing for LOCM with Optimised Plans).

Related Work

Within the planning literature, there are many domain model acquisition systems. These systems each have varying levels of detail in their input observations. LOCM-derived systems use a minimal amount of input (only plan traces) whereas most other systems use predicates, initial and goal states and possibly intermediate states. The compromise is that Algorithm 1 The Preserve Optimality testing algorithm.

Require: M : an output domain model from LOCM2 Require: T : a set of LOCM2 generated problems Require: P : a subset of the parameters for each operator function preserveOptimality for t 2 T do optP optimal input plan for t dom Mplus statics defined by P prob t plus ground statics defined by optP optT optimal solution to dom↪ prob if length(optT) < length(optP) then return false end if end for return true end function

the target language in LOCM is simpler than many other systems. The Opmaker2 system [McCluskey et al., 2009; Richardson, 2008] learns models in the target language of OCL [McCluskey and Porteous, 1997] and requires a partial domain model, along with example plans as input. The ARMS system [Wu et al., 2007], can learn STRIPS domain models with partial or no observation of intermediate states in the plans, but does at least require predicates to be declared.

The LAMP system [Zhuo et al., 2010] can target PDDL representations with quantifiers and logical implications. Systems that learn planning models in the presence of noisy and incomplete data [Mourao et al., 2012] have also been studied. Other types of learning include [Mehta et al., 2011] considering the task of learning a single state space with no input plans, but with a system by which an oracle can validate plan hypotheses. A form of transfer learning has been considered [Zhuo et al., 2011] where action schema are constructed via a combination of analysing exisiting domains and using web queries to match operator names. The closest system to LOP, specifically designed to detect static information is the recent ASCOL system [Jilani et al., 2015].

2 Static Relations in Planning

Static relations are often thought of by their semantic interpretations: road maps in Driverlog, successor relations in Zenotravel and Freecell, for example. This is seen in Figure 1 for the Driverlog domain. We now present an alternative purely syntactic interpretation of static relations that is critical to our work.

Defining Static Relations

Static relations can be seen as restrictions on the groundings of each operator. Instead of thinking of how the objects are related, we now think of which combinations of ground operator parameters are valid. The static relations in a domain can be defined as, for each operator, a table of all the valid groundings for that operator. The static relations for any domain can be encoded as a single relation per operator.

This observation allows us to construct our hypothesis space of potential static relations. Each operator can be seen to have a static relation associated with it, and we have to identify the minimal subset of parameters that permit exactly the valid groundings of an operator. We can now present definition of the minimal static relation identification problem:

Definition 1 (Minimal Static Relation Identification). Given an operator template:

We define a minimal static relation as the subset Pm ✓ p1↪ ▷▷▷↪ pn such that all pm 2 Pm are members of static preconditions of op.

Thus, this problem is simply to identify the parameters which play a part in the static relation.

Universal Static Relations

Some statics are defined for specific instances and are different in different instances depending on the problem objects. These include the road maps in Driverlog and the locations of the hoists in Depot, for example. In contrast to these types of static relations, there are also those that hold in all instances. For example, in Peg Solitaire, all instances use the same underlying board. In Zeno Travel, the static relation that encodes the successor relation for the fuel levels is the same in all problem instances. If a static relation holds between all instances, we call that a universal static relation.

Issues in Detecting Statics

The key issue in detecting statics using plan traces as input is that there are domains which look very similar, but which vary in the static relations. For example, Blocksworld and Freecell, in which the goal in both is to rearrange stacks of objects. In Blocksworld there are no static relations, in Freecell there are static relationships between the ranks and colours of the cards. In order to address this issue we use additional information about the plans, other than simply the plan traces. Namely, we identify a set of optimal plans to be used in the learning phase. In the following sections, we detail exactly how we use optimal plans to discover static relations.

3 The LOP Algorithm

We now present the LOP algorithm that we use to detect static relations. LOP has the assumption that LOCM2 returns the correct domain model dynamics. The algorithm is sketched as follows:

1. Run LOCM2 on both the optimal and suboptimal training data, constructing the LOCM2 domain model.
2. Identifyminimal subsets of each action's parameters that 'preserve' the optimal length of all plans.
3. Split each relation into a minimal partition that preserve optimal plan lengths.
4. Identify the universal static relations.
5. Return the valid ground relations and the problemspecific templates.

3.1 Preserving Optimality

All stages of the LOP algorithm rely on testing whether or not optimality is preserved for a set of input plans. We now define exactly what we mean by preserving optimality. Consider the following optimal input plan:

Algorithm 2 Minimal static relation hypothesis algorithm.

function MSR for o : operators do msr(o) MSRo(o) end for return msr end function functionMSRo(o : operator) minS parameters(o) for p 2 minS do minS0 (minS ∩ ¶p♦) if preserveOptimality(minS0 ) then minS minS0 end if end for return minS end function

(drive truck loc1 loc2) (drive truck loc2 loc3)

Now, consider the drive action and PDDL problem fragment induced by LOCM2:

(:action drive :parameters (?t - truck ?l1 ?l2 - loc) :precondition (at ?t ?l1) :effect (and (not(at ?t ?l1)) (at ?t ?l2)) ) (:init (at truck loc1)) (:goal (at truck loc3))

Note that the dynamics of the drive action are correct: the truck moves from the start location to the destination location. However, if we solve this output using an optimal planner we find the following plan:

(drive truck loc1 loc3)

This plan is shorter than the input plan which we knew to be optimal. Therefore, we say that the drive action does not preserve optimality. In order to restore the optimality we add static relations both in the action preconditions and the corresponding ground predicates in the initial state. For example, the set of all parameters yields the following action and problem fragment:

(:action drive :parameters (?t - truck ?l1 ?l2 - loc) :precondition (and (at ?t ?l1) (drive_static ?t ?l1 ?l2) :effect (and (not(at ?t ?l1)) (at ?t ?l2)) ) (:init (at truck loc1) (drive_static truck1 loc1 loc2) (drive_static truck1 loc2 loc3) ) (:goal (at truck loc3))

Algorithm 1 presents the algorithm for testing if optimality is preserved for a particular parameter set of the operators. In essence, it checks that each input plan preserves optimality Algorithm 3 Minimal static relation splitting algorithm. In this algorithm rank refers to the rank of the partition (the size of the largest block minus the total number of blocks).

function MSR Split(P : a partition of the MSR) if preserveOptimality(P) = false then return ? end if min P for P 0 2 refinement(P ) do minP0 MSR Split(P 0 ) if evaluate(minP0 ) < evaluate(min) then min minP0 end if end for return min end function function evaluate(P : a partition of the MSR) if P = ? then return 1 else return rank(P ) end if end function

for that parameter set. The algorithm for discovering minimal static relations (or MSRs) is presented in Algorithm 2 which attempts to remove each parameter in turn from a candidate relation, adding it back in if it leads to shorter optimal solutions. Depending on the current MSR hypotheses for each operator, Algorithm 2 may return different results. For this reason, the algorithm is run repeatedly until a fix-point is reached, when the MSRs do not change following an iteration.

3.2 Splitting The Static Relation

Once a minimal static relation is found for each operator, we test if it can be divided into multiple smaller static relations. As an example, the Freecell domain has the operator: move(?card↪ ?cols↪ ?ncols↪ ?cells↪ ?ncells) where there is a static relation between cols and ncols and between cells and ncells. The minimal static relation will be across all four of these parameters, where it would clearly be beneficial to identify two separate relations. In order to split the relation, we need to check the possible partitions of the parameters in the minimal static relation. Checking every partition is computationally prohibitive for actions with a large number of parameters. For this reason, we propose a pruning technique based on dominated partition refinements. A description of the algorithm is given in Algorithm 3.

3.3 Testing for Universality

As a final step, we test the static relations for universality. If a static relation is universal, then all instances share the same groundings for that relation. Intuitively, we collect all of the instances of the static relations found in the earlier stages of LOP and combine the groundings across instances. When we combine these ground instances, if the combined relation preserves optimality then we accept the relation as universal.

4 Evaluation

Our experimental setup is as follows: we used the Fast Downward [Helmert, 2006] planner, with the LMCut heuristic [Helmert and Domshlak, 2009] with a fifteen minute cutoff to find optimal plans to as many of the benchmark planning problems as possible. These form the optimal training plans needed for the static analysis. In our first experiment we have a set of plans which we know to be optimal and we use these plans for the LOP analysis. In our second experiment, we treat goal-directed plans that are not proven to be optimal the same way as we treat optimal plans in our previous analyses. For this, we use the LAMA planner [Richter and Westphal, 2010], with a 120 second time cutoff.

Table 1 shows the results of both experiments. Generally the results are very positive: of the domains that have static relations and had valid dynamic output from LOCM2, nine out of twelve had their static relations discovered error free. LOP can be seen as a LOCM-like system in that it produces an overly general result when incorrect. We now present a discussion of some of the more interesting results (more detail on individual domains is presented in [Gregory and Cresswell, 2015]). In the Driverlog domain, the structure of both statics are detected correctly. These are the roads that the trucks drive on and the path that the drivers can walk on. The paths are incorrectly identified as universal statics. We are unsure whether this happens because the path maps are completely consistent with the input data, or that the path maps are very dense, leading to many alternative route.

Zeno Travel encodes the possible transitions of the fuel level of the planes as universal static relations. These restrict the groundings of the fly, zoom and refuel operators. LOP successfully induces these relations in their scope and universality, and can be said in a way to improve on the original domain. In the original domain, the zoom operator, (zoom plane loc1 loc2 f3 f2 f1) encodes that the plane in question uses two units of fuel. The preconditions encode this as the two predicates (next f3 f2)↪ (next f2 f1). The static relation identified by LOP is between the two parameters f3 and f1 and ignores f2. This may initially be viewed as a mistake, but on closer inspection, the universal relation identified encodes the n plus two relation. The parameter f2 is, in fact, redundant. Summing up, our empirical analysis demonstrates that the LOP algorithm is effective at discovering static relations for a wide range of problems. We have also demonstrated domains in which LOCM2 fails to discover the correct domain dynamics, possibly suggesting new direction.

5 Conclusions

Domain model acquisition is useful whenever a knowledge engineer has access to a controllable system that acts, but for which the structure of those actions has not been formally specified. We have presented a solution to the problem of domain model acquisition under the presence of static relations. The LOP algorithm relies on the quality of the input plans serving as a guide to refining an overly general model generated by the LOCM2 system.