Picat is a new constraint logic programming language that has obtained promising results in international competitions. These results have been achieved thanks to several features. The most e ective of them is an e cient handling of a tabling technique applied to search algorithms. A compiler from PDDL to Picat, which automatically enables to run PDDL models in Picat, has been recently developed. This paper describes a method which automatically optimizes the output of such a compiler, using a di erent representation of the states that better takes advantage of Picat's Tabling technique.
One of the rst and most important research areas in AI is planning. It deals with the search for a strategy, in order to resolve a speci c problem, in a given world with xed rules. The operation of nding this sequence of actions, performed by the planner, can be seen as the search for a path in a direct graph, where every node represents a state of the world, and every edge corresponds to an action.
The ancestor of modern planners is STRIPS (Stanford Research Institute
Problem Solver [
The popularity of planning was increasing, but there were no common
guidelines or modeling style, at least until the 1998, when PDDL (Planning Domain
De nition Language) was proposed [
Picat [
In this paper we propose a method, inspired by Planning Graph technique [
We assume the reader has a basic knowledge of Planning, PDDL, and Picat (Prolog-like) syntax.
State representation used in PDDL is known as Factored Representation: a state is identi ed by a set of atoms, i.e. a set of predicates denoting that some primitive properties of the world are true. An atom can be rigid, if it represents a never changing property (e.g. the fact that in location (x; y) there is a wall), or uent, that can be false or true depending on the current state (e.g. the fact that in location (x; y) at time t there is a robot). Below there is an example of a factored representation (inspired by the problem known as Nomystery ), encoded in PDDL and Picat, respectively: f a t ( t r u c k 1 , l o c 1 ) , . . . , c o n n e c t e d ( l o c 1 , l o c 2 ) g $ [ a t ( t r u c k 1 , l o c 1 ) , . . , c o n n e c t e d ( l o c 2 , l o c 3 ) ]
In a Structured Rapresentation the state is represented using internal data structures, such as lists or sets, and where it is possible it enables a reduction of the symmetries. The use of data structures is very suitable for the tabling technique used by Picat. In fact the states that are memorized during the plan seek can share common elements present in the structures used to represent them, reducing the usage of memory during the computation.
Considering the Nomystery domain described above, one of its possible structured state representations do not use the predicate connect, because it is a rigid predicate that describes the map and there is no need to replicate it in every state. However, it is possible to go further, memorizing the state simply as: s ( f l o c 1 , l o c 2 , l o c 3 g ) In this state representation the three trucks are directly encoded using their positions, avoiding the presence of symmetric states during the search. Since all the trucks are identical there will be no signi cant di erence among two equals states in which the position of two trucks is exchanged. E.g. one of the two states can be at(truck1; loc1); at(truck2; loc2) and the other one can be at(truck2; loc1); at(truck1; loc2). At the end \s" can have other arguments, e.g., storing the set of desired truck destinations, or other domain informations.
Picat implements two main search techniques to nd a plan: depth- rst
and resource-bounded. Both of the previously mentioned approaches exploit
the Picat's tabling technique that enables the planner to memorize the
visited states and thus to avoid the re-computation of already-visited branches. In
depth- rst, the solver keeps applying actions until it nds either a dead end,
an already-visited state or a goal state, otherwise it backtracks and it explores
other branches. In the second approach the planner adds a resource amount
value that is used by the planner as convenience measure to decide whether it is
advantageous to re-explore an already visited failing state. [
The goal of the optimization is to automatically transform a model based on
a factored state representation, inherited from PDDL and obtained using the
compiler presented in [
The main intention is to identify the rigid elements and the uent elements inside each main predicate (i.e., those that appear in the e ect of some action, the uent one) in order to reduce the size of them. At this point it is fundamental to distinguish the meaning of the adjectives rigid and uent. In the rst section these two attributes are used to classify the predicates in the domain. So, in this case the rigid elements represent the static information inside a single predicate, while the uent elements represent the dynamic information that evolves according to each action taken by the planner. As a matter of fact the predicate at(truck,location) from Nomystery encodes a static information: the name of the truck. Clearly the name of an entity is something that cannot evolve or change during the di erent explored states so it is possible to de ne it rigid. Instead the location of each truck is more meaningful, it can assume di erent values during the seek in order to nd the goal con guration. Thus each main predicate will be represented only by its uent elements and, where it is possible, some predicates are merged together if they were sharing the same rigid element at the beginning of the compiling phase. Then the state representation is changed accordingly, introducing a term whose arguments are sets of list, one for each new main predicate, and all the actions are modi ed to deal with the new data structures.
The underlying algorithm of the compiler can be split in two main parts. The rst one is a preprocessing step which is inspired by the Planning Graph technique. This step aims to \ground" as predicates as possible, starting from the initial problem state an iterative and terminating procedure tries to apply a xed number of actions in order to instantiate the larger possible number of predicates. In this iterative procedure an action is applied only once and it stops when a xed point is reached: there is no new action applicable to the current state or all the actions have been already applied. When the computational step has nished the analysis one starts. The goal of this last step is to identify the rigid elements inside each predicates performing an arithmetic mean of the positions of the elements that di er among the same grounded predicates. Then the analysis is lifted to the whole problem level working with all the elements of all the predicates at same time. The main idea that is behind this is step is to built a DAG of dependencies among all the predicates elements, thus, for each main predicates in the domains, there exists a directed edge from its rigid elements and its remaining elements that become temporary uent. At the end the DAG is used to modify the main predicates of the domain, holding the original de nition of the rigid predicates. The obtained result should be a more compact state representation since the static elements are deleted from the predicates, then the number of the predicates used can be reduced performing a merge between two predicates that shared the same rigid elements. 4
The e ect of the compiler optimization has been tested on three models as benchmarks: Floortile, Tetris, Nomystery, from the IPC list of benchmarks.
Nomystery
Instance Nomystery 0 Nomystery 1 Nomystery 2 Nomystery 3
SUM
Structured Factored Representation Representation bound time bound time(s) 6 1 6 2.70 9 18.96 9 34.04 13 159.05 13 376.13 15 125.58 15 421.43
304,59 834,30
Tetris Instance Tetris 0 Tetris 1 Tetris 2 Tetris 3 Tetris 4 Tetris 5
SUM Floortile Instance Floortile 0 Floortile 1 Floortile 2 Floortile 3 Floortile 4 Floortile 5
SUM
Structured Factored Representation Representation bound time bound time(s) 2 0 2 0 9 0.15 9 0.16 10 0.05 10 0.352 16 0.22 16 0.587 16 5.39 16 11.554 16 13.473 16 201.157
19.283 213.81
Structured Factored Representation Representation bound time bound time(s) 14 0.005 14 0.007 15 0.057 15 0.088 12 0.17 12 0.21 14 3.09 14 3.194 24 10.34 24 12.95 26 309.41 26 308.37
323.072 325.019
The computational results, reported in Table 1, highlight an improvement of the performance in all instances tested of Nomystery, Tetris and for the most one of Floortile. Focusing on the global time, obtained by the summation of all the times for a speci c problem, it can be observed how all the problems encoded using the optimization have better performance than the ones encoded with the factored representation. As for Nomystery and Tetris we have obtained an improvement of 60% and 90%, respectively. On the other hand, concerning the Floortile problem we have gained only 2 seconds in the global measurement. The running time required by the optimization process is on average around the 350 ms, thus, it is not an overhead for medium-big size problems.
We have also tested direct, manually optimized, Picat encodings of the three benchmarks. The running time on the instances tested are negligible (below 50ms | same results as state-of-the-art planners). Other work is needed to automatize the compiler process to lead to encodings with the same performances. Acknowledgments. We thank Roman Bartak and Neng-Fa Zhou for their help in various stages of this work. A. Dovier is partially supported by INdAM-GNCS 2015{2017 projects.