Liner Planning System – User Manual (Draft)

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.


1. Installation

1.1 Required Further Software

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
  1. Download the stable release of SWI-Prolog/XPCE for Linux (RPM package) from
  2. Convert the RPM package to a DEB package by calling alien as root, e.g.:
    # alien -v pl-5.6.40-290.i586.rpm
  3. Install the DEB package, e.g.:
    # dpkg -i pl_5.6.40-291_i386.deb
Download and install the stable release of SWI-Prolog/XPCE for MacOS X 10.4 from
dot 1.16 and 2.8 Package graphviz Fink package graphviz
Courier-Bold font for dot - Packages gsfonts Fink package msttcorefonts

The dot program must find the font. This requires that courier-bold.ttf is in the directory $DOTFONTPATH. A way to achieve this is by copying the font to some directory:

$ mkdir ~/my-fonts-for-dot
$ cp /sw/lib/X11/fonts/msttf/courbd.ttf ~/my-fonts-for-dot/courier-bold.ttf
and 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/ appropriately.

1.2 Setting up the System

The planning system is packed with the InfraEngine system.
  1. Unpack the distribution archive. A directory 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

2. Invocation

  1. Start SWI-Prolog and consult infra/src/
        ?- consult('~/infra/src/load_just_planner').

    A convenient alternative way to do this is running SWI-Prolog from Emacs, loading infra/src/ into an Emacs buffer and calling the Emacs function prolog-consult-file, which is possibly bound to "\C-c\C-l" in Prolog mode.

  2. The planner can then be controlled by evaluating Prolog queries.

    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.

3. Overview: Resource Oriented View of Planning

In this section we outline the basic concepts of the “resource oriented view” of planning that is adopted by our system. It is related to linear logic. As shown in [HölldoblerSchneeberger89], it is equivalent to the situation calculus, which was the original formulation of planning and is used as basis for many transition system languages, for example the NIST Process Specification Language (PSL). See [Fronhöfer96] for a precise account of the notion of planning rules adopted here.

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.

4. Rulebase

We call the set of planning rules used for a planning task a rulebase. The following definitions make this precise.
  1. A rulebase is a list of rules, facts and fluent declarations.

    Variables in elements of rulebase have scopes that just cover the respective element.

  2. A rule represents a planning rule. It is a term

    rule(Action, Consequent, Antecedent, Constraints)

    Variables can be shared between all the arguments of a rule.

  3. A fact asserts that a literal is consumable in unlimited amounts (or true in all states). It is a term

    fact(Fact, Constraints),

  4. A fluent declaration is a term
            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.)

  5. A literal is a non-variable term that represents a fluent (consumable and producible resource; possibly true at some states and false at others) or a fact (a resource that is consumable in unlimited amounts; always true).

    Literals whose main functor starts with $ are reserved for internal use.

5. Constraints

The planning system extend the basic linear backward chaining mechanism by support for constraint handling, which can for example be used to integrate arithmetic evaluation into planning.

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:

ActiveConstraints is an active constraint term, that is processed by a constraint handling module, which defaults to planner_cs_simple, described below.

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:

Arithmetics: =:=/2, >/2, </2, >=/2, =</2, =\=/2

=:=/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.

Term Operations: \=/2 (non-unifiability)

Atom number conversion: atom_number/2

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.

6. Predicates

plan(+Options, +GoalMultiset, +StartMultiset, +Constraints, +Rulebase)

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.

pool_literal(+Module, +Pool, ?Literal)

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).

7. Planning Options

The following options can be specified in the plan/5 predicate.

7.1 Planning Options: Plan Construction

Create a plan and bind Plan to it.

Create plan with partial-order information. Requires p(Plan).

7.2 Planning Options: Further Outputs

Bind Pool to a representation the pool (multiset of facts available for consumption) at the solution state. The predicate pool_literal/3 is provided to access these pool representations.

Bind Infs to the infs at the solution state. (Q: what are infs?)

7.3 Planning Options: Contrapositive Sorting

o1, o2, o3
Different ways of heuristic contrapositive sorting (o1 is the default).

Random contrapositive sorting.

7.4 Planning Options: Subgoal Sorting

Heuristic subgoal sorting (default).

No subgoal sorting (use as sorted in the input).

Random subgoal sorting.

7.5 Planning Options: Controlling Iterative Deepening

Use a depth bound for iterative deepening. Both bj and bd or none of them can be specified. (Q: what does this mean?)

Use an inference bound for iterative deepening. Both bj and bd or none of them can be specified.

If bd is present: use clause size instead of 1 to decrement depth value for iterative deepening.

If bj is present: use clause size instead of 1 to decrement inference count for iterative deepening.

Used at runtime to specify how depth and inference count are incremented. The following definition of the predicate
    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).

7.6 Planning Options: Constraint Handling

Take active constraints into account. Bind UnsolvedActiveConstraints, which must be a variable, to a active constraint term representing the unsolved constraints of the solution.

This option must be supplied to effect correct handling of active constraints.

Specify that Module is the module that implements constraint handling. The default is planner_cs_simple. Loading of the module must be ensured manually.

7.7 Planning Options: Incomplete Heuristics

Do not generate circular contrapositives. The planner is incomplete with this option!

Perform a cut after a subgoal can be solved by consuming a fact from the pool. The planner is incomplete with this option!

7.8 Planning Options: Handling Generated Code

Specifies how generated Prolog code is passed to the runtime system. If Output is a variable, it will be bound to the generated code as a list of terms. Otherwise, Output must be the name of a file, as atom, to which the generated code is written. Default is '/tmp/'.

Specifies the module where the generated code is installed. Default is out_planner.

Just install a precompiled file (specified by out(Filename)) and run the query. Intended for debugging with hand edited compiler outputs.

8. Examples

8.1 Example: Sussman Anomaly

The following predicate sussman/1 shows how a blocks world planning problem, the so-called Sussman anomaly is expressed. (This problem is also used as example in [Fronhöfer96].)

sussman(Plan) :-
	Options = [p(Plan), pxo, bd, o1, s1],
	GoalMultiset = [ on(a, b),
			 on(b, c) ],
	StartMultiset = [ on(b, table),
	                  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.

[Sussman Problem]

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]

8.2 Example: Partial-Order Planning

The system perform partial-order planning. The following predicate shoes/1 shows how the partial-order planning problem of putting on a pair of shoes from the Planning chapter of the book by Russell and Norvig [RussellNorvig02] can be expressed.
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]

8.3 Example: Constraints, Output Pool

The following predicate table/1 illustrates the use of constraints and the output pool.

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) ],
			   [] ),
		     fact( offered(table_board, 10), [] ),
		     fact( offered(table_leg, 5), [] )

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]

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]


Wolfgang Bibel. A deductive solution for plan generation. New Generation Computing, 4:115-132, 1986.
Bertram Fronhöfer. Cutting connections in linear connection proofs. In International Computer Symposium '96, pages 109-117, 1996.
Steffen Hölldobler and Josef Schneeberger. A New Deductive Approach to Planning. In GWAI-89: Proceedings of the 13th German Workshop on Artificial Intelligence, pages 63-73, Informatik Fachberichte 214, Springer, 1989
Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach (Second Edition). Prentice Hall, 2002. The chapter on planning is available at
Christoph Wernhard. Experiments with a linear backward chaining planner. Unpublished working paper, 1999. Available at

Christoph Wernhard (