Category : Files from Magazines
Archive   : AIAPR87.ZIP
Filename : EXPERT.APR

"Expert's Toolbox"
April 1987 AI EXPERT magazine


LISTING 1 - GPS in Prolog

/* If the STARTSTATE satisfies the GOAL then no actions need be
taken. This is the base case of GPS's recursion. */

gps(STARTSTATE, GOAL, STARTSTATE, []) :- satisfy(STARTSTATE, GOAL), !.


/* Otherwise, work through the algorithm given in pseudocode in
the body of the article. This is a four place relation, meaning
that starting in the STARTSTATE and trying to achieve the GOAL,
gps prescribes performing the ACTS, which will place you in the
ENDSTATE. */

gps(STARTSTATE, GOAL, ENDSTATE, ACTS) :-
majordiff(STARTSTATE, GOAL, DIFF),
suitableact(DIFF, ACT),
prereqs(ACT, PREREQS),
achieve(STARTSTATE, PREREQS, READYSTATE, PREACTS),
result(READYSTATE, ACT, AFTERSTATE),
gps(AFTERSTATE, GOAL, ENDSTATE, POSTACTS),
append(PREACTS, [ACT | POSTACTS], ACTS).


/* This achieves a list of prerequisites PREREQS starting from a
STARTSTATE, using actions PREACTS and ending in ENDSTATE.
It does so by calling gps on each prerequisite in turn, and
appending the actions together. */

/* Base case: if no prerequisites, then no actions are required. */
achieve(STARTSTATE, [], STARTSTATE, []).

/* Recursive case. Save the acts prescribed by gps in FIRSTACTS,
and the state resulting from the action in MIDSTATE. */
achieve(STARTSTATE, [PREREQ1 | PREREQS], ENDSTATE, ACTS) :-
gps(STARTSTATE, PREREQ1, MIDSTATE, FIRSTACTS),
achieve(MIDSTATE, PREREQS, ENDSTATE, RESTACTS),
append(FIRSTACTS, RESTACTS, ACTS).

/* Well known definition of append. */
append([], L, L).
append([A|X], Y, [A|Z]) :- append(X, Y, Z).


_______________________________
Listing 2 - Domain dependent knowledge for trip planning.

/* The geographic model consists of individual "places", which the
program thinks of as point-like, and "regions", which are areas
containing places. In the axioms below, regions are any of the
place names which have something in them; places are all the place names
which have nothing in them. Thus, metmuseum and sanfrancisco are places,
the village and Boston are regions. Regions are organized hierarchically by
containment. We record that the Village is in New York City, which is in
the northeast, which is in the US.

States are simply places - namely, the place where the "robot" is now.
Goals may be either places or regions, where the robot wishes to end up.
Differences are recorded as two regions containing the starting state and
the goal, at the hightest level, together with a thrid region containing
them both. For example, if the state is Astor Place, and the goal is
Berkeley, then the difference is the triple [northeast, bayarea, usa],
since Astor Place is in the north-east, Berkeley is in the Bay area, and
the next level up in the hierarchy is the US, which doesn't distinguish
between the two. Acts are a list of the form [motiontype, startingplace,
endingplace]; for example, [fly, kennedy, sfairport]. */

/* Basic geography. */
in(courant, village).
in(bottomline, village).
in(astorpl, village).
in(sheridansq, village).
in(pennstn, midtown).
in(metmuseum, uppereast).
in(guggenheim, uppereast).
in(yhma92, uppereast).
in(stn86, uppereast).
in(kennedy, queens).
in(village, nyc).
in(midtown,nyc).
in(uppereast,nyc).
in(queens, nyc).

in(widener, harvard).
in(harvardcoop, harvard).
in(harvardsq, harvard).
in(finearts, fenway).
in(fenwaypk, fenway).
in(harvard, boston).
in(fenway,boston).
in(soutstn, boston).

in(nyc, northeast).
in(boston, northeast).

in(sanfrancisco, bayarea).
in(sfairport, bayarea).
in(berkeley, bayarea).
in(marincounty, bayarea).

in(bayarea,usa).
in(northeast,usa).

/* Definition for satisfy: GOAL is satisfied if GOAL contains the STATE. */
satisfy(STATE, GOAL) :- contains(GOAL, STATE).

/* "contains" is the transitive closure of "in". */
contains(A, A).
contains(A, B) :- in(B,C), contains(A,C).

/* The major difference between START and GOAL is two regions or places
STREG and GOALREG, containing START and GOAL respectively, which are
both in COMMONCONTAINER. */
majordiff(START, GOAL, [STREG, GOALREG, COMMONCONTAINER]) :-
contains(STREG, START),
contains(GOALREG, GOAL),
in(STREG, COMMONCONTAINER),
in(GOALREG, COMMONCONTAINER), !.

/* The kind of act necessary to cross an object CONT depends on the
size of CONT. The act must start and end from recognized terminals
(for instance, a subway ride must start and end at a subway station). */
suitableact([STREG, ENDREG, CONTAINER], [ACT, STPL, ENDPL]) :-
crossact(CONTAINER, ACT),
terminal(ACT, STREG, STPL),
terminal(ACT, ENDREG, ENDPL).

/* How to cross different regions. */
crossact(usa,fly).
crossact(northeast, train).
crossact(bayarea, subway).
crossact(nyc, subway).
crossact(boston,subway).
crossact(village, walk).
crossact(uppereast, walk).
crossact(harvard,walk).
crossact(fenway,walk).

/* Transportation terminals. */
terminal(walk, X, X).
terminal(subway, village, astorpl).
terminal(subway, midtown, pennstn).
terminal(subway, queens, kennedy).
terminal(subway, harvard, harvardsq).
terminal(subway, fenway, finearts).
terminal(subway, southstn, southstn).
terminal(subway, X, X) :- in(X, bayarea).
terminal(train, nyc, pennstn).
terminal(train, boston, southstn).
terminal(fly, northeast, kennedy).
terminal(fly, bayarea, sfairport).

/* Definitions for prereqs and result. */
prereqs([MOVE, A,B], [A]).

result(A, [MOVE, A, B], B).