arXiv:0912.2846v1 [cs.AI] 15 Dec 2009

Under consideration for publication in Theory and Practice of Logic Programming

1

Multi-valued Action Languages
with Constraints in CLP(FD) ∗
AGOSTINO DOVIER
Università di Udine,
Dipartimento di Matematica e Informatica
(e-mail: dovier@dimi.uniud.it)

ANDREA FORMISANO
Università di Perugia,
Dipartimento di Matematica e Informatica
(e-mail: formis@dmi.unipg.it)

ENRICO PONTELLI
New Mexico State University,
Department of Computer Science
(e-mail: epontell@cs.nmsu.edu)
submitted 5 January 2009; revised 9 October 2009; accepted 10 December 2009

Abstract
Action description languages, such as A and B (Gelfond and Lifschitz 1998), are expressive instruments introduced for formalizing planning domains and planning problem instances. The paper starts
by proposing a methodology to encode an action language (with conditional effects and static causal
laws), a slight variation of B, using Constraint Logic Programming over Finite Domains. The approach is then generalized to raise the use of constraints to the level of the action language itself.
A prototype implementation has been developed, and the preliminary results are presented and discussed.
To appear in Theory and Practice of Logic Programming (TPLP).
KEYWORDS: Action Description Languages, Knowledge Representation, Planning, Constraint Logic Programming

1 Introduction
The construction of intelligent agents that can be effective in real-world environments has
been a goal of researchers from the very first days of Artificial Intelligence. It has long
been recognized that an intelligent agent must be able to acquire, represent, and reason
with knowledge. As such, a reasoning component has been an inseparable part of most
agent architectures in the literature.
∗ This manuscript is an extended version of the paper “Multi-valued Action Languages with Constraints
in CLP(FD)” in the Proceedings of the International Conference on Logic Programming, pages 255–270,
Springer Verlag, 2007.

2

A. Dovier, A. Formisano, E. Pontelli

Although the underlying representations and implementations may vary between agents,
the reasoning component of an agent is often responsible for making decisions that are
critical to its existence.
Logic programming languages offer many properties that make them very suitable as
knowledge representation languages. Their declarative nature supports the modular development of provably correct reasoning modules (Baral 2003). Recursive definitions can be
easily expressed and reasoned upon. Control knowledge and heuristic information can be
declaratively and incrementally introduced in the reasoning process. Furthermore, many
logic programming languages offer a natural support for non-monotonic reasoning, which
is considered essential for common-sense reasoning (Lifschitz 1999). These features, along
with the presence of efficient inference engines (Apt 2003; Marriott and Stuckey 1998;
Simons 2000; Giunchiglia et al. 2004b; Gebser et al. 2007), make logic programming an
attractive paradigm for knowledge representation and reasoning.
In the context of knowledge representation and reasoning, a very important application of logic programming has been in the domain of reasoning about actions and change
and, more specifically, planning. Planning problems have been effectively encoded using
Answer Set Programming (ASP) (Baral 2003)—where distinct answer sets represent different trajectories leading to the desired goal. Other logic programming paradigms, e.g.,
Constraint Logic Programming over Finite Domains (CLP(FD)) (Jaffar and Maher 1994;
Apt 2003), have been used less frequently to handle problems in reasoning about actions (e.g., (Reiter 2001; Thielscher 2002a)). Comparably more emphasis has been placed
in encoding planning problems as (non-logic programming) constraint satisfaction problems (Lopez and Bacchus 2003).
Recent proposals on representing and reasoning about actions and change have relied on
the use of concise and high-level languages, commonly referred to as action description
languages; some well-known examples include the languages A and B (Gelfond and Lifschitz 1998)
and extensions like K (Eiter et al. 2004) and ADC (Baral et al. 2002). Action languages allow one to write propositions that describe the effects of actions on states, and to create
queries to infer properties of the underlying transition system. An action domain description is a specification of a planning domain using an action language.
The goal of this work is to explore the relevance of constraint solving and constraint logic
programming (Marriott and Stuckey 1998; Apt 2003) in dealing with action languages and
planning. The push towards this exploratory study came from recent investigations (Dovier et al. 2005;
Dovier et al. 2009a) aimed at comparing the practicality and efficiency of answer set programming versus constraint logic programming in solving various combinatorial and optimization problems. The study indicated that CLP offers a valid alternative, especially
in terms of efficiency, to ASP when dealing with planning problems. Furthermore, CLP
offers the flexibility of programmer-developed search strategies and the ability to handle
numerical constraints.
The first step, in this paper, is to illustrate a scheme that directly processes an action
description specification, in a language similar to B (Gelfond and Lifschitz 1998), producing a CLP(FD) program that can be used to compute solutions to the planning problem. Our encoding has some similarities to the one presented by Lopez and Bacchus
(Lopez and Bacchus 2003), although we rely on constraint logic programming instead of

Multi-valued Action Languages in CLP(FD)

3

plain constraint satisfaction (CSP), and our action language supports static causal laws
and non-determinism—while the work of Lopez and Bacchus is restricted to STRIPS-like
specifications.
While the first step relies on using constraints to compute solutions to a planning problem, the second step brings the expressive power of constraints to the level of the action
language, by allowing multi-valued fluents and constraint-producing actions to be used in
the domain specification. The extended action language (named B MV ) can be as easily
supported by the CLP(FD) framework, and it allows a declarative encoding of problems
involving actions with resources, delayed effects, and maintenance goals. These ideas have
been developed in a prototype, and some preliminary experiments are reported.
We believe that the use of CLP(FD) can greatly facilitate the transition of declarative extensions of action languages to concrete and effective implementations, overcoming some
inherent limitations (e.g., efficiency and limited handling of numbers) of other logic-based
systems (e.g., ASP).
The presentation is organized as follows. The first part of our paper (Sections 2 and 3)
provides an overview of the action language B and illustrates our approach to modeling
problem specifications in B using constraints and constraint logic programming. Section 4
provides motivations for the proposed multi-valued extensions. Section 5 introduces the
full syntax of the new language B MV . The action language B MV expands the previous
language to a language with constraints and multi-valued fluents, that enables the use of
dynamic and static causal laws (a.k.a. state constraints), executability conditions, and nonMarkovian forms of reasoning with arbitrary relative or absolute references to past and
future points in time. The semantics and the abstract implementation of B MV is incrementally developed in Section 6, where we first consider a sub-language not involving
non-Markovian references, and later we extend it to the full B MV . A concrete implementation in CLP(FD) is described in Section 7, and an experimental evaluation is discussed
in Section 8. Section 9 presents an overview of related efforts appeared in the literature,
while Section 10 presents conclusions and the directions for future investigation.

2 The Action Language B
“Action languages are formal models of parts of the natural language that are used for
talking about the effects of actions” (Gelfond and Lifschitz 1998). Action languages are
used to define action descriptions that embed knowledge to formalize planning problems.
In this section, we use the same variant of the language B used in (Son et al. 2001)—see
also Section 9 for a comparison. With a slight abuse of notation, we simply refer to this
language as B.

2.1 Syntax of B
An action signature consists of a set F of fluent names, a set A of action names, and
a set V of values for fluents in F . In this section, we consider Boolean fluents, hence

4

A. Dovier, A. Formisano, E. Pontelli

V = {0, 1}.1 A fluent literal is either a fluent f or its negation neg(f ). Fluents and actions
are concretely represented by ground atomic formulae p(t1 , . . . , tm ) from an underlying
logic language L. For simplicity, we assume that the set of terms is finite—e.g., either there
are no function symbols in L, or the use of functions symbols is restricted, for instance by
imposing a fixed maximal depth on the nesting of terms, to avoid the creation of arbitrary
complex terms.
The language B allows us to specify an (action) domain description D. The core components of a domain description are its fluents—properties used to describe the state of
the world, that may dynamically change in response to execution of actions—and actions—denoting how an agent can affect the state of the world. Fluents and actions are
introduced by assertions of the forms fluent(f ) and action(a). An action description D relates actions, states, and fluents using axioms of the following types —where
[list-of-conditions] denotes a list of fluent literals:2
• causes(a, ℓ, [list-of-conditions]): this axiom encodes a dynamic causal
law, describing the effect (i.e., truth assignment to the fluent literal ℓ) of the execution
of action a in a state satisfying the given conditions
• caused([list-of-conditions], ℓ): this axiom describes a static causal law—
i.e., the fact that the fluent literal ℓ is true in any state satisfying the given preconditions.
Moreover, preconditions can be imposed on the executability of actions by means of assertion of the forms:
• executable(a, [list-of-conditions]): this axiom asserts that, for the action a to be executable, the given conditions have to be satisfied in the current state.
A domain description is a set of static causal laws, dynamic laws, and executability
conditions. A specific planning problem hD, Oi contains a domain description D along
with a set O of observations describing the initial state and the desired goal:
• initially(ℓ) asserts that the fluent literal ℓ is true in the initial state
• goal(ℓ) asserts that the goal requires the fluent literal ℓ to be true in the final state.
In the specification of an action theory, we can take advantage of a Prolog-like syntax to
express in a more succinct manner the laws of the theory. For instance, to assert that in the
initial state all fluents are true, we can simply write the following rule:
initially(F) :- fluent(F).

instead of writing a fact initially(f ) for each possible fluent f . Remember that the
notation H : − B1 , . . . , Bk is a syntactic sugar for the logical formula
∀X1 · · · Xn (B1 ∧ · · · ∧ Bk → H)
where X1 , . . . , Xn are all the variables present in H, B1 , . . . , Bk .
1
2

For simplicity, we use 0 to denote false and 1 to denote true. Consequently, we often say that a fluent is true
(resp., false) if its value is 1 (resp., 0).
We will sometimes write true as a synonymous for the empty list of conditions.

Multi-valued Action Languages in CLP(FD)

5

%% Some Type Information
barrel(5).
barrel(7).
barrel(12).
liter(0).
liter(1).
.
.
.
liter(12).
%% Identification of the fluents
fluent(cont(B,L)):- barrel(B), liter(L), L ≤ B.
%% Identification of the actions
action(fill(X,Y)):- barrel(X), barrel(Y), X 6= Y.
%% Dynamic causal laws
causes(fill(X,Y), cont(X,0), [cont(X,LX), cont(Y,LY)]) :action(fill(X,Y)), fluent(cont(X,LX)),
fluent(cont(Y,LY)), Y-LY ≥ LX.
causes(fill(X,Y), cont(Y,LYnew), [cont(X,LX), cont(Y,LY)]) :action(fill(X,Y)), fluent(cont(X,LX)),
fluent(cont(Y,LY)), Y-LY ≥ LX, LYnew is LX+LY.
causes(fill(X,Y), cont(X,LXnew), [cont(X,LX), cont(Y,LY)]) :action(fill(X,Y)), fluent(cont(X,LX)),
fluent(cont(Y,LY)), LX ≥ Y-LY, LXnew is LX-Y+LY.
causes(fill(X,Y), cont(Y,Y), [cont(X,LX), cont(Y,LY)]) :action(fill(X,Y)), fluent(cont(X,LX)),
fluent(cont(Y,LY)), LX ≥ Y-LY.
%% Executability conditions
executable(fill(X,Y), [cont(X,LX), cont(Y,LY)]) :action(fill(X,Y)), fluent(cont(X,LX)),
fluent(cont(Y,LY)), LX > 0, LY < Y.
%% Static causal laws caused([cont(X,LX)], neg(cont(X,LY))) :fluent(cont(X,LX)), fluent(cont(X,LY)),
barrel(X), liter(LX), liter(LY), LX6=LY.
%% Description of the initial and goal state
initially(cont(12,12)).
initially(cont(7,0)).
initially(cont(5,0)).
goal(cont(12,6)).
goal(cont(7,6)).
goal(cont(5,0)).

Fig. 1. B description of the 12-7-5 barrels problem.
Example 1
Figure 1 presents an encoding of the three-barrel planning problem using the language B.
There are three barrels of capacity N (an even number), N/2+1, and N/2−1, respectively.
At the beginning, the largest barrel is full of wine while the other two are empty. We wish
to reach a state in which the two larger barrels contain the same amount of wine. The only
permissible action is to pour wine from one barrel to another, until the latter is full or the
former is empty. Figure 1 shows the encoding of the problem for N = 12. Notice that we
also require that the smallest barrel is empty at the end. 
2.2 Semantics of B
If f ∈ F is a fluent, and S is a set of fluent literals, we say that S |= f if and only if f ∈ S
and S |= neg(f ) if and only if neg(f ) ∈ S. A list of literals L = [ℓ1 , . . . , ℓm ] denotes

6

A. Dovier, A. Formisano, E. Pontelli

a conjunction of literals, hence S |= L if and only if S |= ℓi for all i ∈ {1, . . . , m}.
We denote with ¬S the set {f ∈ F : neg(f ) ∈ S} ∪ {neg(f ) : f ∈ S ∩ F }. A
set of fluent literals is consistent if there is no fluent f s.t. S |= f and S |= neg(f ).
If S ∪ ¬S ⊇ F then S is complete. A set S of literals is closed w.r.t. a set of static
laws SL = {caused(C1 , ℓ1 ), . . . , caused(Cm , ℓm )}, if for all i ∈ {1, . . . , m} it holds
that S |= Ci implies S |= ℓi . The set CloSL (S) is defined as the smallest set of literals
containing S and closed w.r.t. SL. CloSL (S) is uniquely determined and not necessarily
consistent.
The semantics of an action language on the action signature hV, F , Ai is given in terms
of a transition system hS, ν, Ri (Gelfond and Lifschitz 1998), consisting of a set S of
states, a total interpretation function ν : F × S → V (in this section V = {0, 1}), and
a transition relation R ⊆ S × A × S.
Given a transition system hS, ν, Ri and a state s ∈ S, let:
Lit(s) =

{f ∈ F : ν(f, s) = 1} ∪ {neg(f ) : f ∈ F , ν(f, s) = 0}.

Observe that Lit(s) is consistent and complete.
Given a set of dynamic laws {causes(a, ℓ1 , C1 ), . . ., causes(a, ℓm , Cm )} for the action a ∈ A and a state s ∈ S, we define the (direct) effects of a in s as follows:
E(a, s) = {ℓi : 1 6 i 6 m, Lit(s) |= Ci }.
The action a is said to be executable in a state s if it holds that
Lit(s) |=

h
_

Ci ,

(1)

i=1

where executable(a, C1 ), . . ., executable(a, Ch ) for h > 0, are the executability axioms for the action a in D. Observe that multiple executability axioms for the same action
a are considered disjunctively. Hence, for each action a, at least one executable axiom must
be present in the action description.3
Let D be an action description defined on the action signature hV, F , Ai, composed of
dynamic laws DL, executability conditions EL, and static causal laws SL.
The transition system hS, ν, Ri described by D is a transition system such that:
• S is the set of all states s such that Lit(s) is closed w.r.t. SL;
• R is the set of all triples hs, a, s′ i such that a is executable in s and
Lit(s′ ) =

CloSL (E(a, s) ∪ (Lit(s) ∩ Lit(s′ )))

(2)

Let hD, Oi be a planning problem instance, where {ℓ | initially(ℓ) ∈ O} is a consistent and complete set of fluent literals. A trajectory in hS, ν, Ri is a sequence
hs0 , a1 , s1 , a2 , · · · , aN , sN i
such that hsi , ai+1 , si+1 i ∈ R for all i ∈ {0, . . . , N − 1}.
3

Observe that even if an action is “executable”, its execution may lead to an inconsistent state (which effectively prevents the use of such action in that context). Even though “enabled” would be a better term to use
for an action that can be executed in a state, we prefer to maintain the same terminology as used for B in
(Son et al. 2001)—see also Remark 2.

Multi-valued Action Languages in CLP(FD)

7

A sequence of actions ha1 , . . . , aN i is a solution (a plan) to the planning problem hD, Oi
if there is a trajectory hs0 , a1 , s1 , . . . , aN , sN i in hS, ν, Ri such that:
• Lit(s0 ) |= r for each initially(r) ∈ O, and
• Lit(sN ) |= ℓ for each goal(ℓ) ∈ O.
The plans characterized in this definition are sequential—i.e., we disallow concurrent actions. Observe also that the desired plan length N is assumed to be given.
Remark 1
In this paper we focus on sequential plans only. Hence, we assume that only one action is
executed in each state transition composing a given trajectory.
Note that the constraint-based encoding we will propose in the rest of this manuscript
can be easily adapted to deal with concurrent actions. Nevertheless, we have opted to ignore
this aspect in this manuscript, to avoid further complications of notation, and dealing with
issues of concurrency goes beyond the scope of this paper. The interested reader is referred
to (Dovier et al. 2009b) for some further considerations on this matter.
Remark 2
Notice that the satisfaction of (1) is just a necessary requirement for the executability of an
action and it might not represent a sufficient precondition. Indeed, as far as the definition
of transition system is considered, it is easy to see that, even if (1) is satisfied for certain a
and s, the execution of a in s might be inhibited because of the contradictory effects of the
causal laws. A simple example is represented by the following action description D:
executable(a,[]).
causes(a,f ,[]).
causes(a,neg(f ),[]).

The action a is always executable (according to its executability law), but the execution of
a would yield an inconsistent situation. Indeed, the execution of a does not correspond to
any state transition in the transition system described by D.
The above example also suggests a possible extension of the action description language
that involves laws of the form
nonexecutable(a, D).

The semantics for such an extended action language can be defined by replacing the condition (1), with the following one:
Lit(s) |=

h
_

i=1

Ci ∧ ¬

k
_

Dj ,

j=1

where executable(a, C1 ), . . ., executable(a, Ch ) and nonexecutable(a, D1 ),
. . ., nonexecutable(a, Dk ), for h > 0 and k > 0, are defined for the action a. Thus, the
action a is executable only if at least one of the Ci s is satisfied and all Dj s are unsatisfied
in the state s.
An alternative interpretation of the nonexecutable axioms can be adopted. Namely,
the law nonexecutable(a, D) can be considered simply as shorthand for the pair of

8

A. Dovier, A. Formisano, E. Pontelli
FromState
✩
✬
u ✉
Fℓ1
Aa
1

Fℓup ✉

✫

✲

ToState
✬
✉Fℓv1

✉Fℓvp
Pm
✪
✫
i=1 Aai = 1
Aam ✲

✩
✪

Fig. 2. Action constraints from state to state. (The states are described by p fluents,
ℓ1 , . . . , ℓp , and one among m possible actions is executed.)
dynamic causal laws causes(a, f , D) and causes(a, neg(f ), D). (Actually, this
possibility also applies to the languages proposed in (Gelfond and Lifschitz 1998)).
This shows that (non)executability laws do not increase the expressive power of the
action language. Nevertheless, the availability of both types of laws permits the direct and
explicit formalization of preconditions for actions execution.
3 Modeling B and Planning Problems Using Constraints
Let us describe how action descriptions are mapped to finite domain constraints. We will
focus on how constraints can be used to model the possible transitions from each individual
state of the transition system.
3.1 Modeling an Action Theory as Constraints
Let us consider a domain description D and the state transition system described by D.
Let us also denote with u and v the starting and ending states of an arbitrary transition of
such a system. We assert constraints that relate the truth value of fluents in u and v. This is
intuitively illustrated in Figure 2, where u = FromState and v = ToState.4
A Boolean variable is introduced to describe the truth value of each fluent literal in a
state. The value of a fluent literal ℓ in u is represented by the variable Fℓu ; analogously,
its value in the destination state v is represented by the variable Fℓv . For the sake of simplicity, we will freely refer to these variables as Boolean entities—and compose them with
logical connectives to form Boolean expressions—as well as 0/1 variables—and compose
them with arithmetic operators. Concrete CLP(FD) systems, e.g., SICStus, ECLiPSe, and
BProlog,5 enable this type of alternative perspectives, providing basic primitive constraints
(e.g., #= and #>) and Boolean compositions of constraints.
Given a conjunction of literals α = [ℓ1 , . . . , ℓm ] we will denote with αu the expression
u
Fℓ1 ∧. . .∧Fℓum . We will also introduce, for each action a, a Boolean variable Aua , representing whether the action is executed or not in the transition from u to v under consideration.
4
5

For the sake of readability, the two variables named FromState and ToState are also used in the concrete
implementation of B (cf., Section 3.3 and Figure 6).
Web
sites
for
some
CLP(FD)
systems.
SICStus:
www.sics.se/sicstus.html,
ECLiPSe: http://87.230.22.228/, BProlog: http://www.probp.com/

Multi-valued Action Languages in CLP(FD)

Dynuℓ

↔

mℓ
_

(αuℓ,j ∧ Auai

hℓ
_

v
γℓ,j

ℓ,j

)

9

(3)

j=1

Statvℓ

↔

(4)

j=1

Firedu,v
ℓ
Fℓv

↔
↔

Dynuℓ ∨ Statvℓ

(5)

¬Firedu,v
∨ ¬Firedu,v
ℓ
ℓ̄

(6)

Firedu,v
∨ (¬Firedu,v
∧ Fℓu )
ℓ
ℓ̄

(7)

Fig. 3. The constraint Cℓu,v for the fluent literal ℓ (cf., Section 3.1).
Given a specific fluent literal ℓ, we develop constraints that determine when Fℓv is true
and false. Let us consider the dynamic causal laws that have ℓ as a consequence:
causes(aiℓ,1 , ℓ, αℓ,1 )

···

causes(aiℓ,mℓ , ℓ, αℓ,mℓ )

Let us also consider the static causal laws related to ℓ
caused(γℓ,1 , ℓ)

···

caused(γℓ,hℓ , ℓ)

Finally, for each action a we will have its executability conditions:
executable(a, δa,1 )

···

executable(a, δa,pa )

Figure 3 describes the Boolean constraints that can be used in encoding the relations that
determine the truth value of the fluent literal ℓ. In the table, we denote with ℓ̄ the complement of literal ℓ, i.e., if ℓ is the fluent f , then ℓ̄ is neg(f ), while if ℓ is the literal neg(f )
then ℓ̄ is the fluent f . The intuitive meaning of the constraints is as follows:
(3) This constraint states that dynamic causal laws making ℓ true can fire if their conditions
are satisfied and the corresponding actions are chosen for execution.
(4) This constraint captures the fact that at least one of the static causal laws that make f
true is applicable.
(5) This constraint expresses the fact that a fluent literal ℓ can be made true during a
transition form state u to state v, either by a dynamic causal law (determined by Dynuℓ )
or a static causal law (determined by Statvℓ ).
(6) This constraint is used to guarantee consistency of the action theory—in no situations
a fluent and its complement are both made true.
(7) This constraint expresses the fact that a fluent literal ℓ is true in the destination state
if and only if it is made true (by a static or a dynamic causal law) or if is true in the
initial state and its truth value is not modified by the transition (i.e., inertia). Observe the
similarity between this constraint and the successor state axiom commonly encountered
in situation calculus (Levesque et al. 1998).
We will denote with Cℓu,v the conjunction of such constraints.
Given an action domain specification over the signature hV, F , Ai and two states u and
u,v
v, we introduce the system of constraints CF
which includes:
• for each fluent literal ℓ in the language of F , the constraints Cℓu,v .

10

A. Dovier, A. Formisano, E. Pontelli
• the constraint
X

Aua = 1

(8)

a∈A

• for each action a ∈ A, the constraints
Aua →

pa
_

u
δa,j
.

(9)

j=1

Notice that the sequentiality of the plan if imposed through the constraint (8), while constraint (9) reflects actions’ executability conditions.
3.2 Soundness and Completeness Results
Let us proceed with the soundness and completeness proofs of the constraint-based encoding. Consider a state transition from the state u to the state v and the corresponding
constraint Cfu,v described earlier.
Let S = Lit(u) and S ′ = Lit(v) be the sets of fluent literals that hold in u and v, respectively. Note that, from any specific S (resp., S ′ ), we can obtain a consistent assignment σS
(resp., σS ′ ) of truth values for all the variables Ffu (resp., Ffv ) of u (resp., v). Conversely,
each truth assignment σS (resp., σS ′ ) for all variables Ffu (resp., Ffv ) corresponds to a
consistent and complete set of fluents S (resp., S ′ ).
Regarding the occurrence of actions, recall that in each state transition a single action a
occurs and its occurrence is encoded by a specific Boolean variable, Aua . Let σa denote the
assignment of truth values for such variables such that σa (Aua ) = 1 if and only if a occurs
in the state transition from u to v.6 Note that the domains of σS , σS ′ , and σa are disjoint,
so we can safely denote with σS ◦ σS ′ ◦ σa the composition of the three assignments. With
a slight abuse of notation, in what follows we will denote with E the direct effects E(a, u)
of an action a in u. Observe that E ⊆ S ′ .
Theorem 1 states the completeness of the system of constrains introduced in Section 3.1.
It asserts that for any given D = hDL, EL, SLi, if a triple hu, a, vi belongs to the transition
u,v
.
system described by D, then the assignment σ = σS ◦ σS ′ ◦ σa satisfies the constraint CF
Theorem 1 (Completeness)
Let D = hDL, EL, SLi. If hu, a, vi belongs to the transition system described by D, then
u,v
.
σS ◦ σS ′ ◦ σa is a solution of the constraint CF
Proof
In constraints (3)–(7) of Figure 3 and (8)–(9) defined at the end of Subsection 3.1, a number
of auxiliary constraint variables are defined, whose values are uniquely determined once
the values of the fluents are assessed. In other words, when S, S ′ , and a are fixed, the
substitution σS ◦ σS ′ ◦ σa uniquely determines the value of the right-hand sides of the
constraints (3)–(5). To prove the theorem, we need to verify that if S ′ = CloSL (E ∪ (S ∩
S ′ )), then the constraints (6) and (7) along with the constraints about the action variables
Aua (i.e., constraints of the form (8) and (9)) are satisfied for every fluent f .
6

We will use mapping applications either as σ(X) or in postfix notation as Xσ.

Multi-valued Action Languages in CLP(FD)

11

Let us observe that (8) is equivalent to say that if Aa is true (Aa = 1) then Ab is false for
all b 6= a. Moreover, it also states that if all Ab for b 6= a are false then Aa is true. Namely,
(8) is equivalent to the conjunction, for a ∈ A of:
^
¬Ab
Aa ↔
b∈A\{b}

Let us start by looking at the action occurrence. Let a be the action executed in state u,
thus σa = {Aua /1} ∪ {Aub /0 | b 6= a}. Hence, (8) is satisfied by σa .
Similarly, since the semantics require that actions are executed only if the executability
conditions are satisfied, it holds that S |= δa,h (for at least one h ∈ {1, . . . , pa }, correWpa u
δa,j is
sponding to a condition executable(a, δa,h ) in SL). This quickly leads to j=1
true, and this allows us to conclude that (9) is satisfied by σS ◦ σa .
Let us now consider the constraints dealing with fluents. We recall that S ′ is a set of
fluent literals that is consistent, complete, and closed w.r.t. SL. Let us consider a fluent f
and let us prove that constraint (6) of Figure 3 is satisfied. Assume, by contradiction, that
u,v
u,v
Firedf σ and Firedneg(f ) σ are both true. Four cases must be considered:
1. Dynuf σ and Dynuneg(f ) σ are true. Since these values are determined by u, a, v, this means
that both f and neg(f ) belong to E(a, u). Since the closure under SL is monotonic this
means that Lit(v) = S ′ is inconsistent, representing a contradiction.
2. Dynuf σ and Statvneg(f ) σ are true. This means that f is in E(a, u) and neg(f ) is added
to S ′ by the closure operation. This implies that S ′ is inconsistent, which represents a
contradiction.
3. Statvf σ and Dynuneg(f ) σ are true. This leads a contradiction as in the previous case.
4. Statvf σ and Statvneg(f ) σ are true. This means that f and neg(f ) are added to S ′ by the
closure operation. Thus, S ′ is inconsistent, which is a contradiction.
It remains to prove that constraint (7) is satisfied by σ. Let us assume that f ∈ S ′ . Thus,
Ffv σS ′ is true. Three cases must be considered.
1. f ∈ E(a, u). This means that there is a dynamic causal law causes(a, f, αf,i ) where
S |= αf,i . From the definition, this leads to αuf,i σ being true and σa (Aua ) = 1. Thus,
constraints (3) and (5) set Dynuf σ and Firedu,v
f σ both true. As a consequence, constraint
(7) is satisfied.
2. f ∈
/ E(a, u) and f ∈ S. This means that f ∈ S ∩ S ′ . In this case Firedu,v
neg(f ) σ must be
false, otherwise S ′ would be inconsistent (by closure). Thus, Ffu σS should be true, Ffv σS ′
is true and Firedu,v
neg(f ) σ is false, which satisfy constraint (7) (regardless of the value of
u,v
Firedf σ).
3. f ∈
/ E(a, u) and f ∈
/ S. This means that f is inserted in S ′ by closure. Thus, there is a
static causal law of the form caused(γf,j , f ) such that S ′ |= γf,j . In this case, by (4),
u,v
Statvf σ is true and, by (5), so is Firedf σ. Thus, constraint (7) is satisfied.
If f ∈
/ S ′ , then neg(f ) ∈ S ′ and the proof is similar with positive and negative roles
interchanged.
Let us observe that the converse of the above theorem does not necessarily hold. The
problem arises from the fact that the implicit minimality in the closure operation is not

12

A. Dovier, A. Formisano, E. Pontelli

reflected in the computation of solutions to the constraint. Consider the domain description
where F = {f, g, h} and A = {a}, with the following laws:
executable(a,[]).
causes(a,f ,[]).

caused([g],h).
caused([h],g).

Let us consider S = {neg(f ), neg(g), neg(h)}. Then, S ′ = {f , g, h} determines a
u,v
solution of the constraint CF
with the execution of action a, but CloSL (E ∪ (S ∩ S ′ )) =
′
{f } ⊂ S . However, the following holds:
Theorem 2 (Weak Soundness)
u,v
. Then
Let D = hDL, EL, SLi. Let σS ◦ σS ′ ◦ σa identify a solution of the constraint CF
′
′
CloSL (E(a, u) ∪ (S ∩ S )) ⊆ S .
Proof
It is immediate to see that σS and σS ′ uniquely determines two consistent and complete
sets of fluent literals u and v. Let f be a positive fluent in CloSL (E(a, u) ∪ (S ∩ S ′ )). We
show now that f ∈ S ′ .
1. If f is in S ∩ S ′ we are done.
2. If f ∈ E(a, u), there is a law causes(a, f, αf,i ) such that S |= αf,i . Since S is determined
by σS , by (3), we have that σS ◦ σa is a solution of αuf,i ∧ Aua , which implies that Dynuf is
true, and σS ′ (Ffv ) is true in σS ′ . Therefore, f ∈ S ′ . Observe also that σa making true Aua
u
is true (for some h ∈ {1, . . . , pa }), which will imply satisfiability of
will imply that δa,h
the executability preconditions for a.
3. We are left with the case of f ∈
/ E(a, u) and f ∈
/ S ∩ S ′ . Since S ′ is determined by σS ′ ,
′
and f ∈ CloSL (E(a, u) ∪ (S ∩ S )), there is a law caused(γf,j , f ) such that S ′ |= γf,j ,
v
true. Thus, Statvf is true and therefore Ffv is true.
and by construction σS ′ makes γf,j
Hence, f ∈ S ′ .
The proof proceeds similarly in the case of a negative fluent neg(f ) in CloSL (E(a, u) ∪
(S ∩ S ′ )).
Let us consider the set of static causal laws SL. We can introduce a notion of positive
dependence graph, following the traditional principle of dependence analysis used in logic
programming (e.g., (Lin and Zhao 2004)). The graph G(SL) is defined as follows:
• the set of the nodes in G(SL) corresponds to the set of fluent literals, i.e.,
Nodes(G(SL)) = {f | f ∈ F } ∪ {neg(f ) | f ∈ F }
• edges are created to denote the dependence of a fluent literal on other literals due to
a static causal law, i.e.,
Edges(G(SL)) = {(ℓ1 , ℓ2 ) | caused(L, ℓ1 ) ∈ SL, L = [..., ℓ2 , ...]}
A set of fluent literals L is a loop if, for any ℓ1 , ℓ2 ∈ L, we have that there is a path from ℓ1
to ℓ2 in G(SL) such that all nodes encountered in such path are in L. We say that a domain
specification D = hDL, EL, SLi is acyclic if the graph G(SL) does not contain any loops.

Multi-valued Action Languages in CLP(FD)

13

F ∪ ¬F
•ℓ
E
S

S′

Fig. 4. Sets of fluents involved in a state transition and a literal ℓ introduced by closure.
Theorem 3 (Acyclic Soundness)
u,v
. If the
Let D = hDL, EL, SLi. Let σS ◦ σS ′ ◦ σa be a solution of the constraint CF
′
′
dependency graph of P is acyclic, then CloSL (E(a, u) ∪ (S ∩ S )) = S .
Proof
Theorem 2 proves that CloSL (E(a, u) ∪ (S ∩ S ′ )) ⊆ S ′ . It remains to prove that for any
(positive or negative) fluent ℓ, if ℓ ∈ S ′ , then ℓ ∈ CloSL (E(a, u) ∪ (S ∩ S ′ )).
If ℓ ∈ E(a, u) or ℓ ∈ S, then trivially ℓ ∈ CloSL (E(a, u) ∪ (S ∩ S ′ )).
Let us prove that (cf., Figure 4):
(ℓ ∈ S ′ ∧ ℓ ∈
/ E(a, u) ∪ (S ∩ S ′ )) → ℓ ∈ CloSL (E(a, u) ∪ (S ∩ S ′ ))
To this aim, consider the dependence graph G(SL). Because of the acyclicity of G(SL),
there are nodes in G(SL) without incoming edges—we will refer to them as leaves. For
any node ℓ of G(SL), let d(ℓ) denote the length of the longest path from a leaf of G(SL)
to ℓ. We prove the property for a positive fluent literal ℓ = f , by induction on d(ℓ).
Base case. If f ∈
/ E(a, u) ∪ (S ∩ S ′ ) is a positive fluent which is a leaf (the proof is similar
for the case of negative literals), then two cases could be possible.
• There is no law of the form caused( , f ) in SL. In this case, it cannot be that f ∈ S ′
due to constraint (4).
• There is a law caused([ ], f ). In this case f ∈ S ′ by closure.
Inductive step. Let f ∈
/ E(a, u) ∪ (S ∩ S ′ ) be a positive fluent such that there are laws
caused(γf,1 , f ), . . . , caused(γf,h , f ) in SL. By the inductive hypothesis, let us assume
that the thesis holds for each fluent literal ℓ such that d(ℓ) < d(f ). Since f ∈
/ E(a, u) and
f ∈
/ S ∩ S ′ , we have that Ffu is false, Ffv is true, and Dynuf is false under σS ◦ σS ′ ◦ σa .
From the fact that constraint (7) is satisfied, it follows that Statvf is true. Moreover, Dynuf
is false because f ∈
/ E(a, u). On the other hand, because of (6), we have that Dynuneg(f ) ,
u,v
v
Statneg(f ) , and Firedneg(f ) are all false. Consequently, constraint (7) can be rewritten as
W
h
v
Ffv ↔ j=1 γf,j
. Since f ∈ S ′ (i.e., Ffv is true), there must exists a j ∈ {1, . . . , h} such
v
that γf,j is verified by σS ′ . This implies that, for each fluent g required to be true (resp.,
false) in γf,j , Fgv is set true (resp., false) by σS ′ . By inductive hypothesis, such fluent
literals (either g or neg(g)) belong to CloSL (E(a, u) ∪ (S ∩ S ′ )). Since CloSL (E(a, u) ∪
(S ∩ S ′ )) is closed w.r.t. the static laws, it follows that f ∈ CloSL (E(a, u) ∪ (S ∩ S ′ )).

14

A. Dovier, A. Formisano, E. Pontelli

The proof in case of a negative fluent neg(f ) is similar.
In order to achieve soundness in cases where the graph G(SL) contains loops, it is necu,v
essary to introduce additional constraints in conjunction with CF
. Intuitively, in the semantics of B, cyclic dependencies created by the static causal laws are resolved by the
closure operation CloSL (·) by minimizing the number of fluent literals that are made
true—this derives by the implicit minimality of the closure. Additional constraints can
be added to enforce this behavior; these constraints can be derived by following a principle similar to that of loop formulae commonly used in the context of logic programming (Lin and Zhao 2004).
The notion of loop formulae can be developed in our context as follows. Let L =
{ℓ1 , . . . , ℓk } be a loop in G(SL) and let us consider the transition from u to v as studied earlier. Let us define a counter-support for ℓi w.r.t. the loop L as a set of constraints cs
with the following properties:
• for each causes(aj , ℓi , α) in DL, cs contains either Auaj = 0 or Fℓ̄u = 1 for some
ℓ in α;
• for each caused(γ, ℓi ) in SL such that none of ℓ1 , . . . , ℓk is in γ, for some ℓ in γ
cs contains Fℓ̄v = 1;
• cs contains either Fℓ¯ui = 1 or Fℓ¯vi = 1.
(As usual, we might identify a set cs of constraint with their conjunction, depending on the
need.) Let us denote with Counters(ℓi , L)u,v the set of all such counter-supports. The loop
formulae for L w.r.t. u, v is the set of constraints
Form(L)u,v = {c1 ∧ · · · ∧ ck → Fℓv1 = 0 ∧ · · · ∧ Fℓvk = 0 | ci ∈ Counters(ℓi , L)u,v }.
To take into account all different loops in G(SL), let Form(D)u,v be the constraint
^
Form(L)u,v .
Form(D)u,v =
L is a loop in G(SL)

Following the analogous proofs relating answer sets and models of a program completion that satisfies loop formulae (e.g., (Lin and Zhao 2004)) one can show:
Theorem 4 (Soundness)
u,v
∧
Let D = hDL, EL, SLi and let σS ◦ σS ′ ◦ σa be a solution of the constraint CF
Form(D)u,v . Thus, CloSL (E(a, u) ∪ (S ∩ S ′ )) = S ′ .
Let the action description D meet the conditions of Theorem 4 and let hS, ν, Ri be its
underlying transition system. The following can be proved.
Theorem 5
There is a trajectory hs0 , a1 , s1 , a2 , . . . , aN , sN i in the transition system hS, ν, Ri if and
only if s0 is closed w.r.t. SL and there is a solution for the constraint
N−1
^
j=0

s ,sj+1

CFj

∧ Form(D)sj ,sj+1



Multi-valued Action Languages in CLP(FD)

15

Proof
The result follows directly by application of Theorems 1 and 4 and by observing that for
s ,s
each transition hsj , aj+1 , sj+1 i, the satisfaction of constraint CFj j+1 implies that the state
sj+1 is closed w.r.t. SL.
Let hD, Oi be an instance of a planning problem where D is an action description and
O contains any number of axioms of the form initially(C) and goal(C). We can state
the following.
Corollary 1
There is a trajectory hs0 , a1 , s1 , a2 , . . . , aN , sN i for the planning problem hD, Oi if and
only if s0 is closed w.r.t. the static causal laws of D and there is a solution for the constraint
^

initially(C)∈O

C s0 ∧

N−1
^
j=0

s ,sj+1

CFj

∧ Form(D)sj ,sj+1



∧

^

C sN

goal(C)∈O

3.3 Mapping the Model to CLP(FD)
The modeling described in Section 3.1 has been translated into a concrete implementation using SICStus Prolog. In this translation, constrained CLP variables directly reflect
the Boolean variables modeling fluents and action’s occurrences. Consequently, causal
laws and executability conditions are directly translated into CLP constraints (and inherit the corresponding completeness and soundness results). In this section we highlight the main aspects of the implementation—while the complete code can be found
at www.dimi.uniud.it/dovier/CLPASP.
A plan with exactly N + 1 states, p fluents, and m actions is represented by:
• A list, called States, containing N + 1 lists, each composed of p terms of the form
fluent(fluent name, Bool var). The variable of the ith term in the j th list is
assigned 1 if and only if the ith fluent is true in the j th state of the trajectory. For
example, if we have N = 2 and the fluents f, g, and h, we have:
States = [[fluent(f,X_f_0),fluent(g,X_g_0),fluent(h,X_h_0)],
[fluent(f,X_f_1),fluent(g,X_g_1),fluent(h,X_h_1)],
[fluent(f,X_f_2),fluent(g,X_g_2),fluent(h,X_h_2)]]

• A list ActionsOcc, containing N lists, each composed of m terms of the form
action(action name,Bool var). The variable of the ith term of the j th list is
assigned 1 if and only if the ith action occurs during the transition from state j to
state j + 1. For example, if we have N = 2 and the actions are a and b, then:
ActionsOcc = [[action(a,X_a_1),action(b,X_b_1)],
[action(a,X_a_2),action(b,X_b_2)]]

The planner makes use of these structures in the construction of the plan; appropriate constraints are set between the various Boolean variables to capture their relationships. For
each list in ActionsOcc, exactly one action(ai ,VAi ) contains a variable that is assigned
the value 1 (cf., constraint (8)).

16
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)

A. Dovier, A. Formisano, E. Pontelli
clpplan(N, ActionsOcc, States) :setof(F, fluent(F), Lf),
setof(A, action(A), La),
make states(N, Lf, States),
make action occurrences(N, La, ActionsOcc),
setof(F, initially(F), Init),
setof(F, goal(F), Goal),
set initial(Init, States),
set goal(Goal, States),
set transitions(ActionsOcc, States),
set executability(ActionsOcc, States),
get all actions(ActionsOcc, AllActions),
labeling(AllActions).

Fig. 5. Main predicate of the CLP(FD) planner.
The CLP implementation of the B language assumes that the action description is encoded as Prolog facts—observe that the syntax of B is compliant with Prolog’s syntax, allowing us to directly store the domain description as rules and facts in the Prolog database.
The entry point of the planner is shown in Figure 5.
The main predicate is clpplan(N, ActionsOcc, States) (line (1)) that computes
a plan of length N for the action description present in the Prolog database. If such a plan
exists, the variables in ActionsOcc and States will be instantiated so as to describe the
found trajectory.
Lines (2) and (3) collect the lists of all fluents (Lf) and all actions (La). Lines (4) and (5)
are used for the creation of the lists States and ActionsOcc. In particular, all the variables for fluents and actions are declared as Boolean variables. Furthermore, a constraint
is added to enforce that in every state transition, exactly one action can be fired.
Lines (6) and (7) collect the description of the initial state (Init) and the required content of the final state (Goal). These information are then added to the Boolean variables
related to the first and last state, respectively, by the predicates in lines (8) and (9).
Lines (10) and (11) impose the constraints on state transitions and action executability,
as described in Section 3.1. We will give more details on this part below.
Line (12) gathers all variables denoting action occurrences, in preparation for the labeling phase (line (13)). Note that the labeling is focused on the selection of the action to
be executed at each time step. Some details on the labeling strategy are discussed in Section 8. Please observe that in the code of Figure 5 we omit the parts concerning delivering
the results to the user.
The main constraints are added by the predicate set transitions. The process is
based on a recursion across fluents and consecutive states. The predicate set one fluent
is called (see Figure 6) at the core of the recursion. Its parameters are the fluent F, the
starting state FromState, the next state ToState, the list Occ of action variables, and
finally the variables IV and EV, related to the value of the fluent F in FromState and
ToState, respectively (see also Figure 2).
For a given fluent F, the predicate set one fluent collects the list DynPos (respectively DynNeg) of all the pairs [Action,Preconditions] such that the dynamic action
Action makes F true (respectively false) in the state transition (lines (15) and (16)). The
variables involved are then constrained by the procedure dynamic (lines (17) and (18)).
Similarly, the static causal laws are handled by collecting the lists of conditions that
affect the truth value of a fluent F (i.e., the variables StatPos and StatNeg, in lines

Multi-valued Action Languages in CLP(FD)
(14)
(15)
(16)
(17)
(18)
(19)
(20)
(21)
(22)
(23)
(24)
(25)
(26)

set one fluent(F, IV, EV, Occ, FromState, ToState) :findall([X,L], causes(X,F,L), DynPos),
findall([Y,M], causes(Y,neg(F),M), DynNeg),
dynamic(DynPos, Occ, FromState, DynP, EV),
dynamic(DynNeg, Occ, FromState, DynN, EV),
findall(P, caused(P,F), StatPos),
findall(N, caused(N,neg(F)), StatNeg),
static(StatPos, ToState, StatP, EV),
static(StatNeg, ToState, StatN, EV),
bool disj(DynP, StatP, PosFired),
bool disj(DynN, StatN, NegFired),
PosFired*NegFired #= 0,
EV #<=> PosFired #\/ (#\ NegFired #/\ IV).

(27)
(28)
(29)
(30)
(31)
(32)
(33)
(34)

dynamic([], , , [], ).
dynamic([[Action,Precondition]|R], Occ, FromState, [Flag|Flags], EV) :member(action(Action,VA), Occ),
get precondition vars(Precondition, FromState, ListPV),
length(ListPV, NPrec),
sum(ListPV, SumPrec),
(VA #/\ (SumPrec #= NPrec)) #<=> Flag,
dynamic(R, Occ, FromState, Flags, EV).

(35)
(36)
(37)
(38)
(39)
(40)
(41)

static([], , [], ).
static([Cond|Others], ToState, [Flag|Flags], EV) :get precondition vars(Cond, ToState, ListPV),
length(ListPV, NPrec),
sum(ListPV, SumPV),
(SumPV #= NPrec) #<=> Flag,
static(Others, ToState, Flags, EV).

17

Fig. 6. Transition from state to state.

(19)–(20)) and constraining them through the procedure static (lines (21) and (22)). The
disjunctions of all the positive and negative conditions are collected in lines (23) and (24)
and stored in PosFired and NegFired, respectively.
Finally, lines (25) and (26) take care of the relationships between all these variables.
Line (25) implements the constraint (6) for the state ToState of Figure 3, stating that we
do not want inconsistent action theories. If PosFired and NegFired are both false, then
EV = IV (inertia). Precisely, a fluent is true in the next state (EV) if and only if there is an
action or a static causal law making it true (PosFired) or it was true in the previous state
(IV) and no causal law makes it false.
Let us consider the predicate dynamic (see line (27) in Figure 6). It recursively processes a list of pairs [Action,Preconditions]. The variable VA associated to the execution of action Action is retrieved in line (29). The variables associated to its preconditions
are retrieved from state FromState and collected in ListPV in line (30). A precondition
holds if and only if all the variables in the list ListPV are assigned value 1, i.e., when their
sum is equal to the length, NPrec, of the list ListPV. If (and only if) the action variable
VA is true and the preconditions holds, then there is an action effect (line (33)).
Similarly, the predicate static (line (35) in Figure 6) recursively processes a list of
preconditions. The variables involved in each of such precondition Cond are retrieved from
the state ToState and collected in ListPV (line (37)). A precondition holds if and only if
all the variables in the list ListPV have value 1, i.e., when their sum is equal to the length,
NPrec, of ListPV. This happens if and only if there is a static action effect (see line (40)).
Executability conditions are handled as follows. For each state transition and for each
action Act, the predicate set executability sub is called (see Figure 7). The variable
VA, encoding the application of an action Act is collected in line (44). A precondition hold

18
(42)
(43)
(44)
(45)
(46)
(47)
(48)
(49)
(50)
(51)
(52)
(53)
(54)
(55)

A. Dovier, A. Formisano, E. Pontelli
set executability sub([], , ).
set executability sub([[Act,C]|CA], ActionsOcc, State) :member(action(Act,VA), ActionsOcc),
preconditions flags(C, State, Flags),
bool disj(Flags, F),
VA #==> F,
set executability sub(CA, ActionsOcc, State).
preconditions flags([], , []).
preconditions flags([C|R], State, [Flag|Flags]) :get precondition vars(C, State, Cs),
length(Cs, NCs),
sum(Cs, SumCs),
(NCs #= SumCs) #<=> Flag,
preconditions flags(R, State, Flags).

Fig. 7. Executability conditions.
if and only if the sum of the (Boolean) values of its fluent literals equals their number
(lines (52)-(54)). The variable Flags stores the list of these conditions and the variable F
their disjunction. If the action is executed (VA = 1, see line (47)), then at least one of the
executability conditions must hold.

4 The Action Language with Constraints on Multi-valued Fluents
As a matter of fact, constraints represent a very declarative notation to express relationships
between unknowns. As such, the ability to use them directly in an action language greatly
enhances the declarative and expressive power of the language, facilitating the encoding
of complex action domains, such as those involving multi-valued fluents. Furthermore, the
encoding of an action theory using multi-valued fluents leads to more concise and more
efficient representations and better exposing non-determinism (that could be exploited, for
example, by a parallel planner). Let us consider some representative examples.
Example 2 (Maintenance Goals)
It is not uncommon to encounter planning problems where along with the type of goals
described earlier (known as achievement goals), there are also maintenance goals, representing properties that must persist throughout the trajectory. Constraints are a natural
way of encoding maintenance properties, and can be introduced along with simple temporal operators. E.g., if the fluent f uel represents the amount of fuel available, then the
maintenance goal which guarantees that we will not be left stranded could be encoded as:
always(f uel > 0). 
Example 3 (Control Knowledge)
Domain-specific control knowledge can be formalized as constraints that we expect to be
satisfied by all the trajectories. For example, we may know that if a certain action occurs
at a given time step (e.g., ingest poison) then at the next time step we will always perform
the same action (e.g., call doctor). This could be encoded as
caused([occ(ingest poison)], occ(call doctor)1 )

where occ(a) is a fluent describing the occurrence of the action a and f 1 indicates that the
fluent f should hold at the next time step. 

Multi-valued Action Languages in CLP(FD)

19

Example 4 (Delayed Effect)
Let us assume that the action request reimbursement has a delayed effect (e.g., the increase by $50 of bank account after 30 time units). This could be expressed as a dynamic
causal law:
causes(request reimbursement,incr(bank account,50)30 ,[])

where incr is a constraint introduced to deal with additive computations—in a way closer
to B’s syntax we should write:
causes(request reimbursement,bank account30 = bank account + 50,[]).

This is a particular case of additive fluents (Lee and Lifschitz 2003).



In what follows we introduce the action description language B MV in which multivalued fluents are admitted and constraints are first-class components in the description of
planning problems. The availability of multi-valued constraints enables a number of immediate language extensions and improves the expressive power of the overall framework.
Action description languages such as B rely on the common assumption, traditionally referred to as Markovian property in the context of systems and control theory: the
executability of an action and its effects depend exclusively on the current state of the
world (Gabaldon 2002; McCarthy 1998). Nevertheless, it is not uncommon to encounter
real world situations where such property is not satisfied, i.e., situations where the executability and/or the effects of an action depend not only on what holds in the current
situation, but also on whether some conditions were satisfied at a previous point in time.
For example, an agent controlling access to a database should forbid access if in the recent
past three failed password submission attempts have been performed by the user.
Although non-Markovian preconditions and effects can be expressed in a Markovian
theory through the introduction of additional fluents (and a correct handling of inertia), the
resulting theory can become significantly larger and less intuitive. An alternative solution
consists of admitting past references in modeling such kind of situations. In this frame of
mind, B MV allows timed references to past points in time within constraints, i.e., nonMarkovian expressions that might involve fluents’ values. Effects of dynamic laws that
involves future references might also be specified. As a further feature the B MV language
admits the specification of global constraints (involving absolutely specified points in time)
and costs for actions and plans.
The resulting description language supports all the kind of modeling and reasoning outlined in the above Examples 2–4.
In the next sections, we first introduce the syntax of the full-blown action description
language B MV (Section 5). In Section 6 we will develop the semantics and the constraintbased abstract implementation of this new language. In doing this, for the sake of readability, we proceed incrementally in order to focus on the main points and features of the
framework. We first consider the sub-language B0MV obtained from B MV by disallowing
timed references (Section 6.1); in Section 6.2, we treat the general case dealing with past
and future references. The abstract implementation is provided in Section 6.3. Finally, we
give the semantics to the complete language involving cost and global constraints (Section 6.4).

20

A. Dovier, A. Formisano, E. Pontelli
5 The Language B MV

As for B, the action signature consists of a set F of fluent names, a set A of action names,
and a set V of values for fluents in F . In the following we assume that V ⊆ Z.
In an action domain description, an assertion (domain declaration) of the type
fluent(f, {d1 , . . . , dk })

declares that f is a fluent and that its set of values is {d1 , . . . , dk }; we refer to the set
{d1 , . . . , dk } as the domain of f . We also admit the simplified notation fluent(f, d1 , d2 )
to specify all the integer values in the interval [d1 , d2 ] as admissible (with d1 ≤ d2 ).
An annotated fluent (AF) is an expression f t , where f is a fluent and t ∈ Z. We will
often denote f 0 simply by f . Intuitively speaking, if t < 0 then f t denotes the value that
the fluent f had t steps ago in the past; similarly, if t > 0, then f t denotes the value f will
have t steps in the future. We refer to annotated fluents with t > 0 as positively annotated
fluents.
Annotated fluents can be used in Fluent Expressions (FE), which are defined inductively
as follows:
FE ::= d | AF | FE1 ⊕ FE2 | − (FE) | abs(FE) | rei(FC)

where d ∈ V and ⊕ ∈ {+, −, ∗, /, mod}. FC is a fluent constraint (see below). We refer
to the fluent expressions rei(FC) as the reification of the fluent constraint FC—its formal
semantics is given in Section 6.1.
Fluent expressions can be used to build primitive fluent constraints (PC), i.e., formulae
of the form FE1 op FE2 , where FE1 and FE2 are fluent expressions, and op is a relational
operator, i.e., op ∈ {=, 6=, ≥, ≤, >, <}. Fluent constraints are propositional combinations
of primitive fluent constraints:
PC
C

::=
::=

FE1 op FE2
PC | ¬C | C1 ∧ C2 | C1 ∨ C2

The constant symbols true and false can be used as a shorthand for true constraints
(e.g., d = d, for some d ∈ V) and unsatisfiable constraints (e.g., d 6= d).
The language B MV allows one to specify an action domain description, which relates
actions, states, and fluents using axioms of the following forms (P C denotes a primitive
fluent constraint, while C is a fluent constraint).
• Axioms of the form executable(a, C), stating that the fluent constraint C has to
be satisfied by the current state for the action a to be executable.
• Axioms of the form causes(a, P C, C) encode dynamic causal laws. When the action a is executed, if the constraint C is satisfied by the current state, then state
produced by the execution of the action is required to satisfy the primitive fluent
constraint P C.
• Axioms of the form caused(C1 , C2 ) describe static causal laws. If the fluent constraint C1 is satisfied in a state, then the constraint C2 must also hold in such state.
An action domain description of B MV is a tuple hDL, EL, SLi, where EL is a set of
executability conditions, SL is a set of static causal laws, and DL is a set of dynamic

Multi-valued Action Languages in CLP(FD)

21

causal laws. In the following, we assume that positively annotated fluents can occur only
in the effect part of dynamic causal laws.
A specific instance of a planning problem is a pair hD, Oi, where D is an action domain description and O contains any number of axioms of the form initially(C) and
goal(C), where C is a fluent constraint.
Example 5
A sample action theory in B MV is:
fluent(f , {1, 2, 3, 4, 5}).
fluent(g, {1, 2, 3, 4, 5}).
fluent(h, {1, 2, 3, 4, 5}).
causes(a, f = g + 2, g < 3).
executable(a, true).
initially(f = 1).
initially(g = 1).
initially(h = 1).
goal(f = 5).


Notice that, for any given dynamic law causes(a, P C, C), such that a is executed in
a state u satisfying C, the constraint P C has to be evaluates/satisfied in the target state v.
Hence, the (relative) timed references occurring in P C (respectively, in C) are resolved
with respect to v (resp., u). On the other hand, for a static law caused(C1 , C2 ), relative
timed references of both C1 and C2 have to be resolved with respect to the current state.
5.1 Absolute Temporal References
The language B MV allows the definition of absolute temporal constraints, i.e., constraints
that refer to specific moments in time in the trajectory (by associating the time point 0 to
the initial state). differently from the case of annotated fluents, where points in time are
relative to the current state. A timed fluent is defined as an expression of the form
FLUENT @ TIME.

Timed fluents can be used to build timed fluent expressions (T E) and timed primitive constraints (T C), similarly to what done for normal fluents. For instance, the constraint
f @2 < g@4
states that the value the fluent f has at time 2 in the plan is less than the value that the
fluent g has at time 4. Similarly, h@2 = 3 imposes that the fluent h must assume value 3 at
time 2.
Timed constraints can be used in the following kind of assertion:
time constraint(T C)

The assertion requires the timed constraint T C to hold.
Some other accepted constraints are:

22

A. Dovier, A. Formisano, E. Pontelli
• holds(F C, n): this constraint is a particular case of the previous one. It is satisfied
if the primitive fluent constraint F C holds in the nth state. It is therefore a generalization of the initially axiom. Observe that assertions of this kind can be
used to guide the search of a plan by adding some point-wise information about the
states occurring along the computed trajectory (e.g., this is useful to implement the
landmarks model as used in the FF planner (Hoffmann et al. 2004)).
• always(F C): this constraint imposes the condition that the fluent constraint F C
holds in all the states. Observe that F C has to be evaluated in all states, and its
evaluation is strict—i.e., any reference to fluents outside the time limits leads to the
satisfaction of the constraint; hence, annotated fluents should be avoided in F C.

In specifying a planning problem hD, Oi, we can consider such kinds of assertions as part
of the observations O.
Example 6
Let us consider the case of an agent that has a certain amount of money (e.g., $5, 000)
to invest; she is interested in purchasing as many stocks as possible. The stocks can be
purchased from three trading agencies (1, 2, and 3); each agency has 1, 000 stocks available
at $2 each. The stocks have to be purchased in separate transactions, but each trading
agency require the agent to have a balance of at least $2, 000 at the start of the day before
agreeing in the transaction. A purchase can be of at most 3, 000 shares at a time.
We can model this problem with the following fluents:
fluent(money, 0, 5000).
fluent(have(stock2), 0, 1000).
fluent(available(stock1), 0, 1000).
fluent(available(stock3), 0, 1000).
fluent(price(stock1), 2, 2).
fluent(price(stock3), 2, 2)).

fluent(have(stock1), 0, 1000).
fluent(have(stock3), 0, 1000).
fluent(available(stock2), 0, 1000).
fluent(price(stock2), 2, 2).

The only action is
action(buy(StockT ype, N )) : −N > 0, N < 3000.

The executability condition for the action captures one property: the agent is accepted by
the trading agency.
executable(buy(T ype, N ), money@0 > 2000 ∧ money > N ∗ price(T ype)).

The dynamic causal law for this action is:
causes(buy(T ype, N ), money = money − N ∗ price(T ype), true).
causes(buy(T ype, N ), have(T ype) = have(T ype) + N, true).

The initial state can be described as
initially(price(stock1) = 2).
initially(price(stock3) = 2).
initially(have(stock2) = 0).
initially(money = 5000).
initially(available(stock2) = 1000).



initially(price(stock2) = 2).
initially(have(stock1) = 0).
initially(have(stock3) = 0).
initially(available(stock1) = 1000).
initially(available(stock3) = 1000).

Multi-valued Action Languages in CLP(FD)

23

5.2 Cost Constraints
In B MV it is possible to specify information about the cost of each action and about the
global cost of a plan (that is defined as the sum of the costs of all its actions). This type of
information are useful to explore the use of constraints in determining optimal plans.
The cost of actions is expressed using assertions of the following forms (where F E is a
fluent expression built using the fluents present in the state):
• action cost(a, F E) specifies the cost of the execution of the action a as result of
the expression F E.
• state cost(F E) specifies the cost of a state as the result of the evaluation of F E.
Whenever, for an action or a state, no cost declaration is provided, a default cost of 1 is
assumed. Once we have provided the costs for actions and states, we can impose constraints
on the cumulative costs of specific states or complete trajectories. This can be done in B MV
using assertions of the following types (where k is a number and op a relational operator):
• cost constraint(plan op k); the assertion adds a constraint on the global cost
of the plan.
• cost constraint(goal op k); the assertion imposes a constraint on the global
cost of the final state.
• cost constraint(state(i) op k); the assertion imposes a constraint on the
global cost of the ith state of the trajectory.
As an immediate generalization of the above constraints, we admit assertions of the form
cost constraint(C), where C is a constraint, possibly involving fluents, where the
atoms plan, goal, and state(i) might occur in any place where a fluent might—
intuitively representing the cost of a plan, of the goal state, and of the ith state, respec-

tively.
Some directives can be added to an action theory to select optimal solutions with respect
to the specified costs:
minimize cost(F E),

where F E is an expression involving the atoms plan, goal, and state(i), and possibly
other fluents. This assertion constrains the search to determine a plan that minimizes the
value of the expression F E. For instance, the two assertions minimize cost(plan) and
minimize cost(goal) constrain the search of a plan with minimal global cost and with
minimal cost of the goal state, respectively.
We provide a more precise semantics for all these assertions in Section 6.4. In specifying
a planning problem hD, Oi, we consider cost constraints as part of the observations O.
6 Semantics and Abstract Implementation of B MV
We will build the semantics of the language B MV incrementally. We will start by building
the semantics for the sub-language of B MV devoid of any form of time reference and cost
constraints (Section 6.1). This core language is called B0MV . The subsequent Sections 6.2–
6.4 treat the full B MV .

24

A. Dovier, A. Formisano, E. Pontelli
6.1 Semantics for Timeless Constraints

Each fluent f is uniquely assigned to a domain dom(f ) in the following way:
• if fluent(f, Set) ∈ D, then dom(f ) = Set.
A function v : F → V ∪ {⊥} is a state if v(f ) ∈ dom(f ) ∪ {⊥} for all f ∈ F . The
special symbol ⊥ denotes that the value of the fluent is undefined. A state v is complete if
for all f ∈ F , v(f ) 6= ⊥. For a number N > 1, we define a state sequence ~v as a tuple
hv0 , . . . , vN i where each vi is a state.
Given a state v, and an expression ϕ, we define the value of ϕ in v (with abuse of
notation, denoted by v(ϕ)) as follows:7
•
•
•
•
•
•
•

v(x) = x if x ∈ V
v(f ) = v(f ) if f ∈ F (abuse of notation here)
v(−(ϕ)) = −(v(ϕ))
v(abs(ϕ)) = |(v(ϕ))|
v(ϕ1 ⊕ ϕ2 ) = v(ϕ1 ) ⊕ v(ϕ2 )
v(rei(C)) = 1 if v |= C
v(rei(C)) = 0 if v 6|= C

(10)

We treat the interpretation of the various ⊕ operations and relations as strict with respect
to ⊥ (i.e., ⊥ ⊕ x = x ⊕ ⊥ = ⊥, abs(⊥) = ⊥, etc.).
The last two cases in (10) specify the semantics of reification. Reified constraints are
useful to enable reasoning about the satisfaction state of other formulae. The intuitive
semantics is that a fluent expression rei(C), where C is a fluent constraint, assumes a
Boolean value (0 or 1) depending on the truth of C. Note that the semantics of reified constrains relies on the notion of satisfaction, which in turn is defined by structural induction
on constrains, as follows. Given a primitive fluent constraint ϕ1 op ϕ2 , a state v satisfies
ϕ1 op ϕ2 , written v |= ϕ1 op ϕ2 , if and only if it holds that v(ϕ1 ) op v(ϕ2 ) where the semantics of the arithmetic relators/operators is the usual one on Z. If either v(ϕ1 ) or v(ϕ2 )
is ⊥, we assume that v 6|= ϕ1 op ϕ2 (and v 6|= ϕ1 nop ϕ2 where nop is the negation of
the operator op). Basically undefined formulas are neither proved nor disproved. The satisfaction relation |= can be generalized to the case of propositional combinations of fluent
constraints in the usual manner.
Given a constraint C, let fluents(C) be the set of fluents occurring in it. A function
σ : fluents(C) −→ V is a solution of C if σ |= C. We denote the domain fluents(C) of
the function σ as dom(σ). In other words, a solution σ of C can be seen as a partial state
satisfying C. Observe that we require the solution to manipulate exclusively the fluents
that appear in the constraint.
Example 7
Let us consider an action theory over the fluents f, g, h, where each fluent has domain
{1, . . . , 5}. If C is the constraint f > g + 2, then a solution of C is σ = {f /5, g/2}.
Note that the substitution θ = {f /5, g/2, h/1} is not a solution of C, since dom(θ) 6=
fluents(f > g + 2). 
7

The expression |n| denotes the (algebraic) absolute value of n.

Multi-valued Action Languages in CLP(FD)

25

Let σ be a solution of a constraint C and v a state, with ine(σ, v) we denote the state
obtained completing σ in v by inertia, as follows:

σ(f ) if f ∈ dom(σ)
ine(σ, v)(f ) =
v(f ) otherwise
Example 8
Let us continue with Example 7. If σ = {f /5, g/2} and v = {f /1, g/1, h/1}, then
ine(σ, v) = {f /5, g/2, h/1}. 
An action a is executable in a state v if there is an axiom executable(a, C) such that
v |= C.
Remark 3
As for the case of the language B, also in B MV the executability laws express necessary
but not sufficient preconditions for action execution (cf., Remark 2). Moreover, thanks to
the generality of the constraint language—i.e., any propositional combination of primitive
constraints can be used in B MV —the executable laws also allow direct formulation
of non-executability conditions and the roles of the executable and nonexecutable
axioms coincide.
Let us denote with Dyn(a) the set of dynamic causal law axioms for action a. The effect
of executing a in state v, denoted by Eff (a, v), is a constraint defined as follows:
^
Eff (a, v) =
{C | causes(a, C, C1 ) ∈ Dyn(a), v |= C1 } .
6.1.1 B0MV without static causal laws
Let us start by considering the simplified situation in which SL = ∅, i.e., no static causal
laws are specified in the domain description.
During the execution of an action a, a fluent has to be considered as inertial, provided
that it does not appear among the effects of the dynamic laws for a. In other words, since
these effects are expressed through constraints, a fluent is inertial if it does not occur in any
of the constraints specified in the dynamic laws for a.
The description of the state transition system corresponding to a given action description
theory hDL, EL, ∅i can be completed by defining the notion of transition.
A triplet hv, a, v ′ i, where v, v ′ are complete states and a is an action, is a valid state
transition if:
• the action a is executable in v, and
• v ′ = ine(σ, v), where σ is a solution of the constraint Eff (a, v).
Let hD, Oi be an instance of a planning problem, ~v = hv0 , . . . , vN i be a sequence of
complete states and a1 , . . . , aN be actions. We say that hv0 , a1 , v1 , . . . , aN , vN i is a valid
trajectory if:
• for each axiom of the form initially(C) in O, we have that v0 |= C,
• for each axiom of the form goal(C) in O, we have that vN |= C, and
• for all i ∈ {0, . . . , N − 1}, hvi , ai+1 , vi+1 i is a valid state transition.

26

A. Dovier, A. Formisano, E. Pontelli

Example 9
Let us consider the Example 5. Observe that h{f /1, g/1, h/1}, a, {f /5, g/3, h/1}i is a
valid trajectory. 
Remark 4
Given a planning problem hD, Oi in B0MV , differently from what happens in the case of B,
a solution to a planning problem is described by a valid trajectory, not just by a sequence of
actions. This is the case because actions might have non-deterministic effects. For instance,
let us consider Example 5. If the action a is executed and the precondition g<3 holds, then
the dynamic causal law imposes the constraint f=g+2 in the reached state. There are many
different ways to satisfy this requirement. Hence, in general, a sequence of actions might
not characterize a unique state sequence.
The same argument also applies to the action description language B MV , so in what
follows we will consider the valid trajectories as the solutions of a planning problem.
6.1.2 Abstract implementation in absence of static laws
In this section we propose a constraint-based characterization of the state transition system
defined in Section 6.1.1. Similarly to what we have done in the case of B, for any specific
state, each fluent f will be represented by an integer-valued constraint variable. Boolean
variables will instead model the occurrences of actions.
Let u be a state; given a fluent f , we indicate with Ffu the variable representing f in u.
We generalize such a notation to any constraint C, i.e., we denote with C u the constraint
obtained from C by replacing each fluent f ∈ fluents(C) by Ffu . For each action a ∈ A,
a Boolean variable Aua is introduced, representing whether the action is executed or not in
the transition from u to the next state.
Given a specific fluent f , we develop a system of constraints to constrain the values
of Ffu . Let us consider the dynamic causal laws that have f within their consequences:

DLf = causes(aif,1 , Cf,1 , αf,1 ), · · · , causes(aif,mf , Cf,mf , αf,mf )
For each action a we will have its executability conditions:

ELa = executable(a, δa,1 ), · · · , executable(a, δa,pa )

u,v
Figure 8 describes the constraints Cf,a
that can be used in encoding the relations that
determine the value of the fluent f in the state v (i.e., constrain the variable Ffv ) w.r.t.
the application of the action a in the state u. After the settings of the domains (by (11)),
we impose through (12) that if action a is executed, then at least one of the preconditions
for its executability must hold in u. For each j ∈ {1, . . . , mf } the constraint (13) defines
a Boolean flag Dynuf,j that holds if and only if action aif,j is applicable in u and the
preconditions of the j th dynamic causal law for f holds in u. The constraint (14) requires
that if Dynuf,j is true, then the corresponding effects must hold in the new state v. Finally,
inertia constraints are set by means of (15).

We will denote with Cfu,v the conjunction of these constraints for all actions a ∈ A.
Given an action domain specification over the signature hV, F , Ai and two states u, v, the
u,v
system of constraints CF
includes:

Multi-valued Action Languages in CLP(FD)
Ffv , Ffu

∈

Aua

→

dom(f )
pa
_
u
δa,j

27
(11)
(12)

j=1

Auai

↔

Dynuf,j

∀j ∈ {1, . . . , mf }

(13)

Dynuf,j

→

v
Cf,j

∀j ∈ {1, . . . , mf }

(14)

Dynuf,j

→

Ffu = Ffv

f,j

∧ αuf,j

mf

¬

_

(15)

j=1

u,v
Fig. 8. The constraints Cf,a
for a state transition from u to v, for a fluent f .

• the constraint Cfu,v for each fluent literal f in the language of F
P
• the constraint a∈A Aua = 1 (unique action execution in the state transition).

The next theorem states completeness and soundness of the encoding described so far.
u,a
We need a further piece of notation. Given two states u, v and an action a, let CF
be the
u,v
constraint obtained from CF
by setting Aa = 1, Ab = 0 for all b 6= a, and Ffu = u(f )
for each fluent literal f .
Theorem 6
Let D = hDL, EL, ∅i and let u, v two states and a an action. Then hu, a, vi is a valid
transition in the semantics of the language B0MV if and only if v represents a solution of
u,a
the constraint CF
.
Proof
(⇒) Let hu, a, vi be a valid transition. Then, a is executable in u. Hence u |= δa,j for
some j ∈ {1, . . . , pa } and (12) is satisfied. By the definition of state we have that (11)
is also satisfied. Let v = ine(σ, u) with σ solution of Eff (a, u).
If f is a fluent not belonging to dom(σ) then f does not occur in Eff (a, u) and it is
not affected by any dynamic causal law involved in the state transition. By definition
of ine(·) we have that v(f ) = u(f ) and this satisfies constraint (15). Satisfaction of
constraints (13) and (14) is immediately verified by observing that for all dynamic causal
laws causes(aif,h , Cf,h , αf,h ) having f in Cf,h , the constraint αf,h is false in u. Then,
the corresponding flag Dynuf,h is set false by (13). Consequently, (14) is satisfied.
Assume now that f is a fluent in dom(σ). This means that there are dynamic causal
laws causes(aif,h , Cf,h , αf,h ) such that αf,h is true in u, for h ∈ X = {j1 , . . . , jr } ⊆
{1, . . . , mf }. Consequently, the flag Dynuf,h is set true for h ∈ X and false otherwise.
v
for all j ∈ X. This
Since σ is a solution of Eff (a, u), v satisfies the constraint Cf,j
implies that (14) is satisfied for each j ∈ {1, . . . , mf }. Since some flags Dynuf,i are true
constraint (15) is satisfied too.
u,a
(⇐) Assume that v satisfies the constraint CF
. By (12), because Aa = 1, some of the
u
constraints δa,h is satisfied. Hence, action a is executable in u. By the satisfaction of (13)
v
and (14), v satisfies all constraints Cf,j
for which the corresponding αuf,j is satisfied.
Then, v is a solution for Eff (a, u). Consequently, since v = ine(v, u) (by definition,
since v is complete), hu, a, vi is a valid transition.

28

A. Dovier, A. Formisano, E. Pontelli

Let hD, Oi be an instance of a planning problem where D is an action description and O
contains any number of axioms of the form initially(C) and goal(C). We can state
the following.
Theorem 7
There is a valid trajectory hv0 , a1 , v1 , a2 , . . . , aN , vN i if and only if there is a solution for
the constraint
^

C v0 ∧

initially(C)∈O

N−1
^
j=0

v ,vj+1 

CFj

∧

^

C vN

goal(C)∈O

Proof
The result follows from (repeated) applications of Theorem 6.
6.1.3 Adding static causal laws
In this section we consider the case of action theories hDL, EL, SLi of B0MV , involving
static causal laws (i.e., such that SL =
6 ∅).
The presence of static laws requires refining the semantics of the language, in order to
ensure proper treatment of inertia in the construction of a valid trajectory.
We start by defining three operations ∩, ∪, and △ on states, as follows:

v1 (f ) if v1 (f ) = v2 (f )



v1 (f ) if v2 (f ) = ⊥
v1 ∪ v2 (f ) =

v (f ) if v1 (f ) = ⊥

 2
⊥
otherwise

v1 (f ) if v1 (f ) = v2 (f )
v1 ∩ v2 (f ) =
⊥
otherwise

v1 (f ) if f ∈ S
△(v1 , v2 , S)(f ) =
v2 (f ) otherwise
where the set S used in △ is a set of fluents. Observe that ine(σ, v) = △(σ, v, dom(σ)).
A state v is closed w.r.t. a set of static causal laws
SL = {caused(C1 , D1 ), . . . , caused(Ck , Dk )}
if v |= (C1 → D1 ) ∧ · · · ∧ (Ck → Dk ). We denote this property as v |= SL.
Given two states v, v ′ , a set of fluents D, and a set SL of static causal laws, we say that
′
v is minimally closed w.r.t. v, D, and SL if
• v ′ |= SL (i.e., v ′ is closed) and
• for all S ⊆ D, if △(v, v ′ , S) 6= v ′ then △(v, v ′ , S) 6|= SL.
The notion of minimally closed state is intended to capture the law of inertia, w.r.t. a given
set D of fluents. Notice, in fact, that △(v, v ′ , ∅) = v ′ . Intuitively speaking, v ′ is minimally
closed when it is obtainable from v by applying a minimal set of (necessary) changes in the
values of the ‘inertial’ fluents (those in D). In other words, it is not possible to obtain from

Multi-valued Action Languages in CLP(FD)
△(v, v ′ , D) :

v

29

v′
D
F \D

△(v, v ′ , S)
for S ⊆ D :

S

v

v′
D

F \S
F \D

Fig. 9. The set △(v, v ′ , X) is obtained by combining a portion of v and a portion of v ′ ,
depending on the third argument X, which acts as a regulator in “mixing” portions of v
and v ′ . The figure visualizes, in gray, the two sets △(v, v ′ , D) (above) and △(v, v ′ , S)
(below) for S ⊆ D ⊆ F and illustrates the definition of minimal closure. A state v ′ is
minimally closed if and only if v ′ |= SL and for all S ⊆ D, if △(v, v ′ , D) 6= v ′ then
△(v, v ′ , S) 6|= SL. In both cases, the surrounding frame represents the set F of all fluents.
v a state different from v ′ and closed w.r.t. SL, by applying “fewer changes” than those
involved in obtaining v ′ . A pictorial representation of △(v, v ′ , X) is shown in Figure 9.
Observe that if SL = ∅ then v ′ is minimally closed w.r.t. v, D, and SL if and only if
v = v′ .
Example 10
Let f, g, h be fluents with dom(f ) = dom(g) = dom(h) = {0, 1} and
SL = {caused(f = 1, g = 1), caused(f = 0, g = 0)}.
Consider the states v = {f /0, g/0, h/0}, v ′ = {f /1, g/1, h/1}, v ′′ = {f /0, g/0, h/1}
and let D = {f, g}. Then, v ′ and v ′′ are both closed w.r.t. SL.
However, v ′′ is minimally closed w.r.t. v, D, and SL, while v ′ is not minimally closed
since △(v, v ′ , D) = {h/1, f /0, g/0} is different from v ′ and closed. 
A triplet hv, a, v ′ i, where v and v ′ are complete states and a is an action, is a valid
transition if:
1. the action a is executable in v and
2. we have that v ′ = ine(σ, v ′ ) where
• σ is a solution of the constraint Eff (a, v), and
• v ′ is minimally closed w.r.t. v, F \ dom(σ), and SL.
Intuitively, the conditions that define a transition are designed to guarantee that:

30

A. Dovier, A. Formisano, E. Pontelli
• a solution σ for the constraints describing the effects of the action is determined;
• such solution is part of the new state v ′ constructed (thanks to v ′ = ine(σ, v ′ )); and
• the new state is minimally closed with respect to all the fluents not affected by the
execution of the action.

Let us observe that, since all fluents in the domain of any solution σ of Eff (a, v) maintain
the same value in v ′ , it holds that v ′ |= Eff (a, v).
Notice that the notion of a valid transition given in presence of static laws properly
extends the one given in Section 6.1.1. In fact, the following property holds:
Lemma 1
If SL = ∅ then ine(σ, v) = ine(σ, v ′ ).
Proof
It is sufficient to note that, if SL = ∅ then v ′ is minimally closed w.r.t. F \ dom(σ) if and
only if ine(σ, v) = v ′ .
Example 11
Let us extend the action description of Example 10. We consider the following domain
description:
fluent(f, {0, 1}).
fluent(h, {0, 1}).
action(a).
causes(a, h = 1)
caused(f = 1, g = 1).

fluent(g, {0, 1}).
executable(a, h = 0).
caused(f = 0, g = 0).

Let us consider the three states v = {f /0, g/0, h/0}, v ′ = {f /1, g/1, h/1}, and v ′′ =
{f /0, g/0, h/1}. Then hv, a, v ′′ i is a valid transition, while hv, a, v ′ i is not. 
Let hD, Oi be a planning problem instance. Let ~v = hv0 , . . . , vN i be a sequence of
complete states and let a1 , . . . , aN be actions. Then hv0 , a1 , v1 , . . . , aN , vN i is a valid
trajectory if the following conditions hold:
• v0 |= SL, and for each axiom initially(C) in O, we have that v0 |= C;
• for each axiom of the form goal(C) in O, we have that vN |= C;
• hvi , ai+1 , vi+1 i is a valid transition, for each i ∈ {0, . . . , N − 1}.
6.1.4 Abstract implementation in presence of static laws
Let us consider a fluent f and a transition from state u to state w, due to an action a, and let
us adopt the same notation (Ffu , C u , Aua , etc.) introduced in Section 6.1.2. The state transition from u to w can be seen as the composition of two steps involving an intermediate
state v. The first of these steps reflects the effects of the dynamic laws, whereas the second
step realizes the closure w.r.t. the static causal laws. Hence we proceed by introducing a
set of variables corresponding to the intermediate state v = ine(σ, u), where σ is a solution
of Eff (a, u). The constraint-based description of the first step is essentially the same we
described in Section 6.1.2—thus, we only need to extend the constraint system defined in
Figure 8 to reflect the second part of the transition.

Multi-valued Action Languages in CLP(FD)

31

Ffw

∈

dom(f )

Dynuf,j

→

Ffw = Ffv

∀j ∈ {1, . . . , mf }

(17)

Gw
f,j

→

w
Df,j

∀j ∈ {1, . . . , hf }

(18)

Statvf

↔

^ „“ m
_f `

g∈Lf

Statvf

→

(16)

^

Dynuf,j ∧ g ∈ fluents(Cf,j )

j=1

´”

→ Fgv = Fgu

Fgw = Fgv

«

(19)
(20)

g∈Lf

E(a, u)
Inertia

u

SL

a

v

w

SL

E(a, u)

Fig. 10. The constraints for a state transition from u to w (with intermediate state v), for a
fluent f .
Given a set L ⊆ F of fluents, let SLL ⊆ SL be the collection of all static causal laws
in which at least one fluent of L occurs. Moreover, for simplicity, let SLf denote SL{f } ,
i.e., the set of all static causal laws that involve the fluent f .
Let us define a relation R ⊆ F × F so that f1 Rf2 if and only if SLf1 ∩ SLf2 6= ∅. R
is an equivalence relation and it partitions F . Each element (i.e., equivalence class) of the
quotient F /R is said to be a cluster (w.r.t. SL). Notice that a cluster can be a singleton
{f }. Let f be a fluent, we denote with Lf its cluster w.r.t. SL.
Example 12
Assume that SL consists of the rules
caused(true, f = 1).

caused(g = 2, h = 3).

Then the two clusters are {f } and {g, h, r}.

caused(h < 5, r = 2).



Given a fluent f , let us consider the sets of dynamic and executability laws DLf and
ELa , as defined in Section 6.1.2. Moreover, let us consider the cluster containing f , let it
be Lf = {f1 , . . . , fk }, and the corresponding set of static causal laws SLLf :

SLLf = caused(Gf,1 , Df,1 ), · · · , caused(Gf,hf , Df,hf ) .
Figure 10 describes the constraints (to be added to those in Figure 8) that are used in

32

A. Dovier, A. Formisano, E. Pontelli

encoding the relations that determine the value of the fluent f in state w (represented
through the variable Ffw ) after the execution of action a in the state u (we recall that v is
to be considered as an intermediate state v = ine(σ, u)).
The constraint (16) sets the domains for the variables Ffw . The constraint (17) propagates
to w the effects of the dynamic laws. Constraint (18) imposes closure w.r.t. the static causal
laws. Finally, constraints (19)–(20) require that if all the fluents in dom(σ) that belong to
the cluster Lf are left unchanged in the transition, then all the fluents of Lf should not
change their values. More precisely, as far as (19) is concerned, Statvf is set to true if, for
all fluents g in Lf , either g is not affected by the dynamic laws (i.e., Fgv = Fgu ), or for
each activated dynamic law causes(aif,j , Cf,j , αf,j ) (i.e., such that its precondition αuf,j
is true), g does not occur in its effects (i.e., in Cf,j ). Notice that, with respect to a specific
state transition, we are not considering subject to inertia all those fluents that occur in the
effects of (at least) one activated dynamic law.
The enforcement of the constraint (20) constitutes a necessary, but not sufficient, condition for the target state to be minimally closed. We will discuss later on this point.
Let us denote with Cfu,w the conjunction of the constraints (11)–(18) for all actions
a ∈ A. Given an action domain specification over the signature hV, F , Ai, the system of
u,w
constraints CF
includes:
• the constraint Cfu,w for each fluent literal f in the language of F ;
P
• the constraint a∈A Aua = 1.

Similarly, let Stat u,w
denote the conjunction of all the constraints of the forms (19) and
F
(20).
The next theorem states completeness of the encoding described so far. Again, given
u,a
two states u, w and an action a, let CF
and Stat u,a
F denote the constraints obtained from
u,w
,
respectively,
by
setting
A
=
1,
Ab = 0 for all b 6= a, and Ffu = u(f )
and Stat u,w
CF
a
F
for each fluent literal f .
Theorem 8
Let D = hDL, EL, SLi and let u, w two states and a an action. Then, if hu, a, wi is a
valid transition in the semantics of the language B0MV , then w represents a solution of the
u,a
constraint CF
∧ Stat u,a
F .
Proof
For the constraints (11)–(16), considering the transition from u to v, the proof proceeds
analogously to the first part of the proof of Theorem 6.
Let us sketch the part of the proof regarding the effect of the static causal laws. Since
hu, a, wi is a valid transition, w = ine(σ, w), w agrees with v = ine(σ, u) on all fluents
in dom(σ), hence (17) hold. Moreover, w is closed w.r.t. SL, hence it satisfies (18). From
the fact that w is minimally closed w.r.t. ine(σ, u), F \ dom(σ), and SL, it follows that w
satisfies (19)–(20).
The above encoding does not guarantee soundness. This is because the constraints (17)–
(18) in Figures 8 and 10 might admit solutions not corresponding to minimally closed
states.

Multi-valued Action Languages in CLP(FD)

33

We introduced the notion of cluster to partially recover the soundness of the encoding.
Intuitively speaking, a cluster generalizes, to the multi-valued case, the notion of loop seen
in Section 3.2: a cluster is a set of fluents whose values have been declared to be mutually
dependent through a set of static causal laws. In a state transition, similarly to the case of
loops, changes to the fluents of a cluster might occur because of their mutual influence, not
being (indirectly) caused by dynamic laws.
Constraints (19) and (20) impose inertia on all the fluents of a cluster whenever none
of them is influenced by dynamic laws. However, note that imposing (19)–(20) does not
completely circumvent the problem because state transitions violating the inertia are still
admitted. In fact, (19)–(20) do not impose inertia on the fluents of a cluster when at least
one of them is changed by the dynamic laws. This might lead to invalid transitions, in
which a change in the value of a fluent of a cluster happens even if this is not necessary in
order to satisfy all the static causal laws.
Nevertheless, we introduced the constraints (19) and (20) because they constitute a good
compromise w.r.t. the efficiency of a concrete implementation (as discussed later).
To completely enforce soundness, we need to apply a filter on the solutions that are
admitted by the encoding described so far. To this aim, let us introduce a condition on the
values of the fluent, which is intended to mimic, in the multi-valued setting, the effect of
loop formulae.
Let us assume that the action a is executed in the state u, and that σ, v, and w have been
u,w
. In this situation the following constraint
determined so that to satisfy the constraint CF
characterizes an hypothetical state x, different from w:

u,x
u,a
∧
(21)
Form(D)
=
CF
^ m
_f

f ∈F

_

f ∈F

Dynuf,j → Ffx = Ffw

j=1

Ffx

6=

Ffw

∧

^ 

f ∈F

Ffx

6=



∧

Ffw

→

(22)
Ffx

=

Ffu



(23)

Intuitively, the satisfaction of such a formula witnesses the existence of a counterexample
for the minimal closure of w. Notice that, being σ, v, and w already determined, the only
fluents/variables to be determined are those describing the state x, if any. The conjunct in
line (21) states that x is a target state alternative to w; in particular, it enforces the closure
of x w.r.t. SL. The conjunction (22) states that x and w agree on the fluents in dom(σ).
Finally, (23) states that x must differ from w and it must agree with u in at least one
fluent—that, because of (22), it is in F \ dom(σ).
We can prove the following result, that generalizes Theorem 6 to the case of SL =
6 ∅.
Theorem 9
Let D = hDL, EL, SLi and u, w two states, with u closed w.r.t. SL. Let a an action such
u,a
that w represents a solution of the constraint CF
. Then hu, a, wi is a valid transition in
MV
u,a
the semantics of the language B0 , if Form(D) is unsatisfiable.
Proof

34

A. Dovier, A. Formisano, E. Pontelli

By proceeding as in the proof of Theorem 6, we can show that all needed conditions for
hu, a, wi to be a valid transition are satisfied, except for the minimal closure of w.
Let us assume, by contradiction, that w is not minimally closed w.r.t. u, F \ dom(σ),
and SL. Then, there exists S ⊆ F \ dom(σ) such that x = △(u, w, S) 6= w and x |= SL
For each fluent f 6∈ S it holds that Ffx = Ffw . Moreover, Ffv = Ffw holds too, because w
u,a
satisfies CF
. Hence, Dynuf,j → Ffx = Ffv holds for all j.
x
For each fluent f , since x is closed w.r.t. SL, we have that Gxf,j → Df,j
(for all j ∈
{1, . . . , hf }). Observe that the conditions of the forms (11)–(16) in the conjunct at line (21)
u,x
(i.e., in CF
) do not depend on the specific x. Then, the conjunct (21) is satisfied.
Let us also observe that condition (22) holds too. This is so because, for all f ∈ dom(σ)
W
we have that Ffx = Ffw = Ffv . From the fact that x 6= w it follows that f ∈F Ffx 6= Ffw
holds. Finally, the condition (23) is satisfied because, whenever Ffx 6= Ffw holds, by the
definition of △, it must be the case that Ffx = Ffu . It follows that Form(D)u,a is satisfiable
(by x).
This is a contradiction and proves that w is minimally closed w.r.t. u, F \ dom(σ), and
SL, and that hu, a, wi is a valid transition.
Let hD, Oi be an instance of a planning problem, where D is a domain description and
O contains any number of axioms of the form initially(C) and goal(C). We conclude
this section by stating a generalization of Theorem 7 to the case of SL =
6 ∅.
Theorem 10
There is a valid trajectory hv0 , a1 , v1 , a2 , . . . , aN , vN i if and only if
• v0 |= SL
• There is a solution for the constraint
^

C v0 ∧

initially(C)∈O

N−1
^
j=0

v ,vj+1

CFj

∧

^

C vN

goal(C)∈O

• For each j ∈ {0, . . . , N − 1} the formula Form(D)vj ,aj+1 is unsatisfiable.
Proof
The result follows from Theorems 8 and 9.
Remark 5 (Embedding of B into B0MV )
We conclude this section by showing that B0MV is at least as expressive as B. To this aim
it suffices to describe how to translate a domain description D of B to a B0MV domain
description D′ , in such a way that the semantics of the domain is preserved. Let us outline
the main points of such a translation.
Each Boolean fluent f in D can be modeled in B0MV by a multi-valued fluent f ′ whose
domain is V = {0, 1} ⊆ Z.
Each action in D uniquely corresponds to an action in D′ .
Let us consider a dynamic causal law of D, e.g.,
causes(a, f, [f1 , . . . , fk , neg(g1 ), . . . , neg(gh )]).

Multi-valued Action Languages in CLP(FD)

35

This law is translated in D′ as
causes(a, f ′ = 1, [f1′ = 1, . . . , fk′ = 1, g1′ = 0, . . . , gh′ = 0]).

In a similar manner, static laws and executability conditions of D are mapped into B0MV .
Consequently, the two domain descriptions D and D′ describe two isomorphic transition
systems.
6.2 Adding annotated fluents and non-Markovian references
In this section, we generalize the treatment described in Section 6.1 in order to provide
a state-transition semantics for B MV suitable to cope with temporal references. The first
form of temporal references involves annotated fluents and concerns relative access to their
past values, w.r.t. the current state. There is no restriction on the occurrences of this kind of
annotated fluents: they might be used in all laws of a domain description. In this case, the
extension of the semantics described in Section 6.1 comes rather naturally. Since references
may relate different points in time along the plan, the approach consists of considering
sequences of states instead of pairs of states, to define the transition constraints.
Regarding references to future points in time (i.e., positively annotated fluents), we recall
that they are admitted in the consequences of dynamic causal laws only. This restriction
allows the treatment of future and past references by exploiting the very same mechanisms.
The semantics is further enriched in Section 6.4 to encompass state constraints specified
by using absolute time references, as well as costs.
Let ~v = hv0 , . . . , vN i be a state sequence. Given ~v , and i ∈ {0, . . . , N}, we define the
concept of value of ϕ in ~v at time i (with abuse of notation, denoted by ~v (i, ϕ)) as follows:8
~v (i, x) = x if x ∈ V
~v (i, f j ) = vi+j (f ) if f ∈ F , and 0 6 i + j 6 N
~v (i, f j ) = v0 (f ) if f ∈ F and i + j < 0
~v (i, f j ) = vN (f ) if f ∈ F and i + j > N
~v (i, abs(ϕ)) = |~v (i, ϕ)|
~v (i, −(ϕ)) = −(~v (i, ϕ))
~v (i, ϕ1 ⊕ ϕ2 ) = ~v (i, ϕ1 ) ⊕ ~v (i, ϕ2 )
~v (i, rei(C)) = 1 if ~v |=i C
~v (i, rei(C)) = 0 if ~v 6|=i C
where n ∈ V, ⊕ ∈ {+, −, ∗, /, mod}.
As for (10) of Section 6.1, the semantics of reified constraints relies on the notion of
satisfaction, which in turn has to be contextualized to a specific point in time i. More
formally, given a fluent constraint ϕ1 op ϕ2 and a state sequence ~v, the notion of satisfaction
at time i is defined as ~v |=i ϕ1 op ϕ2 ⇔ ~v (i, ϕ1 ) op ~v (i, ϕ2 ). The notion |=i is generalized
to the case of propositional combinations of fluent constraints in the usual manner.
Given a constraint C, let >-fluents(C) be the set of annotated fluents f i , for i > 0,
8

A slightly simplified treatment could be described if only past references are admitted. In this case, we consider i to be the current point in time and j to be negative. The notation could then be simplified by considering
just a prefix ~
v = hv0 , . . . , vi i of the state sequence.

36

A. Dovier, A. Formisano, E. Pontelli

occurring in C. Given a state sequence ~v = hv0 , . . . , vi i, with 0 6 i < N, a function
σ : >-fluents(C) −→ V is an i-solution of C w.r.t. ~v , if it holds that
hv0 , . . . , vi , ine(σ|0 , vi ), (σ|1 ), . . . , (σ|N−(i+1) )i |=i+1 C,
where each σ|k (for k > 0) is the restriction of the assignment σ to the fluent annotated
with k, and µ denotes the substitution obtained by completing µ, with assignment to ⊥ for
all fluents not in dom(µ). Note that we treat the interpretation of the various operations as
strict w.r.t. ⊥ and we assume satisfied all constraints that refer to undefined expressions.
Hence, for instance, if C is constraint and there is a sub-expression ψ of C evaluated as ⊥,
then we assume ~v |=i C.
Example 13
Let N = 3 and i = 1. Consider the constraint C ≡ (g 0 = f −1 + f −2 ) and let ~v =
hv0 , v1 i = h{f /2, g/1}, {f /1, g/2}i.
Then σ = {g/3} = σ|0 is a 1-solution of the constraint C, since
• ine(σ|0 , {f /1, g/2}) = ine({g/3}, {f /1, g/2}) = {f /1, g/3}, and
• h{f /2, g/1}, {f /1, g/2}, {f /1, g/3}, {f /⊥, g/⊥}, i |=2 g 0 = f −1 + f −2 , in fact,
we have that ~v (2, C) is ~v (2, g 0 ) = ~v (2, f −1 + f −2 ), which is equivalent to v2 (g 0 ) =
v1 (f ) + v0 (f ).

A state sequence ~v = hv0 , . . . , vh i is closed w.r.t. a set of static causal laws
SL = {caused(C1 , D1 ), . . . , caused(Ck , Dk )}
if for all i ∈ {0, . . . , h} it holds that ~v |=i (C1 → D1 ) ∧ · · · ∧ (Ck → Dk ).
We also generalize the notion of minimal closure as follows: given a state sequence
~v = hv0 , . . . , vi i and a state v ′ we say that v ′ is minimally closed w.r.t. ~v , D, and SL if
• hv0 , . . . , vi , v ′ i is closed w.r.t. SL
• for all sets of fluents S ⊆ D, if the state ∆(vi , v ′ , S) is different from v ′ , then
hv0 , . . . , vi , ∆(vi , v ′ , S)i is not closed w.r.t. SL.
The action a is executable in ~v at time i if there is an axiom executable(a, C) such
that ~v |=i C.
Let us denote with Dyn(a) the set of dynamic causal laws for an action a. The effects
of executing a in ~v at time i, denoted by Eff (a, ~v , i), is
^
Eff (a, ~v , i) =
{P C | causes(a, P C, C) ∈ Dyn(a), ~v |=i C}

Given a constraint C, we denote by shift t (C) the constraint obtained from C by replacing each fluent f x with f x−t .
Let us assume that ~v = hv0 , . . . , vi i is a sequence of complete states and that ~a is a sequence of actions ha1 , . . . , ai+1 i. The effects of the sequence of actions in ~v is represented
by the formula
E(i, ~a, ~v ) =

i
^

j=0

i ^
 ^
shift j−i Eff (aj+1 , ~v , j) ∧
f j−i = vj (f )
j=0 f ∈F

Multi-valued Action Languages in CLP(FD)

37

Let us observe that this constraint might involve all fluents of the states v0 , . . . , vi , as
well as fluents of future states. The values of fluents in states v0 , . . . , vi are fixed by ~v .
Let hD, Oi be a planning problem instance, ~v = hv0 , . . . , vN i be a sequence of complete
states and a1 , . . . , aN be actions. Then, hv0 , a1 , v1 , . . . , aN , vN i is a valid trajectory if the
following conditions hold:
•
•
•
•

hv0 , . . . , vN i is closed w.r.t. SL
for each axiom of the form initial(C) in O, we have that ~v |=0 C
for each axiom of the form goal(C) in O, we have that ~v |=N C
for each i ∈ {0, . . . , N − 1} the following conditions hold
— action ai+1 is executable in ~v at time i and
— we have that vi+1 = ine(σ|0 , vi+1 ) where
– σ is a i-solution of the constraint E(i, ha1 , . . . , aN i, hv0 , . . . , vN−1 i) w.r.t.
hv0 , . . . , vi i,
– vi+1 is minimally closed w.r.t. hv0 , . . . , vi i, F \ dom(σ), and SL.

Example 14
Let us consider the following domain specification and planning problem instance (for
N = 2):
fluent(f, 1, 5).
fluent(g, 1, 5).
fluent(h, 1, 5).
action(a).
action(b).
executable(a, true).
executable(b, true).
causes(a, g 0 = g −1 + 2, true).
causes(b, f 0 = g −1 + h−2 , true).
initially(f = 1).
initially(g = 1).
initially(h < 3).
goal(f > 4).
Observe that the only valid trajectory is
h{f /1, g/1, h/2}, a, {f /1, g/3, h/2}, b, {f /5, g/3, h/2}i.
The validity can be verified by observing that:
• {f /1, g/1, h/2} satisfies all the constraints provided in the initial declarations;
• {f /5, g/3, h/2} satisfies the goal constraint f > 4;
• the action a is executable in hv0 i = h{f /1, g/1, h/2}i and action b is executable in
hv0 , v1 i = h{f /1, g/1, h/2}, {f /1, g/3, h/2}i
(since both their executability laws and the action conditions are trivially true).
• Consider the first state transition and i = 0 and note that >-fluents(g 0 = g −1 + 2) =
{g}. Then, σ ′ = {g/3} is a 0-solution of g 0 = g −1 + 2 w.r.t. h{f /1, g/1, h/2}i. In
fact, σ ′ |0 = σ ′ , σ ′ |1 = {}, and

38

A. Dovier, A. Formisano, E. Pontelli
— v1 = ine(σ ′ |0 , v0 ) = ine({g/3}, {f /1, g/1, h/2}) = {f /1, g/3, h/2}
— hv0 , v1 , σ ′ |1 i = hv0 , v1 , {f /⊥, g/⊥, h/⊥}i |=1 g 0 = g −1 + 2.
— v1 is minimally closed w.r.t. h{f /1, g/1, h/2}i, {f, h} and ∅.
• Consider the second state transition and i = 1 and note that >-fluents(f 0 = g −1 +
h−2 ) = {f }. Then, σ ′′ = {f /5} is a 1-solution of f 0 = g −1 + h−2 w.r.t. hv0 , v1 i.
In fact, σ ′′ |0 = σ ′′ , and
— v2 = ine(σ ′′ |0 , v1 ) = ine({f /5}, {f /1, g/3, h/2}) = {f /5, g/3, h/2}
— hv0 , v1 , v2 i |=2 f 0 = g −1 + h−2 .
— v2 is minimally closed w.r.t. hv0 , v1 i, {g, h} and ∅.



6.3 Abstract implementation of B MV
The constraint encoding for B MV is similar to the one developed earlier for the case of
B0MV (cf., Figures 8 and 10). In the encoding of a trajectory hv0 , a1 , v1 , . . . , aN , vN i in
B0MV , we introduced a variable Ffvi to represent the value of the fluent f in the ith state vi .
In each state transition, say from vi to vi+1 , the implementation of B0MV imposes only
constraints involving the variables/fluents of the current state. In the language encompassing timed references, each constraint occurring in the action description can address the
values that fluents assume in any of the states of the sequence ~v = hv0 , . . . , vN i. Since
all the variables representing these values are present in the encoding, only the following
change is needed to adapt to B MV the implementation designed for B0MV : to obtain from a
constraint C (involving fluents), a constraint C ~v ,i (involving the corresponding variables),
v
at time i, we replace each f j with the variable Ff i+j .
By adopting this refined construction for C ~v,i , we can inherit all the results of Section 6.1.4. In particular, for an action description D, similarly to what done in Section 6.1.4,
v
,v
~
v ,ai
and by Form(D)~v ,ai the constraints homologous to CFi−1 i and
we denote by CF
vi−1 ,ai
Form(D)
, respectively.
The completeness result for B MV directly generalizes that obtained for B0MV . With
regards to soundness, the observation made w.r.t. B0MV in Section 6.1.4 still applies. In
fact, let hD, Oi be an instance of a planning problem where D is a domain description and
O contains axioms of the form initially(C) and goal(C). We state the following:
Theorem 11
There is a valid trajectory ~v = hv0 , a1 , v1 , . . . , vN , vN i if and only if
• ~v is closed w.r.t. SL
• There is a solution for the constraint
^

initially(C)∈O

C ~v ,0 ∧

N−1
^
j=0

~
v ,aj+1

CF

∧

^

C ~v ,N

goal(C)∈O

• For each j ∈ {0, . . . , N − 1} the formula Form(D)~v ,aj+1 is unsatisfiable.

Multi-valued Action Languages in CLP(FD)

39

6.4 Adding costs and global constraints
Cost and time constraints can be introduced by filtering the solutions characterized by Theorem 11, in order to rule out the unsatisfactory solutions. More precisely, given a trajectory
hv0 , a1 , v1 , . . . , aN , vN i satisfying the requirements of Theorem 11, we say that the trajectory satisfies a set of global constraints as described in Sections 5.1 and 5.2 if all the
constraints described next hold.
Let us start by investigating the cost constraints. Let
action cost(a1 , F E1 ), . . . , action cost(aN , F EN )

and state cost(F E ′ ) be specified in the action description.9
Let us recall that the general form of cost constraints is cost constraint(C), where
C is a constraint defined as in Section 5, with the added ability to refer to the atoms plan,
goal, and state(i) wherever fluents can be used. Consequently, we extend our definition
of value of an expression ϕ in ~v = hv0 , . . . , vN i at time i (for all j):
~v (j, plan) = v0 (F E1 ) + · · · + vN−1 (F EN )
~v (j, goal) = vN (F E ′ )
~v (j, state(i)) = vi (F E ′ ) if 0 6 i 6 N
(assigning cost constraints to to states outside the plan is senseless. However, for completeness, for i < 0 or i > N we set ~v (j, state(i)) = 0 but any other choice — e.g., ⊥, or the
values on states 0 or N — is reasonable). This modification allows us to derive the notion
of satisfaction of a cost constraint C from the notion of satisfaction defined in Section 6.3.
As particular cases, we obtain that:
• for each assertion cost constraint(plan op k) the plan cost (v0 (F E1 ) + · · · +
vN−1 (F EN )) has to satisfy the stated constraint, i.e., it must hold that (v0 (F E1 ) +
· · · + vN−1 (F EN )) op k;
• for each assertion cost constraint(goal op k), the cost vN (F E ′ ) of the goal
state must satisfy the constraint: vN (F E ′ ) op k;
• for each assertion cost constraint(state(i) op k), the cost vi (F E ′ ) assigned
to the ith state has to satisfy the constraint vi (F E ′ ) op k.
The handling of time constraints requires the following modifications:
• for each assertion time constraint(C), it holds that hv0 , . . . , vN i |=0 C, where
each timed fluent f @i is evaluated as vi (f );
• for each assertion of the form holds(C, i) it holds that hv0 , . . . , vN i |=i C;
• for each assertion of the form always(C), it holds that hv0 , . . . , vN i |=i C for all
i ∈ {0, . . . , N}.
Moreover, if minimize cost(F E ′′ ) is specified, then there exists no other trajectory ~v ′
such that ~v ′ (N, F E ′′ ) < ~v (N, F E ′′ ). As particular cases, we have that
• if minimize cost(plan) is specified, then there exists no other trajectory having a
smaller plan cost;
9

As mentioned, if some of these assertion is missing a default cost 1 is assumed.

40

A. Dovier, A. Formisano, E. Pontelli
• if minimize cost(goal) is specified in the action description, then there is no tra′
′
jectory hv0′ , a′1 , v1′ , . . . , a′N , vN
i, fulfilling all constraints, and such that vN
(F E ′ ) <
′
vN (F E ).

In this manner, we characterize the solutions of a given planning problem to be exactly
those solutions described by Theorem 11 that additionally satisfy all the global constraints,
the requirements on costs, and the time constraints expressed in the action description.
Soundness and completeness properties directly carry over.
7 Concrete Implementation of B MV
The overall structure of the concrete implementation of the language B MV follows that
used for implementing the B language. We focus here on the main differences.
To start, let us briefly describe the code depicted in Figure 11 and show that this concrete
implementation reflects the abstract one defined in Figure 8.10 Hence, we preliminarily
ignore lines (65)–(66) of Figure 11.
The first difference w.r.t. the implementation of B (cf., Section 3) is that each fluent
variable is assigned to a finite set domain, drawn from the fluent declaration—instead of
being treated as a Boolean variable.
The predicate set one fluent (lines (56)–(68)) has a similar role as in the implementation of B. Given the fluent FluentName, the relevant parts of the dynamic causal laws
are collected in lines (57)–(59). The predicate zero subterm is an auxiliary predicate that
detects if a constraint involves a fluent—i.e., it looks for an occurrence of FluentName in
the constraint imposed by the dynamic causal laws. All the fluents explicitly involved in
the consequence of a dynamic law are collected. In line (63), the variable EV identifying
the fluent FluentName in the following state ToState is retrieved.
The predicate dynamic (line (64)) collects the list of Boolean flags DynFormula. If one
of the variables in Dyn is true then the variable EV is involved in a constraint imposed by
a dynamic causal law. In line (67) the disjunction of these flag variables is computed in
Formula (let us ignore, for the time being, the variable StatFormula). In line (68) the
inertia constraint is added: if Formula is false then the value of the fluent is left unchanged
by the transition (i.e., IV = EV). This corresponds to the ine(·) operator.
For each action Act affecting the value EV, the predicate dynamic (lines (69)–(82)) retrieves its preconditions and builds the constraint C involving EV that must be imposed if
the preconditions are satisfied. The flag variable Flag in line (80) is introduced to keep
track of the fact that the action has occurred (i.e., VA is true) and the corresponding precondition holds. If Flag is true then the constrain C is asserted (line (81)). All flags are stored
in a list (cf., the variable DynFormula in line (64)).
Lines (83)–(114) provide an excerpt of the definition of the predicate rel parsing.
This predicate is used to transform fluent expressions to internal expressions involving
fluent variables. States is a list of states (each of them, in turn is a list of all the fluent
variables). The first argument is the fluent expression and the second one is the output
10

Observe that the concrete implementation uses the functors eq, neq, etc. to denote the primitive constraints
=, 6=, etc.

Multi-valued Action Languages in CLP(FD)

41

(56)
(57)
(58)
(59)
(60)
(61)
(62)
(63)
(64)
(65)
(66)
(67)
(68)

set one fluent(fluent(FluentName,IV), ActionOccs, Now, States) :findall([Act,OP,FE1,FE2,L],
(causes(Act,FC,L), zero subterm(FluentName,FC),
FC =.. [OP,FE1,FE2]), Dyn),
state select(Now, States, FromState),
Next is Now+1,
state select(Next, States, ToState),
member(fluent(FluentName,EV), ToState),
dynamic(Dyn, ActionOccs, FromState, DynFormula, Next, States),
cluster rules(FluentName, Stat), %%% These 2 lines can be dropped in
static(Stat, States, Next, StatFormula),%%% absence of static laws
bool disj(DynFormula, StatFormula, Formula),
#\ Formula #=> EV #= IV.

(69)
(70)
(71)
(72)
(73)
(74)
(75)
(76)
(77)
(78)
(79)
(80)
(81)
(82)

dynamic([], , , [], , ).
dynamic([[Act,OP,FE1,FE2,Prec]|Rest],AOccs,State,[Flag|PF1],Now,States) :member(action(Act,VA), AOccs),
Last is Now-1, %%% Looks for preconditions in FromState and before
get precondition vars(Last, Prec, States, ListPV),
length(Prec, NPrec),
sum(ListPV, SumPrec),
%%% The effect is in the next state (Now=Last+1)
rel parsing(FE1, Val1, Now, States),
rel parsing(FE2, Val2, Now, States),
exp constraint(Val1, OP, Val2, C),
(VA #/\ (SumPrec #= NPrec)) #<=> Flag,
Flag #=> C,
dynamic(Rest, ActionOccs, State, PF1, Now, States).

(83)
(84)
(85)
(86)
(87)
(88)
(89)
(90)
(91)
(92)
(93)
(94)
(95)
(96)
(97)
(98)
(99)
(100)
(101)
(102)
(103)
(104)
(105)
(106)
(107)
(108)
(109)
(110)
(111)
(112)
(113)
(114)

rel parsing(Num, Num, , ) :integer(Num), !.
rel parsing(rei(RC), Val, Time, States) :RC =.. [OP,E1,E2],
rel parsing(E1, Val1, Time, States),
rel parsing(E2, Val2, Time, States),
exp constraint(Val1, OP, Val2, Val), !.
rel parsing(abs(FE), Val, Time, States) :- %%% similar for -(FE)
rel parsing(FE, Val1, Time, States),
Val #= abs(Val1), !.
rel parsing(FE, Val, Time, States) :FE =.. [OP,FE1,FE2],
member(OP, [+,-,mod,/,*]),
rel parsing(FE1, Val1, Time, States),
rel parsing(FE2, Val2, Time, States),
( OP = + -> Val #= Val1 + Val2;
OP = - -> Val #= Val1 - Val2;
OP = * -> Val #= Val1 * Val2;
OP = / -> Val #= Val1 / Val2;
OP = mod -> Val #= Val1 mod Val2 ), !.
rel parsing(FluentˆDelta, Val, Time, States) :H is Time+Delta,
length(States,N),
in interval(H,N,E),
state select(E, States, State),
member(fluent(Fluent,Val),State),!.
rel parsing(Fluent @ Time, Val, , States) :state select(Time,States,State),
member(fluent(Fluent,Val),State), !.
rel parsing(Fluent, Val, Time, States) :state select(Time, States, State),
member(fluent(Fluent,Val), State).

(115)
(116)

parsing(Fluent, Val, State) :rel parsing(Fluent, Val, 0, [State]).

(117)
(118)
(119)
(120)
(121)
(122)
(123)

exp constraint(L, OP, R, C) :(OP == eq -> C #<=> L #= R;
OP == neq -> C #<=> L #\= R;
OP == geq -> C #<=> L #>= R;
OP == leq -> C #<=> L #=< R;
OP == gt -> C #<=> L #> R;
OP == lt -> C #<=> L #< R).

Fig. 11. Relevant parts of the B MV implementation.

42

A. Dovier, A. Formisano, E. Pontelli

internal expression. The argument Time represents the specific point in time in which a
fluent is referred to (cf., the variable Now used in lines (69)–(82) and (124)–(134) to specify
the precise point in time in which a fluent expression/constraint has to be evaluated). The
predicate in interval called in line (106) sets E = H if 0 ≤ H ≤ N, E = 0 (resp.,
E = N) if H < 0 (resp., H > N). Similarly, predicate exp constraint (lines (117)–(123))
transforms fluent constraints into the corresponding constraints on the fluent variables.
The above described fragment of implementation is completed with the code needed to
handle initial and goal state specifications. Namely, for a specific instance of a planning
problem hD, Oi, as done for B, all constraint on the initial state (resp., those on the goal
state) are reflected by constraining the variables Ff in the representation of the initial (resp.,
final) state.
We proceed by splitting the correctness proof into steps. We can now state the following
result.11
Theorem 12
The concrete implementation (partially depicted in Figure 11) is correct and complete w.r.t.
the system of constraints of Figure 8.
Proof
This result immediately follows from the above argument. In fact, the constraint (11) of
Figure 8 is implicitly rendered by domain assignment for CLP variables. Constraints (13)
and (14) are dealt with in lines (57)–(64). Line (68) imposes constraint (15). Concerning
the sequentiality of the plan and the executability conditions (i.e., constraint (12)), we can
observe that the implementation does not differ from that of B (in Figure 11 we omitted
the corresponding code, see Figure 7).
(124)
(125)
(126)
(127)
(128)
(129)
(130)
(131)
(132)
(133)
(134)

static([], , , []).
static([[OP,FE1,FE2,Cond]|Others], States, Now, [Flag|Flags]) :get precondition vars(Now, Cond, States, List),
length(List, NL),
sum(List, Result),
rel parsing(FE1, Val1, Now, States),
rel parsing(FE2, Val2, Now, States),
exp constraint(Val1, OP, Val2, C),
(Result #= NL) #<=> Flag,
Flag #=> C,
static(Others, States, Now, Flags).

Fig. 12. Static causal laws treatment
Let us now consider the presence of static causal laws. In Figure 12, we list the predicate
used to add constraints for the static causal laws. Notice that the concrete implementation
of Figure 12 contains a discrepancy with respect to the abstract one of Figure 10. In particular, the concrete implementation does not deal with an intermediate state (named v in the
abstract implementation). The fluents of the target state are computed by exploiting direct
relationships with the starting state of the transition. This allows us to introduce fewer CLP
variables.
11

When establishing completeness an soundness results for the concrete implementation, we assume the same
properties hold for the real implementation of the CLP(FD) solver at hand (in our case, SICStus Prolog).

Multi-valued Action Languages in CLP(FD)

43

In line (65) of Figure 11 the predicate cluster rules collects all the (static) conditions
imposed on the fluents of the cluster of FluentName. The call to the predicates static
(line (66)) collects the list of Boolean flags StatFormula which are used to model the
constraints (19) and (20) of Figure 10. In line (67), the disjunction of these flag variables,
together with those originating from the dynamic causal laws (i.e., DynFormula), is computed in Formula, as explained above.
For each condition implied by a static causal law, the predicate static (lines (124)–
(134)) builds the constraint C that must be imposed to ensure closure. The flag variable
Flag in line (132) is introduced to reflect the satisfaction of the constraint. If Flag is true
then the constrain C is asserted (line (133)). All such flags are stored in the list Flags (cf.,
the variable StatFormula).
We have the following result:
Theorem 13
The concrete implementation (partially depicted in Figures 11 and 12) is complete w.r.t.
the system of constraints of Figures 8 and 10.
Proof
The result directly follows from the above argument. Constraint (16) of Figure 10 is implicitly rendered by the domain assignment for the CLP variables (let us remember that the
intermediate state v is not explicit in the concrete implementation). Constraints (11)–(15)
are dealt with as done in Theorem 12. The conditions originating from the static causal
laws are dealt with through the predicates cluster rules and static.
Let us observe that there is a second difference between the concrete implementation of
Figures 11 and 12 and the abstract one of Figure 10: no requirements for the unsatisfiability
of Form(D)~v ,ai are imposed in correspondence of the state transition from vi−1 to vi (for
any i). This allows the generation of state transitions where the target state is potentially
not minimally closed. This means that the concrete implementation may produce solutions
(i.e., plans) that the abstract semantics would forbid because of the non-minimal effects of
(clusters of) static causal laws. On the other hand, we reflect constraints (19) and (20) as
described earlier, through the predicates static (listed in Figure 12) and cluster rules
(whose obvious code is omitted).
The final step in the design of the concrete implementation is the introduction of suitable
restrictions on the labeling phase of the CLP solver. Notice that, if at step i in a trajectory,
a consequence of a dynamic law involves a fluent f j , for j > i, then such a constraint
has to be evaluated considering as already assessed all the states vh preceding vi . Hence,
the labeling has to proceed “left-to-right” w.r.t. the CLP variables that model the states
v1 , . . . , vi . In other words, when searching for a solution, the variables representing the
state vh have to be labeled before those representing the state vh+1 , for each vh in the
trajectory. The implementation of this labeling strategy is depicted in Figure 13. Moreover,
observe that we impose further restrictions (through the predicate no loop in lines (147)–
(155)) to avoid loops in plans, i.e., to forbid those trajectories where the same state appears
twice.
To complete the implementation of B MV we need to take care of the cost-based constraints, whose behavior relies on the optimization features offered by SICStus’ labeling
predicate: the labeling phase is guided by an objective function to be optimized.

44

A. Dovier, A. Formisano, E. Pontelli

(135)
(136)
(137)
(138)
(139)
(140)
(141)
(142)
(143)
(144)
(145)
(146)

lm labeling(Actionsocc, States) :lm labeling(Actionsocc, States, 1).
lm labeling([], , ) :- !.
lm labeling([CurrAct|Actions], States, I) :lm labeling aux(CurrAct),
no loop(States, I),
I1 is I+1,
lm labeling(Actions, States, I1).
lm labeling aux([]).
lm labeling aux([action( ,A)|R]) :indomain(A),
lm labeling aux(R).

(147)
(148)
(149)
(150)
(151)
(152)
(153)
(154)
(155)

no loop(States, A) :state select(A, States, StateA),
no loop(A, States, StateA).
no loop(0, , ) :- !.
no loop(B, States, StateA) :B1 is B-1,
state select(B1, States, StateB),
StateA \== StateB,
no loop(B1, States, StateA).

Fig. 13. Implementation of a leftmost labeling strategy.

Constraints on costs, as well as absolute temporal constraints, are handled by asserting
suitable CLP constraints on the variables that model fluent values. This is realized through
the predicates listed in Figure 14. In particular, set cost constraints deals with constraints on actions/plans and states. For instance, set statecosts (line 167) retrieves
all the assertions of the form cost constraint(state(I) OP Num) and imposes the
corresponding constraints. A similar predicate set goal (not reported in the figure) accomplishes the same for the final state only. The predicate set plancost acts similarly,
using the predicate make one action occurrences (lines (192)–(193)) where the cost
for each single action is considered.
All the absolute temporal constraints defined in the action description are handled by
the predicate set time constraint (cf., lines (194)–(202)). Also in this case, direct references to CLP variables implement the references to fluent expressions in any absolute
point in time.
As mentioned, all these constraints can be seen as filters used to validate each trajectory found by the labeling phase. The planner described in Figures 11–13 is completed
by adding the code in Figure 14. Completeness of the implementation of the full B MV
immediately follows from the above discussion.

8 Experimental Analysis
We implemented CLP-based prototypes of B and B MV . These have been realized in SICStus Prolog 4, and they have been developed on an AMD Opteron 2.2GHz Linux machine.
Extensive testing has been performed to validate our CLP-based approach. Here we concentrate on a few representative examples. The source code of the implementations and the
examples can be found at www.dimi.uniud.it/dovier/CLPASP. No particular built-in
predicates of SICStus have been used and therefore porting to other CLP-based Prolog

Multi-valued Action Languages in CLP(FD)
(156)
(157)
(158)
(159)

set cost constraints(States, PlanCost, GOALCOST) :set goalcost(States, GOALCOST),
set plancost(PlanCost),
set statecosts(States).

(160)
(161)
(162)
(163)
(164)
(165)
(166)

set plancost(PC) :findall([OP,Num],(cost constraint(C), C =.. [OP,plan,Num]), PlanCosts),
set plancost aux(PlanCosts,PC).
set plancost aux([], ).
set plancost aux([[OP,Num]|PlanCosts],PC) :add constraint(PC,OP,Num),
set plancost aux(PlanCosts,PC).

(167)
(168)
(169)

set statecosts(States) :findall([I,OP,N],(cost constraint(C), C =.. [OP,state(I),N]), Costs),
set statecost aux(Costs,States).

(170)
(171)
(172)
(173)
(174)
(175)

set statecost aux([], ).
set statecost aux([[I,OP,Num]|StateCosts],States) :(state cost(FE),!; FE = 1),
rel parsing(FE,Val,I,States),
add constraint(Val,OP,Num),
set statecost aux(StateCosts,States).

45

(176)
(177)
(178)
(179)
(180)
(181)
(182)
(183)
(184)
(185)
(186)
(187)
(188)
(189)
(190)
(191)
(192)
(193)

make action occs(N, ActionsOcc, PlanCost, Na) :setof(A, action(A), La),
length(La, Na),
make action occurrences(N, La, ActionsOcc, PlanCost).
make action occurrences(1, , [], 0).
make action occurrences(N, List, [Act|ActionsOcc], Cost) :N1 is N-1,
make action occurrences(N1, List, ActionsOcc, Cost1),
make one action occurrences(List, Act, Cost2),
get action list(Act, AList),
fd only one(AList),
Cost #= Cost1+Cost2.
make one action occurrences([], [], 0).
make one action occurrences([A|Actions], [action(A,OccA)|OccActs], Cost) :make one action occurrences(Actions, OccActs, Cost1),
fd domain bool(OccA),
(action cost(A,CA),!; CA = 1), %%%Default action cost = 1
Cost #= OccA*CA+Cost1.

(194)
(195)
(196)

set time constraints(States) :findall([FE1,OP,FE2], (time constraint(C),C =.. [OP,FE1,FE2]), TimeCs),
set time constraints(TimeCs, States).

(197)
(198)
(199)
(200)
(201)
(202)

set time constraints([], ).
set time constraints([[FE1,OP,FE2]|Rest], States) :rel parsing(FE1, Val1, , States),
rel parsing(FE2, Val2, , States),
add constraint(Val1, OP, Val2),
set time constraints(Rest, States).

(203)
(204)

add constraint(L, OP, R) :exp constraint(L, OP, R, 1).

Fig. 14. Handling of global constraints and costs.

systems is straightforward. A porting to B-Prolog has been realized and used to participate
in the 2009 ASP Competition.12
In the rest of this section, we analyze the performance of the implementation on a diverse set of benchmarks. For each benchmark, we compare a natural encoding using the
traditional B language with an encoding using B MV .
The problems encoded in B have been solved using both the CLP(FD) implementation

12

See the web site http://www.cs.kuleuven.be/˜dtai/events/ASP-competition/Teams/Bpsolver-CLPFD.shtml

46

A. Dovier, A. Formisano, E. Pontelli

and implementations obtained by mapping the problem to ASP and using different ASP
solvers (Smodels, Clasp, and Cmodels with different SAT-solvers).
In order to solve a B-planning problem hD, Oi using an ASP solver, we have developed
a Prolog translator that takes as input hD, Oi and the plan length n, and it generates an
ASP program, whose stable models are in one-to-one correspondence with the plans of
length n for hD, Oi. This encoding follows the general ideas outlined in (Lifschitz 1999).
In particular, the definitions of fluent, action, and initially are already in ASP
syntax. The length of the plan n is used to define the predicate time(0..n). The ASPbased planner makes use of a choice rule to ensure that exactly one action is applied at
each time step:
1{occ(Act,Ti):action(Act)}1 :- time(Ti), Ti < n.
The predicate hold(Fluent,Time) defines the truth value of a fluent Fluent at a given
time step (Time). The truth value of the fluents at time 0 are given as facts describing the
initial state; we require the initial state to be complete. The executability rules, the dynamic
causal laws and the static causal laws are instantiated for each admissible time step. Finally,
the goal conditions are added to define the predicate goal; the requirement that the goal
has to be satisfied at the end of the plan is imposed using an ASP constraint of the form
:- not goal.
As far as the CLP-based implementations are concerned, we use a leftmost variable
selection strategy. Moreover, we included a loop control feature to avoid the repetition of
the same state in a trajectory (cf., the predicate no loop in Figure 13).
Tables 1–5, discussed in detail in the next subsections, illustrate an excerpt of the experimental results. In order to simplify the comparison among the solvers, in each table
we introduce an extra column, denoted by “Best ASP,” which indicates the performance
of an hypothetical ASP-solver that always acts as the best between all the ASP-solvers
considered.
The specific meaning of the various columns is as follows:
•
•
•
•
•
•
•
•
•

•

Instance: the name of the specific instance of the problem
Length: the plan length used in searching for a solution
Answer: indication of whether an answer exists or not for the given plan length
lparse: the time required to ground the ASP encoding of the problem (using lparse
1.1.1)
Smodels: the execution time using the Smodels system (using Smodels 2.32)
Cmodels: the execution time using the Cmodels system (using Cmodels 3.70 with
different SAT solvers)
Clasp: the execution time using the Clasp system (using Clasp 1.0.2)
Best ASP: a summary of the best execution time across all the different ASP solvers
CLP(FD): the execution time using the CLP(FD)-based implementation of B. Execution times have the form t1 +t2 , where t1 is the time needed for posting constraints
and t2 the time for solving the constraints (i.e., finding a plan)
B MV : the execution time using the B MV encoding of the problem. The first column
is related to computations where no constraints for the plan cost are imposed. Instead, the computations of the second column have a constraint that limits the plan

Multi-valued Action Languages in CLP(FD)

47

cost to the number in parenthesis. The format is t1 + t2 as explained in the previous
point.
In the remaining subsections we briefly describe the benchmarks tested and the obtained
results. The actual encoding in B and B MV have been placed in the Appendix for the
sake of readability. A summary and a discussion of all the experiments is presented in
Section 8.6.
8.1 Three-barrel Problem
We experimented with different encodings of the three-barrel problem. Our formulation is
as described in Example 1. Figure 1 and Section A.1 show the encoding of the problem
(for N = 12) in B and in B MV , respectively. Notice that, in order to represent each multivalued fluent f of the B MV formulation, a number of Boolean fluents have to be introduced
in the B encoding, one for each admissible value of f .
Table 1 provides the execution times (in seconds) for different values of N and different
plan lengths. The results show that the constraint-based encoding of B outperforms the
ASP encodings (if we consider both grounding and execution). In turn, the B MV encoding outperforms all other encodings. This can be explained by considering that the CLP
encoding of this problem benefits from numerical fluents (in reduced number, w.r.t. the B
formulation) and from arithmetic constraints (efficiently handled by CLP(FD)).
8.2 2-Dimensional Protein Folding Problem
The problem we have encoded is a simplification of the protein structure folding problem.
The input is a chain α1 α2 · · · αn with αi ∈ {0, 1}, initially placed in a vertical position, as
in Figure 15-left. We will refer to each αi as an amino acid. The permissible actions are
the counter-clockwise/clockwise pivot moves. Once one point i of the chain is selected, the
points α1 , α2 , . . . , αi will remain fixed, while the points αi+1 , . . . , αn will perform a rigid
counter-clockwise/clockwise rotation. Each conformation must be a self-avoiding-walk,
i.e., no two amino acids are in the same position. Moreover, the chain cannot be broken—
i.e., two consecutive amino acids are always at points at distance 1 (i.e., in contact). The
goal is to perform a sequence of pivot moves leading to a configuration where at least k
non-consecutive amino acids of value 1 are in contact. Figure 15 shows a possible plan to
reach a configuration with 4 contacts. Table 2 reports some execution times. Section A.2
reports the B MV action description encoding this problem. Since the goal is based on the
notion of cost of a given state, for which reified constraints are used extensively, a direct
encoding in B does not seem to be feasible.
Let us consider the resolution of the instance depicted in Figure 15, i.e., the folding of
the input chain 1001001001 of n = 10 amino acids. Asking for a plan of 8 (resp. 10) moves
and for a solution with cost > 4, our planner finds the 8-moves plan shown in Figure 15center in 50.46s (a 10-moves plan in found in 603.37s). By removing the two constraints
that keep fixed α2 :
always(x(2) eq 10).
always(y(2) eq 11).

Answer

8-5-3
8-5-3
8-5-3
8-5-3
12-7-5
12-7-5
12-7-5
12-7-5
16-9-7
16-9-7
16-9-7
16-9-7
20-11-9
20-11-9
20-11-9
20-11-9

B

Length

A. Dovier, A. Formisano, E. Pontelli

Barrels’
capacities

lparse

6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

N
Y
Y
Y
N
Y
Y
Y
N
Y
Y
Y
N
Y
Y
Y

8.74
8.92
8.87
9.03
34.47
34.54
35.42
35.69
115.47
114.03
115.60
114.60
185.38
186.76
186.31
189.28

Smodels
0.10
0.20
0.20
0.17
1.98
2.28
1.60
0.68
11.15
12.30
6.06
1.75
43.71
40.08
21.67
4.39

zchaff
0.34
1.87
7.34
17.60
153.36
98.72
125.84
342.40
1508.43
586.43
793.00
2963.37
2949.10
3053.53
1866.28
5482.78

Cmodels
relsat
0.63
2.39
3.63
5.02
14.56
15.78
20.45
42.36
613.42
58.45
151.56
128.91
2312.09
1187.10
2265.05
586.18

Clasp
minisat
0.30
0.55
0.62
0.60
41.34
11.71
83.06
97.99
75.67
65.19
157.38
145.11
493.98
1152.27
1378.93
1746.81

0.27
0.23
0.53
2.34
29.13
52.15
35.81
111.36
1838.39
1133.21
744.60
14106.98
–
11292.40
12286.98
–

Best
ASP
0.10
0.20
0.20
0.17
1.98
2.28
1.60
0.68
11.15
12.30
6.06
1.75
43.71
40.08
21.67
4.39

CLP(FD)
0.14+0.29
0.22+0.28
0.26+1.04
0.24+1.03
0.58+4.85
0.64+2.61
0.73+8.11
0.79+6.23
1.30+27.16
1.53+13.35
1.62+37.69
1.67+26.98
2.76+102.14
2.94+45.43
3.05+120.90
3.17+80.54

48

Table 1. Experimental results with various instances of the three-barrel problem (timeout 24000sec).

unconstrained
plan cost
0.03+0.03
0.03+0.02
0.05+0.07
0.02+0.05
0.04+0.13
0.02+0.07
0.07+0.18
0.07+0.14
0.03+0.31
0.06+0.13
0.07+0.37
0.07+0.27
0.09+0.58
0.09+0.24
0.09+0.68
0.10+0.46

BM V
constrained plan cost
(in parentheses)
(70)
0.02+0.03
(70)
0.02+0.02
(70)
0.01+0.06
(70)
0.02+0.06
(120)
0.04+0.13
(120)
0.03+0.07
(120)
0.05+0.19
(120)
0.07+0.14
(200)
0.07+0.31
(200)
0.07+0.14
(200)
0.07+0.36
(200)
0.07+0.27
(300)
0.08+0.57
(300)
0.10+0.24
(300)
0.09+0.65
(300)
0.10+0.43

Multi-valued Action Languages in CLP(FD)

19

10

✉
r
r
✉
r
r
✉
r
r
✉
10

pivot(2,clock)
pivot(3,clock)
pivot(9,clock)
pivot(8,clock)
pivot(7,antick)
pivot(6,clock)
pivot(4,antick)
pivot(5,clock)

10

1(001)3 -4

49

r r
✉✉r
✉✉r
r r
10

Fig. 15. An instance of the HP-protein folding problem: initial configuration, a plan, and
final configuration with 4 contacts between 1-amino acids.
Instance
17 -2
17 -2
113 -6
113 -6
1(001)2 -2
1(001)2 -2
1(001)3 -4
1(001)3 -4
1(001)3 -4
1(001)3 -4

Len.
3
4
3
4
3
4
7
8
9
10

Ans.
Y
Y
N
Y
N
Y
N
Y
?
Y

FD
BM
V
0.07+0.01
0.09+0.01
0.42+19.91
0.57+35.16
0.06+0.09
0.07+0.01
0.47+7521.13
0.49+50.46
–
0.63+603.37

Table 2. The HP-protein folding problem: some results for different sequences, and plan
lengths (timeout 12000sec).
the solutions are found in 52.72s and 617.68s, respectively. On the other hand, by keeping
fixed α2 and adding the two constraints
holds(x(3) eq 11,1).
holds(y(3) eq 11,1).

the execution time is reduced to 4.06s and 52.97s. Adding the additional constraints
holds(x(4) eq 11,2).
holds(y(4) eq 10,2).

the plans are found in only 0.37s and 4.62s. This shows that the use of multi-valued fluents
and the ability to exploit domain-specific knowledge, in the form of symmetry-breaking
constraints, allows B MV to effectively converge to a solution.
8.3 The Community Problem
The Community problem is formulated as follows. There are M individuals, identified by
the numbers 1, 2, . . . , M . At each time step, one of them, say j, gives exactly j dollars
to someone else, provided she/he owns more than j dollars. Nobody can give away all of

50

A. Dovier, A. Formisano, E. Pontelli

Room8

Room11

Room1

Room7

Room6

Room5

Room2
Room3

Room4

Answer

Room9

Length

Room10

Instance

her/his money. The goal consists of reaching a state in which all the participants have the
same amount of money.
Table 3 lists some results for four variants of the problem: the person i initially owns
2 ∗ i dollars (instances AM ), i + 1 dollars (instances BM ), i ∗ i dollars (instances CM ), or
i ∗ (1 + i) dollars (instances DM ).
The representations of this problem are reported in Sections A.3.1 and A.3.2.
Notice that the large number of Boolean fluents that have to be introduced in the B description causes failures due to lack of memory during the grounding phase (these instances
are marked “mem” in Table 3). For all these experiments, the bound on memory usage was
4 GB (for the grounder, the ASP-solvers, and the CLP(FD) engine). Observe that, in some
cases, also the CLP(FD)-based solver for B runs out of memory, while the failures of the
CLP(FD) solver for B MV have been caused by expiration of the time limit. In summary,
the constraint-based encodings provides better performance in most of the instances, especially considering their better scalability w.r.t. the size of the instances. This originates
from the smaller number of numerical fluents and from the efficiency of the underlying
constraint solver.

A1
A1
B1
B1
B1
B1
B1
B2
B2
B2
B2
B2
B3
B3
B3
B3
B3
B4
B4
B4
B4
B4

6
7
10
11
12
13
14
10
11
12
13
14
10
11
12
13
14
10
11
12
13
14

N
Y
N
Y
Y
Y
Y
N
Y
Y
Y
Y
N
Y
Y
Y
Y
N
Y
Y
Y
Y

BM V
0.07 + 13.48
0.10 + 5.35
0.17 + 3846.20
0.14 + 1802.76
0.15 + 933.35
0.16 + 302.34
0.14 + 4.60
0.13 + 11134.82
0.15 + 4191.20
0.16 + 2156.52
0.18 + 710.53
0.17 + 6.36
0.12 + 18763.27
0.16 + 6124.91
0.15 + 3148.43
0.20 + 1145.04
0.18 + 9.97
0.11 + 17109.05
0.15 + 6173.49
0.14 + 3180.53
0.16 + 1159.27
0.18 + 10.34

Fig. 16. On the left: a simple schema of the 11 rooms for the Gas-diffusion problem. The
locked gates are in red color. The gas (in pink) is flowing through the open gate (in green),
from Room7 to Room1 . On the right: some results for different instances (i.e., different
goals and initial allocations of amounts of gas—see Section 8.4).

Instance

Length

Answer

A4
A4
A4
A5
A5
A5
B5
B5
B5
B7
C5
C5
C7
D4
D4
D4
D5
D5

5
6
7
5
6
7
5
6
7
5
5
6
5
5
6
7
5
6

N
Y
Y
N
Y
Y
N
Y
Y
N
N
N
N
N
N
N
N
N

34.34
34.90
35.44
201.88
202.64
202.12
51.87
52.04
52.94
mem
mem
mem
mem
138.91
139.88
139.82
mem
mem

Smodels
11.12
1.43
15.72
100.58
11.43
34.02
30.04
2.07
13.49

zchaff
1.78
0.26
0.39
5.22
1.85
2.81
4.24
1.32
0.80

7.08
90.32
1015.44

1.28
11.56
104.36

B
Cmodels
relsat minisat
11.68
0.67
7.38
0.57
47.74
0.80
125.63
2.30
442.22
1.63
114.74
2.31
44.49
1.49
37.96
0.99
41.86
1.27

13.48
87.11
788.94

0.76
3.62
33.70

Clasp
0.45
0.09
0.10
1.19
0.28
0.27
0.69
0.14
0.42

Best
ASP
0.45
0.09
0.10
1.19
0.28
0.27
0.69
0.14
0.42

0.43
3.72
22.86

0.43
3.72
22.86

CLP(FD)

BM V
CLP(FD)

0.71+14.14
0.82+0.10
0.94+0.12
2.64+157.48
3.17+0.21
3.71+447.87
1.03+77.06
1.31+0.11
1.40+0.17
7.67+3345.56
16.98+85.71
20.44+1926.97
mem
3.70+21.19
4.32+0.50
5.17+5.55
24.64+24.12
29.60+1490.48

0.01+3.31
0.03+0.00
0.03+0.01
0.02+41.15
0.01+0.04
0.04+142.27
0.03+23.13
0.04+0.02
0.05+0.04
0.05+1421.54
0.02+49.83
0.04+888.30
0.05+3186.34
0.01+6.83
0.02+0.74
0.04+7.64
0.05+93.88
0.02+1801.78

Multi-valued Action Languages in CLP(FD)

lparse

Table 3. Experimental results for instances of the Community problem. “mem” denotes out-of-memory failures. Some results are missing for the
ASP solvers, for those instances that are unable to complete grounding.

51

52

A. Dovier, A. Formisano, E. Pontelli
8.4 The Gas-diffusion Problem

The Gas-diffusion problem can be formulated as follows. A building contains a number
of rooms. Each room is connected to (some) other rooms via gates. Initially, all gates
are closed and some of the rooms contain a quantity of gas—while the other rooms are
empty. Each gate can be opened or closed—open(x,y) and close(x,y) are the only
possible actions, provided that there is a gate between room x and room y. When a gate
between two rooms is open, the gas contained in these rooms flows through the gate. The
gas diffusion continues until the pressure reaches an equilibrium. The only condition to be
always satisfied is that a gate in a room can be opened only if all the other gates are closed.
The goal is to move a desired quantity of gas to one specified room.
We experimented with instances of the problem where the building has a specific topology: there are eleven rooms, all having the same physical volume. Each room is connected
to the other rooms via gates as depicted in Figure 16. Since all rooms have the same volume, when equilibrium is reached between two rooms sharing an open gate, they will both
contain the same amount of gas.
A B MV specification of this planning problem is given in Section A.6. We experimented
with different instances of the Gas-diffusion problem obtained by considering different
goal states and by requiring that some of the rooms have to be kept empty. Moreover, we
seek plans of different length. Figure 16 (on the right) summarizes the results obtained. In
particular, all instances share the same initial state: rooms 10 and 3 contain 128 moles of
gas. All the other rooms are empty. Moreover,
• in the instance A1 the goal state is: room 1 contains at least 32 moles of gas;
• in all the instances Bi the goal is: room 1 contains at least 50 moles of gas. The Bi
instances differ in the constraints imposed on the desired plan:
— in the instance B1 , rooms 7, 9, and 4 must remain empty. This condition can
be imposed by including in the action description the constraints
always(contains(7) eq 0).
always(contains(9) eq 0).
always(contains(4) eq 0).

— in the instance B2 , rooms 7, 8, and 5 must be kept empty.
— in the instance B3 , only room 6 must be kept empty.
— in the instance B4 , no constraint is imposed.
Observe that it is quite natural to design a B MV encoding of this problem, by exploiting
the multi-valued fluents. On the other hand, adopting the naive approach used for the threebarrel problem would force the introduction of (at least) 128 distinct boolean fluents for
each multi-valued fluent. Such a large number of boolean fluents generates a large state
space, making the task of any solver for B considerably harder.
8.5 Other Puzzles
We report results from two other planning problems. The first—3x3-puzzle—is an encoding of the 8-tile puzzle problem, where the goal is to find a sequence of moves to re-order

Multi-valued Action Languages in CLP(FD)

53

the 8 tiles, starting from a random initial position. The performance results for this puzzle
are reported in Table 4. The second problem is the well-known Wolf-goat-cabbage problem. The performance results are reported in Table 5.
Notice that these planning problems are predominantly Boolean. The constraint-based
encodings perform well in solving the instances of the Wolf-goat-cabbage problem. In
contrast, for the 8-tile puzzle problem, the use of numerical fluents allows us to achieve a
compact encoding, but it does not necessarily lead to a better performance w.r.t. ASP.
8.6 A Summary of the Experiments
Table 6 pictorially summarizes some of the results relating the performance of the different
approaches. For each problem instance, we compare the execution times obtained by the
best ASP-solver and the CLP(FD) solvers for B and B MV action description languages.
We considered only those instances for which at least one of the solvers gave an answer. A
score of 1 (0, −1) is assigned to the fastest (second fastest, slowest) solver. The scores of
all instances of a problem have been summed together, and this provides the radius of the
circles in the figure. Instances have been separated between “Yes” instances (they admit a
solution) and “No” instances (they have no solutions).
The success of the constraint-based approach is evident. However, it is interesting to
observe that the planning problems that do not make significant use of non-boolean fluents tend to perform better in the ASP-based implementations—possibly due to the greater
efficiency of ASP solvers in propagating boolean knowledge during search for a solution.
Conversely, when numerical quantities are relevant in modeling a planning problem, the
use of multi-valued fluents and constraints not only reduces the modeling effort, yielding
more concise formalizations, but also requires a smaller number of fluents (compared with
the analogous Boolean encoding). This, combined with the use of constraints, often translates into a smaller state space to be explored in finding a solution. These seem to be the
main reasons for the better behavior provided by the B MV approach.
The distinction between “Yes” and “No” instances is also very relevant. The CLP-based
solvers tend to perform better on the “Yes” instances, especially for large instances. It is
interesting to observe that a similar behavior has been observed in recent studies comparing
performance of ASP and CLP solutions to combinatorial problems (Dovier et al. 2005;
Dovier et al. 2007; Dovier et al. 2009a).
9 Related work
The literature on planning and planning domain description languages is extensive, and
it would be impossible to summarize it all in this context. We focus our discussion and
comparison to the papers that present languages and techniques similar to ours.
The language investigated in this work is a variant of the language B originally introduced in (Gelfond and Lifschitz 1998), as presented in (Son et al. 2001, Sect. 2). Apart
from minor syntactical differences, any action description D from the language of (Son et al. 2001)
can be embedded in our B. The semantics for B presented here reproduces the one of (Gelfond and Lifschitz 1998).
The language ADC has been introduced in (Baral et al. 2002) to model planning prob-

Instance

Length

Answer

A. Dovier, A. Formisano, E. Pontelli
54

CLP(FD)

BM V
CLP(FD)

0.64+4.42
0.73+5.43
1.03+57.54
1.06+7.08
1.39+967.26
1.46+597.92
1.70+13887.17
1.84+79.20
1.69+11092.48
1.84+18301.15

0.25+2.64
0.29+3.64
0.40+38.67
0.43+4.60
0.54+673.66
0.52+435.96
0.71+10109.58
0.73+57.00
0.73+9155.79
0.73+14195.54

B
lparse

I1
I1
I2
I2
I3
I3
I4
I4
I5
I5

9
10
14
15
19
20
24
25
24
25

N
Y
N
Y
N
Y
N
Y
N
N

41.49
41.80
42.68
43.14
43.76
44.52
51.59
55.54
49.64
51.07

Smodels
0.94
2.02
27.10
50.73
739.39
368.28
10247.47
1430.43
6936.39
14079.78

zchaff
2.06
2.52
34.46
49.50
1255.46
1090.66
–
954.68
–
3747.96

Cmodels
relsat
minisat
3.36
1.54
7.36
2.06
90.07
7.15
131.38
8.90
911.82
91.75
1445.78
58.89
5613.98
7862.10
1023.22
437.11
6041.87
1239.72
8583.44 11745.93

Clasp
0.52
0.70
7.42
1.98
268.69
268.59
4185.42
875.16
4901.13
8557.94

Best
ASP
0.52
0.70
7.15
1.98
91.75
58.89
4185.42
437.11
1239.72
3747.96

Table 4. Experimental results for instances of the 8-tile puzzle problem (timeout 36000 sec).

Length

Answer

Multi-valued Action Languages in CLP(FD)

21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

N
N
Y
N
Y
N
Y
N
Y
N
Y
N
Y
N
Y
N

55
BM V

B
lparse Smodels

0.10
0.10
0.10
0.11
0.12
0.12
0.13
0.14
0.14
0.15
0.15
0.16
0.16
0.17
0.18
0.18

0.19
0.25
0.26
0.43
0.27
0.68
0.43
1.24
0.41
2.97
0.49
2.78
1.06
3.61
1.39
4.55

Cmodels
zchaff

relsat

minisat

1.38
1.46
2.30
3.10
1.15
7.23
1.93
9.44
1.75
16.17
8.40
23.76
31.92
38.62
31.10
43.97

1.89
3.32
4.34
4.75
4.92
11.52
6.68
18.72
15.55
43.53
7.10
38.58
26.67
51.22
30.25
57.21

0.67
0.77
0.58
0.67
0.74
1.18
0.93
1.59
1.10
2.31
0.89
2.20
1.23
3.11
3.20
4.24

Clasp

Best
ASP

CLP(FD)

CLP(FD)

0.19
0.56
0.13
1.09
0.42
0.69
0.84
2.15
0.60
1.78
4.60
5.37
0.57
5.86
4.21
12.68

0.19
0.25
0.13
0.43
0.27
0.68
0.43
1.24
0.41
1.78
0.49
2.20
0.57
3.11
1.39
4.24

0.10+0.20
0.09+0.21
0.12+0.17
0.07+0.32
0.12+0.06
0.10+0.49
0.10+0.03
0.10+0.80
0.11+0.01
0.11+1.08
0.12+0.01
0.13+1.35
0.10+0.07
0.13+1.75
0.15+0.54
0.13+1.87

0.09+0.15
0.11+0.17
0.07+0.15
0.06+0.25
0.08+0.08
0.10+0.40
0.06+0.03
0.08+0.69
0.07+0.03
0.08+1.05
0.11+0.04
0.09+1.32
0.14+0.06
0.10+1.60
0.08+0.32
0.11+1.79

Table 5. Experimental results for instances of the Wolf-goat-cabbage problem.
lems in presence of actions with duration and delayed effects. The language relies on multivalued fluents, akin to those used in our language. ADC actions have two types of effects:
1. Direct modification of fluent values, described by dynamic causal laws of the forms
a causes f = g(f, f1 , . . . , fn , t) from t1 to t2

(24)

a contributes g(f, f1 , . . . , fn , t) to f from t1 to t2

(25)

The first axiom describes the value of the fluent f as a function, that modifies its
value over the period of time from t1 to t2 —these represent time units relative to the
current point in time. The second axiom is similar, except that it denotes the quantity
that should be added to the value of f over the period of time. These axioms are
important when describing actions whose effect has a known duration over time
(i.e., the interval of length t2 − t1 ).
2. Indirect modifications through the initiation and termination of processes, that can
modify fluents until explicitly stopped; the axioms involved are axioms for the creation and termination of processes:
a1 initiates p from t1

(26)

a2 terminates p at t2

(27)

and axioms that describe how processes modify fluents
p is associated with f = g(f, f1 , . . . , fn , t)

(28)

p is associated with f ← g(f, f1 , . . . , fn , t)

(29)

The first axiom describes how the value of the fluent f will change as a function
of time once a process is started; the second axiom determines how the value of f
changes while the process p is active.

BM V -CLP(FD)

B-CLP(FD)

B-B EST-ASP

BM V -CLP(FD)

B-CLP(FD)

B-B EST-ASP

BM V -CLP(FD)

B-CLP(FD)

A. Dovier, A. Formisano, E. Pontelli

B-B EST-ASP

56

Three-barrel

Community

Goat&C.

Tile-puzzle
“No” instances

“Yes” instances

All instances

Table 6. Relative performance of the solvers for each set of instances (the radii of the
circles are proportional to the performance of the specific solver).
ADC has some similarities to B MV ; they both allow multi-valued fluents and some forms
of temporal references. B MV has the flexibility of allowing non-Markovian behavior and
it allows references to values of fluents at different time points, features that are missing in
ADC. On the other hand, ADC allows the representation of continuous time and the ability
to describe continuous changes to the value of fluents.
Several features of ADC can be reasonably simulated in B MV ; we will focus on the
axioms of type (26)–(29), since these subsume the capabilities of axioms (24) and (25):
• we can represent each process p using a corresponding fluent;
• the axioms (26) and (27) can be simulated by
causes(a1 , pt1 −1 = 1, true)

causes(a2 , pt2 −1 = 0, true)

• the axiom (28) can be simulated by introducing the static causal law
caused(p > 0, f = g(f −1 , f1−1 , . . . , fn−1 , p−1 ) ∧ p = p−1 + 1)

Note that, due to the inability of B MV to handle continuous time, we are considering only
discrete time measures.
The language C + proposed in (Giunchiglia et al. 2004a) also has some similarities to the
language B MV . C + does not offer capabilities for non-Markovian and temporal references,
but supports multi-valued fluents. The syntax of C + builds on a language of fluent constants
(each with an associated domain) and action names (viewed as Boolean variables):

Multi-valued Action Languages in CLP(FD)

57

• Static causal laws
caused F if G
where F and G are fluent formulae (i.e., propositional combinations of atoms of
the form f = v for f fluent and v ∈ dom(f )). The language introduces syntactic
restrictions that are effectively equivalent to preventing cyclic dependencies among
fluents. Static causal laws describe dependencies between fluents within a state of
the world.
• Fluent dynamic laws
caused F if G after H
where F and G are fluent formulae and H is a formula that may also contain action
variables. The semantics of dynamic laws can be summarized as follows: if H holds
in a state, then the implication G → F should hold in the successive state.
• Actions that can be freely generated are declared to be exogenous
exogenous a
• Fluents can be declared to be inertial (i.e., they satisfy the frame axiom)
inertial f
The relationships between the two languages can be summarized as follows:
• C + is restricted to non-cyclic dependencies among fluents, while B MV lifts this restriction.
• C + is capable of identifying fluents as inertial or non-inertial, while B MV focuses
only on inertial fluents (though it is relatively simple to introduce an additional type
of constraint to create non-inertial fluents).
• C + can describe domains where concurrent actions are allowed—by allowing occurrences of different action variables in the H component of the fluent dynamic laws;
although B MV does not currently supports this feature, a similar extension has been
investigated in a recent paper (Dovier et al. 2009b).
Subsets of B MV and C + can be shown to have the same expressive power; in particular, let us consider the subset of C + that contains only domains that meet the following
requirements:
• there are no concurrent actions—i.e., each H contains exactly one occurrence of an
action variable; thus
caused F if G after a ∧ H
where H is a fluent formula;
• for each action a, there is a declaration
exogenous a.
Under these restrictions, it is possible to map a C + domain D to an equivalent domain in
B MV . In particular:
• for each non-inertial fluent f , with default value v, we introduce the static law
caused(f −1 6= v, f 0 = v)

58

A. Dovier, A. Formisano, E. Pontelli
• for each static causal law caused F if G we introduce a causal law caused(G, F )
• for each fluent dynamic law r of the form caused F if G after a ∧ H, we introduce
the following axioms (where exec r is a fresh fluent):
causes(a, exec r = 1, H)
causes(a, exec r1 = 0, H)
caused(exec r = 1 ∧ G, F )

Logic programming, and more specifically Prolog, has been also used to implement
the first prototype of GOLOG (as discussed in (Levesque et al. 1997)). GOLOG is a programming language for describing agents and their capabilities of changing the state of
the world. The language builds on the foundations of situation calculus. It provides high
level constructs for the definition of complex actions and for the introduction of control
knowledge in the agent specification. Prolog is employed to create an interpreter, which
enables, for example, to answer projection queries (i.e., determine the properties that hold
in a situation after the execution of a sequence of actions). The goals of GOLOG and the
use of logic programming in that work are radically different from the focus of our work.
The work by (Thielscher 2002a) takes a different perspective in using constraint programming to handle problems in reasoning about actions and change. Thielscher’s work
builds on the use of Fluent Calculus (Thielscher 1999) for the representation of actions
and their effects. Fluent calculus views states as sets of fluents, constructed using an operator ◦, and with the ability to encode partially specified sets (e.g., f1 ◦ f2 ◦ Z where Z
represents the “rest” of the state). In (Thielscher 2002a), an encoding of the fluent calculus axioms using Constraint Handling Rules (CHRs) is presented; the encoding uses lists
to represent states, and it employs CHRs to explicitly implement the operations on lists
required to operate on states—e.g., truth or falsity of a fluent, validation of disjunctions
of fluents. The ability to code open lists enables reasoning with incomplete knowledge.
Experimental results (reported in (Thielscher 2002b)) denote a good performance with respect to GOLOG. The framework is very suitable for dealing with incomplete knowledge
and sensing actions. Differently from our framework, it does not support non-Markovian
reasoning, multi-valued reasoning, and it does not bring the expressiveness of constraint
programming to the level of the action specification language. The use of constraints in the
two approaches is radically different—Thielscher’s work develops new constraint solvers
to implement reasoning about states, while we use existing solvers as black boxes.
A strong piece of work regarding the use of constraint programming in planning is (Vidal and Geffner 2006).
The authors use constraint programming, based on the CLAIRE language (Caseau et al. 2002),
to encode temporal planning problems and to search for minimal plans. They also use a series of interesting heuristics for solving that problem. This line of research is more accurate
than ours from the implementation point of view—although their heuristic strategies can
be implemented in our system and it would be interesting to exploit them during the labeling phase. On the other hand, the proposal by Vidal and Geffner only deals with Boolean
fluents and without explicitly defined static causal laws.
Similar considerations can be done with respect to the cited proposal by Lopez and
Bacchus (Lopez and Bacchus 2003). The authors start from Graphplan and exploit constraints to encode k-plan problems. Fluents are in this case only Boolean (not multi-valued)

Multi-valued Action Languages in CLP(FD)

59

and the process is deterministic once an action is chosen (instead, we deal also with nondeterminism, e.g., when we have consequences such as f > 5). The proposal of Lopez and
Bacchus does not address the encoding of static causal laws.
10 Conclusions and Future Work
In this paper, we investigated the application of constraint logic programming technology
to the problem of reasoning about actions and change and planning. In particular, we presented a modeling of the action language B using constraints, developed an implementation
using CLP(FD), and reported on its performance. We also presented the action language
B MV , which allows the use of multi-valued fluents and the use of constraints as conditions
and consequences of actions. Once again, the use of constraints is instrumental in making
these extensions possible. We illustrated the application of both B and B MV to several
planning problems. Both languages have been implemented using SICStus Prolog.
We consider the research and the results discussed in this paper as a preliminary step in a
very promising direction. The experimental results, as well as the elegance of the encodings
of complex problems, shows the promise of constraint-based technology to address the
needs of complex planning domains. A number of research directions are currently being
pursued:
• we have introduced the use of global constraints to encode different forms of preferences (e.g., action costs) and control knowledge. Global constraints have been
widely used in constraint programming to enhance efficiency, by providing more
effective constraint propagations between sets of variables; we believe a similar use
of global constraints can be introduced in the context of planning—e.g., the use of
techniques used to efficiently handle the alldifferent global constraint to enforce
non-repetition of states in a trajectory.
• We also believe that significant improvements in efficiency can be achieved by delegating parts of the constraint solving process to an efficient dedicated solver (e.g.,
encoded using a constraint platform such as GECODE, possibly enhanced with local
search moves).
• The encoding in CLP(FD) allow us to think of extensions in several directions, such
as the encoding of qualitative and quantitative preferences (a preliminary study has
been presented in (Tu et al. 2007)), and the use of constraints to represent incomplete
states—e.g., to determine most general conditions for the existence of a plan and to
support conformant planning (Son et al. 2007).
• An interesting line of research is represented by the application of the approach
discussed here to multi-agent systems. In that case, besides admitting the execution of more that one action in each state transition (cf., Remark 1), other important issues have to be addressed, since different agents may compete or collaborate
in order to reach the desired results. For instance, concurrency of actions may be
subject to constraints to model incompatibilities or interdependencies among the occurrences/effects of different actions executed by different agents (even in different
points in time). Hence, the action description language, as well as its CLP encoding,
has to be suitably enriched in order to deal with these aspects. A first step in this
direction has been presented in (Dovier et al. 2009b).

60

A. Dovier, A. Formisano, E. Pontelli
Acknowledgments

The authors would like to thank the following researchers for their help, comments, and
suggestions: Son Cao Tran, Michael Gelfond, and the anonymous reviewers of ICLP 2007
and TPLP.
The research has been partially supported by NSF Grants IIS-0812267, HRD-0420407,
and CNS-0220590, by the FIRB grant RBNE03B8KK, and by GNCS—Gruppo Nazionale
per il Calcolo Scientifico (project Tecniche innovative per la programmazione con vincoli
in applicazioni strategiche).
References
A PT, K. R. 2003. Principles of constraint programming. Cambridge University Press.
BARAL , C. 2003. Knowledge representation, reasoning and declarative problem solving. Cambridge
University Press.
BARAL , C., S ON , T., AND T UAN L-C. A transition function based characterization of actions
with delayed and continuous effects. Principles and Practice of Knowledge Representation and
Reasoning, Morgan Kaufmann, pp. 291–302, 2002.
C ASEAU , Y., J OSSET, F-X., AND L ABURTHE F. CLAIRE: combining sets, search and rules to
better express algorithms. Theory and Practice of Logic Programming, 2(6):769–805, 2002.
D OVIER , A., F ORMISANO , A., AND P ONTELLI , E. 2005. A comparison of CLP(FD) and ASP
solutions to NP-complete problems. In Proc. of ICLP 2008, M. Gabbrielli and G. Gupta, Eds.
Lecture Notes in Computer Science, vol. 3668. Springer Verlag, 67–82.
D OVIER , A., F ORMISANO , A., AND P ONTELLI , E. 2007. An experimental comparison of constraint
logic programming and answer set programming. In Proceedings of the Twenty-Second AAAI
Conference on Artificial Intelligence. AAAI Press, Vancouver, British Columbia, Canada, 1622–
1625.
D OVIER , A., F ORMISANO , A., AND P ONTELLI , E. 2009a. An empirical study of CLP and ASP
solutions of combinatorial problems. Journal of Experimental & Theoretical Artificial Intelligence 21, 2 (Jun.), 79–121.
D OVIER , A., F ORMISANO , A., AND P ONTELLI , E. 2009b. Representing multi-agent planning in
CLP. In Logic Programming and Non-monotonic Reasoning, 10th International Conference,
LPNMR 2009, Potsdam, Germany, September 14-18, 2009, Proceedings, E. Erdem, F. Lin, and
T. Schaub, Eds. Lecture Notes in Computer Science, vol. 5753. Springer, 423–429.
E ITER , T., FABER , W., L EONE , N., P FEIFER , G., AND P OLLERES , A. 2004. A logic programming approach to knowledge-state planning: Semantics and complexity. ACM Transactions on
Computational Logic 5, 2 (Apr.), 206–263.
G ABALDON , A. 2002. Non-Markovian control in the situation calculus. In Proceedings of the
Eighteenth National Conference on Artificial Intelligence, R. Dechter, M. Kearns, and R. S. Sutton,
Eds. American Association for Artificial Intelligence, AAAI Press, Menlo Park, California, 519–
524.
G EBSER , M., K AUFMANN , B., N EUMANN , A., AND S CHAUB , T. 2007. Clasp: A conflict-driven
answer set solver. In Logic Programming and Non-Monotonic Reasoning, C. Baral, G. Brewka,
and J. S. Schlipf, Eds., Springer Verlag, 260–265.
G ELFOND , M. AND L IFSCHITZ , V. 1998. Action languages. Electronic Transactions on Artificial
Intelligence 2, 193–210.
G IUNCHIGLIA , E., L EE , J., L IFSCHITZ , V., M C C AIN , N., AND T URNER , H. 2004. Non-monotonic
causal theories. Artificial Intelligence 153, (1–2), 49–104.
G IUNCHIGLIA , E., L IERLER , Y., AND M ARATEA , M. 2004. SAT-based answer set programming.
In AAAI-04, D. L. McGuinness and G. Ferguson, Eds. The MIT Press, 61–66.

Multi-valued Action Languages in CLP(FD)

61

H OFFMANN , M.J., P ORTEOUS , J., AND S EBASTIA , L. 2004. Ordered landmarks in planning. Journal of Artificial Intelligence Research, 22:215–278.
JAFFAR , J. andM AHER , M. 1994. Constraint logic programming: a survey. Journal of Logic Programming, 19/20:503–581.
L EE , J. AND L IFSCHITZ , V. 2003. Describing additive fluents in action language C+. In IJCAI-03,
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, Acapulco,
Mexico, August 9-15, 2003, G. Gottlob and T. Walsh, Eds. Morgan Kaufmann, 1079–1084.
L EVESQUE , H. J., P IRRI , F., AND R EITER , R. 1997. GOLOG: a logic programming language for
dynamic domains. Journal of Logic Programming, 31(1–3):59–83.
L EVESQUE , H. J., P IRRI , F., AND R EITER , R. 1998. Foundations for the situation calculus. Electronic Transactions on Artificial Intelligence 2, 159–178.
L IFSCHITZ , V. 1999. Answer set planning. In Proc. of the 16th Intl. Conference on Logic Programming, D. de Schreye, Ed. MIT Press, 23–37.
L IN , F. AND Z HAO , Y. 2004. ASSAT: Computing answer sets of a logic program by SAT solvers.
Artificial Intelligence 157, 1–2, 115–137.
L OPEZ , A. AND BACCHUS , F. 2003. Generalizing Graphplan by formulating planning as a CSP. In
IJCAI-03, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence,
Acapulco, Mexico, August 9-15, 2003, G. Gottlob and T. Walsh, Eds. Morgan Kaufmann, 954–960.
M ARRIOTT, K. AND S TUCKEY, P. J. 1998. Programming with constraints. The MIT Press.
M C C ARTHY, J. 1998. Elephant 2000 - A programming language based on speech acts. Available in
www.formal.stanford.edu/jmc.
R EITER , R. 2001. Knowledge in action: logical foundations for describing and implementing dynamical systems. MIT Press, Bradford Books, Cambridge, MA.
S IMONS , P. 2000. Extending and implementing the stable model semantics. Ph.D. thesis, Helsinki
University of Technology.
S ON , T. C., BARAL , C., AND M C I LRAITH , S. A. 2001. Planning with different forms of domaindependent control knowledge - An answer set programming approach. In Logic Programming and
Non-monotonic Reasoning, 6th International Conference, LPNMR 2001, Vienna, Austria, September 17-19, 2001, Proceedings, T. Eiter, W. Faber, and M. Truszczyński, Eds. Lecture Notes in
Computer Science, vol. 2173. Springer, 226–239.
S ON , T. C., T U , P. H., AND BARAL , C. 2007. Reasoning and planning with sensing actions, incomplete information, and static causal laws using answer set programming. Theory and Practice
of Logic Programming 7, 4, 377–450.
T HIELSCHER , M. 1999. From situation calculus to fluent calculus: state update axioms as a solution
to the inferential frame problem. In Artificial Intelligence, 111(1–2):277–299.
T HIELSCHER , M. 2002a. Reasoning about actions with CHRs and finite domain constraints. Lecture
Notes in Computer Science 2401, 70–84.
T HIELSCHER , M. 2002b. Pushing the envelope: programming reasoning agents. In AAAI Workshop
on Cognitive Robotics, AAAI Press.
T U , P. H., S ON , T. C., AND P ONTELLI , E. 2007. CPP: A constraint logic programming based
planner with preferences. In Logic Programming and Non-monotonic Reasoning, 9th International
Conference, LPNMR 2007, Tempe, AZ, USA, May 15-17, 2007, Proceedings, C. Baral, G. Brewka,
and J. S. Schlipf, Eds. Lecture Notes in Computer Science, vol. 4483. Springer, 290–296.
V IDAL , V., and G EFFNER , G. 2006. Branching and pruning: an optimal temporal POCL planner
based in constraint programming. Artificial Intelligence 170:298–335.

62

A. Dovier, A. Formisano, E. Pontelli
Appendix A Some of the codes of the Experimental Section
A.1 The Three-Barrel Problem: B MV description of the 12-7-5 barrels problem

The B MV encoding of the three barrels planning problem for N = 12. (Figure 1 presents
an encoding using the language B.)
barrel(5).
barrel(7).
barrel(12).
fluent(cont(B),0,B) :- barrel(B).
action(fill(X,Y)) :- barrel(X), barrel(Y), neq(X,Y).
causes(fill(X,Y), cont(X) eq 0, [Y-cont(Y) geq cont(X)]) :action(fill(X,Y)).
causes(fill(X,Y), cont(Y) eq cont(Y)ˆ(-1)+cont(X)ˆ(-1),
[Y-cont(Y) geq cont(X)]) :action(fill(X,Y)).
causes(fill(X,Y), cont(Y) eq Y, [Y-cont(Y) lt cont(X)]) :action(fill(X,Y)).
causes(fill(X,Y), cont(X) eq cont(X)ˆ(-1)-Y+cont(Y)ˆ(-1),
[Y-cont(Y) lt cont(X)]) :action(fill(X,Y)).
executable(fill(X,Y), [cont(X) gt 0, cont(Y) lt Y]) :action(fill(X,Y)).
caused([], cont(12) eq 12-cont(5)-cont(7)).
initially(cont(12) eq 12).
goal(cont(12) eq cont(7)).

Multi-valued Action Languages in CLP(FD)

63

A.2 The HP Protein Folding Problem
B MV encoding of the HP-protein folding problem with pivot moves on input of the form
1001001001. . . starting from a vertical straight line.
length(10).
amino(A) :- length(N), interval(A,1,N).
direction(clock).
direction(antick).
fluent(x(A),1,M) :length(N), M is 2*N, amino(A).
fluent(y(A),1,M) :length(N), M is 2*N, amino(A).
fluent(type(A),0,1) :amino(A).
fluent(saw,0,1).
action(pivot(A,D)) :length(N), amino(A),
1<A, A<N, direction(D).
executable(pivot(A,D), []) :- action(pivot(A,D)).
causes(pivot(A,clock), x(B) eq x(A)ˆ(-1)+y(B)ˆ(-1)-y(A)ˆ(-1), []) :action(pivot(A,clock)), amino(B), B > A.
causes(pivot(A,clock), y(B) eq y(A)ˆ(-1)+x(A)ˆ(-1)-x(B)ˆ(-1), []) :action(pivot(A,clock)), amino(B), B > A.
causes(pivot(A,antick), x(B) eq x(A)ˆ(-1)-y(B)ˆ(-1)+y(A)ˆ(-1), []) :action(pivot(A,antick)), amino(B), B > A.
causes(pivot(A,antick), y(B) eq y(A)ˆ(-1)-x(A)ˆ(-1)+x(B)ˆ(-1), []) :action(pivot(A,antick)), amino(B), B > A.
caused([x(A) eq x(B), y(A) eq y(B)], saw eq 0) :amino(A), amino(B), A < B.
initially(saw eq 1).
initially(x(A) eq N)
initially(y(A) eq Y)
initially(type(X) eq
initially(type(X) eq

::1)
0)

length(N), amino(A).
length(N), amino(A), Y is N+A-1.
:- amino(X), X mod 3 =:= 1.
:- amino(X), X mod 3 =\= 1.

goal(saw gt 0).
state cost(FE) :- length(N), auxc(1,4,N,FE).
auxc(I,J,N,0) :- I > N-3,!.
auxc(I,J,N,FE) :- J > N, !, I1 is I+1,
J1 is I1+3, auxc(I1,J1,N,FE).
auxc(I,J,N,FE1+type(I)*type(J)*rei(abs(x(I)-x(J))+abs(y(I)-y(J)) eq 1)) :J1 is J+2, auxc(I,J1,N,FE1).
always(x(1) eq 10). always(y(1) eq 10).
always(x(2) eq 10). always(y(2) eq 11).
cost constraint(goal geq 4).

64

A. Dovier, A. Formisano, E. Pontelli
A.3 The Community Problem
A.3.1 B description of the instance A4
max people(4).
person(X) :- max people(N), interval(X,1,N).
money(X) :- max people(N), M is N*(N+1), interval(X,1,M).
fluent(owns(B,M)) :- person(B), money(M).
action(gives(X,Y)) :person(X), person(Y), neq(X,Y).
executable(gives(X,Y), [owns(X,Mx)]) :action(gives(X,Y)),
fluent(owns(X,Mx)), Mx > X.
causes(gives(X,Y), owns(X,NewMx), [owns(X,Mx)]) :action(gives(X,Y)), money(Mx),
fluent(owns(X,NewMx)), fluent(owns(X,Mx)),
NewMx is Mx-X.
causes(gives(X,Y), owns(Y,NewMy), [owns(Y,My)]) :action(gives(X,Y)), money(My),
fluent(owns(Y,NewMy)), fluent(owns(Y,My)),
NewMy is My+X.
caused([owns(X,Mx)], neg(owns(X,Other))) :fluent(owns(X,Mx)), fluent(owns(X,Other)),
person(X), money(Mx), money(Other), neq(Mx,Other).
initially(owns(X,M)) :person(X), M is 2*X.
goal(owns(X,Mid)) :person(X), max people(N), Mid is (N*(N+1))//N.

A.3.2 B MV description of the instance A4
max people(4).
person(X) :- max people(N), interval(X,1,N).
fluent(owns(B),1,M) :person(B), max people(N), M is N*(N+1).
action(gives(X,Y)) :person(X), person(Y), neq(X,Y).
executable(gives(X,Y), [owns(X) gt X]) :action(gives(X,Y)).
causes(gives(X,Y), owns(X) eq owns(X)ˆ(-1)-X, []) :action(gives(X,Y)).
causes(gives(X,Y), owns(Y) eq owns(Y)ˆ(-1)+X, []) :action(gives(X,Y)).
initially(owns(X) eq M) :person(X), M is 2*X.
goal(owns(X) eq Mid) :person(X), max people(N), Mid is (N*(N+1))//N.

Multi-valued Action Languages in CLP(FD)
A.4 The 8-Tile Puzzle Problem
A.4.1 B description of the instance I1
cell(X) :- interval(X,1,9).
val(X) :- interval(X,1,9), neq(X,3).
near(1,2). near(1,4).
near(2,1). near(2,3). near(2,5).
near(3,2). near(3,6).
near(4,1). near(4,5). near(4,7).
near(5,2). near(5,4). near(5,6). near(5,8).
near(6,3). near(6,5). near(6,9).
near(7,4). near(7,8).
near(8,5). near(8,7). near(8,9).
near(9,6). near(9,8).
fluent(at(X,Y)) :- val(X), cell(Y).
fluent(free(Y)) :- cell(Y).
action(move(X,Y)) :- val(X), cell(Y).
executable(move(X,Y), [at(X,Z), free(Y)]) :val(X), cell(Y), cell(Z), near(Z,Y).
causes(move(X,Y), at(X,Y), []) :val(X), cell(Y).
causes(move(X,Y), free(Z), [at(X,Z)]) :val(X), cell(Y), cell(Z).
caused([at(X,Y)], neg(free(Y))) :val(X), cell(Y).
caused([at(X,Y)], neg(at(X,Z))) :val(X), cell(Y), cell(Z), neq(Y,Z).
caused([at(X,Y)], neg(at(W,Y))) :val(X), val(W), cell(Y), neq(X,W).
initially(at(1,1)). initially(at(2,3)). initially(at(4,8)).
initially(at(5,2)). initially(at(6,9)). initially(at(7,4)).
initially(at(8,6)). initially(at(9,7)). initially(free(5)).
initially(neg(at(1,X))) :- cell(X), neq(X,1).
initially(neg(at(2,X))) :- cell(X), neq(X,3).
initially(neg(at(4,X))) :- cell(X), neq(X,8).
initially(neg(at(5,X))) :- cell(X), neq(X,2).
initially(neg(at(6,X))) :- cell(X), neq(X,9).
initially(neg(at(7,X))) :- cell(X), neq(X,4).
initially(neg(at(8,X))) :- cell(X), neq(X,6).
initially(neg(at(9,X))) :- cell(X), neq(X,7).
initially(neg(free(X))) :- cell(X), neq(X,5).
goal(at(X,X)) :- val(X).
goal(free(3)).

65

66

A. Dovier, A. Formisano, E. Pontelli
A.4.2 B MV description of the instance I1

cell(X) :- interval(X,1,9).
tile(X) :- interval(X,1,9), neq(X,3).
near(1,2). near(1,4).
...%as for B...
near(9,6). near(9,8).
fluent(at(X),1,9) :- tile(X).
fluent(free,1,9).
action(move(X,Y)) :- cell(Y), tile(X).
executable(move(X,Y), [at(X) eq Z, free eq Y]) :tile(X), cell(Y), near(Z,Y).
causes(move(X,Y), at(X) eq Y, []) :tile(X), cell(Y).
causes(move(X,Y), free eq at(X)ˆ(-1), []) :tile(X), cell(Y).
initially(at(1) eq 1). initially(at(2)
initially(at(4) eq 8). initially(at(5)
initially(at(6) eq 9). initially(at(7)
initially(at(8) eq 6). initially(at(9)
initially(free eq 5).
goal(at(X) eq X) :- tile(X).
goal(free eq 3).

eq
eq
eq
eq

3).
2).
4).
7).

Multi-valued Action Languages in CLP(FD)
A.5 The Wolf-Goat-Cabbage Problem
A.5.1 B description of the Wolf-goat-cabbage problem
obj(goat).
obj(cabbage).
obj(wolf).
obj(man).
side(left). side(right).
pos(X) :- side(X).
pos(boat).
fluent(is in(X,Y)) :- obj(X), pos(Y).
fluent(boat at(Y)) :- side(Y).
fluent(alive).
action(sail(A,B)) :- side(A), side(B), neq(A,B).
action(go aboard(A)) :- obj(A).
action(get off(A)) :- obj(A).
executable(sail(A,B), [boat at(A), is in(man,boat)]) :side(A), side(B), neq(A,B).
executable(go aboard(A), [boat at(L), is in(A,L)]) :obj(A), side(L).
executable(get off(A), [is in(A,boat)]) :obj(A).
causes(sail(A,B), boat at(B), []) :side(A), side(B), neq(A,B).
causes(go aboard(A), is in(A,boat), []) :obj(A).
causes(get off(A), is in(A,L), [boat at(L)]) :obj(A), side(L).
caused([is in(Ogg,L1)], neg(is in(Ogg,L2))) :obj(Ogg), pos(L1), pos(L2), neq(L1,L2).
caused([boat at(L1)], neg(boat at(L2))) :side(L1), side(L2), neq(L1,L2).
caused([is in(A,boat), is in(B,boat)], neg(alive)) :obj(A), obj(B), diff(A,B,man).
caused([is in(wolf,L), is in(goat,L), neg(is in(man,L))], neg(alive)) :pos(L).
caused([is in(cabbage,L), is in(goat,L), neg(is in(man,L))], neg(alive)) :pos(L).
initially(is in(A,left)) :- obj(A).
initially(alive).
initially(boat at(left)).
goal(is in(A,right)) :- obj(A).
goal(alive).

67

68

A. Dovier, A. Formisano, E. Pontelli
A.5.2 B MV description of the Wolf-goat-cabbage problem

obj(goat).
obj(cabbage).
obj(wolf).
obj(man).
% 0=boat, 1=on-the-left, 2=on-the-right:
fluent(is in(X),0,2) :- obj(X).
fluent(boat at,1,2).
fluent(alive,0,1).
action(sail).
action(go aboard(A)) :- obj(A).
action(get off(A)) :- obj(A).
executable(sail, [is in(man) eq 0]).
executable(go aboard(A), [boat at eq is in(A)]) :obj(A).
executable(get off(A), [is in(A) eq 0]) :obj(A).
causes(sail, boat at eq 1, [boat at
causes(sail, boat at eq 2, [boat at
causes(go aboard(A), is in(A) eq 0,
obj(A).
causes(get off(A), is in(A) eq boat
obj(A).

eq 2]).
eq 1]).
[]) :atˆ(-1), []) :-

caused([is in(A) eq 0, is in(B) eq 0], alive eq 0) :obj(A), obj(B), diff(A,B,man).
caused([is in(wolf) eq is in(goat),
is in(man) neq is in(wolf)], alive eq 0).
caused([is in(cabbage) eq is in(goat),
is in(man) neq is in(cabbage)], alive eq 0).
initially(is in(A) eq 1) :- obj(A).
initially(boat at eq 1).
initially(alive eq 1).
goal(is in(A) eq 2) :- obj(A).
goal(alive eq 1).

Multi-valued Action Languages in CLP(FD)
A.6 The Gas-diffusion Problem: B MV description of the instance A4
room(N) :- interval(N,1,11).
gate(1,2).
gate(1,7).
gate(1,11).
gate(2,3).
gate(3,4).
gate(4,5).
gate(5,6).
gate(6,7).
gate(6,8).
gate(8,9).
gate(9,10).
gate(10,11).
fluent(contains(N),0,255) :- room(N).
fluent(is open(X,Y),0,1) :- gate(X,Y).
action(open(X,Y)) :- gate(X,Y).
action(close(X,Y)) :- gate(X,Y).
executable(open(X,Y),L) :action(open(X,Y)),
findall((is open(X,Z) eq 0), gate(X,Z),L1),
findall((is open(Z,X) eq 0), gate(Z,X),L2),
findall((is open(Y,Z) eq 0), (gate(Y,Z),neq(Z,X)),L3),
findall((is open(Z,Y) eq 0), (gate(Z,Y),neq(Z,X)),L4),
append(L1,L2,La),append(L3,L4,Lb),append(La,Lb,L).
executable(close(X,Y), [is open(X,Y) eq 1]) :action(close(X,Y)).
causes(open(X,Y),
contains(Y) eq (contains(X)ˆ(-1)+contains(Y)ˆ(-1))/2,
[]) :action(open(X,Y)).
causes(open(X,Y),
contains(X) eq (contains(X)ˆ(-1)+contains(Y)ˆ(-1))/2,
[]) :action(open(X,Y)).
causes(open(X,Y), is open(X,Y) eq 1, []) :action(open(X,Y)).
causes(close(X,Y), is open(X,Y) eq 0, []) :action(close(X,Y)).
initially(is open(X,Y) eq 0) :- gate(X,Y).
initially(contains(10) eq 128).
initially(contains(3) eq 128).
initially(contains(A) eq 0) :- room(A), diff(A,3,10).
goal(contains(1) gt 50).

69

