% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
%     Extracts from the book "Natural Language Processing in Prolog"    %
%                      published by Addison Wesley                      %
%        Copyright (c) 1989, Gerald Gazdar & Christopher Mellish.       %
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %

Pragmatics

We can use Prolog inference directly for simple prediction.  We define
a predicate ''say'' that can be given a set of assertions that might be
derived from an English sentence.

    say(X) :- X, !.
    say(X) :- asserta(X).

It will add them to its world model if they are not already predicted.
Assertions may contain variables, corresponding to pronouns that need
to be resolved, in which case ''say'' uses Prolog''s backwards inference
to try and infer substitutions for the pronouns.  Here is a tiny set
of example inference rules, based on the Morton Underwell exercise:

    church(church_of(Town)) :- town(Town).
    see(people,Object) :- famous(Object), object(Object).
    object(Spire) :- spire(Spire).
    object(Spire) :- spire(Church).
    spire(spire_of(Church)) :- church(Church).

The predicate ''say'' can be used by a person simulating the output of a
natural language front end, providing lists of assertions in the order
they might be generated from a text:

    ?- say(town(morton_underwell)).
    yes
    ?- say(spire(It)).
    It = spire_of(church_of(morton_underwell)) ?
    yes
    ?- say(famous(spire_of(church_of(morton_underwell)))).
    yes
    ?- say(see(people,It)).
    It = spire_of(church_of(morton_underwell)) ?
    yes

In this example, the prediction program is able to predict the
existence of the spire on the church in Morton Underwell, and is able
to predict that it is this, rather than the church or the town, that
people probably come to see.

We can easily represent a script in Prolog, with a predicate ''script''
whose first argument is a term giving the name of the script with
variables for the key players, and whose second argument is a list of
terms, each of which represents an event occurring in sequence.  In
addition, we can directly associate conditions on the type of entity
that can substitute for the variables in the script.  When humans go
to a restaurant, they (normally) pay for the food eaten, and are thus
customers.  When cats visit restaurants, they do not pay, and are thus
not customers.

Here are a couple of scripts represented this way:

    script(restaurant(Customer,Restaurant,Food),
        [
        enters(Customer,Restaurant),
        calls(Customer,Server),
        brings(Server,Food),
        eats(Customer,Food),
        pays(Customer,Teller),
        leaves(Customer,Restaurant)
        ]) :-
        human(Customer),
        human(Server),
        human(Teller),
        restaurant(Restaurant),
        food(Food).

    script(cat_burglary(Cat,Location,Food),
        [
        enters(Cat,Location),
        picks_up(Cat,Food),
        leaves(Cat,Location),
        eats(Cat,Food),
        sleeps(Cat)
        ]) :-
        cat(Cat),
        food(Food).

And here is some of the relevant "typing" information that our scripts
need to make use of:

    cat(a_cat).
    cat(garfield).
    food(some_food).
    food(lasagne).
    human(a_person).
    human(kim).
    restaurant(a_restaurant).
    restaurant(pizzahut).

The code we need to use these scripts to "understand" stories is
pretty trivial -- find a script, then match the story against the
events in the script:

    understand(Story,Summary,Events) :-
        script(Summary,Events),
        match(Story,Events).

Here ''match'' imply attempts to unify each event in the story with some
event in the script, subject to the constraint that the order of
events in the story is consistent with that in the script:

    match([],Events).
    match([Event1|Events1],[Event1|Events2]) :-
        match(Events1,Events2).
    match([Event1|Events1],[Event2|Events2]) :-
        match([Event1|Events1],Events2).

That essentially completes our program (in scripts.pl) which
implements a simple script applier in Prolog.  It differs from actual
script appliers, in that it expects to be given the set of
propositions from a whole text, rather than having to work out
plausible scripts at the end of each sentence.  Moreover, it
incorporates no special mechanism for script cueing -- each script is
assumed to be potentially applicable.

Here are a couple of examples of the program in use:

    1.  The story:
          enters(kim, pizzahut)
          eats(She, lasagne)
       Summary:
          restaurant(kim, pizzahut, lasagne)
       Chronology:
          enters(kim, pizzahut)
          calls(kim, a_person)
          brings(a_person, lasagne)
          eats(kim, lasagne)
          pays(kim, a_person)
          leaves(kim, pizzahut)

    2.  The story:
          enters(garfield, pizzahut)
          eats(He, lasagne)
       Summary:
          cat_burglary(garfield, pizzahut, lasagne)
       Chronology:
          enters(garfield, pizzahut)
          picks_up(garfield, lasagne)
          leaves(garfield, pizzahut)
          eats(garfield, lasagne)
          sleeps(garfield)

In these examples, the program is given lists of propositions that
might arise from texts like the following:

    1. Kim went to Pizza Hut.  She had a lasagne.
    2. Garfield snuck into Pizza Hut.  He ate the lasagne.

In the latter case, because Garfield is a cat, and not a person, the
program has decided that a "cat_burglary" script is applicable to the
sequence of actions.  In doing so, it has obtained the referent of the
pronoun, and although the text only mentions two actions, the script
indicates that in fact five actions took place, including Garfield
picking up the lasagne, leaving the restaurant, and sleeping.

Language generation as a goal-oriented process

PLAN_GEN.PL implements a simple planner that can develop plans such as
these two examples.  Operators are represented in Prolog with 4
arguments, the first being the name of the operator bundled up as a
term with its arguments, the second is a list of CAN_DO preconditions,
the third a list of WANT preconditions, and the fourth a list of
effects.  The use of lists for the last three arguments allows us to
express multiple preconditions and effects.  Here is our REQUEST
operator in this notation:

    operator(request(Speaker,Addressee,Action),
       [Addressee can_do Action,channel(Speaker,Addressee)],
       [Speaker wants request(Speaker,Addressee,Action)],
       [Addressee believes Speaker wants Action]).

Note that we have defined ''believes'', ''wants'' and ''can_do'' as infix
operators.  We represent the initial state of the world for the
planner with a predicate ''initial'' which provides a list of facts
describing the world in question.  So that we can have clauses for
several examples in the database, we provide ''initial'' with a first
(numeric) argument to identify the example.

    initial(1,[
       channel(sue,alan),
       at(alan,inside),
       at(sue,inside)
       ]).

Goals as expressed by the ''goal'' predicate have three arguments: the
number of the example, the name of the agent whose goal it is, and the
goal itself:

    goal(1,sue,at(alan,outside)).

Although the planner plays the part of a particular agent in building
the plan and therefore reasons within the beliefs of that agent, for
convenience we will express the world model in an impartial way, with
all belief contexts explicitly spelled out.  Moreover, in presenting
goals to the planner, we will omit the "AGENT believes" that should
precede each one.  Of course, if the goals involve predicates about
which there is universal knowledge, then there is no distinction
anyway.

Depth-first search, which is Prolog''s default search strategy, is
actually a bad search strategy for planning, because there are usually
infinitely many ways of achieving a given goal and arbitrarily long
plans to investigate.  For instance, if Sue wants Alan to move out of
the room, she could simply make a request, or go out of the room and
make the request, or go out of the room, come back into the room and
make the request, and so on.  Depth-first search is unlikely to find
the best plan, which is probably the shortest plan, and it is liable
to get into infinite loops trying to generate longer and longer plans.
Because of this problem, the PLAN_GEN.PL program uses a modified
depth-first strategy.  It uses ''listlen'' to generating uninstantiated
lists of actions of increasing length.  The first attempt tries an
empty list of actions, then a one action list, then a two action list,
and so on, until a plan of the given length is found.  Although this
approach (known as iterative deepening) involves a lot of duplicated
work, it does ensure that the program finds a shortest plan and does
not get into infinite loops.

    planner(Id) :-
          listlen(Actions,_),
          initial(Id,World),
          goal(Id,Agent,Goal),
          plan(Agent,Goal,World,Actions,[],Done).

Here is a trace of a successful search for a plan applicable to the
goal and initial world of example 1, as given in the examples above:

    ?- planner(1).

    [trying, plan, length, 0]
     [trying, plan, length, 1]
     [trying, operator, move(alan, _1, outside)]
      [trying, plan, length, 2]
      [trying, operator, move(alan, _2, outside)]
      [trying, operator, cause_to_want(_3, alan, move(alan, inside, outside))]
      [trying, operator, move(alan, _4, _2)]
       [trying, plan, length, 3]
       [trying, operator, move(alan, _5, outside)]
       [trying, operator, cause_to_want(_6, alan, move(alan, inside, outside))]
       [trying, operator, request(_6, alan, move(alan, inside, outside))]

    ** plan is:

       [request(sue, alan, move(alan, inside, outside)),
        cause_to_want(sue, alan, move(alan, inside, outside)),
        move(alan, inside, outside)]

The plan returned is a list representing the sequence of actions that
should be performed (in the order given) to achieve the goal.  The
predicate ''plan'' takes the following arguments:

    (i) AGENT - the agent who is doing the planning,
    (ii) GOAL - the current goal,
    (iii) WORLD - the world in which the goal is to be pursued (i.e.
    the list of facts that are true in that world),
    (iv) ACTIONS1, ACTIONS2 - a difference list encoding the plan
    necessary to achieve the goal,
    (v) DONE - a flag to signal termination.

The first main possibility for it to investigate is whether the GOAL
is already true.  Since we are planning from the point of view of a
particular AGENT, we actually need to test whether the AGENT believes
that it is true, unless the goal involves a predicate that is
universally known.  Predicate ''db_goal'' produces a new version of
GOAL, DBG, which has an "AGENT believes" prefix if the goal does not
involve a predicate about which there is universal knowledge:

    plan(Agent,Goal,World,Actions,Actions,Done) :-
       db_goal(Agent,Goal,DBG),
       member(DBG,World).

The other main possibility is to find an operator that could achieve
the goal by one of its effects.  For such an operator, the program
tries planning to achieve the preconditions (CAN_DOs and WANTs),
calling the predicate ''allplan'' to produce the various subplans:

    plan(Agent,Goal,World,[Action|Actions0],Actions2,Done) :-
       operator(Action,Can_do,Want,Effects),
       member(Goal,Effects),
       write([trying,operator,Action]), nl,
       allplan(Agent,Can_do,World,Actions0,Actions1,Done),
       allplan(Agent,Want,World,Actions1,Actions2,Done).

The predicate ''allplan'' basically works like ''plan'', except that is
expects a list of goals, rather than a single goal.  It attempts to
achieve them in sequence:

    allplan(Agent,[],World,Actions,Actions,Done).
    allplan(Agent,[Goal|Goals],World,Actions0,Actions2,Done) :-
       plan(Agent,Goal,World,Actions0,Actions1,Done),
       allplan(Agent,Goals,World,Actions1,Actions2,Done).

Although we have now convered the main parts of the program, the
program also deals with various special cases.  For instance, in order
to achieve "can_do(X,Y)", it looks up the CAN_DO preconditions for
action "Y" and tries to achieve these.  The planner also knows
explicitly about the predicates about which there is universal
knowledge.

The program implemented in PLAN_GEN.PL is a restricted planner in the
following respect.  It chains backwards from the desired goal to an
action that will achieve that goal; then it looks for an unsatisfied
precondition of that action and finds an action that will make that
precondition true; then it looks for an unsatisfied precondition of
that action; and so on, until an action is reached, all of whose
preconditions are initially true.  It then stops (the stopping is
implemented by instantiating the "Done" variable that is passed to all
the ''plan'' and ''allplan'' goals; ''allplan'' actually checks whether this
variable is instantiated and, if so, stops doing any further
planning).  At this point, the list of actions it has chained through
gives a rough idea of a sequence of actions to be performed, but there
is no guarantee that any but the first of these can actually be
performed.  It is quite possible, for instance, that a remaining
unsatisfied precondition of one of the actions cannot be made true in
any way.  Or that for some reason one of the effects of carrying out
one of the actions is to make one of the other actions impossible.
The key feature of a planning system that this program lacks is the
ability to reason properly about the changes in the world that result
from performing an action and how these interact with the
preconditions and effects of other planned actions.