Our work is intended to model and solve artificial planning problems with logic based planning, using the novel semantics called p-stable, which is an alternative of stable semantics. Also we present a method to encode a general planning problem and then we present an example, which is the blocks world problem. This can be applied in a variety of tasks including robotics, process planning, updates, making evacuation plans and so on.
Automated planning is a branch of artificial intelligence and it has been an area
of research for over three decades. The automated planning is a key ability for
intelligent systems, increasing their autonomy and flexibility through the
construction of plans or sequences of actions in order to achieve their goals. This
sequence of actions can be executed by intelligent agents, autonomous robots,
and so on [
Planning in Artificial Intelligence is decision making about the actions to be taken.
Imagine an intelligent robot. The robot is a computational mechanism that takes
input through its sensors and act with the effectors, which can be motors, lights,
and so on. So the sensors allow the robot to perceive its environment and to
build a representation of the world has perceived before as well as its immediate
surroundings. Then the robot must act according to the representation of the
world it has, that cames from its perception. The robot acts through its effectors
which are devices that allow the robot to change the states of the environment
interacting with it as changes the states of itself, like move from a place to
another, move items, and so on. At an abstract level, a robot is a mechanism
that maps its observations to actions which are obtained through sensors and
performed by the effectors respectively. In this context. planning is the decision
making, where gives a sequence of actions by a sequence of observations [
The p-stable semantics is a novel semantics that came from an alternative for
stable semantics [
In this work, we are interested in two basic parts: the first one is to present
the action language A, where it is intended to show how we can model easily a
planning problem and the second one is to present a different method, which is
more complete, of how we can model a planning problem with p-stable semantics
rules based in the language A. We will illustrate this by presenting as example
the world blocks problem. In order to see what models we get, we use as resolver
the last implementation of p-stable semantics [
This paper is structured as follows. In section 2 we introduce the general syntax of the logic programs used in this paper. We also provide the definition of stable and p-stable semantics. In section 3 we present the logic basic planning with action language A and the p-stable approach, and then we present the world blocks problem represented in both, language A and p-stable rules. Finally in section 4 we present the conclusions. 2
In this section we summarize some basic concepts and definitions used to understand this paper. 2.1
A signature L is a finite set of elements that we call atoms, or propositional symbols. The language of a propositional logic has an alphabet consisting of proposition symbols: p0, p1, . . . ; connectives: ∧, ∨, ←, ¬; and auxiliary symbols: (, ). Where ∧, ∨, ← are 2-place connectives and ¬ is a 1-place connective. Formulas are built up as usual in logic. A literal is either an atom a, called positive literal ; or the negation of an atom ¬a, called negative literal. The formula F ≡ G is an abbreviation for (F ← G) ∧ (G ← F ). A clause is a formula of the form H ← B (also written as B → H), where H and B, arbitrary formulas in principle, are known as the head and body of the clause respectively. The body of a clause could be empty, in which case the clause is known as a fact and can be denoted just by: H ←. In the case when the head of a clause is empty, the clause is called a constraint and is denoted by: ← B. A normal clause is a clause of the form H ← B+ ∪ ¬B− where H consists of one atom, B+ is a conjunction of atoms b1 ∧ b2 ∧ . . . ∧ bn, and ¬B− is a conjunction of negated atoms ¬bn+1 ∧ ¬bn+2 ∧ . . . ∧ ¬bm. B+, and B− could be empty sets of atoms. A finite set of normal clauses P is a normal program.
Finally, we define RED(P, M ) = {H ← B+, ¬(B− ∩ M ) | H ← B+, ¬B− ∈ P }. For any program P , the positive part of P , denoted by P OS(P ) is the program consisting exclusively of those rules in P that do not have negated literals. 2.2
From now on, we assume that the reader is familiar with the notion of classical
minimal model [
Definition 1. [
Definition 2. [
The following theorem shows the relation between the stable and p-stable semantics for normal logic programs.
Theorem 1. [
In this section we present how we model planning into the p-stable semantics. 3.1
In a planning problem, we are interested in looking for a sequence of actions
that leads from a given initial state to a given goal state. There exist different
action languages that are formal models used to model planning problems, such
as A, B, or C [
Language A The alphabet of the language A consists of two nonempty disjoint sets of symbols F and A. They are called the set of fluents, and the set of actions. Intuitively, a fluent expresses the property of an object in a world, and forms part of the description of states of the world. A fluent literal is a fluent or a fluent preceded by ∼. A state σ is a set of fluents. We say a fluent f holds in a state σ if f ∈ σ. We say a fluent literal ∼ f holds in σ if f ∈ σ. Actions when successfully executed change the state of the world. Situations are representations of the history of action execution. The situation [an, . . . , a1] corresponds to the history where action a1 is executed in the initial situation, followed by a2, and so on until an. There is a simple relation between situations and states. In each situation s some fluents are true and some others are false, and this ‘state of the world’ is the state corresponding to the situation s.
The language A can be divided in three sub-languages: Domain description
language, Observation language, and Query language [
Domain description language. It is used to express the transition between states due to actions. The domain description D consists of effect propositions of the following form: a causes f if p1, . . . , pn, ∼ q1, . . . , ∼ qr where a is an action, f, p1, . . . , pn, q1, . . . , qr are fluents. Intuitively, the above effect proposition means that if the fluent literals p1, . . . , pn, ∼ q1, . . . , ∼ qr hold in the state corresponding to a situation s then in the state corresponding to the situation reached by executing a in s the fluent literal f must hold. The role of effect propositions is to define a transition function, Φ, from states and actions to states. The domain description part also can include executability conditions: executable a if p1, . . . , pn, ∼ q1, . . . , ∼ qr where a is an action and, p1, . . . , pn, q1, . . . , qr are fluents. Intuitively, it means that if the fluent literals p1, . . . , pn, ∼ q1, . . . , ∼ qr hold in the state σ of a situation s, then the action a is executable in s.
Observation language. A set of observations O consists of value propositions of the form: initially f . Given a consistent domain description D the set of observations O is used to determine the states corresponding to the initial situation, referred to as initial states and denoted by σ0.
Query language. We say a consistent domain description D in the presence of a set of observations O entails a query Q of the form f after a1, . . . , am if for all initial states σ0 corresponding to (D, O), the fluent literal f holds in the state [am, . . . , a1]σ0. We denote this as D |=O Q.
Hence, in order to model a planning problem using language A, we must specify a triple (D, O, G) where D is a domain description, O is a set of observations, and G is a collection of fluent literals G = {g1, . . . , gl}, which we will refer to as a goal. So, we require to find a sequence of actions a1, . . . , an such that for all 1 ≤ i ≤ l, D |=O gi after a1, . . . , an. We then say that a1, . . . , an is a plan for achieves goal G with respect to (D, O). 3.3
We have described before, how to model planning problems using language A. In this section we present a more complete method to encode planning problems with background knowledge into p-stable semantics, since this semantics is new, there is no application made for planning purposes, but we can translate the language A model into p-stable rules as follows:
Background knowledge The background knowledge is declared as facts, but if it has elements from others, they are set as the body of the rule: background(b1), . . . , background(bi). compoundbackground(Bj) ← background(Bj).
Vocabulary Fluents f1, . . . , fn can be defined in two forms: if they do not have elements of the background knowledge they are delcared as facts, otherwise they are defined in terms of their background knowledge, where the the fluent be at the head and the background knowledge at the body respectively: fluent(f1), . . . , fluent(fi). fluent(Fj, Fk) ← background(Fj) , background(Fk). fluent(Fn) ← background(Fn).
Similar as above, the actions a1, . . . , an can be declared in two ways: as facts if they do not have elements of the background knowledge, or as rules if they do: action(a1), . . . , action(ai). action(Aj, Ak) ← background(Aj) , background(Ak). action(An) ← background(An).
Also we need to set the time. It can be done, by defining a constant and then a fact called time where goes from 0 to the constant defined: const length=t. time(0..length).
Encoding domain description. The propositions of the form: executable a if p1, . . . , pn, ∼ q1, . . . , ∼ qr. can be declared by the following rule: executable(A,T) ← holds(p1, . . . , pn, T), not holds(q1, . . . , qr, T), background(A), time (T), T<length.
Propositions of the following form: a causes f if p1, . . . , pn, ∼ q1, . . . , ∼ qr can be declared just as: causes(action(A),fluent(F))← background(A), background(F). In order to encode the rules, we express them with holds, which means that the fluent is satisfied at time T.
Because the holds rule need that executable rule and causes rule be truth, and both have the same conditions, then there is no necessary to add the conditions to the causes rule.
We use four auxiliary rules. The first two are to set what fluent must be set as true: literal(G) ← fluent(G). literal(neg(G)) ← fluent(G).
The second two help us to set the opposite of the truth value of a fluent: contrary(F, neg(F)) ← fluent(F). contrary(neg(F), F) ← fluent(F).
We define three holds rules. The first one refers to the initial state, which shows what fluents are satisfied at the beginning: holds(F,0) ← literal(F),initially(F).
The second is for setting the fluents that are truth in the next time, which is T + 1, by some conditions of the previous time, which is T: holds(F, T+1) ← literal(F), time(T), T < length, action(A), executable(A,T), occurs(A,T), causes(A,F).
The third is for setting the opposite of the fluent value for the next time: holds(F, T+1) ← literal(F), literal(G), contrary(F,G), time(T), T < length, holds(F,T), not holds(G, T+1).
We also need to add the rule occurs and not occurs, which means that the action A occurs or not at time T respectively. To define the rule occurs we use the auxiliary possible rule, that shows which actions are possible to execute at time T and if there is no evidence of achieving the goal: possible(A,T) ← action(A),time(T),executable(A,T), not goal(T). With the possible rule we define the rules occurs and not occurs: occurs(A,T) ← action(A),time(T),possible(A,T), not not occurs(A,T). not occurs(A,T) ← occurs(AA,T),action(A),action(AA),time(T),A!=AA.
Encoding observation language. These prepositions represents the initial state of the problem. It can be declared by initially facts of what fluents are satisfied at the beginning: initially(fa), . . ., initially(fm).
Encoding query language. These prepositions declare the goal, or the wished state at time N. It is represented as finally facts: finally(fa), . . ., finally(fm).
We use two auxiliary rules which help us to determine whether if the goal is reached or not. not goal(T) ← time(T), literal(X), finally(X), not holds(X,T). goal(T) ← time(T), not not goal(T).
For last, the purpose of solving a planning problem is to find a plan in a given time. So we include two rules that indicates this to the program. The first indicates that exists a plan if the goal is reached according to the length of time. exists plan ← goal(length).
The second is a restriction which states that we do not want that a plan do no exist: ← not exists plan.
In the following section we give a brief example of a planning problem modeled into language A and into p-stable semantics in order to clarify this. 3.4
Here we present the worlds block problem, that consists of the following scenario:
There is a set of cubes (blocks) sitting on a table. The goal is to build one or
more vertical stacks of blocks. The catch is that only one block may be moved
at a time: it may either be placed on the table or placed atop another block.
Because of this, any blocks that are, at a given time, under another block cannot
be moved [
We present this planning problem modeled using language A and encoded into p-stable semantics. Briefly we remark that an A model is based on a set of fluents, actions, executable conditions, an initial state and a goal.
In language A Here we show how to model the problem into language A.
First we are going to represent our background knowledge. As we can see is composed by the three blocks: {block(a),block(b),block(c)}.
Our set of fluents are: {on(X,Y),ontable(X), clear(X),holding(X),handempty} The first fluent indicates the state of block X is on block Y. The second fluent indicates the state of block X is on the table. The third fluent shows that block X is clear, which means that there is no block above it. The fourth fluent indicates that block is holding by the hand. The last fluent indicates that the hand is empty.
We define four actions, which are: {pick up, put down, stack, unstack} These actions are the operations allowed to do. Pick up and put down refers to set or remove a block from the table. Stack and unstack refers to set or remove a block from another.
The domain description propositions are the executable conditions and, what causes an action A. We define a executable condition for each action: executable pick up(X) if clear(X), ontable(X), handempty. executable put down(X) if holding(X). executable stack(X,Y) if holding(X), clear(Y). executable unstack(X,Y) if clear(X), handempty, on(X,Y).
As well we define what causes each action: pick up(X) causes not ontable(X), not clear(X), holding(X), not handempty. put down(X) causes ontable(X), clear(X), not holding(X), handempty. stack(X,Y) causes not holding(X), not clear(Y), clear(X), handempty, on(X,Y). unstack(X,Y) causes holding(X), clear(Y), not clear(X), not handempty, not on(X,Y).
The observation language, which declare the initial state of the problem is: handempty, clear(c), clear(b), ontable(a), ontable(b), on(c,a).
Finally the query language propositions, that mean the goal, which is the configuration of the blocks stacked in decreasing order: handempty, clear(c), on(c,b), on(b,a), ontable(a).
In p-stable semantics In this section we present its encoding based on p-stable
semantics. In particular we use the new implementation for p-stable semantics
[
Briefly, we mention that is close similar from smodels [
There are more instances of the blocks world problem in [
const length=6. time(1..length). block(a). block(b). block(c).
Then the fluents and actions can be represented respectively as follows: fluent(on(X,Y)) ← block(X), block(Y). fluent(ontable(X)) ← block(X). fluent(clear(X)) ← block(X). fluent(holding(X)) ← block(X). fluent(handempty). action(pick up(X)) ← block(X). action(put down(X)) ← block(X). action(stack(X,Y)) ← block(X), block(Y).
not goal(T)← time(T), literal(X), finally(X), not holds(X,T). goal(T) ← time(T), not not goal(T). exists plan ← goal(length). ← not exists plan.
We add the auxiliary rules mentioned earlier. literal(G) ← fluent(G). literal(neg(G)) ← fluent(G). contrary(F, neg(F)) ← fluent(F). contrary(neg(F), F) ← fluent(F). holds(F, 1) ← literal(F), initially(F). holds(F, T+1) ← literal(F), time(T), T < length, action(A), executable(A,T),occurs(A,T), causes(A,F). holds(F, T+1) ← literal(F), literal(G), time(T), T < length, contrary(F,G), holds(F,T), not holds(G, T+1). possible(A,T) ← action(A), time(T), executable(A,T), not goal(T). occurs(A,T) ← action(A), time(T), possible(A,T), not not occurs(A,T). not occurs(A,T) ← action(A), action(AA), time(T), occurs(AA,T), A!=AA.
The following rules represent the observation language, that is the initial state of the problem. As we have shown before, we represent them by initially facts: initially(handempty). initially(clear(c)). initially(clear(b)). initially(ontable(a)). initially(ontable(b)). initially(on(c,a)).
Finally the rules of the query language, indicates the goal state that we want to have at time N, where N represents the number of steps. This has been defined by the const length. finally(handempty). finally(clear(c)). finally(on(c,b)). finally(on(b,a)). finally(ontable(a)).
With these rules, we have modeled the blocks world problem. Then we use
a recent implementation of p-stable semantics [
We only obtained one model, because it could not be found another plan that satisfies the rules shown before in 6 steps. We explain the plan into the following table:
Time Action State 0 unstack(c,a) clear(a), clear(c), ontable(a), ontable(b), on(c,a), handempty 1 put down(c) clear(a), clear(b), ontable(a), ontable(b), holding(c) 2 pick up(b) clear(a), clear(b), clear(c), ontable(a), ontable(b), ontable(c), handempty 3 stack(b,a) clear(a), clear(c), ontable(a), ontable(c), holding(b) 4 pick up(c) clear(b), clear(c), ontable(c), ontable(a), on(b,a), handempty 5 stack(c,b) clear(b), ontable(a), on(b,a), holding(c) 6 - clear(c), ontable(a), on(c,b), on(b,a), handempty It is easy to verify that the plan is correct.
Comparing the results obtained in this example with p-stable models and
answer sets, they both obtain models in different ways according to its semantics.
However, in [
Planning involves the representation of actions and world models, reasoning
about the effects of actions, and so on. We show that p-stable semantics is a good
way to model and solve planning problems, giving us with the p-stable models
the plans that we need, in order to go from an initial state to a goal. It can be
applied in a variety of tasks including robotics, process planning, autonomous
agents and spacecraft mission control [
This work was supported by the CONACyT [CB-2008-01 No.101581].