Part 2 of the lecture Robotic
Intelligence
AI programming
Difference between AI
programming and conventional
Guy Steels who wrote the specification of Java language (together with
James Gosling, Sun company), said that programming language "shape" the
way a programmer think.
Reasoning in AI is logic based. To arrive to a conclusion, an
inference procedure considers all given axioms and rules. One can
also consider "algorithm" in AI as "search". As the search space
in most AI problems are extremely large, to achieve a practical
solution, AI search uses "heuristics".
AI programming mimics human logical reasoning. It is mostly
symbolic. For example,
Man(x)
-> Mortal(x).
Man(socrates).
---------------------
Mortal(socrates).
The final conclusion is logical consequence of the rule and the axiom
given above.
Another main difference between AI programming and other programming
task is that AI task treats "program as data". That is program
and data are interchangeable. Most programming task in AI is to
generate another "program" to perform the task. To achieve this,
it uses a universal data structure, the most well-known is
"list". For example: a list of three objects (A (B C)) is
->
[* | ] --> [ * | / ]
| |
A [ * | ]
--> [ * | / ]
| |
B C
where [ | ] denotes a data structure of "cell"
containing two pointers, * is the first pointer, the second
pointer can be a pointer to the next cell, / denotes a "nil", it
signifies the end of a list. A, B, C are represented
internally as objects (sometimes called "atom").
A program itself can be represented using this same universal data
structure. For example: (ADD 1 2)
->
[ * | ] --> [ * | ] --> [ * | / ]
|
| |
ADD
1 2
When consider a list as a program, to "execute the program", an
evaluator function can be applied to the list. The "eval"
traverses the list, interpreting the first object as an operator and
the rest as arguments. A list can be constructed using
"constructor" operator "cons", for example (cons 'a 'b) --> (a b), (cons 'a
nil) --> (a).
So, this is a program:
(eval
(cons 'ADD (cons '1 (cons '2 nil ))))
which will return 3, given that "eval" is the appropriate "interpreter"
operator. Even the interpreter itself can be represented in this
form. (You can read the LISP interpreter written in LISP itself
in McCarthy, LISP 1.5 primer).
A recursive struture can be represented naturally. For example, a
definition of a factorial function:
(define
fac (n)
(if (= n 0 ) 1
(* n (fac (- n
1))))
Now, we know that "program" can be represented as "data". The
next question is "what data represent"?
Data is central to AI programming. To perform reasoning, we can
use "rules" such as, in a medical expert system,
(this is overly simplified medical knowledge to diagnose anemia)
to conclude that the patient is anemia,
we look for the symptom of
1) yellowish skin
2) has mild fever
3) dark-stool
then we perform complete blood count
if the blood count is low then we can give the diagnosis that the
patient is anemia.
We can write this "knowledge" into this form:
(rule1
(and yellowish-skin (and has-mild-fever dark-stool))
(do complete-blood-count
(diagnosis (if
(lower CBC 300) anemia)))
The above knowledge can be regarded as a "program" if we consider that
we can "eval" the following template:
(rule
(... cause ...) (do ...test...) (diagnosis (condition
answer)))
The above template is "data" that has been transformed into "program"
by having an appropriate "evaluator" for it. The "eval" can be
regarded as "meta program".
So, AI programming is about thinking how to represent "data" in the
most natural way for the problem and then write "eval" function to
interpret the data. This way of programming is most distinguished
character of AI programming.
A programming system
for robotic
The above discussion regards "reasoning" at a high level. It
assumes somehow the information in the world is transformed into an
appropriate 'symbol" (but read "symbol grounding problem" for the
argument against this philosophy).
A robot program might be simply:
forever
loop
sense, think, act
The above program assumes there is "a model of the world" such as the
reasoning system can choose (think) an appropriate action to perform to
achieve the intended goal. Or graphically it can be represented:
[ === think =====]
|
|
| sensing | action
|
|
------------------------------ grounded, real world
That the "thinking" part is an abstract that is supported by two
pillars: sensing, to access a world and build its model, action, to
change the state of the world.
However, the above idea did not work well with a real robot. The
first problem is with the world model. It is difficult or almost
impossible to have an accurate world model for a task.
Uncertainty is unavoidable. The second is with the
reasoning. For a logic based inference procedure, it is
impossible to perform a reasoning as "the whole" (holistic
way). For example, we can give a simple and valid reasoning that
"if an object is at A, and it is moved to B, the object will be at
B". This is appropriate to reason about an individual
object. When there is an earthquake, it is likely that all
objects in a room are moved. There is no way to reason about that
except we reason about each and every objects in that room on a
one-by-one basis (read "frame problem" by Minsky and
"circumscription" by McCarthy to explore this topic). The third
and final problem is with time. The robot must work in real-time,
therefore the "thinking" process must terminate or comes to a
conclusion in a bounded time to be useful. For example, if a
robot is sitting on the top of a timed bomb, it should not spent too
much time thinking about what to do in every details, it is better to
make some conclusion before the bomb goes off.
One of the main school of thought to attack the above problem comes
from Rodney Brooks (now the director of MIT AI lab). I will call
this paradigm "insect intelligence" (read the classic MIT AI memo
no. 899 which is never published anywhere).
Brooks proposed that instead of monolithic intelligence program, one
should break it into many autonomous agents that sense, make decision
by themselves and communicate with others. He proposed a
concrete architecture, a "subsumption architecture" where intelligence
of a robot is divided into several layers, each layer composed of many
autonomous agents performing their task but the higher level layer can
"subsume" the lower layer.
His work is in the project COG (a coginitive robot) where a
humanoid robot, only the upper half, having a robot head with
complete stereo vision and two "impedance controlled" arm, can learn to
perform some task by itself. The task includes play a drum, saw a
log, interact with a human to grab a soft doll etc.
Conclusion
AI programming has a distintively different way of thinking about
program. It treats "program as data" and mostly the program is a
"meta program" (that generate programs to perform a task). In AI
programming, data is central. One develop program around
"data". The "reasoning" part is a high level concept. In a
real robot there is always a "low level" program that performs the task
such as controlling an arm to move etc. The right "interface"
between these levels is an important issue and subject to future
research.
References
Guy Steels, DDJ Jan 2006, interview
Peter Norvig, AI programming, textbook
McCarthy, LISP 1.5 primer
Minsky, Frame problem
McCarthy, circumscription (comm. of ACM)
< text book by Brooks, ... robotic, MIT press>
End of lecture
Prabhas Chongstitvatana
20 Februay 2006