\documentstyle[a4,epsf,alltt]{article}
\begin{document}


\include{commands}
\newcommand{\ital}[1]{{\it #1}}

\title{Production systems (3)}
\author{Jocelyn Ireson-Paine}
\maketitle


\section{Introducing {\tt gbug}}

This handout arises from something Gareth was trying to do in order to
make the bug's behaviour more directed. It demonstrates how data in STM
--- particularly goals and planned paths --- can be used to control
behaviour.

To begin, please try running \verb/gbug/ in \verb/gworld/, by doing
\begin{verbatim} eps( gbug, gworld ). \end{verbatim} When you try this
for the first time, switch off the diagnostics with the \verb/-/ control
command, and then run the bug for about 100 cycles by doing \verb/s
100/. This will enable you to appreciate the bug's behaviour without
being distracted by streams of diagnostics.

Notice that there is a lot less ``dithering'' than in the other bugs
you've seen. When the bug sees a piece of food, it heads straight
towards it, ignoring distractions on the way. Most of the other bugs got
confused by two pieces of food equally near them, and would continuously
turn toward one and then the other, never actually getting to either.
\verb/gbug/ doesn't do this.

How does this bug work? Its code is shown below, in
figure~\ref{ps3:gbug}.
\vfigstart
\begin{verbatim}
resolve [p,r].

stm [ goal(notice_food) ].

stm_predicates [goal,path].


goal(notice_food),
can_see(+)
=>
erase(goal(notice_food)),
goal(plan_path).

goal(notice_food),
not(can_see(+))
=>
wander.


goal(plan_path),
retina(X,Y,nearest(+)),
retina_path( [3,2], [X,Y], Path )
=>
path(Path),
erase(goal(plan_path)),
goal(check_path_found).


goal(check_path_found),
path(not_found)
=>
erase(goal(check_path_found)),
goal(notice_food).

goal(check_path_found),
not(path(not_found))
=>
erase(goal(check_path_found)),
goal(follow_path).


goal(follow_path),
path( [First|Rest] )
=>
exec( First ),
erase(path(_)),
path(Rest).

goal(follow_path),
path( [] ),
over(+)
=>
erase(goal(follow_path)),
erase( path([]) ),
exec( [grab] ),
exec( [use] ),
goal( notice_food ).

goal(follow_path),
path( [] ),
not( over(+) )
=>
erase(goal(follow_path)),
erase( path([]) ),
goal( notice_food ).


:- prolog_language(pop11).

needs retina_path;

define safe(awm,x,y);
    awm(x,y) /= `*`
enddefine;

define find_path(start,goal);
    lvars start, goal;
    retina_path( retina(),start,goal,safe);
enddefine;

:- prolog_language(prolog).

:- reconsult('path_to_moves.pl').

retina_path( Start, Goal, Moves ) :-
    prolog_eval( find_path(Start,Goal), Path ),
    path_to_moves( [0,1], Path, Moves_, _ ),
    moves_to_commands( Moves_, Moves ),
    !.

retina_path( Start, Goal, not_found ).


moves_to_commands( [], [] ) :- !.

moves_to_commands( [Move|Rest], [[Move]|Rest1] ) :-
    moves_to_commands( Rest, Rest1 ).
\end{verbatim}
\vfigend{ps3:gbug}{{\tt gbug}}             

At the end of this code, you will see a notation that will be strange to
you. This is a mixture of Prolog and Pop-11, and is there to interface a
path-planning predicate to the rules. I'll say more about that later.

Once you have tried the bug with the diagnostics turned off, run it
again with them on, and let it get as far as finding two or three pieces
of food. Exactly what it does will vary from run to run because of the
random element in \verb/wander/. However, you should find that 30 cycles
are sufficient. Then print out the view window so you can examine it more
closely. You can do this in two ways. Either edit the window with the
\verb/v/ control command during a life, and then give the ENTER
\verb/ctcprint/ command to Ved. Or wait until the life has finished, and
then do \verb/ved view/ from Prolog, followed by the ENTER \verb/ctcprint/
command. If you haven't already been shown how to use the CTC printer,
ask me. It's a dot matrix one, so it isn't very quick.

Having got a paper copy of your trace, look at the way that STM changes,
and at the rules that are fired. As you can see from the \verb/stm/
declaration, there are two STM predicates: \verb/goal/ and \verb/path/.
Each of these has one argument --- predicates with arguments were
introduced towards the end of my second handout on production systems.
In the trace, when STM predicates appear in the rules, they are marked
with an \verb/@/ symbol, although this doesn't appear in STM, or in the
rules as you write them. That helps to distinguish STM predicates from
perceptual ones, and is useful as a check against failing to declare
them properly. Before proceeding to the following section, try to get an
idea of what's going on for yourself. Concentrate on how the arguments
to these two STM predicates change in each PS cycle.

One minor point is that the resolution step never needs to be carried
out. I have constructed the rules in such a way that only one matches at
any stage. That makes the trace shorter; more important, it also makes
the program easier to understand. Although resolution is an important
component of PS's as psychological models, it does make the effect of a
program harder to predict. In general, unless you are using PS's for
cognitive modelling, it is worth making rule conditions as explicit as
possible, to cut down the number of rules that need to be resolved.


\section{Goals}

Every rule's condition contains a test on \verb/goal/, and many of the
rules erase the old \verb/goal/ fact and add a new one. This predicate
has four possible arguments:
\begin{verbatim}
check_path_found
follow_path
notice_food
plan_path
\end{verbatim}

Each argument indicates that the bug is trying to achieve a particular
goal, and is carrying out a particular kind of behaviour in order to do
so. What conditions cause it to change from one to another? You can
depict this diagrammatically in a {\it state transition diagram}. Take
some paper, and draw four points, one for each of the arguments. Label
each with its argument. Then think about the circumstances under which
the bug will change its goal from --- for example --- \verb/notice_food/
to \verb/plan_path/. Draw an arrow pointing from the \verb/notice_food/
node to the \verb/plan_path/ node. Write alongside this arrow the
circumstance which causes this change of goal. You can either write it
in English, or as a rule condition.

Altogether, with four points, there are twelve possible arrows. However,
not all of them exist in this bug. Fill in the rest of the ones that do,
and write the corresponding circumstance by each. This kind of diagram
is often useful in getting an overview of how complex systems behave.
The points, incidentally, are usually drawn as little circles, and
called {\it nodes}; the arrows are often called {\it arcs}. In many
systems, the transition from one node to another will not be
deterministic, and the arcs will have probabilities associated with
them.


\subsection{Adding a new goal}

If you have understood how STM predicates work, and how \verb/erase/
works, I hope it's not necessary for me to explain the goals further,
except in their interaction with path-planning. You can test your
understanding by trying the following problem.

\verb/gworld1/ is similar to \verb/gworld/. You will notice however that
each piece of food is next to some water. In this new world, once the
bug has eaten a piece of food, he becomes dirty. The smell attracts
predators, and if the bug does not wash himself within the next few
turns, he will be eaten! (The current version of Eden does not make the
predators visible, because it can't deal properly with other autonomous
objects: so far, they're just my plot device to explain why the bug
dies.)

You can demonstrate this by running \verb/gbug/ in the new world.
Lacking the necessary cleaning behaviour, it will soon perish. Note the
state of the bug's cleanliness, displayed on the second status line.

Now, assume that once the bug has eaten the food, he must set himself a
new goal: to wash. This entails first getting over the water, which can
be done with \verb/move_towards/, and then \verb/use/ing it. Having
washed, he should then go back to noticing food. Because each piece of
food is always very near to water, it isn't necessary to do
path-planning: you can just call \verb/move_towards/. Add a new rule or
rules to do this, imitating the use of goals in \verb/gbug/. Once it
works, update your state-transition diagram accordingly.


\subsection{Adding another goal}

In \verb/gworld2/, it isn't the world but the bug that I have made more
complicated. As in \verb/gworld1/, the bug must wash immediately after a
meal. But it also needs to defecate. Eating food puts the bug into a
state of digestion, shown on the first status line. Once in this state,
it must defecate within 15 moves, otherwise it will burst. Defecation is
achieved by performing the (new) action \verb/defecate/, and can only be
done in an empty cell. You can demonstrate this via the manual bug. To
make it defecate, type \verb/O/ when you get the initial list of
actions. This will bring up a new list, with just one option. Type
\verb/d/ in reply.

Now modify \verb/gworld2/ so that after eating, the bug not only cleans
itself, but also relieves itself. You will need to add a new goal. When
obeying this goal, the animal should seek an empty spot in which to
defecate. You denote this as \verb/' '/. Once you have modified your
rules, update your state transition diagram accordingly.

Finally, draw a new state transition diagram. Unlike the previous one,
this must reflect the state of the bug's environment and physiology, not
its mind. These put the bug into one of states: smelly-and-digesting,
smelly, digesting, dead, and neutral. The last one represents the bug
before it has eaten for the first time, or after it has cleaned and
relieved itself.

To end, it hardly needs saying that I do not intend the bugs as serious
models of animal physiology. However, they are not serious models of
animal {\it psychology} either, but just exercises --- in this case, on
goals. As I mentioned in the {\it AI and PopBeast} handout, some
researchers do not believe that folk-psychology entities such as goals
are explicitly represented in the mind; others go even further and
assert that they should not be represented in engineered artifacts such
as robots, because doing so leads to inflexible behaviour. Even
neglecting that point of difference, there are many many others between
the bug and real animals, and you should not infer that one is intended
as a model of the other.                   


\section{Path planning}

The rules below are the ones from \verb/gbug/ that either plan paths or
use them.
\begin{verbatim}
goal(plan_path),
retina(X,Y,nearest(+)),
retina_path( [3,2], [X,Y], Path )
=>
path(Path),
erase(goal(plan_path)),
goal(check_path_found).


goal(check_path_found),
path(not_found)
=>
erase(goal(check_path_found)),
goal(notice_food).

goal(check_path_found),
not(path(not_found))
=>
erase(goal(check_path_found)),
goal(follow_path).


goal(follow_path),
path( [First|Rest] )
=>
exec( First ),
erase(path(_)),
path(Rest).

goal(follow_path),
path( [] ),
over(+)
=>
erase(goal(follow_path)),
erase( path([]) ),
exec( [grab] ),
exec( [use] ),
goal( notice_food ).

goal(follow_path),
path( [] ),
not( over(+) )
=>
erase(goal(follow_path)),
erase( path([]) ),
goal( notice_food ).
\end{verbatim}

The idea is that when the bug spots a piece of food, it works out a
sequence of moves that will get it there. This sequence is not
guaranteed to be the shortest, though it often will be. Having generated
the sequence, the bug stores it as the argument to the STM predicate
\verb/path/. The sequence is represented as a {\it
list}: this word has a specific technical meaning in computing, implying
something about how elements of the sequence are connected together.
However, for your purposes, the main thing to note is that you can tell
something's a list by the fact that it's displayed in square brackets.
This is demonstrated below, with an extract from one of the diagnostic
traces.
\begin{verbatim}
path( [[right], [forward], [right], [forward]] )
\end{verbatim}


\subsection{Retinal coordinates and the {\tt retina} predicate}

The rule that generates these sequences is this one:
\begin{verbatim}
goal(plan_path),
retina(X,Y,nearest(+)),
retina_path( [3,2], [X,Y], Path )
=>
path(Path),
erase(goal(plan_path)),
goal(check_path_found).
\end{verbatim}
Its left-hand side contains one STM predicate, and two perceptual
predicates, \verb/retina/ and \verb/retina_path/. The former is related
to \verb/can_see/, but instead of just indicating whether an object is
within view, it also gives its coordinates in the retinal image. These
are expressed relative to the bottom left-hand corner of the retina as
\verb/(1,1)/, as shown in figure~\ref{ps3:retina} below:
\vfigstart
\begin{verbatim}
\begin{alltt}
1,7  _,_  _,_  _,_  5,7
_,_  _,_  _,_  _,_  _,_
_,_  _,_  _,_  _,_  _,_
_,_  _,_  _,_  _,_  _,_
_,_  _,_  _,_  _,_  _,_
_,_  _,_   B   _,_  _,_
1,1  _,_  _,_  _,_  5,1
\end{alltt}
\end{verbatim}
\vfigend{ps3:retina}{A bug's visual field}
In this figure, the bug's position is shown as a \verb/B/, and is
\verb/(3,2)/.

The first two arguments of the \verb/retina/ predicate are an object's X
and Y location. The third argument specifies the object. It can either
by a simple symbol, such as \verb/+/ or \verb/'S'/; or a designator of
the form \verb/nearest(+)/ or \verb/nearest('S')/.

This second case is the one we're interested in. When Prolog tries to
establish the truth of the condition
\begin{verbatim}
retina( X, Y, nearest(+) )
\end{verbatim}
it searches the retinal image for the nearest piece of food. It then
fills in the variables \verb/X/ and \verb/Y/ with its coordinates. These
can then be used again in the same rule.


\subsection{Retinal path-planning}

The second perceptual predicate in the rule is \verb/retina_path/. Now,
before explaining what it does, I have to explain that it isn't really a
perceptual predicate at all. Prolog is a general-purpose
logic-programming language in which one can write predicates about many
different subjects --- including simulated microworlds. What I have
called perceptual predicates up to now are actually perfectly normal
Prolog predicates which refer to particular aspects of the Eden
simulation. They all access the data structures which represent the
bug's perceptions, and are designed to give you information which
enables you to find out what the bug ``experiences''.

Like \verb/retina/, \verb/can_see/ and \verb/over/, \verb/retina_path/
is a normal Prolog predicate. Like them, it accesses the data structures
which represent the bug's perceptions. Unlike them, it does not just
report raw ``perceptions''. Instead, it goes through a fairly complex
searching process which is designed to find a free path. The type of
search used is one known as {\it hill-climbing}. The predicate starts by
making a list of all the ``safe'' (passable) cells next to the bug's
starting point. It then computes the distance from each of these cells
to the food, and takes the cell with the least distance. It then
repeats, finding all the neighbours of this new cell, and calculating
{\it their} distance. And so on. Eventually, it should get to the goal.

Sometimes, it won't be able to find a clear path. In that case, it will
back-up to the last choice it made between neighbours, select the next
nearest cell, and try again. Sometimes, no choice will lead it to the
goal.

The method of choosing, if possible, the neighbour nearest to the food
is not guaranteed to find the shortest path, but it often will. It's an
example of a {\it heuristic}: a computationally cheap rule-of thumb
which delivers a good-enough solution often enough to be worth
tolerating when it doesn't.    

If \verb/retina_path/ can find a path, it will set its third argument to
a list of the moves required to follow it. If it can't, it will set it
to \verb/not_found/.

So one effect of the whole rule,
\begin{verbatim}
goal(plan_path),
retina(X,Y,nearest(+)),
retina_path( [3,2], [X,Y], Path )
=>
path(Path),
erase(goal(plan_path)),
goal(check_path_found).
\end{verbatim}
is to put into STM either the fact \verb/path(not_found)/, or a fact of
the form \verb/path( [ [right], [forward], ... ] )/. The rule also
changes the current goal to \verb/check_path_found/.


\subsection{Checking that a path was found}

This is done by the two rules
\begin{verbatim}
goal(check_path_found),
path(not_found)
=>
erase(goal(check_path_found)),
goal(notice_food).

goal(check_path_found),
not(path(not_found))
=>
erase(goal(check_path_found)),
goal(follow_path).
\end{verbatim}

They just test the argument of \verb/path/ to see whether it is
\verb/not_found/. If it is, the bug goes back to looking for food, on
the assumption that it can't get to the piece it has just seen. This is
probably not very sensible behaviour, since it is likely to get the bug
into a loop, where it repeatedly notices the same piece of food, tries
to plot a path to it, and fails. Check whether this is so by
building a world in which the bug can see, but not get to, some food. If
the argument is not \verb/not_found/, it must be a path, so the bug
changes its goal to \verb/follow_path/.


\subsection{Following a path}

This is handled by the three rules below:
\begin{verbatim}
goal(follow_path),
path( [First|Rest] )
=>
exec( First ),
erase(path(_)),
path(Rest).

goal(follow_path),
path( [] ),
over(+)
=>
erase(goal(follow_path)),
erase( path([]) ),
exec( [grab] ),
exec( [use] ),
goal( notice_food ).

goal(follow_path),
path( [] ),
not( over(+) )
=>
erase(goal(follow_path)),
erase( path([]) ),
goal( notice_food ).
\end{verbatim}

The first rule checks the argument of \verb/path/ to see whether it
still contains some moves, using the special construction
\verb/[First|Rest]/. The condition \verb/path([First|Rest])/ will
succeed only if the path is not empty. If it does, then this will set
\verb/First/ to the first move, and \verb/Rest/ to a list containing the
others. The right-hand side of the rule then obeys the first move, and
resets the path so it contains only the rest.

The second rule's condition succeeds if the path is now empty and the
bug is over food. In this case, we just grab and eat it, and reset the
goal.

The third rule is a safety clause. It could happen that by the time we
get to the end of the path, the food has gone. For example, something
else might have eaten it, the path might have been miscalculated, or a
move might not have had the desired effect. If so, the bug doesn't waste
time trying to eat non-existent food, but goes back to looking for more.


\subsection{Cognitive versus subcognitive competances}

Now print out the rules in \verb/gbug3/. Notice that all but one of
the rules are the same as in \verb/gbug/ There is one that's different:
\begin{verbatim}
goal(follow_path),
path(Path)
=>
exec_list(Path),
erase(path(Path)),
path([]).
\end{verbatim}

This rule has a new motor command on its right-hand side,
\verb/exec_list/. This is like \verb/exec/, except that it obeys a whole
list of actions in one go, thus avoiding the necessity to run the same
rule over and over again, taking the first element from the path,
obeying it, replacing the whole path by its tail, and then repeating.
Try running \verb/gbug3/ in \verb/gworld/, and follow the trace to see
how \verb/exec_list/ is used.

This ought to be quicker, because fewer rules need be fired in order to
follow the path. However, it does have limitations, which you can
demonstrate as follows. Try running it in \verb/gworld3/. This is like
\verb/gworld/, except that it contains a few bombs (\verb/b/). These
will explode and kill you if you pass over them. Now try running
\verb/gbug/ in the same world. This too will get blown up.

Now try altering each bug so that if it sees the bomb ahead of it, it
alters course to avoid it. You may want to discard the rest of the
planned path and plan a new one after changing course; or you may want
to try rejoining the old path. The latter is harder!

Which bug is harder to make avoid bombs? Why? What does this have to do
with the organization of large companies?   


\section{Giving the bug commands}

There is another facility in Eden with which you can give commands to a
bug. To demonstrate this, run \verb/gbug5/ in any world. When Eden first
requests a control command, type \verb/l/ followed by RETURN. It will
then invite you to type a sentence, and will move the cursor to the
start of line three, ready for this. Type \verb/left/ and then hit
RETURN. The sentence is now stored in the bug's ``auditory buffer'', and
can be accessed by the perceptual predicate \verb/heard/.

When you have hit RETURN, Eden will ask you for another control command.
This time, hit \verb/y/ to execute one cycle. Notice that the bug
obeys your command. You can see how it works by looking at the code in
figure~\ref{ps3:gbug5}, below.
\vfigstart
\begin{verbatim}
resolve [p,r].

stm [].

stm_predicates [].


heard( S )
=>
exec( S ).

not(heard(S))
=>
reply([please,type,something]),
exec([wait]).
\end{verbatim}
\vfigend{ps3:gbug5}{{\tt gbug5}}

The predicate \verb/heard/ only succeeds if you have just typed a
sentence, in which case it sets its argument to the sentence as a list
of words. Thus, if you do type something, the first rule will fire, and
will execute the word you type. If this is an action name, then the bug
will obey the corresponding action.

If you don't type something, \verb/heard/ will be false, and the second
rule will fire. It calls another motor predicate, \verb/reply/, which
replies by displaying its argument on the fourth line. It then calls
\verb/exec([wait])/.     

As a final exercise, try modifying one of the \verb/g/-series bugs so
that if it's stuck for an action, and you type something, it will obey
it. This is an exercise where it may be easier {\it not} to introduce
another goal.

\end{document}
