Knowledge Representation & Reasoning

2. Logic-based knowledge representation and reasoning

2.2. Logic-based action planning

In order to model the evolution of the world over time, we describe a
framework in FOL called situation calculus. In situation calculus, world states and actions' pre- and postconditions are bound to an abstract symbol representing a certain situation. In context of a robot agent, a situation represents one cycle in the perception-action loop:

Technically, a situation is denoted by a term in FOL, i.e., the constant symbol $S_0$ denoting the initial situation, or a function $do(a, s)$ representing the situation that is obtained when an action $a$ is executed in situation $s$ .
Actions are represented by terms in FOL. Constant symbols stand for actions without arguments (e.g., Stop), and functions represent actions that can be parameterized (e.g., Open(DrawerLeft)). There is a dedicated predicate $possible(a,s)$ , which states that an action $a$ is applicable in situation $s$ .
Fluents represent certain aspects of a world state that may change from one situation to another. Fluents can be represented by predicates, like $\lnot contains(Pot01, Corn01, S_0)$ or functions like $temperature(StoveCenter, S_0)$ ). Fluents are always bound to specific situations that they refer to because they may change their values over time. States that are constant over all situations are called atemporary and do not need to be assigned a situation. Examples of such predicates are the \textit{type} assertions as introduced above, such as $type(Corn01, Corn)$ .

The function

$do$ is also called projection as it predicts the states of future situations that are obtained through action execution. By nesting multiple do functions, one can represent the final situation that is obtained after execution of a complete sequence of actions. For example, the situation after execution of the three actions

Put(Pot01, StoveCenter)
Pour(Bowl01, Pot01)
TurnKnow(switch(StoveCenter))

can be denoted by

do(TurnKnob(switch(StoveCenter)),

do(Pour(Bowl01, Pot01),

do(Put(Pot01, StoveCenter ), $S_0$ )))

By convention, the last argument in the list of arguments (if any) always denotes the situation symbol.

State Axioms. We have to describe the state of the environment in the initial situation

$S_0$ through fluent and atemporal axioms. In order to describe the popcorn world, for instance, we have to assert the types of objects in our environment:

type(TabletopLeft, Location) $\land$ type(StoveCenter, Location) $\land$ type(TabletopRight, Location)

$\land$ type(DrawerLeft, Drawer) $\land$ type(DrawerRight, Drawer)

$\land$ type(ShelfLeft, Shelf) $\land$ type(ShelfRight, Shelf)
$\land$ type(Corn01, Corn) $\land$ type(Pot01, CookingPot)
$\land$ type(Bowl01, Bowl) $\land$ type(Plate01, Plate)

The atemporal axioms may also represent a subsumption relation in order to construct a hierarchy of concepts, e.g.,

$\forall x.$ (type(x, Bowl)

$\lor$ type(x, CookingPot)

$\lor$ type(x, Plate))

$\Rightarrow$ type(x, Container)

$\forall x.$ (type(x, Bowl)

$\lor$ type(x, CookingPot)

$\lor$ type(x, Corn)

$\lor$ type(x, Bowl)

$\lor$ type(x, Lid)

$\lor$ type(x, SaltGrinder))

$\Rightarrow$ type(x, MovableObject),

which enables us to refer to collections of object types in later axioms. The fluents represent the mutable parts of a situation, such as the object locations:

location(Pot01, ShelfRight, $S_O$ )

...

Note that, in standard FOL, it is insufficient to only specify the positive axioms but we also need to declare what does not hold. It is, however, common to make a closed-world assumption, which means that the framework assumes all ground atoms to be false, whose truth values have not been explicitly declared.

Action axioms. Actions are represented by two kinds of axioms, the possibility axiom}, which specifies under which circumstances an action is possible, and a successor state axiom, which describes the way in which the successor situation is affected by an action. The possibility axioms are sentences in FOL of the form

$\forall s. \psi(a)\Rightarrow possible(a,s)$ ,

where

$\psi(a)$ is a sentence with a free variable

$a$ specifying the preconditions of the action

$A$ . The successor states are specified by axioms of the form

$\forall a,s.\ possible(a,s) \Rightarrow (\phi (do(a,s)) \Leftrightarrow (\varepsilon^+_\phi(a,s)\lor (\phi(s)\land\lnot\varepsilon^-_\phi(a,s)))$ ,

where

$\phi(s)$ is a fluent declaration in situation

$s$ and

$\varepsilon^+_\phi(a,s)$ is a specification of the positive effects of an action

$a$ on

$\phi$ in situation

$s$ . Analogously,

$\varepsilon^-_\phi(a,s)$ specifies the negative effects of action

$a$ on

$\phi$ in

$s$ . An axiom of the form of the Equation can be read as follows: "In a situation

$s$ where action

$a$ is applicable, the fluent

$\phi$ will hold after execution of

$a$ if and only if

$a$ has made

$\phi$ true (positive effect), or

$\phi$ was already true in

$s$ and

$a$ did not make

$\phi$ false (negative effect).''

The situations in situation calculus can be compared to single frames on a filmstrip, which is why these axioms are also called frame axioms. The action effects specifications determine the changes from one frame to the next one. However, only considering the aspects that
change is not enough. In most cases, only a small subset of fluents will be affected by an action and nearly all others stay the same. In FOL, this needs to be explicitly stated. In order to account for this problem, which is also known as the frame problem, it is necessary to also consider

$\varepsilon^-_\phi(a,s)$ in the successor state axiom.

As an exemplary action, we consider the action of moving an object from one location to another. In our popcorn world, we consider seven locations, at which movable objects may be put down, i.e., two counter tops, two shelves, two drawers and the stove top. For simplicity, we assume that each location is able to hold only one single object at a time. Let us first examine the possibility axiom for $Put(o,l)$ , which denotes the action of putting an object

$o$ to the location

$l$ . Obviously, based on the above presumptions, $Put(o,l)$ is only possible if $o$ is movable and $l$ is not already occupied by another object. In addition, we have to consider that objects in drawers are not accessible unless the the drawer is open. We can capture this knowledge in a fluent accessible and a possibility axiom,

$\forall o, s.$ accessible(o,s) $\Leftrightarrow\exists l.$ location(o,s) $= l\land$ (type(l, Drawer) $\Rightarrow$ open(l,s)))

$\forall o, l, s.$ (type(o,MovableObject) $\land$ type(l, Location)

$\land\lnot(\exists o'.$ location(o',s) = l) $\land$ accessible(o,s)) $\Rightarrow$ possible(Put(o,l),s).

For the accessible fluent of an object

$o$ to hold in situation

$s$ ,

$o$ 's location must either not be a drawer, or, if it is a drawer, it must be open. Otherwise, the object is not accessible. The positive effect of

$Put(o,l)$ is that the object will be at location

$l$ in the successor state, whereas the negative effect is that it will disappear from its original location:

$\forall a,o,l,s.$ possible(a,s) $\Rightarrow$

(location(o, do(a,s))= l $\Leftrightarrow$ a= Put(o,l)

$\lor$ (location(o,s) = l $\land\lnot(\exists l'. l'\neq l\land$ a = Put(o,l'))),

i.e., the location of an object

$o$ will be

$l$ in the successor state, if and only if

$o$ has been put to

$l$ or it has already been at

$l$ and was not put away to some other location

$l'$ .