Robotic Intelligence
6 Feb 2006
lecture in 2 parts:
1 What is AI?
2 AI programming
What is AI?
Logic, plan, philosophy
symbolic vs non-symbolic
Physical Symbol Hypothesis
How to make a machine
think?
logic
predicate logic
Father(prabhas,som)
has truth value: true
Close world assumption, what is not true is false.
Father(x,y)
first order logic, has variables.
variables can have scope. there exist, for all
for
all x Prime(x)
there exists x
Divisible(x,3)
Grandfather(x,y)
is Father(x,z) and Father(z,y)
This is a logic deduction.
To reason about fact, one can use deductive logic from first order and
predicate logic. Higher order logic allows predicate to be
variables. Any higher order logic can be transformed into first
order logic.
Telling a story
(Thai folklore)
In and Na are both fisherman. They are friends. One day, In
and Na go fishing together. They caught a fish. They argue
on dividing that fish. They ask Yu to divide the fish for
them. Yu divides a fish into head, tail, and middle. Yu
took the best part, the middle.
To reason about this story, we transform it into sentences in logic.
Fisherman(In)
Fisherman(Na)
Friend(In, Na)
Caught_fish(In,fish123)
Caught_fish(Na,fish123)
not Divide_fish(In,fish123)
not Divide_fish(Na,fish123)
Divide_fish(Yu,fish123)
Fish_part(fish123,head,middle,tail)
Own(Yu,middle)
We can ask questions about the story, such as, what In and Na
got? (not the middle). We can infer that being friends is
having the same occupation, fisherman.
Friend(x,y) is Fisherman(x) and Fisherman(y).
We can ask who caught the fish?
Caught_fish(x,fish123)
x = In, Na
A computer can perform deduction using a mechanism called
"resolution", invented by Robinson (a mathematician) around
1960. Robinson invented a step-by-step method to arrive at
conclusion from premises which can be implemented in a computer.
The idea is simply:
If you want to prove something is true, let it be P.
Use "not P" to prove by contradiction that "not P" can not
be a logical consequent from premises. Therefore, P is true.
This is a bit counter intuitive but proving by contradiction is a very
powerful prove method used widely in logic. (another extremely
useful prove style is induction proof).
Beside using logic for deduction, we can "synthesis" using logic.
This is called synthesis by proof. Let give an example on
designing a digital device. We begin with an obviously
correct specification of what we want the digital device to be, let say
a digital watch. We write a model of the device. It will be
a few sentences in logic to describe the target device. Our watch
does counting:
Count(t+1) = Count(t) +
1 and this will happen once a second.
Minute(t+1,x) = if Count(t)
> 60 then x = x+1 and reset count
(a few more sentences to take care of details)
Then from these sentences, we "prove" by transforming them using a
"sound logical rules" into another sentences. In some finite
steps, we "rewrite" the original specification into "grounded
sentences". A grounded sentence composes only of the predicate
that is known to be implementable in hardware such as, { and, or, not}
gates. They will become, counter, decoder, multiplexor, etc.
The "correctness" of the final "grounded sentences" is secured by the
fact that each transformation step preserves the correctness (by being
"sound logic rules"). The advantage of this method is that
the final device need not be tested to be correct in terms of
design. However, in terms of fabrication (microelectronics) it is
not "prove" to be correct. But, it is still an enormous saving
cost not having to test all functionality of the device, only
electrical characteristics need to be tested. The impracticality
of this method is that "rewritting" the spec. into "grounded sentences"
is not always automatic. It is combinatoric. (i.e. the
choice exploded so that it is impossible to find good choice)
Therefore, human assistance is required. The current state
of the art technique makes small scale industrial applications
possible,like proving the communication protocol or even a simple
microprocessor. Even a simple microprocessor, it has thousands of
axiom to begin with.
Planning
Planning is to achieve a goal by searching for a group of sentences
that satisfied the goal (make the goal true).
Example from a block world:
goal
On(c,b) and On(b,a) and On(a,table)
building a tower of block c (on top) b and a (on table).
The primitives to manipulate this world can be:
put(x,y)
reads put object x on object y (y can be block or table, x
must be block)
pick(x)
reads the robot hand picks up block x
if initially the world is :
On(a,table)
and On(b,table) and On(c,b)
then a plan to build the tower can be:
pick(c)
put(c,table) ; clear top of b
pick(b) put(b,a)
pick(c) put(c,b)
Planning is to search for such sequence of action to achieve the goal
state. It is quite easy to get a "planner" stuck at some state
which can not apply any primitive to move to other state. It
depends on heuristic how to guide the plan to achieve a goal. One
famous problem is called "instant insanity" where the planner gets
stuck in a loop and cannot make any progress toward the goal.
The above example can illustrate the case. If we use a heuristic
that a planner should try to achieve the goal by counting the "correct"
relation of blocks,
goal
On(c,b) and On(b,a) and On(a,table)
Each of these goals when achieve gives one point.
If the planner chooses action which maximise points, then "clear top of
b" will not be chosen because it reduces the point!
To apply logic to a wide real-world we need "logic of common
sense". John McCarthy is the main figure who attack this
problem. You can read many of his master work from his homepage.
I think logic allone will not take us very far on the road towards
intelligent machines. To enable machines to do more things, we
will need to give them "motivation". Emotion is one
of the most interesting topic in AI. How to give machines
emotion? How we understand emotion in human? Can we
reason about emotion? Marvin Minsky, who is called (together with
McCarthy) "father of AI", is very much interested in such topics.
Most of his work concentrate on understanding emotion, human jokes, how
children think about playing with blocks, how our memory work, etc. He
had written a famous book "Society of mind" explained his theory.
He is in the process of writting a new book on "emotional machines".
You can read all his work from his homepage.
The progress in logic is towards new kind of logic. "non
monotonic logic" "causal logic". Shoham invented "logic of
cause and reason". (read his homepage) These new
logic can be applicable to many "abstract" idea such as "time",
"belief" etc.
Another idea worthy consideration is that the East thinking is
different from the West. For example, in Buddhist teaching
about mind, we do not have "exclusion of the middle" like in western
logic. In western logic, the truth value is either true or
false, it can not be both. For East, we do have
neither good nor bad.
Philosophy
The grandest question in AI is still "Can a machine think?" This
is not a scientific question. It is a pholosiphical
question. Many people believe that if we can define "thinking"
then we can answer the question. I believe that for the
thing like "thinking", it is unlilkely that we will have a "definition"
that everyone will agree upon and hence answering the question is still
an open problem.
Alan Turing deviced an 'test" (now called Turing test). It is a
thought experiment. There are two rooms, in one room a
human, in another room, a human or a computer. The person in the
first room communicates with a person/or a computer in another room via
typing (let make it a modern version, via "chat"). If the human
in the first room after a while chatting with a human/computer in
another room cannot tell whether he/she is conversing with a human or a
machine. Then, if it is the computer in another room which does
all the correspondences, we say the computer is as "intelligent" as a
human (because a human can not tell it apart from a fellow human).
Let us dispense with many minor details (such as whether there is limit
on the topic of conversasion), the thought experiment above caught
imagination of people. People are enthusiastically debate about
this experiment. In some contest around 1990, many
computer programs had passed the Turing test. (they fool
human to think that it is a human who chat to them). Some people
even invented a more rigourous test called Total Turing Test, or TTT
that is much harder for a machine to pass.
Of course, there are strong protaganist of AI. Especially a
strong version of AI. I need to explain: weak AI and strong
AI first. Weak AI denotes the belief that AI can "mimick" human
intelligent (they will fool people) but if looking closely we can
detect. This makes AI useful but not claiming that machines can
really think. Strong AI holds belief that a machine can really
think, machines can do the same task that human define as "thinking".
The most famous protaganist of AI is John Searl. He is a
philosopher. He holds the position that machines cannot
think. He published his most debated work proposing a scenario
called "Chinese room" to argue that machines cannot think. Let
hear his argument:
Chinese Room
There is a room that will accept an input in form of questions written
in Chinese on a piece of paper. The room will process the
question and answer back by writing the answer on a piece of paper in
Chinese. From what people see from outside, this room can
"think", it gives the correct answer every times.
Inside the room, there is an English gentleman, he knows nothing of
Chinese language. What he does is to look up the instruction in
the room which is full of English book of rules how to answer the
question. He follows those instructions rigourously. The
rule tells him how to answer, which Chinese characters to write
etc. So, without knowing the meaning of the text he can answer
the question.
There is no "intelligent" no "understanding" in Chinese room.
Therefore, a machine cannot think.
This is a superb piece of writing. It took on every AI experts,
and I have to say, 26 years has passed, thousands of paper debated
about it and still no conclusion can be found.
(McCarthy has a reply in his collection of writing "Philosophical
Debate of AI").
I think the value of this philosophical "gymnastic" is not in finding
the truth (whatever it is, the truth about "thinking"?). It is
about "searching" for the meaning. As long as people are intrique
about "machines that think" then there will be people who want to think
deeply about it. More people will do AI. Young people will
do AI. The progress will be made in due time.
References
<will update references soon>
Basic AI text book
Classic work of McCarthy, Minsky
Alan Turing, Turing machine, Turing test
Searle's Brain Behaviour, Science original paper
Shoham
End of the first part of lecture
Part 2 AI programming
Prabhas Chongstitvatana