Intelligent agents solving problems in the real-world require domain models containing widespread knowledge of the world. Synthesising operator descriptions and domain speci c constraints by hand for AI planning domain models is time-intense, error-prone and challenging. To alleviate this, automatic domain model acquisition techniques have been introduced. For example, the LOCM system requires as input some plan traces only, and is e ectively able to automatically encode the dynamic part of the domain model. However, the static part of the domain, i.e., the underlying structure of the domain that can not be dynamically changed, but that a ects the way in which actions can be performed is usually missed, since it can hardly be derived by observing transitions only. In this paper we introduce ASCoL, a tool that exploits graph analysis for automatically identifying static relations, in order to enhance planning domain models. ASCoL has been evaluated on domain models generated by LOCM for the international planning competition, and has been shown to be e ective.
Intelligent agents that solve problems in the real-world use models containing vast knowledge of that world to plan their actions. Designing complete domain models and gathering application knowledge is crucial not only for the e ciency of intelligent planning systems, but also for the correctness of the resulting action plans generated by intelligent agents. Creating such models is a di cult task, that is usually done manually; it requires planning experts and it is timeconsuming and error-prone.
In this paper we present ASCoL, (Automated Static Constraint Learner), a tool that can e ectively identify static knowledge by considering plan traces as the only source of information.
In the following sections, we rst provide a general background of the areas and concepts included in this research which is followed by the research question, problem, contribution, the developed system and system evaluation. The paper is concluded with a discussion of some future goals.
The term Planning refers to the process of reasoning about actions and then organizing those actions to accomplish a desired goal. It gives a full scheme for doing or accomplishing something. In Arti cial Intelligence (AI) terms this scheme is known as a Plan. Plan generation is considered an important property of intelligent behaviour. AI Planning has been a part of study in arti cial intelligence for over two decades.
Classical planning [
Knowledge Acquisition and Knowledge Engineering (KE) have been signi cant to Arti cial Intelligence (AI) research since the elds inception. Acquiring domain knowledge from input training data has attracted much interest in research.
The domain model acquisition problem has mainly been tackled by exploiting
two approaches. On the one hand, knowledge engineering tools for planning
have been introduced over time, for supporting human experts in modelling the
knowledge. Two particular examples are itSIMPLE [
One such knowledge acquisition tool is LOCM (Learning Object-Centred
Models) [
The LOCM method is unique in that it requires no prior knowledge and can
learn action schema without requiring any additional information about
predicates or initial, goal or intermediate state descriptions of objects for the example
action sequences. The exception to this is that LOCM e ectively determines the
dynamic part of the domain model of objects but not the static part i.e., the
underlying structure of the domain that can not be dynamically changed, but
that a ects the way in which actions can be performed.
1. Dynamic Knowledge: a set of parametrised operator schema representing
generic actions and resulting changes in the domain under study.
2. Static Knowledge: relationships/constraints that are implicit in the set of
operators and are not directly expressed but essentially are present while
de ning a domain model. These can be seen to appear in the preconditions
of operators only and not in the e ects. In simple words static facts never
change in the world. According to Wickler [
In many domains, there are static relationships or constraints which restrict the values of variables in domain modelling. For example learning the map of roads in transport domains or the xed card stacking rules between speci c cards in card-games domains, that never change with the execution of actions. 3
Our work is aimed at automating the acquisition of static constraints. We aim to enhance the LOCM system to learn complete domain models including the knowledge of static constraints by using sequences of plans as the only input training data. The static knowledge is not explicitly captured in the plan traces and so it is a big challenge to learn such static constraints from them.
We introduced ASCoL, an e cient and e ective tool for identifying static knowledge missed by domain models automatically acquired.
The proposed approach generates a directed graph for each pair of sametype arguments of operators and, by analysing linearity properties of the graphs, identi es relevant relations between arguments. Remarkably, the contributions of ASCoL, as demonstrated by our large experimental analysis, are: (i) the ability to identify di erent types of static relations, by exploiting graph analysis; (ii) ASCoL can work with both optimal and suboptimal plan traces; (iii) considering pairs of same-typed objects allows the identi cation of all the static relations considered in the benchmark models, and (iv) it can be a useful debugging tool for improving existing models, which can indicate hidden static relations helpful for pruning the search space.
A preliminary version of ASCoL has been presented in [
We de ne the learning problem that ASCoL addresses as follows. Given the knowledge about object types, operators and predicates, and a set of plan traces, how can we automatically identify the static relation predicates that are needed by operators' preconditions? We base our methodology on the assumption that plan traces contain tacit knowledge about constraints validation/acquisition.
Speci cally, a learning problem description is a tuple (P, T), where P is a set of plan traces and T is a set of types of action arguments in P (taken from the LOCM learnt domain model). The output for a learning problem is a constraint repository R that stores all admissible constraints on the arguments of each action A in plan traces P. 4
We now brie y present the ASCoL tool that has been developed for identifying useful static relations. The process steps can be summarised as follows: 1. Read the partial domain model (induced by LOCM) and the plan traces. 2. Identify, for all operators, all the pairs of arguments involving the same object types. 3. For each of the pairs, generate a directed graph by considering the objects involved in the matching actions from the plan traces. 4. Analyse the directed graphs for linearity and extract hidden static relations between arguments. 5. Run inequality check. 6. Return the extended domain model that includes the identi ed static relations.
The main information available for ASCoL comes from the input plan traces. As a rst control, we remove from the plan traces all the actions that refer to operators that do not contain at least two arguments of the same type.
Even though, theoretically, static relations can hold between objects of different types, they mostly arise between same-typed objects. This is the case in transport domains, where static relations de ne connections between locations. Moreover, considering only same-typed object pairs can reduce the computational time required for identifying relations. It is also worth noting that, in most of the cases where static relations involve objects of di erent types, this is due to a non-optimal modelling process. Furthermore, such relations can be easily identi ed by naively checking the objects involved in actions; whenever some objects of di erent type always appear together, they are likely to be statically related. 5
Remarkable results have been achieved in complex domains, with regards to the number of static relations. We considered fteen di erent domain models, taken either from IPCs1 or from the FF domain collection (FFd)2.
We selected domains that are encoded using di erent modelling strategies,
and their operators include more than one argument per object type. Table 1
shows the results of the experimental analysis. A detailed interpretation of
results can be found in the recent AI*IA publication. All domains but Gripper,
Logistics and Hanoi, exploit static relations. Input plans of these domains have
been generated by using the Metric-FF planner [
Interestingly, we observe that ASCoL is usually able to identify all the static relations of the considered domains. Moreover, in some domains it is providing 1 http://ipc.icaps-conference.org/ 2 https://fai.cs.uni-saarland.de/ho mann/ -domains.html additional static relations, which are not included in the original domain model. Remarkably, such additional relations do not reduce the solvability of problems, but reduce the size of the search space by pruning useless instantiations of operators. 6
We are considering several paths for future work. Grant, in [