![[Sussman Problem]](images/sussman_problem.png)
The Liner planning system is a prototype implementation of the linear backward chaining (LBC) planning algorithm [Fronhöfer96], which is based on the linear connection method [Bibel86]. The system performs partial-order planning and includes a constraint handling interface, for example to integrate arithmetic evaluation. It runs in the SWI-Prolog environment. Outputs are represented by Prolog terms. Plans can also be displayed as images of graphs.
The system was originally written in 1999 in Eclipse-Prolog, has been ported to SWI-Prolog in 2002 and adapted to recent versions of SWI-Prolog in 2007. The 1999 Eclipse version of the system (called LBCP at that time) along with performance results is described in [Wernhard99]. The performance of the system is comparable to state-of-the-art planners around that time. The implementation proceeds by compiling planning tasks to Prolog code, similar to the Prolog Technology Theorem Prover (PTTP) by Mark Stickel.
Liner is embedded into InfraEngine, an experimental prototype of a Semantic Web inference engine with RDF interfaces.
It is released under the GNU General Public License.
The system has been tested on Debian Linux and Mac OS-X platforms, details on requirements are shown in the following table. It should be possible to install the system analogously also on other Linux platforms and on Windows with Cygwin.
| Software | Tested versions | For Debian 4.0 “etch” | For Mac OS-X 10.4 with Fink 0.8.1 |
|---|---|---|---|
| SWI-Prolog | 5.6.40 |
|
Download and install the stable release of SWI-Prolog/XPCE for MacOS X 10.4 from http://www.swi-prolog.org |
| dot | 1.16 and 2.8 | Package graphviz | Fink package graphviz |
| Courier-Bold font for dot | - | Packages gsfonts | Fink package msttcorefonts
The $ mkdir ~/my-fonts-for-dot $ cp /sw/lib/X11/fonts/msttf/courbd.ttf ~/my-fonts-for-dot/courier-bold.ttfand setting DOTFONTPATH e.g. by the following line
in ~/.bash_profile:
export DOTFONTPATH="${HOME}/my-fonts-for-dot"
|
| xli | 1.17 | Package xli | Fink package xli
Package xli is unfortunately only in unstable. You can also configure another program, for example display from package imagemagick, as viewer by modifying the entry config:config(planner_image_viewer, xli).in file infra/src/load_just_planner.pl
appropriately.
|
infra
is created. The source files can be found (along with the sources of
other modules of the InfraEngine system) in infra/src.
$ tar xzvf infra.tgz
infra/src/load_just_planner.pl:
?- consult('~/infra/src/load_just_planner').
A convenient alternative
way to do this is running SWI-Prolog from Emacs, loading
infra/src/load_just_planner.pl into an Emacs buffer and
calling the Emacs function prolog-consult-file, which
is possibly bound to "\C-c\C-l" in Prolog mode.
The system runs in the SWI-Prolog environment. It accepts as inputs Prolog terms that are read in by SWI-Prolog interpreter. Thus we describe the input syntax of the planning systems abstractly, with the notions term, atom, variable, non-variable term and list in the sense of the underlying Prolog system.
States and Actions. Executing an action leads from a state of the world to a successor state. A state is represented by a multiset of fluents, facts whose truth value is state dependent.
Planning Rules. The effects of an action are specified by a set of planning rules for that action. A planning rule has two main parts, its antecedent and its consequent. Both parts are multisets of fluents.
Operational Reading of Rules. The fluents in the antecedent are matched against the fluents in the initial state: for each fluent in the antecedent, a matching fluent in the state is removed. The fluents in the consequent are then added to the state, to yield the successor state. Matching is performed with unification: rules and states may contain logic variables which are bound during matching.
Fluents are considered as resources, objects that can be consumed and provided. A rule application means, that the fluents of the consequent are provided, after the fluents in the antecedent have been consumed.
Planning Tasks and Plans. Given a set of rules, a start state and a goal state, a planning task is to determine, whether there exists a sequence of rule applications that leads from the start to the goal state. A plan is the proof graph of such a solution. Its nodes are labeled by actions. An action in our system is represented by a term, that may share variables with its rules. The plan represents a partial ordering of action instances (i.e. nodes labeled with actions). Any sequence of action applications compatible with the partial ordering leads from the start to the goal state.
Variables in elements of rulebase have scopes that just cover the respective element.
Action terms whose main functor starts with $ are reserved for internal use.
The empty list as Antecedent is currently only supported if Consequent contains a single literal. The rule then is equivalent to a fact, except that the action is recorded in the plan.
Variables can be shared between all the arguments of a rule.
declare(fluent, Fluent),where Fluent is a literal.
This declaration is required to specify that Fluent is understood as a fluent (in contrast to a fact) in cases where Fluent does not occur in the Consequent of some rule. (It affects literals that unify with Fluent in the input states of a planning task.)
Literals whose main functor starts with $ are reserved for internal use.
Note: This was implemented before SWI-Prolog featured constraint handling rules, so it should probably be revised.
The Constraints argument of rules, facts and the predicate plan/5 is a list of constraint specifications of the following forms:
A Constraints argument may contain at most one occurrence of cs(ActiveConstraints).
The constraint handling module planner_cs_simple is a dummy implementation that just evaluates constraints as soon as they are sufficiently instantiated. (An experimental linear equation solver can be found as module planner_cs_linear in the source directory.) An active constraint term processed by planner_cs_simple is a list of terms whose meaning is analogous to the corresponding predicates in SWI-Prolog.
The following terms are supported:
=:=/2 is evaluated using is/2 as soon as one side is ground and the other a variable. If both sides are ground, it is evaluated using =:=/2. So arithmetic compound terms should only appear within the constraints, i.e., the planning rules should not bind variables to arithmetic compound terms.
Other terms just remain unsolved.
Heuristic hint that the constraint should fail if terms X and Y are instantiated to syntactically identical values. This is not enforced: arguments can be instantiated to identical values after explicit processing of the constraint has been performed.
Declare variable Variable as being of type
Type. Effects compilation
of Variable
into a functor wrapped variable.
Type can be an atom or list, e.g. t1 for
t1(X), and [t1, t2, t3] for
t1(t2(t3(X))). Non-variable objects have to be explicitly
written in the functor wrapped forms.
Call the planner on the task specified by the arguments.
Solutions are returned as bindings of variables in Planning Options. Alternative solutions are enumerated by Prolog backtracking.
The planner is complete in the sense that if a plan for the task exists, then it outputs a plan after a finite number of steps. Otherwise it may fail or not terminate.
This predicate is in module planner_run.
It can involve variables from both GoalMultiset and StartMultiset.
Enumerates the literals in the result pool of a planning task.
The generated code for the planning task code must still be installed in the module specified by Module.
This predicate is in module planner_run.
Displays a plan as a graph.
This predicate is in module planner_dotgraph.
This predicate makes use of the Graphviz system and an external program for image viewing. Its behavior can be configured by predicate config/2 in module config. Example settings are:
config:config(planner_dotgraph_fontname, 'Courier-Bold').
config:config(planner_dotgraph_fontsize, '11').
config:config(planner_image_viewer, xli).
gen_dj(+DJSpec, -Depth, -Inferences)
shows possible values of DJSpec and their effects:
gen_dj(d, N, M) :- maxdj(M), countup(0, N).
gen_dj(j, M, N) :- maxdj(M), countup(0, N).
gen_dj(d(B), N, M) :- maxdj(M), countup(B, N).
gen_dj(j(B), M, N) :- maxdj(M), countup(B, N).
gen_dj(dkj(K), K, J) :- countup(0, J).
gen_dj(djk(K), D, K) :- countup(0, D).
gen_dj(dkjk(D,J), D, J).
maxdj(N) :- prolog_flag(max_tagged_integer, N).
countup(N, N).
countup(N, N1) :- N2 is 1 + N, countup(N2, N1).
This option must be supplied to effect correct handling of active constraints.
planner_cs_simple.
Loading of the module must be ensured manually.
'/tmp/out_planner.pl'.out_planner.
sussman(Plan) :- Options = [p(Plan), pxo, bd, o1, s1], GoalMultiset = [ on(a, b), on(b, c) ], StartMultiset = [ on(b, table), clear(b), on(a, table), on(c, a), clear(c) ], Constraints = [], Rulebase = [ rule( puton(Block, From, To), [on(Block, To), clear(From), clear(Block)], [on(Block, From), clear(Block), clear(To) ], [] ), fact( clear(table), [] ) ], plan(Options, GoalMultiset, StartMultiset, Constraints, Rulebase).
The problem starts with b on the table, c on top of a, and a on the table. The agent must stack the blocks such that a is on top of b is on top of c.
Loading the definition of sussman/1 and invoking it from Prolog with
?- sussman(Plan), view_plan(Plan).effects that a plan is computed and displayed as image:
![[Sussman Plan]](images/sussman_plan.gif)
shoes(Plan) :- Options = [p(Plan), pxo, bd, o1, s1], GoalMultiset = [ shoe_on(right), shoe_on(left) ], StartMultiset = [ bare(right), bare(left) ], Constraints = [], Rulebase = [ rule( shoe(RL), [ shoe_on(RL) ], [ sock_on(RL) ], [] ), rule( sock(RL), [ sock_on(RL) ], [ bare(RL) ], [] ), declare(fluent, bare(_)) ], plan(Options, GoalMultiset, StartMultiset, Constraints, Rulebase).Some remarks on the differences of this formulation to that by Russell and Norvig:
Loading the definition of shoes/1 and invoking it from Prolog with
?- shoes(Plan), view_plan(Plan).effects that a partial-order plan is computed and displayed as image:
![[Shoes Plan]](images/shoes_plan.gif)
The goal of the plannng task is having a table. In the start situation there is a budget of 100 Euros. A solution is buying a table board and four table legs, and assembling these.
table(Plan, OutPool, OutConstraints) :- Options = [p(Plan), pool(OutPool), cs(OutConstraints), pxo, bd, o1, s1], GoalMultiset = [ have(table) ], StartMultiset = [ budget(100) ], InputConstraints = [], Rulebase = [ rule( buy(Object, Price), [ have(Object), budget(NewBudget) ], [ offered(Object, Price), budget(OldBudget) ], [ cs([NewBudget =:= OldBudget - Price]) ] ), rule( assemble_table, [ have(table) ], [ have(table_board), have(table_leg), have(table_leg), have(table_leg), have(table_leg) ], [] ), fact( offered(table_board, 10), [] ), fact( offered(table_leg, 5), [] ) ], plan(Options, GoalMultiset, StartMultiset, InputConstraints, Rulebase).
Loading the definition of table/3 and invoking it from Prolog with
?- table(Plan, _OutPool, _OutCs), view_plan(Plan).effects that a plan is computed and displayed as image:
![[Table Plan]](images/table_plan.gif)
The budget fluents create dependencies that prevent the generation of a partial-order plan abstracting from the order of the purchases.
The output pool contains a budget fluent representing the remaining budget. It can be accessed with the following query:
?- table(_Plan, OutPool, _OutCs), !, pool_literal(out_planner, OutPool, L).
...
L = budget(70)
Output constraints OutCs is the empty list, since all constraints can be evaluated. If, however, in the definition of table/3 the constraint of the rule for buy were instead defined as
[ cs([OldBudget =:= NewBudget + Price]) ]
then the planner_cs_simple constraint solver can not
evaluate them, and the following results would be obtained:
?- table(_Plan, OutPool, OutCs), !, pool_literal(out_planner, OutPool, L), pp(L-OutCs).
...
budget(A) -
[ B =:= A + 5,
C =:= B + 5,
D =:= C + 5,
E =:= D + 5,
100 =:= E + 10]
...