bobgian@psuvax.UUCP (01/01/84)
******** ARTIFICIAL INTELLIGENCE -- First Exam ********
The field of Artificial Intelligence studies the modeling of human
intelligence in the hope of constructing artificial devices that display
similar behavior. This exam is designed to study your ability to model
artificial intelligence in the hope of improving natural devices that
display similar behavior. Please read ALL the questions first, introspect
on how an AI system might solve these problems, then simulate that system.
(Please do all work on separate sheets of paper.)
EASY PROBLEM:
The rules for differentiating polynomials can be expressed as follows:
IF the input is: (A * X ^ 3) + (B * X ^ 2) + (C * X ^ 1) + (D * X ^ 0)
THEN the output is:
(3 * A * X ^ 2) + (2 * B * X ^ 1) + (1 * C * X ^ 0) + (0 * D * X ^ -1)
(where "*" indicates multiplication and "^" indicates exponentiation).
Note that all letters here indicate SYMBOLIC VARIABLES (as in algebra),
not NUMERICAL VALUES (as in FORTRAN).
1. Can you induce from this sample the general rule for polynomial
differentiation? Express that rule in English or Mathematical notation.
(The mathematicians in the group may have some difficulty here.)
2. Can you translate your "informal" specification of the differentiation
rule into a precise statement of an inference rule in a Physical Symbol
System? That is, define a set of objects and relations, a notation for
expressing them (hint: it doesn't hurt for the notation to look somewhat
like a familiar programming language which was invented to do mathematical
notation), and a symbolic transformation rule that encodes the rule of
inference representing differentiation.
3. Can you now IMPLEMENT your Physical Symbol System using some familiar
programming language? That is, write a program which takes as input a
data structure encoding your symbolic representation of a polynomial and
returns a data structure encoding the representation of its derivative.
(Hint as a check on infinite loops: this program can be done in six
or fewer lines of code. Don't be afraid to define a utility function
or two if it helps.)
SLIGHTLY HARDER PROBLEM:
Consider a world consisting of one block (a small wooden cubical block)
standing on the floor in the middle of a room. A fly is perched on the
South wall, looking North at the block. We want to represent the world
as seen by the fly. In the fly's world the only thing that matters is
the position of that block. Let's represent the world by a graph
consisting of a single node and no links to any other nodes. Easy enough.
4. Now consider a more complicated world. There are TWO blocks, placed
apart from each other along an East/West line. From the fly's point of
view, Block A (the western block) is TO-THE-LEFT-OF Block B (the eastern
block), and Block B has a similar relationship (TO-THE-RIGHT-OF) to
Block A. Draw your symbolic representation of the situation as a graph
with nodes for the blocks and labeled links for the two relationships
which hold between the blocks. (Believe it or not, you have just invented
the representation mechanism called a "semantic network".)
5. Now the fly moves to the northern wall, looking south. Draw the new
semantic network which represents the way the blocks look to him from his
new vantage point.
6. What you have diagrammed in the above two steps is a Physical Symbol
System: a symbolic representation of a situation coupled with a process
for making changes in the representation which correspond homomorphically
with changes in the real world represented by the symbol system.
Unfortunately, your symbol system does not yet have a concrete
representation for this changing process. To make things more concrete,
let's transform to another Physical Symbol System which can encode
EXPLICITLY the representation both of the WORLD (as seen by the fly)
and of HOW THE WORLD CHANGES when the fly moves.
Invent a representation for your semantic network using some familiar
programming language. Remember what is being modeled are OBJECTS (the
blocks) and RELATIONS between the objects. Hint: you might like to
use property lists, but please feel no obligations to do so.
7. Now the clincher which demonstrates the power of the idea that a
physical symbol system can represent PROCESSES as well as OBJECTS and
RELATIONS. Write a program which transforms the WORLD-DESCRIPTION for
FLY-ON-SOUTH-WALL to WORLD-DESCRIPTION for FLY-ON-NORTH-WALL. The
program should be a single function (with auxiliaries if you like)
which takes two arguments, the symbol SOUTH for the initial wall and
NORTH for target wall, uses a global symbol whose value is your semantic
network representing the world seen from the south wall, and returns
T if successful and NIL if not. As a side effect, the function should
CHANGE the symbolic structure representing the world so that afterward
it represents the blocks as seen by the fly from the north wall.
You might care to do this in two steps: first describing in English or
diagrams what is going on and then writing code to do it.
8. The world is getting slightly more complex. Now there are four
blocks, A and B as before (spread apart along an East/West line), C
which is ON-TOP-OF B, and D which is just to the north of (ie, in back
of when seen from the south) B. Let's see your semantic network in
both graphical and Lisp forms. The fly is on South wall, looking North.
(Note that we mean "directly left-of" and so on. A is LEFT-OF B but has
NO relation to D.)
9. Generalize the code you wrote for question 4 (if you haven't already)
so that it correctly transforms the world seen by the fly from ANY of
the four walls (NORTH, EAST, SOUTH, and WEST) to that seen from any other
(including the same) wall. What I mean by "generalize" is don't write
code that works only for the two-block or four-block worlds; code it so
it will work for ANY semantic network representing a world consisting of
ANY number of blocks with arbitrary relations between them chosen from
the set {LEFT-OF, RIGHT-OF, IN-FRONT-OF, IN-BACK-OF, ON-TOP-OF, UNDER}.
(Hint: if you are into group theory you might find a way to do this with
only ONE canonical transformation; otherwise just try a few examples
until you catch on.)
10. Up to now we have been assuming the fly is always right-side-up.
Can you do question 6 under the assumption that the fly sometimes perches
on the wall upside-down? Have your function take two extra arguments
(whose values are RIGHT-SIDE-UP or UPSIDE-DOWN) to specify the fly's
vertical orientation on the initial and final walls.
11. Up to now we have been modeling the WORLD AS SEEN BY THE FLY. If
the fly moves, the world changes. Why is this approach no good when
we allow more flies into the room and wish to model the situation from
ANY of their perspectives?
12. What can be done to fix the problem you pointed out above? That is,
redefine the "axioms" of your representation so it works in the "multiple
conscious agent" case. (Hint: new axioms might include new names for
the relations.)
13. In your new representation, the WORLD is a static object, while we
have functions called "projectors" which given the WORLD and a vantage
point (a symbol from the set {NORTH, EAST, SOUTH, WEST} and another from
the set {RIGHT-SIDE-UP, UPSIDE-DOWN}) return a symbolic description (a
"projection") of the world as seen from that vantage point. For the
reasons you gave in answer to question 11, the projectors CANNOT HAVE
SIDE EFFECTS. Write the projector function.
14. Now let's implement a perceptual cognitive model builder, a program
that takes as input a sensory description (a symbolic structure which
represents the world as seen from a particular vantage point) and a
description of the vantage point and returns a "static world descriptor"
which is invariant with respect to vantage point. Code up such a model
builder, using for input a semantic network of the type you used in
questions 6 through 10 and for output a semantic network of the type
used in questions 12 and 13. (Note that this function in nothing more
than the inverse of the projector from question 13.)
******** THAT'S IT !!! THAT'S IT !!! THAT'S IT !!! ********
SOME HELPFUL LISP FUNCTIONS
You may use these plus anything else discussed in class.
Function Argument description Return value Side effect
PUTPROP <symbol> <value> <property-name> ==> <value> adds property
GET <symbol> <property-name> ==> <value>
REMPROP <symbol> <property-name> ==> <value> removes property
***********************************************************************
--
Spoken: Bob Giansiracusa
Bell: 814-865-9507
Bitnet: bobgian@PSUVAX1.BITNET
Arpa: bobgian%psuvax1.bitnet@Berkeley
CSnet: bobgian@penn-state.csnet
UUCP: allegra!psuvax!bobgian
USnail: Dept of Comp Sci, Penn State Univ, University Park, PA 16802