DLV
Tutorial
DLV
).
The tutorial does not give a full description of the usage and capabilities of
DLV
.
For a more complete account of these, see the
DLV
homepage and the
DLV
online user manual.
The examples shown in this tutorial work with every recent
DLV
release.
Executables of the DLV
system for various platforms
can be downloaded from the
DLV
homepage.
The tutorial consists of the following sections, each of them being built around a guiding example:
DLV
as a Deductive Database System; Comparison Operators This tutorial is written for computer-literate people with a background different from computer science, or students new to this area. It was originally written for physicists at CERN, and some examples are tailored towards this community.
Datalog is a declarative (programming) language. This means that the programmer does not write a program that solves some problem but instead specifies what the solution should look like, and a Datalog inference engine (or Deductive Database System) tries to find the the way to solve the problem and the solution itself. This is done with rules and facts. Facts are the input data, and rules can be used to derive more facts, and hopefully, the solution of the given problem.
Disjunctive datalog is an extension of datalog in which the logical OR expression (the disjunction) is allowed to appear in the rules - this is not allowed in basic datalog.
DLV
(= datalog with disjunction) is a powerful though
freely available deductive database system.
It is based on the declarative programming language datalog,
which is known for being a convenient tool for knowledge representation.
With its disjunctive extensions, it is well suited for all kinds of
nonmonotonic reasoning, including diagnosis and planning.
Finally, we have to mention to the more advanced reader that
DLV
is relevant to two communities. Firstly, as mentioned,
it is a deductive database engine and can therefore be seen as a way to query
data from databases which is strictly more powerful than for example SQL
(everything that can be done with the core SQL language can also be done with
DLV
, and more), but it is also often described as a
system for answer set programming (ASP). This is a powerful new paradigm
from the area of "Nonmonotonic Reasoning" which allows to formulate even very
complicated problems in a straightforward and highly declarative way.
One may call this paradigm even more declarative than classical logic.
Of course, every programming language to be processed by a computer has to
have both fixed syntax (i.e. a grammar that specifies what programs of this
language have to look like, and what combinations of symbols make a valid
program) and semantics (which abstractly specifies what the computer has to
do with the program by declaring how a program is to be translated into the/a
correct result). There is wide agreement (and also some excitement) that
both the syntax and semantics of the language of DLV
are very simple and intuitive. In fact, we do not know of any way to make
the language even simpler while preserving its characteristics.
Both the syntax and semantics of DLV
will be described in
this tutorial.
Suppose we want to model that every time somebody tells us a joke, we laugh. Furthermore, somebody now tells us a joke. This could be done in the following way:
The first line is called a fact and expresses thatjoke. laugh :- joke.
joke
is true (a simple word such as joke
appearing in a rule or fact
which has a truth value is called a proposition. A more general
name - which we will use in the following - for the constituents of rules
and facts is atom.).
The second line is called a rule.
It is read as "if joke is true, laugh must also be true".
(The sign ":-" is meant to be an arrow to the left, the logic programming
version of the implication.)
If the author of such a program decides it appropriate, one can also interpret
some causality into a rule and read this one as "from joke follows laugh".
This is pure matter of choice of the human, and DLV
does not care about it.
The left side of a rule is called its head, while the right side is
called its body.
A result of a Datalog computation is called a model. The meaning of this is clear: it is a consistent explanation (model) of the world, as far as the Datalog system can derive it. If a datalog program is inconsistent, i.e., it is contradictory, there is simply no model (we will see examples of this later).
Of course, since in this example joke
is certainly true (this is
given by the fact), laugh
is also true.
DLV
now tries to find all those models of the world that correctly
and consistently explain the observations made (= the program).
A model assigns a truth value (either true or false) to
each atom appearing in the program,
and is written as the set of atoms that are true in a certain model.
The model of the above program is {joke, laugh}
.
When all atoms are false in a model, we talk about an empty model
(written as {}
). Note that having an empty model is very different
from finding no model. We will see examples for this later.
Simple datalog programs like the one above always have exactly one model.
In general, though, DLV
programs may have zero
(as mentioned) or even many models. We will see examples of such programs later.
Next, suppose we are not aware of being told a joke. In this case, the correct datalog program looks like this:
The program itself does not express that joke is false, but the so-called Complete World Assumption (CWA) does. It is one of the foundationslaugh :- joke.
DLV
bases its computations on and says that everything about which
nothing is known is assumed to be false.
Therefore, the model for this program is {}
. (This means that
there is a model but it is empty. It is also possible that for a given
program there is no model.)
We will come back to the CWA in more detail later in the section that
discusses DLV
as a deductive database system.
Next, we elaborate a bit on this example. First, we want to express that to be able to understand a joke, one has to hear it and must not be stupid. To hear it, one must not be deaf and there must be a joke. Finally, to laugh about the joke, one must understand it. Alternatively, stupid people might laugh without being told a joke.
In two of the rules, we encounter negated atoms. These are true if the atoms themselves are false. We also encounter rules that contain more than one atom in the body. In such a case, a body is true if each of the literals are true (a literal is a possibly negated atom). For example,joke. hear_joke :- joke, not deaf. understand_joke :- hear_joke, not stupid. laugh :- understand_joke. laugh :- stupid, not joke.
is read as "ifhear_joke :- joke, not deaf.
joke
is true and deaf
is false then
hear_joke
must be true".
The model for this program is
{joke, hear_joke, understand_joke, laugh}
.
Again, by virtue of the CWA, deaf
and stupid
are assumed to be false - there are no facts making these atoms
true and no rules which can derive their truth.
Now suppose we remove joke.
from the program and add
stupid.
instead. Then, the resulting model would be
{stupid, laugh}
.
The model of this program isstupid. laugh :- stupid, not joke.
{stupid, laugh}
. If we now add the
fact joke.
we get the model {stupid, joke}
, from
which the atom laugh
got lost. In other words, you may add
more information and lose information that could be derived before because of
that. Due to this property,
the formalism of DLV
is called nonmonotonic, just
as mathematical functions which are neither monotonically increasing nor
decreasing are called nonmonotonic.
At first sight, this may look like an ugly property of this formalism, but in
fact, it allows to do many useful things.
In the following program, we have two binary predicates, parent
and grandparent
. (They are called binary because they both have
two arguments.)
We have to map some semantics to the two arguments of the predicates. Here, the first argument is assumed to be the older person (the parent or grandparent), while the second argument refers to the younger person (the child or grandchild). Certainly, we could do it the other way as well, but then we would have to adjust all the rules that will follow.
Of course, the model of this program isparent(john, james). parent(james, bill). grandparent(john, bill) :- parent(john, james), parent(james, bill).
{parent(john, james), parent(james, bill), grandparent(john,bill)}
.
With predicates, it is allowed to use variables, which begin with an upper-case character, differently from the constants of the previous program that begin with a lower-case letter. The following program has the same model as the previous example:
This new grandparent rule which uses variables simply models that every parent of a parent is a grandparent.parent(john, james). parent(james, bill). grandparent(X, Y) :- parent(X, Z), parent(Z, Y).
Note that the facts of a program are often called the
Extensional Database (EDB), while the remaining rules are called
the Intensional Database (IDB).
With DLV
, the EDB can be read either from a relational
or object-oriented database, or just simply from files, where no separation
of rules and facts is required.
We can now extend this example a bit to show how DLV
can be used to model knowledge as datalog rules and exploit it.
First we add a few more facts to add more people and to express their gender:
Then we can add more rules that model family relationships.parent(william, john). parent(john, james). parent(james, bill). parent(sue, bill). parent(james, carol). parent(sue, carol). male(john). male(james). female(sue). male(bill). female(carol).
The rules for brother and sister usegrandparent(X, Y) :- parent(X, Z), parent(Z, Y). father(X, Y) :- parent(X, Y), male(X). mother(X, Y) :- parent(X, Y), female(X). brother(X, Y) :- parent(P, X), parent(P, Y), male(X), X != Y. sister(X, Y) :- parent(P, X), parent(P, Y), female(X), X != Y.
X != Y
to require that
X and Y are different (one cannot be his own brother). This is called a
built-in predicate, since it could be written as something like
not_equal(X, Y)
. DLV
knows quite a few of
these built-in predicates.
For this program, DLV
finds the following model
(to simplify readability, the facts already listed above were removed from the
model below; of course, they still belong there):
Let us now exchange the IDB rules against the following (the EDB facts remain the same):{grandparent(william,james), grandparent(john,bill), grandparent(john,carol), father(john,james), father(james,bill), father(james,carol), mother(sue,bill), mother(sue,carol), brother(bill,carol), sister(carol,bill)}
These rules are interesting, since they use recursion to implement transitivity. They express that, to start with, every parent is an ancestor, and, secondly, that every parent of an ancestor is an ancestor. Please note that the semantics used ensures that it is impossible that there be any problems with left-recursion as they occur in languages as Prolog. Inancestor(X, Y) :- parent(X, Y). ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).
DLV
, the programmer can safely ignore such
considerations.
The model of this program combined with the six-entries parent
facts base above results in the following model (where the parent
facts were again removed for readability):
{ancestor(william,john), ancestor(william,james), ancestor(william,bill), ancestor(william,carol), ancestor(john,james), ancestor(john,bill), ancestor(john,carol), ancestor(james,bill), ancestor(james,carol), ancestor(sue,bill), ancestor(sue,carol)}
Finally, some subtle detail has to be noted which is quite useful to improve
the readability of the rules. In the case that a certain argument of a
predicate is irrelevant for a certain rule, no dummy variable has to be
inserted, but the _
can be used. For instance, suppose we want
to derive the persons from the parent facts. For this, we can write the
following rules:
person(X) :- parent(X, _). person(X) :- parent(_, X).
Finally, please avoid calling a predicate as shown in this section a proposition. (It is fine to call them atoms.)
DLV
as a Deductive Database System; Comparison Operators
When you use the CWA in one of your programs, you basically view the
DLV
system as a deductive database system, since you
do not ask for what is logically right, but what you can usefully derive
from your facts base.
Following this approach, you can perform queries on the existing data (the
facts base), derive (and "store") new data using queries(=rules),
which again can be used to deduce even more data, and, using the CWA, even
ask queries as to what is not in (or derivable from) your database.
When the relational tables are encoded as a facts base, we can rewrite the above query into a datalog rule:SELECT e.name, e.salary, d.location FROM emp e, dept d WHERE e.dept = d.dept_id AND e.salary > 31000;
emp("Jones", 30000, 35, "Accounting"). emp("Miller", 38000, 29, "Marketing"). emp("Koch", 2000000, 24, "IT"). emp("Nguyen", 35000, 42, "Marketing"). emp("Gruber", 32000, 39, "IT"). dept("IT", "Atlanta"). dept("Marketing", "New York"). dept("Accounting", "Los Angeles"). q1(Ename, Esalary, Dlocation) :- emp(Ename, Esalary, _, D), dept(D, Dlocation), Esalary > 31000.
As you can see, joins are achieved via variable binding (we use the same variable D both in emp and in dept), selections can for example be achieved by the comparison operators, and projections (i.e. where unwanted data columns are excluded from a query result) can be accomplished by using _ or an unbound variable.
You can use DLV
to ask all the queries that are possible in the
core SQL language. Furthermore, (as you will see when the full expressive power
of DLV
is unveiled later in this tutorial) you can also encode
many useful queries that cannot be expressed in SQL.
This example used another feature of DLV
that has not been
introduced yet: comparison operators. DLV
supports the operators
<, >, >=, <=, and = for integers, floating point values, and strings.
This is an extension that is not part of basic datalog, but it is convenient
and also compatible with the philosophy of datalog, as you can think of an
expression X > Y as a predicate
greater_than(X,Y)
for which the facts base of all the greater-than
relationships between constant symbols in your program are automatically
generated.
Therefore, we call these comparison operators built-in predicates.
Note that you could also rewrite q1
to use the operator = for the
join. The rule below obtains the same result as the one shown earlier:
q1(Ename, Esalary, Dlocation) :- emp(Ename, Esalary, _, D1), dept(D2, Dlocation), D1 = D2, Esalary > 31000.
DLV
supports two kinds of negation.
Here, we emphasize the difference between explicitly expressing the falseness
of an atom and having it done by the Complete World Assumption.
The following program uses the CWA. It has the model
{cross}
because train_approaching is assumed to be false (as it
being true is not stated anywhere).
This kind of negation is called
negation as (finite) failure or naf.
The next program uses so-called true or classical negation. Sincecross :- not train_approaching.
-train_approaching
is not known to be true, the following
program has only an empty model.
The difference between the two kinds of negation is quite important: In the first example, we cross the railroad track if we have no information on any trains approaching, which is quite dangerous, while in the second example, we only cross if we know for sure that no train comes. In particular, the left side of the previous rule will only be true ifcross :- -train_approaching.
is in the facts base of the program.-train_approaching.
True negation is stronger than negation as finite failure. If something is true via true negation, it is always also true if negated by negation as finite failure. For example, the program
has the modelcross :- not train_approaching. -train_approaching.
{cross, -train_approaching}
.
Using True Negation also allows to build programs that are contradictory and have no models. Consider the following example:
Certainly, this program cannot have a model. This is very different from a program that has an empty model, which would just mean that the program represents a possible situation but that all of its atoms are assumed to be false.cross. -cross.
The first rule is called a disjunctive rule; The v is read as "or" and the whole rule is read as "For sure, either the left or the right arm is broken." As we can see here, a disjunctive rule may (but does not have to) have an empty body (= lack a body). It is still called a rule, since it is certainly not a fact. (It is unknown if the left or the right arm is broken.)left_arm_broken v right_arm_broken. can_write :- left_arm_broken. be_angry :- can_write.
Being able to process incomplete information (i.e. being unsure if the
left or the right arm is broken) is one of the great strengths of
DLV
.
The resulting models of this query are
{left_arm_broken, can_write, be_angry}
and
{right_arm_broken}
.
In fact, the disjunction left_arm_broken v right_arm_broken.
also allows both left_arm_broken
and right_arm_broken
to be true at the same time. Still, DLV
does not output
the model {left_arm_broken, right_arm_broken, can_write, be_angry}
due to the computing paradigm that it uses to cope with uncertainty, and which
is called the Stable Model Semantics.
Under this semantics, a model is not stable if there is a smaller model which
is a subset of it (which is the case for both stable models shown
above with respect to the "big" model containing left_arm_broken
and right_arm_broken
).
While this might seem complicated, it is a very powerful feature of
DLV
which is very useful for all kinds of reasoning.
We will come back to this later in this tutorial.
(For the moment, we want to emphasize that this one "big" model which
is not stable would be obviously wrong in this application.)
Note that the same uncertainty can also be expressed by the following program:
left_arm_broken :- not right_arm_broken. right_arm_broken :- not left_arm_broken. can_write :- left_arm_broken. be_angry :- can_write.
This program results in the same pair of models. The method used here is called
Unstratified Negation and is considered less elegant than the first
method. Also, there are certain interesting reasoning problems that
DLV
can solve and which can only be expressed with true
disjunction but not with unstratified negation.
Finally, please note that rule bodies may either contain positive (nonnegated) atoms, atoms negated by true negation, and atoms negated by negation as failure, while rule heads may only contain positive atoms and true negation, but no negation as failure. In other words, a rule such as
is not valid! (The % sign in anot a :- b. % INVALID !!!
DLV
program
starts a comment which goes to the right to the end of the line.)
DLV
also supports integrity constraints
(strong constraints).
A constraint is a rule with an empty head. If its body is true (which is of
course the case exactly if all the literals in the body are true at the same
time), a model is made inconsistent and is removed.
For example, in the family tree example which was presented earlier, we
can easily write an integrity constraint to assure that the facts base does not
erroneously contain contradicting facts saying that a person is male and
female at the same time.
This kind of constraints is called strong constraints because there is also a different kind (weak constraints) supported by:- male(X), female(X).
DLV
which is not addressed in this tutorial.
This other kind of constraints is very useful to solve optimization problems.
Graph 3-colorability is a hard (NP-complete) problem. It is the problem of deciding if there exists a coloring of a map of countries corresponding to the given graph using no more than three colors in which no two neighbour countries (nodes connected by an arc) have the same color. It is known that every map can be colored given these constraints if four colors are available.
node(minnesota). node(wisconsin). node(illinois). node(iowa). node(indiana). node(michigan). node(ohio). arc(minnesota, wisconsin). arc(illinois, iowa). arc(illinois, michigan). arc(illinois, wisconsin). arc(illinois, indiana). arc(indiana, ohio). arc(michigan, indiana). arc(michigan, ohio). arc(michigan, wisconsin). arc(minnesota, iowa). arc(wisconsin, iowa). arc(minnesota, michigan). |
This problem instance has 6 solutions (stable models), therefore, it is 3-colorable. Below, one solution is shown, in which the facts base has again be removed for better readability:% guess coloring col(Country, red) v col(Country, green) v col(Country, blue) :- node(Country). % check coloring :- arc(Country1, Country2), col(Country1, CommonColor), col(Country2, CommonColor).
{col(minnesota,green), col(wisconsin,red), col(illinois,green), col(iowa,blue), col(indiana,red), col(michigan,blue), col(ohio,green)}
This method (guess&check programming) allows to encode a large number of
complicated problems in an intuitive way. DLV
can then
use such an encoding to solve the problems surprisingly efficiently.
As an exercise, you can use DLV
to prove that a
map of Germany, Belgium, Luxembourg and France
is not 3-colorable.
DLV
which are not part of standard datalog.
In the following example, the Fibonacci function is defined, which is relevant in areas as disparate as Chaos Theory and Botanics. Its starts with the following values: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ... (Apart from the first two values, each value is defined as the sum of the previous two.)
This program uses the built-in predicatestrue. fibonacci(1, 1) :- true. fibonacci(1, 2) :- true. fibonacci(F, Index) :- +(F1, F2, F), fibonacci(F1, Index1), fibonacci(F2, Index2), #succ(Index1, Index2), #succ(Index2, Index).
+
(which adds or
subtracts integer numbers) and #succ
(the successor function).
Note that for better readability, it is also correct to write
F = F1 + F2
instead of +(F1, F2, F)
and
Index2 = Index1 + 1
instead of
#succ(Index1, Index2)
.
Still, these simple equations always map to the built-in predicates and
may not be extended any further. (It is not allowed to write
A = B + C + D
, this has to be split into two parts.)
The second topic that has to be discussed at this point is why the fact
true.
was introduced.
The reason for this is the strong separation that is made between EDB and
IDB predicates. Since fibonacci
is used on the left-hand side
of a rule, it is in the IDB. IDB predicates cannot be used in facts (because
then they would have to be in the EDB).
Because of that, a fact is introduced and rules are built that are always true
and are therefore equivalent to facts.
Note that this distinction between IDB and EDB predicates is not necessary
anymore in the most recent versions of DLV
. Therefore,
you can now declare fibonacci(1, 1)
and
fibonacci(1, 2)
simply as facts.
Whenever integer arithmetics are used, the range of possible values has to
be restricted, since DLV
requires the space of possible
solutions to be finite. This is done by invoking DLV
with the option -N
. (For a full description of
DLV
usage, refer to the
DLV
manual.)
For example, invoking DLV
with
results in the modeldl -N=100 fibonacci.dl
These are all the Fibonacci numbers not greater than 100.{true, fibonacci(1,1), fibonacci(1,2), fibonacci(2,3), fibonacci(3,4), fibonacci(5,5), fibonacci(8,6), fibonacci(13,7), fibonacci(21,8), fibonacci(34,9), fibonacci(55,10), fibonacci(89,11)}
To run this program with% guess horizontal position for each row q(X,1) v q(X,2) v q(X,3) v q(X,4) v q(X,5) v q(X,6) v q(X, 7) v q(X,8) :- #int(X), X > 0. % check % assert that each column may only contain (at most) one queen :- q(X1,Y), q(X2,Y), X1 <> X2. % assert that no two queens are in a diagonal from top left to bottom right :- q(X1,Y1), q(X2,Y2), X2=X1+N, Y2=Y1+N, N > 0. % assert that no two queens are in a diagonal from top right to bottom left :- q(X1,Y1), q(X2,Y2), X2=X1+N, Y1=Y2+N, N > 0.
DLV
, type the following:
This will return a result likedl -n=1 -N=8 8queens.dl
To get all 92 correct solutions, type{q(1,3), q(2,7), q(3,2), q(4,8), q(5,5), q(6,1), q(7,4), q(8,6)}
dl -N=8 8queens.dl
DLV
to do diagnosis.
We choose a physics application domain, a simplified version of ECAL
pre-calibration.
The program starts with two facts expressing our observations. Here, both the testpulse reading and the beam reading were found to be correct; below, we will evaluate the program with different observations. The following two rules tell the system that crystals and APDs are either working or broken. After this follows a constraint that assures that they cannot be both at the same time. Finally, there are five rules that are a collection of expert knowledge. They model the knowledge about the domain and show quite clearly why the test pulse is available as a separate input to the APDs: it allows to find out if the APD works correctly without having to make any assumptions about the crystal. If the reaout of the beam on the other hand were not correct, one could not be sure if the responsible part is the crystal or the APD.ok(testpulse_reading). ok(beam_reading). good(crystal) v bad(crystal). good(apd) v bad(apd). :- good(X), bad(X). good(crystal) :- ok(beam_reading). good(apd) :- ok(beam_reading). bad(apd) v bad(crystal) :- not ok(beam_reading). good(apd) :- ok(testpulse_reading). bad(apd) :- not ok(testpulse_reading).
Here, the unique result is the model {good(crystal), good(apd)}
.
Suppose we exchange the two EDB facts (the first two lines of this program)
to ok(testpulse_reading).
then the result changes to
{good(apd), bad(crystal)}
.
The whole set of different cases is shown in the following table:
EDB | Model(s) |
{ok(testpulse_reading). ok(beam_reading).} |
{good(crystal), good(apd)} |
{ok(testpulse_reading).} |
{good(apd), bad(crystal)} |
{ok(beam_reading).} |
no model |
{} |
{bad(apd), good(crystal)}, |
The case that the facts base is {ok(beam_reading).}
is also interesting:
According to our program, if ok(beam_reading)
is true,
ok(testpulse_reading)
also has to be true.
Therefore, there is no consistent model in this case.
In other words, according to our program, such observations cannot be made.
In this example program, we have left away all the possible observations, which we implement as constraints, as shown in the following table:connected(beam, crystal). connected(crystal, apd). connected(testpulse_injector, apd). connected(apd, readout). good_path(X,Y) :- not bad(X), not bad(Y), connected(X, Y). good_path(X,Z) :- good_path(X,Y), good_path(Y, Z). bad(crystal) v bad(apd). testpulse_readout_ok :- good_path(testpulse_injector, readout). beam_readout_ok :- good_path(beam, readout).
Observations (Constraints) | Model(s) (good_path predicates omitted) |
{} |
{bad(crystal), testpulse_readout_ok},
|
{:- testpulse_readout_ok.} |
{bad(apd)} |
{:- beam_readout_ok.} |
{bad(crystal), testpulse_readout_ok},
|
{:- beam_readout_ok. |
{bad(apd)} |
{:- not testpulse_readout_ok.} |
{bad(crystal), testpulse_readout_ok}
|
{:- not beam_readout_ok.} |
no model |
{:- not beam_readout_ok. |
no model |
The following example shall give an idea of how DLV
can be used to do planning.
Please note that there is a DLV
planning frontend
that uses a convenient special-purpose planning language and which is not
described in this tutorial. Instead, we use plain disjunctive datalog for
solving planning problems here.
If you are interested in this frontend, please refer to the
DLV
homepage for further information.
Consider the following classic planning problem. A monkey is in a room with a chair and a banana which is fixed to the ceiling. The monkey cannot reach the banana unless it stands on the chair; it is simply too high up. The chair is now at a position different from the place where the banana is hung up, and the monkey itself initially is at again a different place.
Since the program is quite long compared to the earlier examples, it will be explained step by step.
At each discrete point in time, the monkey performs one of the following for actions: it walks, it moves the chair (while doing this, it also moves through the room), it climbs up the chair, or it does nothing. #int is again a built-in predicate which is true exactly if its argument is an integer value.walk(Time) v move_chair(Time) v ascend(Time) v idle(Time) :- #int(Time).
After climbing up the chair, it is on it. If is is already on it, it cannot climb up any further. While on the chair, it cannot walk around. If it was on the chair earlier, it will be there in the future.monkey_motion(T) :- walk(T). monkey_motion(T) :- move_chair(T). stands_on_chair(T2) :- ascend(T), T2 = T + 1. :- stands_on_chair(T), ascend(T). :- stands_on_chair(T), monkey_motion(T). stands_on_chair(T2) :- stands_on_chair(T), T2 = T + 1.
If the chair is not moved, it will stay at the same place. If the monkey moves the chair, it changes its position.chair_at_place(X, T2) :- chair_at_place(X, T1), T2 = T1 + 1, not move_chair(T1). chair_at_place(Pos, T2) :- move_chair(T1), T2 = T1 + 1, monkey_at_place(Pos, T2).
The monkey is somewhere in the room. (For simplicity, only three positions are possible.)monkey_at_place(monkey_starting_point, T) v monkey_at_place(chair_starting_point, T) v monkey_at_place(below_banana, T) :- #int(T).
The monkey cannot change its position without moving. The monkey cannot stay at the same place if it moves. It cannot climb up the chair if it is somewhere else. It cannot move the chair if it is somewhere else.:- monkey_at_place(Pos1, T2), monkey_at_place(Pos2, T1), T2 = T1 + 1, Pos1 != Pos2, not monkey_motion(T1). :- monkey_at_place(Pos, T2), monkey_at_place(Pos, T1), T2 = T1 + 1, monkey_motion(T1). :- ascend(T), monkey_at_place(Pos1, T), chair_at_place(Pos2, T), Pos1 != Pos2. :- move_chair(T), monkey_at_place(Pos1, T), chair_at_place(Pos2, T), Pos1 != Pos2.
Initially, the monkey and the chair are at different positions.monkey_at_place(monkey_starting_point, 0) :- true. chair_at_place(chair_starting_point, 0) :- true. true.
The monkey can only reach the banana if it stands on the chair and the chair is below the banana. If it can reach the banana, it will eat it, and this will make it happy. Our goal is to make the monkey happy.can_reach_banana :- stands_on_chair(T), chair_at_place(below_banana, T). eats_banana :- can_reach_banana. happy :- eats_banana. :- not happy.
The step rules collect all the things we can derive from the situation and build a consistent plan. (There is no step rule for the action idle since we are not interested in it.)step(N, walk, Destination) :- walk(N), monkey_at_place(Destination, N2), N2 = N + 1. step(N, move_chair, Destination) :- move_chair(N), monkey_at_place(Destination, N2), N2 = N + 1. step(N, ascend, " ") :- ascend(N).
This program again uses integer arithmetics; to find a plan, the maximum integer variable has to be set to at least 3:
This results in the following model (If N is set to a value greater than 3,dl -N=3 banana.dl
DLV
will find other plans that make the monkey happy.)
Download example program.{chair_at_place(chair_starting_point,0), monkey_at_place(monkey_starting_point,0), monkey_at_place(chair_starting_point,1), monkey_at_place(below_banana,2), monkey_at_place(below_banana,3), walk(0), move_chair(1), ascend(2), idle(3), chair_at_place(chair_starting_point,1), chair_at_place(below_banana,2), chair_at_place(below_banana,3), monkey_motion(0), monkey_motion(1), step(0,walk,chair_starting_point), step(1,move_chair,below_banana), step(2,ascend," "), stands_on_chair(3), can_reach_banana, eats_banana, happy}