G5AIAI - Introduction to Artificial Intelligence

This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)


History of AI

This page gives a brief history of AI. In addition, you should take a look at the reading list for this part of the course.


Although this part of the course is titled History of AI, it is only possible to cover some of the main milestones within AI. However, you should also read the reading list texts as these give a fuller picture (for example, they discuss the reasons for the rise and declines of neural network research - something we will not discuss until we reach that part of the course).
The approach I have adopted is to consider key moments (in my opinion) which have shaped our perception of Artificial Intelligence (AI). We also consider a couple of the philosophical debates within the AI arena.

Before you read on though, take a look at this powerpoint presentation, (see notes on powerpoint presentations within this course - this is the big one) which gives us some insight as to why we need AI techniques, especially when we are looking through large search spaces.

 

What is Artificial Intelligence?

Before we start though we need to define what we understand is meant by AI, or more importantly, we need a working definition for this course.

We could debate what AI is over the course of one or more lectures but at the end of the debate we would probably not have a definition that we would all agree upon. Therefore I will work towards a definition that we will use for this course. Of course, you can disagree with that definition but we need something on which to build.

In AIMA (Russell, 1995), four definitions are given, which are taken from recent AI textbooks (see! - even textbooks cannot agree). These definitions are re-produced here.

Systems that think like humans
Systems that think rationally
Systems that act like humans
Systems that act rationally

We can make the following observations about these definitions

In the past, all four approaches have been followed and, as you might expect, there exists tension between the top and the bottom definitions. As we shall see in a moment some of the AI arguments put forward have been trying to persuade others to accept the top or bottom half as the correct way to view AI.

The Turing Test (which we look at later) was designed to provide a satisfactory operational definition of intelligence. If you believe that a computer that can pass the Turing Test is intelligent then you believe that the definition bottom left is correct.

You may believe that for a computer to exhibit intelligence, then it must think like a human (top left). But how do humans think?
There are two possible ways we could find this out. The first is to get "inside the mind" and capture thought processes as they go by. At present this is not possible to do but who knows for the future.
A second approach is to conduct psychological experiments.
If we use this definition of AI as our working model then we are straying into cognitive science. Not a bad thing to do but for the purposes of this course we are going to avoid that.

If you believe that a computer can think rationally then you are looking at the top right definition. This approach is driven by the laws of logic. For example, given two statements (say "Socrates is a man" and "All men are mortal") we can imply further knowledge ("Socrates is mortal").
Using logic, we should be able to build systems that allow us take a description of a problem (in logical notation) and find the answer to that problem.
There are two main problems with this approach.
First, it is difficult to take a problem that is presented informally and transform it into the formal terms required by logical notation. This is particularly true when the knowledge you are representing in less than one hundred percent certain.
Secondly, solving even small problems (those with only a few initial facts) can be computationally expensive. So much so that it may become impractical to solve the problem.

Acting rationally (bottom right) means acting so as to achieve one's goals, given one's beliefs.
Acting rationally, could be considered as acting logically but, as we discussed above, this has limitations. Sometimes, it is also not wise to simply act logically. In these instances something needs to be done and almost anything is better than doing nothing. Consider if you put your hand on an electric ring (one that is glowing red hot). Logically, you might decide the best thing to do is remove the source of the heat. And this will eventually remove the burning sensation, but at what cost.
In this instance you need a reflex action (i.e. move your hand as quickly as possible) - an action that does not require complicated thought processes - do something - almost anything.

During this course we will be taking the "acting rationally" approach. We will not be a slave to it. If you want to develop this theme further then the AIMA book is based around this definition and the development of agents that act rationally. We will simply be using this definition so that we can ignore the cognitive side of AI (except in this introductory lecture) and also so that we do not have to assume that AI is only acting logically.

If you want some other definitions to whet the AI juices then consider these.

"Artificial Intelligence is the part of computer science concerned with designing computer systems, that is, systems that exhibit the characteristics we associate with intelligence in human behavior - understanding, language, learning, reasoning, solving problems and so on…"
(Barr and Feigenbaum, Handbook of AI)

"Artificial Intelligence is the study of how to make computers do things at which, at the moment, people are better"
(Rich)

"AI is the study of mental faculties through the use of computational models"
(Charniak and McDermott)

"AI may be defined as the branch of computer science that is concerned with the automation of intelligent behavior"
(Luger and Stubblefield)

History of AI

Introduction

In this section we pick out a few key aspects of AI history and some of the techniques that the pioneers used. This will give us some appreciation of the way this branch of computer science has evolved and also introduce us to some of the leading figures in the field as the subject evolved.

Physical Symbol System Hypothesis

Newell and Simon (1976) attempted to define intelligence in such a way that it could be replicated on a computer. Much of the work done in AI is based upon their definition. They define a physical system as

A physical system consists of a set of entities, called symbols, which are physical patterns that can occur as components of another type of entity called an expression (or symbol structure). Thus, a symbol structure is composed of a number of instances (or tokens) of symbols related in some physical way (such as one token being next to another). At any instant of time the system will contain a collection of these symbol structures.
Besides these structures, the system also contains a collection of processes that operate on expressions to produce other expressions; processes of creation, modification, reproduction and destruction.
A physical symbol system is a machine that produces through time an evolving collection of symbol structures. Such a system exists in a world of objects wider than just these symbolic expressions themselves.

Newell and Simon then state

The Physical Symbol System Hypothesis (PSSS). A physical system has the necessary and sufficient means for general intelligent action.

The PSSS is only an hypothesis. There does not seem to be any way to prove or disprove it using logic. Therefore, we are faced with using empirical evidence and computers allow us to do this relatively easily.

ELIZA

There is a separate page for ELIZA

MYCIN

MYCIN (Shortliffe, 1976) is an AI program that diagnoses infectious diseases. It is considered as one of the first expert systems as it was attempting to replicate the doctors knowledge in a computer program.
MYCIN uses backwards reasoning (see below) to work backwards from the patients illness to the possible cause.
To do this it uses rules of the form

"If the organism has a certain characteristic as determined by the lab results, then it is likely that the organism is x."

But, as you can see from the above statement, MYCIN uses the idea of assigning probabilities to its diagnoses. This is called a certainty factor and it is an indication as to how much confidence we have in the conclusion of the rule given the evidence that was presented. There are other complications in that certainty factors have to be combined to give an overall certainty factor
A typical MYCIN rule looks like this

If: (1) the stain of the organism is gram-positive, and
(2) the morphology of the organism is coccus, and
(3) the growth conformation of the organism is clumps,
then
there is suggestive evidence (0.7) that the identity of the organism is staphyloccus

These rules are obviously in an English like syntax. The MYCIN program was written in LISP and the above rule would be coded as follows

PREMISE: ($AND (SAME CNTXT GRAM GRAMPOS)
(SAME CNTXT MORPH COCCUS)
(SAME CNTXT CONFORM CLUMPS))
ACTION: (CONCLUDE CNTXT IDENT STAPHYLOCOCCUS TALLY 0.7)

With an expert system such as MYCIN it is difficult to measure its performance exactly due to the inherent complexity of the problems and the "fuzziness" that exists in the decision making process.
Probably the best measure is to test the system against human experts using real-world problems.
In 1982 MYCIN took part, with human medical experts in ten selected meningitis cases. In scored higher than all the humans (Buchanan, 1982).

The development of MYCIN is important for several reasons

XCON/R1

XCON/R1 is one of the most cited expert systems. It was developed by DEC (Digital Equipment Corporation) and was a system that ensured the customer was supplied with all the components and software that was needed to make up the specified computer system that they had ordered.
This is not as easy as it sounds. Building a bespoke computer system means that every system is different and, as such, needs different components and software. For example, if a customer orders a disc drive then DEC has to ensure that the customer also receives the disc controller and the relevant cables.
As a single system can be built from thousands of separate components, it was not easy for a human to ensure that the customer had everything he/she needed to build the system.
XCON/R1 was an expert system that did this job automatically. It saved DEC millions of dollars a year and raised the profile of expert system to a level that had not been seen before.

Forward and Backward Chaining

Forward and backward chaining is important with regards to AI. The two techniques are described here as you will often come across then in the AI literature. Although we will not explicitly use the terms in this course they are still being used in the techniques we implement.

Assume you are trying to get from Nottingham University to Kendal in the Lake District. You have two ways of approaching this problem. You can start at Kendal (in the planning sense) and work your way back to Nottingham. This is known as backward chaining as you are moving backwards from the goal position to the initial position. It is also sometimes called a goal driven search.
Of course, in a problem such as this, you would normally forward chain (move from the initial state to the goal state) as it is more logical for you to do it that way. This is sometimes known as a data driven search.

Which search method you use depends on the problem.
You use backward chaining when


You use forward chaining when

In the lecture we looked at a problem of trying to find out if you were a direct descendant of Isaac Newton. We decided that backward chaining was better for this problem given the (unrealistic) assumption that everybody has three children.

Strong and Weak Problem Solving

Like forward and backward chaining we will not explicitly refer to strong and weak problem solving in this course. But we will be using these techniques and as the terms are used in the AI literature it as well to describe what they are.

Weak problem solving is a technique where we just search for an answer to a problem without having any knowledge of the problem.
Think again about the problem we described above where we need to get from Nottingham University to Kendal. We'll assume the start and end points of our journey are the railway stations. We could provide the program with a list of towns that have train stations along with a list of towns that it is possible to travel to and from using the train.

A weak problem solving method would simply start at Nottingham (assuming forward chaining) and explore the search space until one of the towns it reached was Kendal. In doing this we might have gone via Portsmouth but as the search has no knowledge of what it is trying to do this is perfectly acceptable.

A strong problem solving technique would have some domain knowledge. For example, it might explore stations North of Nottingham first as the knowledge we give the problem is that Kendal is North of Nottingham.
Or we might tell it that the straight line distance between the two towns is 180 miles and any route must not exceed that by a certain percentage.

The benefit of strong problem solving methods is that they are often quicker and can lead to better solutions. The downside is, is that they are problem specific. If we change our destination to London then we need to change the problem as London is South of Nottingham, not North.

General Problem Solver (GPS)

GPS (Newell and Simon, 1963) was the first AI program to exploit an idea called Means-End Analysis (see [rich91, chapter 3.6, pages 94-97] and [caw98, chapter 4.3.2, pages 87-90]).

The idea behind Means-End Analysis is that it is often appropriate to use forward and backward chaining within the context of the same problem. Using such an approach we could solve separate parts of the problem and, eventually, bring all the parts together into one solution.

The main idea behind means-end analysis is that it identifies differences between the initial state and the goal state and then tries to find an operator that will move from the initial state to the goal state. If an operator cannot be found then the problem is reduced to sub-problems and these sub-problems are solved using the same idea.
You can appreciate that means-end analysis can be applied recursively.

Like many other AI techniques, GPS (and means-end analysis) uses a set of rules but it also uses a difference table.
Consider the following problem. We have a room with a table in it. The table has two objects on top of it. We want to move the table and the objects to another room. Before we can move the table we need to move the two objects. We'll assume that a robot will do the work for us.

The operators available to the robot might be as follows.

 

Operator
Preconditions
Result
PUSH(obj,loc) At(robot,obj) ANDLarge(obj) AND Clear(obj) AND ArmEmpty At(obj,loc) AND At(robot,loc)
CARRY(obj,loc) At(robot,obj) AND Small(obj) At(obj,loc) AND At(robot,loc)
WALK(loc) None At(robot,loc)
PICKUP(obj) At(robot,obj) Holding(obj)
PUTDOWN(obj) Holding(obj) NOT Holding(obj)
PLACE(obj1,obj2) At(robot,obj2) AND Holding(obj2) On(obj1,obj2)

 

The difference table might be defined as follows

Push
Carry
Walk
Pickup
Putdown
Place
Move Object
X
X
Move Robot
X
Clear Object
X
Get Object on Object
X
Get Arm Empty
X
X
Be Holding Object
X

 

Given the operators and the difference table we can now start (or the robot can) to solve the problem.

The main difference between the initial state and the goal state is the location of the desk. To reduce this difference we must move the desk and, looking at the difference table, we can see that we can either PUSH or CARRY the desk.

Assume we choose to carry the desk. We need to check that the pre-conditions of the operator are satisfied. There are two of these. One specifies that the robot is at the desk. The other specifies that the desk is small. We can take steps (pun intended) to ensure that the robot is at the desk but we cannot make the desk "small" (we are assuming it is classified as large) as there is no operator that allows us to reduce the size of the desk.

Therefore, we are forced to look at the PUSH operator.

So, our main goal is to PUSH the desk. But to do this we need to ensure we satisfy the pre-conditions of the PUSH operator.

You can see that the initial problem has already led to a number of sub-problems and these in turn lead to other sub-problems. But as we resolve each problem we are reducing the overall difference for each problem, until we get ourselves in a position where we can solve the larger problem.

The basic means-end analysis algorithm presented here does have its limitations; for example

 

Philosophical Issues

The Turing Test and The Chinese Room are both covered in separate pages.

References

 


 Last Updated : 11 Sep 2001