Logic programming provides a declarative framework for modeling and solving many combinatorial problems. Until recently, it was not competitive with state of the art planning techniques partly due to search capabilities limited to backtracking. Recent development brought more advanced search techniques to logic programming such as tabling that simplifies implementation and exploitation of more sophisticated search algorithms. Together with rich modeling capabilities this progress brings tabled logic programing on a par with current best planners. The paper brings an initial experimental study comparing various approaches to search for sequential plans in the Picat planning module.
Automated planning was an important area for Prolog. PLANNER [
For decades the so called domain-independent planning has been perceived
as the major direction of AI research with the focus on “physics-only” planning
domain models. This attitude is represented by International Planning
Competitions (IPC) [
IPC accelerated research in domain-independent planning by providing
encodings (domain models) for many benchmark problems. On the other hand, as
everyone is using IPC benchmark problems to evaluate the planners, there has
not been almost any research about how to encode the planning problems
efficiently. Also, though the role of domain knowledge is well known in planning [
Recently, tabling has been successfully used to solve specific planning
problems such as Sokoban [
Classical AI planning deals with finding a sequence of actions that change the world from some initial state to a goal state. We can see AI planning as the task of finding a path in a directed graph, where nodes describe states of the world and arcs correspond to state transitions via actions. Let γ(s, a) describe the state after applying action a to state s, if a is applicable to s (otherwise the function is undefined). Then the planning task is to find a sequence of actions ha1, a2, . . . , ani called a plan such that, s0 is the initial state, for each i ∈ {1, . . . , n}, ai is applicable to the state si−1 and si = γ(si−1, ai), and, finally, sn satisfies a given goal condition. For solving cost-optimization problems, each action has assigned a non-negative cost and the task is to find a plan with the smallest cost.
As the state space is usually huge, an implicit and compact representation
of states and actions is necessary. Since the time of Shakey, the robot [
In Picat we will preserve the state-transition nature of classical AI planning, but instead of factored representation we will use a structured representation of states. Like in the PDDL, each action will have pre-conditions verifying whether the action is applicable to a given state. However, the precondition can be any Picat call. The action itself will specify how the state should be changed; we will give some examples later. 3
Picat is a logic-based multi-paradigm programming language aimed for generalpurpose applications. Picat is a rule-based language, in which predicates, functions, and actors are defined with pattern-matching rules. Picat incorporates many declarative language features for better productivity of software development, including explicit non-determinism, explicit unification, functions, list comprehensions, constraints, and tabling.
In Picat, predicates and functions are defined with pattern-matching rules. Picat has two types of rules: a non-backtrackable rule (also called a commitment rule) Head, Cond => Body, and a backtrackable rule Head, Cond ?=> Body. In a predicate definition, the Head takes the form p(t1, . . . , tn), where p is called the predicate name, and n is called the arity. The condition Cond, which is an optional goal, specifies a condition under which the rule is applicable. For a call C, if C matches Head and Cond succeeds, then the rule is said to be applicable to C. When applying a rule to call C, Picat rewrites C into Body. If the used rule is non-backtrackable, then the rewriting is a commitment, and the program can never backtrack to C. However, if the used rule is backtrackable, then the program will backtrack to C once Body fails, meaning that Body will be rewritten back to C, and the next applicable rule will be tried on C.
Briefly speaking, Picat programming is very similar to Prolog programming.
By providing features like functions, list comprehensions etc., Picat programs are
even more compact and declarative than equivalent Prolog programs. Moreover,
the possibility of explicit non-determinism and unification gives the programmer
better control of program execution to make the code even more efficient. More
details about the Picat language can be found in the Picat documentation [
The Picat system provides a built-in tabling mechanism [
Mode-directed tabling has been successfully used to solve specific planning
problems such as Sokoban [
The call path(S,Path,Cost) binds Path to an optimal path from S to a final state. The predicate final(S) succeeds if S is a final state, and the predicate action encodes the set of actions in the problem. As mentioned in the previous section, the tabling mechanism supports solving optimization problems, such as looking for the shortest path, using the table modes min and max. When applied to the single-source shortest path problem, linear tabling is similar to Dijkstra’s algorithm, except that linear tabling tables shortest paths from the encountered states to the goal state rather than shortest paths to the encountered states from the initial state. When looking for the shortest path from a single initial state to some goal state only, such as in planning, classical tabling may be too greedy as it visits the states that could be farther from the initial state than the length of the shortest path from start to goal. Resource-bounded search is a way to overcome this inefficiency.
Assume that we know the upper bound for the path length, let us call it a resource. Each time, we expand some state, we decrease available resource by the cost of the action used for expansion. Hence less quantity of resource will be available for expansion of the next state (if action costs are positive). The idea of resource-bounded search is to utilize tabled states and their resource limits to effectively decide when a state should be expanded and when a state should fail. Let SR denote a state with an associated resource limit, R. If R is negative, then SR immediately fails. If R is non-negative and S has never been encountered before, then S is expanded by using a selected action. Otherwise, if the same state S has failed before and R0 was the resource limit when it failed, then SR is only expanded if R > R0, i.e., if the current resource limit is larger than the resource limit was at the time of failure. 4
The Picat system has a built-in module planner for solving planning problems. The planning problem is described as an abstract state transition diagram and solved using techniques exploiting tabling. By abstraction we mean that states and actions are not grounded, but described in an abstract way similar to modeling operators in PDDL. In this section we briefly introduce the planner module, give an example of planning domain model in Picat, and describe available search techniques to solve the planning problems. 4.1
The planner module is based on tabling but it abstracts away tabling from users. For a planning problem, users only need to define the predicates final/1 and action/4, and call one of the search predicates in the module on an initial state in order to find a plan or an optimal plan.
– final(S): This predicate succeeds if S is a final state. – action(S,N extS,Action,ACost): This predicate encodes the state transition diagram of a planning problem. The state S can be transformed to N extS by performing Action. The cost of Action is ACost, which must be non-negative. If the plan’s length is the only interest, then ACost = 1. These two predicates are called by the planner. The action predicate specifies the precondition, effect, and cost of each of the actions. This predicate is normally defined with nondeterministic pattern-matching rules. As in Prolog, the planner tries actions in the order they are specified. When a non-backtrackable rule is applied to a call, the remaining rules will be discarded for the call. 4.2
To demonstrate how the planning domain is encoded in Picat, we will use the
Transport domain from IPC’14. Given a weighted directed graph, a set of trucks
each of which has a capacity for the number of packages it can carry, and a set
of packages each of which has an initial location and a destination, the objective
of the problem is to find an optimal plan to transport the packages from their
initial locations to their destinations. This problem is more challenging than the
Nomystery problem that was used in IPC’11, because of the existence of multiple
trucks, and because an optimal plan normally requires trucks to cooperate. This
problem degenerates into the shortest path problem if there is only one truck
and only one package. We introduced the Picat model of this domain in [
A state is represented by an array of the form {Trucks,Packages}, where Trucks is an ordered list of trucks, and Packages is an ordered list of waiting packages. A package in Packages is a pair of the form (Loc,Dest) where Loc is the source location and Dest is the destination of the package. A truck in Trucks is a list of the form [Loc,Dests,Cap], where Loc is the current location of the truck, Dests is an ordered list of destinations of the loaded packages on the truck, and Cap is the capacity of the truck. At any time, the number of loaded packages must not exceed the capacity.
Note that keeping Cap as the last element of the list facilitates sharing, since the suffix [Cap], which is common to all the trucks that have the same capacity, is tabled only once. Also note that the names of the trucks and the names of packages are not included in the representation. Two packages in the waiting list that have the same source and the same destination are indistinguishable, and as are two packages loaded on the same truck that have the same destination. This representation breaks object symmetries – two configurations that only differ by a truck’s name or a package’s name are treated as the same state.
A state is final if all of the packages have been transported. final({Trucks,[]}) => foreach([_Loc,Dests|_] in Trucks)
Dests == [] end.
The PDDL rules for the actions are straightforwardly translated into Picat as follows.
action({Trucks,Packages},NextState,Action,ACost) ?=>
Action = $load(Loc), ACost = 1, select([Loc,Dests,Cap],Trucks,TrucksR), length(Dests) < Cap, select((Loc,Dest),Packages,PackagesR), NewDests = insert_ordered(Dests,Dest), NewTrucks = insert_ordered(TrucksR,[Loc,NewDests,Cap]),
NextState = {NewTrucks,PackagesR}, action({Trucks,Packages},NextState,Action,ACost) ?=>
Action = $unload(Loc), ACost = 1, select([Loc,Dests,Cap],Trucks,TrucksR), select(Dest,Dests,DestsR), NewTrucks = insert_ordered(TrucksR,[Loc,DestsR,Cap]), NewPackages = insert_ordered(Packages,(Loc,Dest)),
NextState = {NewTrucks,NewPackages}. action({Trucks,Packages},NextState,Action,ACost) =>
Action = $move(Loc,NextLoc), select([Loc|Tail],Trucks,TrucksR), road(Loc,NextLoc,ACost), NewTrucks = insert_ordered(TrucksR,[NextLoc|Tail]),
NextState = {NewTrucks,Packages}.
For the load action, the rule nondeterministically selects a truck that still has room for another package, and nondeterministically selects a package that has the same location as the truck. After loading the package to the truck, the rule inserts the package’s destination into the list of loaded packages of the truck. Note that the rule is nondeterministic. Even if a truck passes by a location that has a waiting package, the truck may not pick it. If this rule is made deterministic, then the optimality of plans is no longer guaranteed, unless there is only one truck and the truck’s capacity is infinite.
The above model is very similar to the PDDL encoding available at IPC web
pages [
The current resource() is a built-in function of the planner giving the maximal allowed cost-distance to the goal. Note that heuristic is a part of the domain model so it is domain dependent.
We discussed some domain modeling principles in [
The planning-domain model is specified as a set of Picat rules that are explored
by the Picat planner. This planner uses basically two search approaches to find
optimal plans. Both of them are based on depth-first search with tabling and
in some sense they correspond to classical forward planning. It means that they
start in the initial state, select an action rule that is applicable to the current
state, apply the rule to generate the next state, and continue until they find a
state satisfying the goal condition (or the resource limit is exceeded).
The first approach starts with finding any plan using the depth first search. The
initial limit for plan cost can (optionally) be imposed. Then the planner tries to
find a plan with smaller cost so a stricter cost limit is imposed. This process is
repeated until no plan is found so the last plan found is an optimal plan. This
approach is very close to branch-and-bound technique [
Despite using tabling that prevents re-opening the same state, this approach still requires good control knowledge to find the initial plan (otherwise, it may be lost in a huge state space) or alternatively some good initial cost limit should be used to prevent exploring long plans.
The second approach exploits the idea of iteratively extending the plan length
as proposed first for SAT-based planners [
Note that the cost limit in the above calls is used to define the function current resource() mentioned in the action rules. Briefly speaking the cost of the partial plan is subtracted from the cost limit to get the value of the function current resource() that can be utilized to compare with the heuristic distance to the goal. 5
The Picat planner uses a different approach to planning so it is important to show
how this approach compares with current state-of-the-art planning techniques
and to understand better the Picat search procedures. In [
domains used in the deterministic sequential track of IPC’14. All of the
encodings are available at: picat-lang.org/ipc14/. The Picat planner was using the
iterative deepening best plan/4 planning algorithm. We have compared these
Picat encodings with the IPC’14 PDDL encodings solved with SymBA. Table
1 shows the number of instances (#insts) in the domains used in IPC’14 and
the number of (optimally) solved instances by each planner. The results were
obtained on a Cygwin notebook computer with 2.4GHz Intel i5 and 4GB RAM.
Both Picat and SymBA were compiled using g++ version 4.8.3. For SymBA, a
setting suggested by one of SymBA’s developers was used. A time limit of 30
minutes was used for each instance as in IPC. For every instance solved by both
planners, the plan quality is the same. The running times of the instances are
not given, but the total runs for Picat were finished within 24 hours, while the
total runs for SymBA took more than 72 hours.
Domain Dependent Planners. We took the following domains: Depots,
Zenotravel, Driverlog, Satellite, and Rovers from IPC’02. The Picat encodings are
available at: picat-lang.org/aips02/. We compared Picat with TLPlan [
All planners found (possibly sub-optimal) plans for all benchmark problems and the runtime to generate plans was negligible; every planner found a plan in a matter of milliseconds. Hence we focused on comparing the quality of obtained plans that is measured by a so called quality score introduced in IPC. Briefly speaking the score for solving one problem is 1, if the planner finds the best plan among all planners; otherwise the score goes down proportionally to the quality of the best plan found. The higher quality score means an overall better system.
For TLPlan, TALPlanner, and SHOP2 we took the best plans reported in the results of IPC’02. Taking in account the nature of planners and their runtimes, there is a little hope to get better plans when running on the current hardware. For the Picat planner we used the branch-and-bound best plan bb/4 planning algorithm. Table 2 shows the quality scores when we gave five minutes to the Picat planner to improve the plan (running under MacOS X 10.10 on 1.7 GHz Intel Core i7 with 8 GB RAM).
The results show that the Picat planner is competitive with other
domaindependent planners and that it can even find better plans. In [
In the second experiment we focused on comparing two search approaches to find cost-optimal plans in Picat, namely branch-and-bound and iterative deepening. When looking for optimal plans, the hypothesis is that iterative deepening requires less memory and time because branch-and-bound explores longer plans and hence may visit more states. On the other hand, the advantage of branchand-bound is that it can find some plan even if finding (and proving) optimal plan is hard (recall, that iterative deepening returns only optimal plans). So the second hypothesis is that when looking for any plan, branch-and-bound could be a better planning approach. Nevertheless, due to depth-first-search nature, branch-and-bound requires good control knowledge to find an initial plan. The final hypothesis is that if none or weak control knowledge is part of the domain model then iterative deepening is a more reliable planning approach.
We used the following domains from the deterministic sequential track of
IPC’14 [
We first report the number of solved problems with respect to time and memory consumed. Note that best plan/4 and best plan bb/4 return costoptimal plans while plan/4 returns some (possibly sub-optimal) plan. Figure 1 shows the number of solved problems within a given time. Figure 2 shows the number of solved problems based on memory consumed.
The results confirm the first and second hypotheses, that is, iterative deepening requires less time and less memory than branch-and-bound when solving problems optimally, but branch-and-bound has the advantage of providing some (possibly sub-optimal) plan fast. If looking for any plan then branch-and-bound also requires less memory.
Describing dependence of planner efficiency on the model is more tricky as it is hard to measure model quality quantitatively. We annotated each involved domain model by information about using control knowledge and domaindependent heuristics in the model. Table 3 shows the annotation of domain models based on these two criteria.
Based on Table 3 we can classify the Picat domain models into following
groups:
– The Picat domain model for Barman is probably closest to the PDDL
encoding; it only uses the structured representation of states, which alone seems
to be advantage over PDDL as Table 1 shows. GED uses a bit specific model
based on a PDDL model different from that one used in the IPC – this model
uses some macro-actions – and hence it is not really tuned for Picat.
– Citycar and Tetris are domains where useful admissible heuristics are used,
but no control knowledge is implemented to guide the planner.
– The Picat domain models for Parking and Transport use some weak control
knowledge in the form of making selection of some actions deterministic (see
the example earlier in the paper). They also exploit admissible heuristics.
– Cave Diving, Childsnack, and Floortile are domains, where we use strong
control knowledge and no heuristics. Control knowledge is used there to
describe reasonable sequencing of actions either via finite state automata or
macro-actions. The domain model for Cave Diving is described in detail in
[
From each class of domain models we selected one representative to
demonstrate how different solving approaches behave (the other domains gave similar
results). Figure 3 shows the number of solved problems for these
representatives. If the Picat domain model is very close to the original PDDL model,
then iterative deepening has a clear advantage when finding optimal plans, see
the Barman domain. This corresponds to popularity of this solving approach in
planners based on SAT techniques [
Adding admissible heuristics makes iterative deepening even more successful, see the Tetris domain. Finding optimal plans by iterative deepening is close to finding any plan by branch-and-bound. Also the gap between finding any plan and finding an optimal plan by branch-and-bound is narrower there. Obviously, this also depends on the quality of first plan found.
An interesting though not surprising observation is that adding even weak control knowledge makes finding any plan by branch-and-bound much more successful and decreases further the gap between iterative deepening and branchFig. 3. The number of solved problems within a given time for specific domains. 36 and-bound when looking for optimal plans, see the Parking domain. The role of control knowledge is even more highlighted in the Childsnack domain, which shows that strong control knowledge has a big influence on efficiency of branchand-bound. Longer runtimes of iterative deepening are caused by exploring short plans that cannot solve the problem before discovering the necessary length of the plan to reach the goal. Still control knowledge helps iterative deepening to find a larger number of optimal plans though it takes longer than for branchand-bound.
The experimental results justify the role of control knowledge for solving planning problems and confirm the last hypothesis that control knowledge is important for the branch-and-bound approach especially if the dead-ends can be discovered only in very long plans. 6
This paper puts in contrast two approaches for searching for sequential plans,
iterative deepening used in [
This paper showed some preliminary results on the relations between various modeling and solving techniques for planning problems. The next step is a deeper study of influence of various modeling techniques on efficiency of planning. Acknowledgments. Research was supported by the Czech Science Foundation under the project P103-15-19877S. The authors would like to thank Agostino Dovier and Neng-Fa Zhou for providing some of the domain models in Picat.