Date: Fri, 24 Sep 1999
From: Michael Gelfond
To: TAG
% Dear all,
% the program below is related to the ZOO problem by Sandewall.
% It formalizes a very small subset of the ZOO world focused
% on the agents ability to move and to mount animals.
% The program is due to Joel Galloway, Monica and Michael.
% We concentrated at this particular aspect of the problem
% because we wanted to see how the geometry of the place can be represented
% without specifying a coordinate system or some other scheme of naming
% all positions of objects in the zoo. (The absence of names for some positions
% is one of Sandewall's requirements).
% There are several reasons we want to share the program with other
% people in the group. First, of course we will appreciate some feedback.
% Our formalization is slightly different from those we used
% before. In particular, inertia rules are somewhat limited, etc.
% Second, we hope that it may help to interest some people
% in the ZOO problem enough to join our (very slow going) effort
% to design a complete formalization. (If someone is interested
% please let us know.) Third, the program is not tight and hence
% is not immediately suitable for CCALC. We hope however that
% CCALC can still be used correctly and we can have more
% experiments to really determine what parameters are important
% for efficiency.
% Let us start with an example:
% We are given the following simple scenario:
% Jack the zookeeper, is in the (very big) elephant cage and wants to mount the
% elephant. Initially Jack is in one corner of the elephant cage next to
% the food trough. An elephant and his dog companion are standing
% next to the water barrel in another corner of the cage.
% We are interested in finding a plan for Jack to mount the
% elephant. We assume that the elephant and other animals
% are cooperative, i.e. do not move in the act of mounting, etc.
% To model the domain we need to describe the effects of the movement
% of people and the zoo animals, and of the action "mount".
% As we mentioned before there is some difficulty in representing
% the agents' movements caused by the absence of a
% coordinate system which would allow us to name positions of objects.
% To overcome the difficulty we visualize the space to be populated by
% clusters of objects: people standing close to each other near the cage,
% a person and a horse standing near the gate, etc. Accordingly, we
% distinguish between long moves (i.e. moves from one cluster to another) and
% short moves, which happen within the cluster. A long move of an agent A to
% a destination D results in A being in the neighborhood of D while a
% short move brings A "next to" D. We assume that if A makes a "short" move
% to D then D does not move out of the neighborhood.
% However, if the move is long then A's move to D
% and D's move to some other place can happen in parallel. In this case
% we assume that A will end up in the same neighborhood as D.
% There is a restriction though: walking in circles is prohibited.
% We also assume that the zoo is not very heavily populated,
% and that clusters of objects are more or less evenly distributed across
% its territory. This can be approximated in terms of two defaults:
% Sparsity assumption: objects normally are not located next to each other.
% Even distribution: Objects normally belong to different clusters.
% ACTION DESCRIPTION
%---------------------------------
% Lists of objects,
%---------------------------------
animal(elephant).
animal(dog).
agent(jack).
agent(mary).
% Objects can be of two types, dynamic and static.
static(gate).
static(water).
static(food).
dynamic(X) :- animal(X).
dynamic(X) :- agent(X).
object(X) :- dynamic(X).
object(X) :- static(X).
%-------------------------------------------------------------------
% Fluents
%-------------------------------------------------------------------
% 1. "X is in the neighborhood of Y"
fluent(in_nh(X,Y)) :-
object(X), object(Y), neq(X,Y).
% 2. " X is next to Y, i.e. close enough to mount or to perform any other
% "short range" action on Y"
fluent(next_to(X,Y)) :-
object(X), object(Y).
% 3.
fluent(mounted(X,Y)) :-
agent(X), animal(Y).
%---------------------------------
% Actions
%---------------------------------
% We have two basic actions, mount and move:
% To define them we first define types of moves:
type_of_move(l). % long move
type_of_move(s). % short move
action(move(MT,X,Y)) :- type_of_move(MT), dynamic(X), object(Y), neq(X,Y).
action(mount(X,Y)) :- agent(X), animal(Y).
% The "generalized" actions below are used to simplify
% the rules and to increase efficiency of planning with SMODELS.
% X makes a move of type MT
occurs(move(MT,X),T) :- type_of_move(MT),time(T), dynamic(X),object(Y),
occurs(move(MT,X,Y),T).
% X makes a move of type MT
occurs(move(X),T) :- type_of_move(MT), time(T), dynamic(X),
occurs(move(MT,X),T).
occurs(mount(X),T) :- time(T), agent(X), animal(Y),
occurs(mount(X,Y),T).
%---------------------------------
%---------------------------------
%---------------------------------
% Effects of actions
%---------------------------------
%---------------------------------
%---------------------------------
%---------------------------------
%---------------------------------
% Long moves, "in_neighborhood" relation.
%---------------------------------
%---------------------------------
%---------------------------------
% Direct effects of a long move
%---------------------------------
% To avoid repetition this also includes
% common effects of both types of moves
% If X moves to the neighborhood of Y it will end up there.
% (Notice that this implies that if Y moves then X catches
% up with him and they end up in the same neighborhood).
holds(in_nh(X,Y), T1) :- next(T,T1), dynamic(X), object(Y),
occurs(move(l,X,Y),T).
% If agent X is mounted on animal Y and X moves to
% some place then Y also moves to that place. Similarly for Y.
occurs(move(MT,Y,Z),T) :- time(T), type_of_move(MT),
agent(X), animal(Y), object(Z),
holds(mounted(X,Y),T),
occurs(move(MT,X,Z),T).
occurs(move(MT,X,Z),T) :- time(T), type_of_move(MT),
agent(X), animal(Y), object(Z),
holds(mounted(X,Y),T),
occurs(move(MT,Y,Z),T).
%---------------------------------
% Indirect effects of a long move
%---------------------------------
% Relation "in neighborhood" is reflexive, symmetric and transitive.
holds(in_nh(X,X),T) :- time(T), object(X).
holds(in_nh(X,Y),T) :- time(T), object(X), object(Y),
holds(in_nh(Y,X),T).
holds(in_nh(X,Z),T) :- time(T), object(X), object(Y), object(Z),
holds(in_nh(X,Y),T),
holds(in_nh(Y,Z),T).
% The next rule relates two relations, "next_to" and "in_nh".
% It says that objects that are next to each other belong to
% the same neighborhood
holds(in_nh(X,Y),T) :- time(T), object(X), object(Y),
holds(next_to(X,Y),T).
%---------------------------------
% Executability conditions for a long move
%---------------------------------
% Long moves are moves between different neighborhoods.
:- time(T), dynamic(X), object(Y),
occurs(move(l,X,Y),T),
holds(in_nh(X,Y),T).
% Agents cannot go to two different neighborhoods at the same time.
:- time(T),dynamic(X),object(Y),object(Z),neq(Y,Z),
not holds(in_nh(Y,Z),T),
occurs(move(l,X,Y),T),
occurs(move(l,X,Z),T).
% Long and short moves of an agent cannot occur together.
:- time(T), dynamic(X),
occurs(move(l,X),T),
occurs(move(s,X),T).
%---------------------------------
% Inertia
%---------------------------------
% Somewhat surprisingly, we do not need a "real" inertia axiom
% here. (Moreover, we tried several formalizations with such axiom
% and they seem to be substantially more complicated).
% Instead we have the following:
% If X and Y were in the same neighborhood at moment T
% and none of them moved they are going to stay in that
% neighborhood at T + 1.
holds(in_nh(X,Y),T1) :- next(T,T1), object(X), object(Y),
holds(in_nh(X,Y), T),
not occurs(move(l,X),T),
not occurs(move(l,Y),T).
% Finally, we formalize our assumption of even distribution
% of clusters: All the above rules defining in_nh(X,Y)
% can be viewed as defining exceptions to this default.
holds(neg(in_nh(X,Y)),T) :- time(T), object(X), object(Y),
not holds(in_nh(X,Y), T).
%---------------------------------
%---------------------------------
% Short moves, "next_to" relation.
%---------------------------------
%---------------------------------
%---------------------------------
% Direct effects of a short move
%---------------------------------
% To describe the effects of moves within a neighborhood we
% recall our assumption which says that objects in the zoo
% are normally not located next to each other. This
% can be represented by the rule:
% SPARSITY ASSUMPTION
holds(neg(next_to(X,Y)), T) :- time(T),object(X), object(Y),
not holds(next_to(X,Y),T).
% There are several exceptions to this default:
% "next_to" can become true as a result of a short
% move or by inertia. These exceptions can be defined as :
% Short move of X to Y results in X being next to Y.
holds(next_to(X,Y), T1) :- next(T,T1), dynamic(X), object(Y),
occurs(move(s,X,Y),T).
% X stays next to Y unless one of them moves or mounts an animal.
holds(next_to(X,Y), T1) :- next(T,T1), object(X), object(Y),
holds(next_to(X,Y),T),
not occurs(move(X),T),
not occurs(move(Y),T),
not occurs(mount(X),T),
not occurs(mount(Y),T).
% (Of course X being next to Y in the initial situation
% provides the third exception to the sparsity assumption
% but it does not require any extra care).
% The last two rules in this section describe static
% relations between the fluents:
% Relation "next to" is symmetric.
holds(next_to(X,Y),T) :- time(T), object(X), object(Y),
holds(next_to(Y,X),T).
% An agent is next to an animal if mounted on it.
holds(next_to(X,Y),T) :- time(T), agent(X), animal(Y),
holds(mounted(X,Y),T).
%---------------------------------
% Executability conditions for a short move
%---------------------------------
% Short moves can only be performed within a neighborhood.
:- time(T), dynamic(X), object(Y),
holds(neg(in_nh(X,Y)),T),
occurs(move(s,X,Y),T).
% As mentioned before we assume that
% if X makes a "short" move to Y then Y does not move
% out of the neighborhood.
:- time(T), dynamic(X), dynamic(Y),
occurs(move(s,X,Y),T),
occurs(move(l,Y),T).
% X cannot move next to itself.
:- time(T), dynamic(X),
occurs(move(s,X,X),T).
% X cannot move next to Y if it is already there.
:- time(T), dynamic(X), object(Y),
occurs(move(s,X,Y),T),
holds(next_to(X,Y),T).
% We assume that short move is a "planar" action, i.e. X cannot get
% next to a mounted Y unless X itself is mounted.
:- time(T), dynamic(X), agent(Y),
occurs(move(s,X,Y),T),
holds(mounted(Y),T),
not holds(mounted(X),T).
% A mounted Y cannot get next to an X which is not mounted.
:- time(T), dynamic(X), agent(Y),
occurs(move(s,Y,X),T),
holds(mounted(Y),T),
not holds(mounted(X),T).
% Here mounted(X) is an auxiliary relation
% defined as follows:
holds(mounted(X),T) :- time(T), dynamic(X), animal(Y),
holds(mounted(X,Y),T).
% If two agents are mounted at the same animal they cannot go
% two different directions.
:- time(T), agent(X1), agent(X2), neq(X1,X2), animal(Y),
object(Z1), object(Z2), neq(Z1,Z2),
holds(mounted(X1,Y),T),
holds(mounted(X2,Y),T),
occurs(move(s,X1,Z1),T),
occurs(move(s,X2,Z2),T).
%---------------------------------
%---------------------------------
% Mount, "mounted" relation.
%---------------------------------
%---------------------------------
%---------------------------------
% Effects of "mount"
%---------------------------------
% Obviously being mounted is not a most typical
% state of an agent. This justifies the default
holds(neg(mounted(X,Y)),T) :- time(T), agent(X), animal(Y),
not holds(mounted(X,Y),T).
% Exceptions to this default come from the inertia
holds(mounted(X,Y),T1) :- next(T,T1), agent(X), animal(Y),
holds(mounted(X,Y),T),
not occurs(dismount(X,Y),T). % this action is not introduced yet
% and the action "mount":
holds(mounted(X,Y),T1) :- next(T,T1), agent(X), animal(Y),
occurs(mount(X,Y),T).
%%%% Mounting an animal also causes some objects to change
%%%% their next_to relation, namely:
% Mounting an animal makes one to be located next to
% the other animal's riders (if there are any).
% (THIS MAY BE REPLACED BY A STATIC LAW
% but we are not too serious here.)
holds(next_to(X1,X2),T1) :- next(T,T1), agent(X1),
agent(X2),animal(Y),
occurs(mount(X1,Y),T),
holds(mounted(X2,Y),T).
% If animals are close so are their riders
holds(next_to(X1,X2),T) :- time(T), agent(X1), agent(X2),
animal(Y1), animal(Y2),
holds(mounted(X1,Y1),T),
holds(mounted(X2,Y2),T),
holds(next_to(Y1,Y2),T).
%---------------------------------
% Executability condition for mount
%---------------------------------
%An agent cannot mount an animal unless it is "next_to" that animal
:- time(T), agent(X), animal(Y),
holds(neg(next_to(X,Y)),T),
occurs(mount(X,Y),T).
% Agents can not mount while moving.
:- time(T), agent(X), animal(Y),
occurs(mount(X,Y),T),
occurs(move(X),T).
% Animals cooperate with their riders
:- time(T), agent(X), animal(Y),
occurs(move(Y),T),
occurs(mount(X,Y),T).
% A mounted agent can not mount (this is a zoo, not a circus)
:- time(T), agent(X), animal(Y),
holds(mounted(X),T),
occurs(mount(X,Y),T).
% Agent can only mount one animal
:- time(T), agent(X), animal(Y1), animal(Y2), neq(Y1,Y2),
occurs(mount(X,Y1),T),
occurs(mount(X,Y2),T).
%%%%%%% To complete our action description we need only
%%%%%%% to define negation:
:- time(T), object(X), object(Y), fluent(F), holds(F,T), holds(neg(F),T).
:- time(T), action(A), occurs(A,T), occurs(neg(A),T).
%%%%%%%%%%%%% As before, this description can be used with
%%%%%%%%%%%%% different control modules to do planning,
%%%%%%%%%%%%% prediction, diagnosis, etc. We will use it
%%%%%%%%%%%%% with a planning module similar to those
%%%%%%%%%%%%% we had before. As in previous cases this
%%%%%%%%%%%%% gives some substantial improvement in the
%%%%%%%%%%%%% efficiency of SMODELS.
%---------------------------------
% Planning Module
%---------------------------------
% At each step an agent A makes a long or short move or mounts
% an animal. Since we are looking for a plan for Jack, variable A below
% should be replaced by Jack. At the end we wanted to experiment
% with the program which has a large number of models.
% To do that we introduced another agent, Mary, who is forced to move
% even if it is not necessary for a plan. Cooperation between
% these agents will not be discussed here.
occurs(move(A),T) :- time(T), not goal(T), agent(A),
not occurs(mount(A,elephant),T).
occurs(mount(A,elephant),T) :- time(T), not goal(T), agent(A),
not occurs(move(A),T).
% Agent has only two types of moves:
occurs(move(l,A),T) :- time(T), agent(A),
occurs(move(A),T),
not occurs(move(s,A),T).
occurs(move(s,A),T) :- time(T), agent(A),
occurs(move(A),T),
not occurs(move(l,A),T).
% Move of every type can be a move to some other object.
occurs(move(MT,A,P),T) :- time(T), type_of_move(MT), object(P), agent(A),
occurs(move(MT,A),T),
not other_occurs(MT,A,P,T).
% Different type of move is made
other_occurs(MT,A,P,T) :- time(T), type_of_move(MT), type_of_move(MT1),
object(P), agent(A),
occurs(move(MT1,A),T),
neq(MT,MT1).
% Move to a different object.
other_occurs(MT,A,P,T) :- time(T), type_of_move(MT),
object(P),object(P1), agent(A),
occurs(move(MT,A,P1),T),
neq(P,P1).
%%% We run the program on different inputs and with different tasks.
%%% Below is a simple sample:
%---------------------------------
%GOAL
%---------------------------------
const lasttime = 3.
goal(T) :- time(T),
holds(mounted(jack,elephant),T),
holds(in_nh(jack,gate),T),
holds(next_to(mary,elephant),T).
:- not goal(lasttime).
time(0..lasttime).
next(T,T1) :- time(T), time(T1), T1 = T + 1.
%---------------------------------
% HISTORY
%---------------------------------
holds(neg(in_nh(X,Y)),0) :- object(X),object(Y),
not holds(in_nh(X,Y),0).
holds(neg(mounted(X,Y)),0) :- agent(X),animal(Y),
not holds(mounted(X,Y),0).
holds(in_nh(elephant,water),0).
holds(in_nh(dog,gate),0).
holds(next_to(jack,elephant),0).
%---------------------------------
% Printout Auxiliary Predicates
%---------------------------------
o(move(MT,A,Y),T) :- agent(A),time (T), object(Y), type_of_move(MT),
occurs(move(MT,A,Y),T).
o(mount(A,Y),T) :- time (T), animal(Y),agent(A),
occurs(mount(A,Y),T).
%h(F) :- fluent(F),holds(F,1).
%h(n(F)) :- fluent(F),holds(neg(F),1).
%h(F,2) :- fluent(F),holds(F,2).
%h(F,4) :- fluent(F),holds(F,4).
hide type_of_move(M).
hide holds(F,T).
hide time(X).
hide next(X,Y).
hide goal(X).
hide animal(X).
hide agent(X).
hide object(X).
hide occurs(X,T).
hide dynamic(X).
hide action(X).
hide other_occurs(X,Y,W,Z).
hide noccurs(X,Y).
hide fluent(X).
hide static(X).
% BELOW WE HAVE SOME TESTING RESULTS:
% OTHER EXPERIMENTS ARE CONSISTENT WITH THIS.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% T E S T I N G
% Example 1
%
%holds(in_nh(elephant,water),0).
%holds(in_nh(dog,gate),0).
%holds(next_to(jack,elephant),0). <-----
%
%const lasttime = 3.
%
%goal(T) :- time(T),
% holds(mounted(jack,elephant),T),
% holds(in_nh(jack,gate),T),
% holds(next_to(mary,elephant),T).
%
% num of models | simple planning module | our planning module
%
% 1 | 2.61 sec | 2.19 sec
% all | 3.54 sec (116 models) | 2.96 sec (42 models)
%
% Example 2
%
%holds(in_nh(elephant,water),0).
%holds(in_nh(dog,gate),0).
%holds(in_nh(jack,mary),0). <------
%
%const lasttime = 4.
%
%
%goal(T) :- time(T),
% holds(mounted(jack,elephant),T),
% holds(in_nh(jack,gate),T),
% holds(next_to(mary,elephant),T).
%
%--------------------------------
% num of models | simple planning module | our planning module
%
% 1 | 22.79 sec | 13.13 sec
% all | 26.43 (8 models) | 15.7 sec (8 models)
%
===========
Date: Wed, 6 Oct 1999
From: Hudson Turner
To: TAG
In thinking about the zoo world specification, I've come to suspect that
there is a typo in the description of the landscape structure that may (or
may not) be important to the approach taken in the partial zoo worlds
description proposed recently by TAG members.
At one point, the specification says:
One designated location is called the {\em outside}; all other locations
are called {\em cages}. ... Each positions [sic] is included in exactly
one location. Informally, each cage as well as the outside consists of
a set of locations, viewed for example as tiles on the floor.
It seems to me that the simplest way to make sense of this portion of the
specification is to assume that the last occurrence of "locations" in this
excerpt should be read "positions."
==========
Date: Wed, 27 Oct 1999
From: Vladimir Lifschitz
To: Michael Gelfond
In the formalization of the Zoo domain that you sent to us on September 24,
the formalization of inertia is somewhat unusual:
> % If X and Y were in the same neighborhood at moment T
> % and none of them moved they are going to stay in that
> % neighborhood at T + 1.
>
> holds(in_nh(X,Y),T1) :- next(T,T1), object(X), object(Y),
> holds(in_nh(X,Y), T),
> not occurs(move(l,X),T),
> not occurs(move(l,Y),T).
This formulation is actually unusual in two ways. First, it includes an
explicit list of actions that are assumed not to occur. In this sense, it
is similar to monotonic solutions to the frame problem--to frame axioms (or
explanation closure axioms), rather than formalizations of the common sense
law of intertia. Second, it contains only the positive half of inertia: it
says that under some conditions in_nh remains true, but there is nothing here
about the conditions when it remains false. it seems that the negative
half of the inertia assumption is replaced by the closed-world assumption
for in_nh:
> holds(neg(in_nh(X,Y)),T) :- time(T), object(X), object(Y),
> not holds(in_nh(X,Y), T).
I am wondering how essential the first of these two features is. Would it
be possible to replace your version of inertia by a rule that doesn't mention
actions? Say, by a normal default in the style of Reiter, or a version
containing the abnormality predicate? It seems to me that this would
improve your formalization by making it more elaboration tolerant. If we
decide to enhance your description of the zoo domain by new actions that
affect the value of in_nh, directly or indirectly, the assumption that these
new actions are not executed would have to be inserted in the body of the
inertia rule that you have now. But the traditional nonmonotonic descriptions
of inertia would not have to be modified when a change like this is made.
========
Date: Tue, 15 Feb 2000
From: Michael Gelfond
To: Vladimir Lifschitz
thanks for reminding me that your question about
our ZOO formalization remains unanswered.
Sorry for the long silence. Changing jobs is a very time
consuming business. I hope that in about ten days life will
be almost back to normal again and I'll be able to be
more active in TAG. I am really looking forward to it.
I start with answering your question:
The first of two features you mentioned in your
question is certainly not essential.
The inertia axiom can be written in the more
traditional way by simply saying
holds(in_nh(X,Y),T1) :- next(T,T1), object(X), object(Y),
holds(in_nh(X,Y), T),
not ab(X,Y,T).
ab(X,Y,T) :- occurs(move(1,X),T).
This is certainly more elaboration tolerant.
If other exceptions are discovered they may be added
in the form of cancellation axioms as above.
That is how we normally do it and there was no special
reason to do it differenly in the ZOO problem.
I guess we were just trying to concentrate on more
interesting parts - representing moves without
fixing the coordinate system, using other
defaults except the inertia, trying to put some control
into the planning module, etc.