Introduction to Artificial Intelligence

1 Historical Perspective of Machine Intelligence

The nature of intelligence and its automation are controversial subjects. The sometimes conflicting points of view have led to heated debates in diverse circles of: computer scientists, mathematicians, neurobiologists, philosophers, educators, and engineers. I prefer to think of computers as tools of human invention, not all that different in kind from other human artifacts. Human cultural evolution is marked by the ingenious methods we have developed to extend the limitations of our biology. Automobiles and airplanes act as extensions of our legs. Telescopes and radar extend the limitations of our eyes. Ultrasound and acoustic emission sensors extend our hearing beyond the audible range. Our cultural and social organizations allow human civilization to attempt massive projects on a planetary level. We have also developed tools to extend our ability to process information. Oral traditions and the written word allowed us to transfer our knowledge to future generations. Many civilizations independently developed simple devices for computation. The Chinese developed the abacus. The Incas used knotted ropes for numerical computation. The Indians gave us the so-called Arabic numerals, a welcome improvement over Roman numerics for computation. The Renaissance mathematicians expanded the realms of geometry, algebra, and number theory, along with the need for faster and more accurate long calculations. The Renaissance was an age of machinery: intricate clockwork, pumps, and gadgetry. The European upper classes were amused by mechanical novelties, such as windup toothpick dispensers and singing birds. Philosophers in trying to explain the natural world, often used these technologies to explain human thought and questioned whether machines could be made to think. Prior to the twentieth century, several inventors and mathematicians made attempts to transform these ideas into a working calculating machine.

One of the first known inventors to take up the challenge was Wilhelm Schickard, a seventeenth century German professor of mathematics and astronomy and friend of Johannes Kepler. He appears to have succeeded in building a mechanical calculator that could add, subtract, multiply, and divide large numbers. Before Schickard was able to send Kepler his calculating machine, a fire broke out in 1624 where the calculator was being assembled and the device was destroyed. Eventually a working copy was reconstructed from Schickard's notes. By that time Schickard was dead of one of the plagues that scourged Europe during the Thirty Years' War. Further development of his calculator appears to have died with him.

Blaise Pascal, the French mathematician and philosopher, independently designed and built an adding machine that he called the arithmétique. It consisted of a brass box about the size of a loaf of bread, with eight dials on its face that represented decimal places. Although built later in time, Pascal's machine was less sophisticated than Schickard's and could only add and subtract. More importantly, it was so expensive that no one wanted to buy it. Pascal was not of the opinion that human intelligence could be entirely automated and questioned the limits to mechanical analytical reasoning as illustrated in his famous quote:

The heart has its reason that reason does not know.

Pascal is also credited for developing probability theory - a subject to be covered in another chapter.

Three decades later, Gottfried Wilhelm Leibnitz, best known as the inventor of calculus, extended Pascal's calculator to include multiplication and division. He hated the tedium of calculation and grumbled: It is unworthy of excellent men to lose hours like slaves in the labor of calculation that could be safely relegated to anyone else if machines were used [Ritchie:57]. Unfortunately, the economics of Europe had not changed since Pascal's time and the Leibnitz wheel was considered only a toy of the very rich. His key insight was not credited during his lifetime: that given a formal language of thought (specifically, calculus) one could construct a thinking machine to replicate this process. Leibnitz died in 1716, neglected by his countrymen and overshadowed by Newton. The only person to show up for Leibnitz funeral was his private secretary. But Leibnitz insight inspired other philosophers and inventors to construct thinking machines.

Perhaps the most successful mechanical contribution to the history of computers came from the unlikely industry of textile manufacturing. Weaving requires arranging thousands of tiny threads in a precise pattern by means of a repetitive sequence of operations. Joseph Jacquard had the idea of building a weaving machine that could work more efficiently, tirelessly and accurately than human workers. The basis of his idea was the use of a program, a set of instructions for weaving patterned cloth. The program was executed via punched cards that were strung together to form an endless belt that passed over the hooks that did the actual weaving. The holes in the cards determined which warp threads were hooked and pulled downward so that when the shuttle of the loom passed across, the proper threads were crossed over other threads, thus creating the desired woven pattern. Jacquard's loom was introduced in 1805 and was immediately successful as a weaving machine and also formed the basis for the punched card programs, called Hollerith cards after their inventor Herman Hollerith, used in early computers of the twentieth century.

In the following decades, Londoner Charles Babbage became obsessed with the immense potential of computing machines. He conceived the Analytical Engine, a machine that consisted of thousands of intricate geared interlocking cylinders. The "engine" was to be steam powered with two major components: (1) a "mill" to carry out arithmetical operations and (2) a "store" to record the variables and answers to the calculations. He planned to use the Jacquard punch-card system to supply the instructions to both components. The Analytical Engine was remarkably similar to the architecture of today's computers with programs instead of punched cards, processing units as the "mill" and memory units for the "store". Babbage's brilliant friend, Lady Ada Lovelace (daughter of Lord Byron) poetically commented that

Although Lady Lovelace is often credited with the idea of using machines for non-numeric symbolic manipulations such as music composition, she also the first to predict the limitations of artificial intelligence:

Unfortunately, precision machining and steam power were not advanced enough to allow the realization of Babbages's dream. The invention of electronic computers in the following century provided the technology for machine intelligence to become a possibility.

2 Computer Intelligence

There are many definitions of artificial intelligence (AI) in the literature. One somewhat circular definition often given is that artificial intelligence is the study of intelligent behavior. The term artificial intelligence as a discipline was coined by John McCarthy in naming the first conference on the subject at Dartmouth College in 1956 [Charniak & McDermott: 1985, p.10,11] . McCarthy proposed:

McCarthy was reported to have been deeply disappointed in the conference (Grevier [1993: 49]). He had hoped for consensus as to what this new emerging field was and where it was going. None of this happened and most of the researchers left and followed their own directions. One lasting outcome of this workshop was the acceptance of McCarthys's preferred expression for this new area of study – artificial intelligence.

Marvin Minsky's [1968: v] definition is: artificial intelligence is the science of making machines do things that would require intelligence if done by men. Elaine Rich [1983] defines artificial intelligence as the study of how to make computers do things at which, at the moment, people do better. Although these may appear to be ephemeral definitions, the slow progress of computers to outperform people makes them less problematical than they might appear at first glance.

Margaret Broden [1977: 4-5] takes a more humanistic view. She relates:

From an engineering perspective, I prefer to think of artificial intelligence as providing the tools for expanding the role of computers; from numerical processors to more general symbol processors. Although numbers are limited kinds of symbols, so are concepts, ideas, names, etc. that are part of human thought and intelligence. Simon's [1981] physical symbol hypothesis states that (1) human thoughts correspond to language, (2) language can be captured in symbols, and (3) by manipulating symbols on a computer, one can simulate human thought processes [Parsaye & Chignell: 6].

3 AI Research Areas

The following list gives examples of problems that fall within the scope of artificial intelligence:

• Game playing
• Theorem proving
• General problem solving
• Perception
• Vision
• Speech
• Signal interpretation
• Pattern recognition
• Robotics
• Natural language understanding
• Expert systems
• Machine learning
• Planning
• Design

4 AI Techniques

As pointed out by AI critics (e.g., [Dreyfus : 1979] and [Dreyfus&Dreyfus:1986]), the predictions of early AI researches are far from coming true. One of the few hard results to come out of the first 20 years of AI research is that intelligence requires knowledge. Knowledge is difficult to encode because it is (1) voluminous, (2) difficult to characterize or quantify, and (3) constantly changing.

An AI technique is a method that exploits knowledge in such a way that:

• It captures generalizations. In other words, it is not necessary to represent separately each individual situation.
• It can be understood by people who must provide it.
• It can be modified to correct errors and to reflect changes in the world and in our world view.

In the 20 years of research limited implementations of the first requirement were forthcoming. In order to implement the research into something practical, the idea of limiting the generality to specific application domains led to what is presently called expert systems.

5 Problem Solving and Problem Characteristics

The first step in solving a problem is understand it and identify its characteristics. A few problem characteristics are listed below. We will discuss problem characteristics in more detail as we get into specific applications.

1. Is the task one of classification (C) and derivation or of synthesis (S)?
2. Decomposable - Can it be broken into smaller parts?
3. Reversibility - Can solution steps be ignored or undone?
4. Deterministic (D) or Uncertain (U) Response to Control?
5. Lack of precision in definition of states - are the states fuzzy (F)?
6. Combinatorial complexity?

How would you classify the following problems?:

• Theorem proving (2,3, & D)
• Chess (D,6)
• Chemical Synthesis (S,2, U)
• Nondestructive Testing (C,3, U,F)
• Controlling a robot arm (2, U?)
• Process Planning (1,D, 6)
• Diagnosis (C, 2, U, F?)
• Design (S, 2?, U?, F?, 6?) - Creative or routine?

A state space representation provides a framework for modeling and communicating problems and their solution. A representation in a state space is a model of the world, which can vary from the simple to the complex. In fact, the complexity of a problem is often defined by how we represent it. Operators or rules are legal moves that describe the possible transitions between states. The initial state is defined from specification from which the solution process begins and the goal state defines the specifications for a successful solution. The initial state is the root node of the tree. At any state an operator can be applied and the given node is expanded. This node becomes a parent node and the successors it generates upon application of the operator are called children or successor nodes. Thus root nodes are the only nodes with no parents (usually there is only one initial state or root node). A node that has no successors or children is called a leaf node.

Most complex problems allow for a range of operators and the number of successor states generated from the initial state can be quite large. The process for looking for a sequence of moves is called a search. A discussion of AI search strategies will be discussed later in this chapter But first consider a standard AI test problem, the 8-Square Puzzle problem.

Suppose we represent each square and what number is in it as a state. There are 9! combinations (about 400,000). This would be a data intensive approach. Although the 8-square problem is solvable using this representation, the larger 15-square version is not. Elaine Rich [1983: 7-11] gives various algorithms and representation schemes for solving this problem. However, before looking them up, first try the following exercises.

1. What control strategies might you apply?
2. Random moves?
3. How would a different representation simplify the problem?

A rule is a declarative piece of knowledge that is often of the following form:

IF <circumstances>

THEN <do action, or conclude something>

We will go into more detail concerning both representation issues and rules of inference for rule-based systems in later chapters. We will, however, introduce the special case of a production system in order to discuss some important concepts associated with search techniques in AI systems.

A production system consists of:

The production system inference engine searches for production rules whose left-hand sides match patterns in working memory. One rule is chosen for action and the working memory is changed accordingly. In the following sections, the classic water jug problem will be used as a working example of a production system and various search strategies will be introduced in order to solve the problem.

Given a particular state, what rule should be applied to perform the next step? There are many ways humans and thus computers solve problems. What are some rules of thumb concerning requirements for a good control strategy?

1. It should recognize the goal state.
2. It should cause some motion.
3. It should be systematic (For example, in the 8-square problem, we could make random moves. We would eventually reach the solution, but we would probably perform many more steps than should be necessary.)

It is this last requirement that motivates the use of a problem-solving metric of performance. One is usually interested in minimizing the number or costs of steps required in finding a solution – this is referred to as the path cost. But it takes time to perform a search and thus the notion of the search cost is also introduced to define the time and memory required to find a solution. The total cost of the search is the sum of the path cost and the search cost. In many cases it may not be "optimal" to find the solution with the lowest path cost if it will take substantial resources to find it. A suboptimal, but "good" solution might be preferred if its search cost is substantially lower. Explicit recognition of this trade-off is called intelligent real time problem solving, where the cost of the solution processing in time and other resources is explicitly balanced against the benefit. (See Bradley & Agogino [1994] for application of this concept to the design process in which they coin the expression intelligent real time design).

Russell & Norvig [1995: 73] list the following criteria: for identifying the right search or control strategy for a particular problem:

You are given two jugs, a 4-gallon one and a 3-gallon one. Neither has any measuring markers on it. There is a pump that can be used to fill the jugs with water. How can you get exactly 2 gallons of water into the 4-gallon jug?

State Space Representation: The states are represented by (S x y), where x represent the number of gallons of water in the 4-gallon jug (x=0,1,2,3, or 4) and y represents the number of gallons of water in the 3-gallon jug (y=0,1,2 or 3). The starting state is (S 0 0) and the goal state is (S 2 n) for any allowable value of y=n because the problem does not specify how many gallons need to be in the 3-gallon jug.

Production Rules: The production rules for the Water Jug Problem in prefix notation are used to initiate an action for changing the states of the water jug: filling the jugs, emptying the jugs, and pouring water from one jug to the other. The prefix expression (IF A B) means that B can be activated if A is satisfied. The "AND" operator is a logical operator requiring that all arguments must be satisfied for the AND expression to be satisfied.

A Few Assumptions:

1. You can fill the jug from the pump.

2. We can pour water out of the jug onto the ground.

3. We can pour water from one jug to another.

4. We only allow positive quantities of water in the gallon.

5. more?

A control or search strategy specifies the order in which the rules will be compared to the database and a way of resolving the conflicts that arise when several rules match at once. Here are some attributes that a control strategy should have:

Uninformed search strategies (Russell & Norvig [1995: 73]) are those in which no information about the number of steps or the path cost from the current state to the goal state is known. This is sometimes also called blind search or weak search.

Consider the following strategy that meets the rules discussed:

Construct a tree with the initial state as its root. Generate all the offspring of the root by applying each of the applicable rules to the initial state. This represents one level of what is called a breadth-first search.

Tree Representation: The next step of a breadth-first search is to generate all possible branches to each leaf of the tree and so on. All the nodes at depth d in the search tree are expanded before the nodes at depth d +1. The diagram below shows the second level (d=2) of a breadth-first search. Continue this process until some rule produces the goal state.

A breadth-first search procedure is guaranteed to find a solution if one exists, provided that there are a finite number of branches of the tree. In addition, it can be shown that if the solution exists, a breadth-first search is guaranteed to find the shortest path to the goal, assuming that there is an equal cost to transversing each arc in the tree.

On the other hand, breadth-first search will be inefficient compared to depth-first search (next section) if there are many paths that lead to a solution, but each of them is relatively long. In addition breadth-first search can require a tremendous amount of memory. The number of nodes at each level of the tree increases exponentially with the level number and must be all be stored.

Russell & Norvig [1995: 75] give an example in which the branching factor is 10 and the assuming a cost of 1000 nodes/second and 100 bytes per node. In this case it would take thirty-five years to reach a solution if the depth is twelve. But the memory requirements are an even bigger problem for breadth-first than the execution time. Very few systems have the luxury of storing the ten gigabytes needed for this search at the eighth level.

Suppose on the other hand, we pursue a single branch of the tree until we can go no further or until some pre-specified depth has been reached before we pursue another branch. This is called a depth-first search . Consider an algorithm that starts at the beginning of the database and activates the first possible rule, starts at the beginning again and activates the first possible rule that leads to a new state. Such an algorithm would lead to the solution given in the figure on the following page. The sequence of rules activated is: [1,2,3,7,2,5,3,7].

Can you think of a more efficient solution in terms of minimizing the number of rules activated? How did you find this solution?

Depth-first search algorithms are often easy to implement and have very modest memory requirements. They need only store the single path from the root to a leaf node, along with the remaining unexpanded sibling node for each node on the path. For a state space with a branching factor b and maximum depth m, depth-first search requires storage of only bm nodes. Compare this to the exponential storage required for the breadth-first search. Thus from the example given in the breadth-first from Russell & Norvig [1995: 77] for the case where d=12 the depth-first search would require 12 kilobytes instead of 111 terabytes, a factor of 10 billion times less in space. However, one risks the danger of spending a lot of time exploring long but unfruitful paths before a successful one is discovered. Some problems have very long or infinite search trees. Thus, in general, depth-first search is neither complete or optimal.

On variant of depth-first search is depth-limited search in which a cut-off is imposed on the maximum depth a path is allowed to take. As with depth-first search any solution found is not guaranteed to be optimal. Furthermore, if the depth limit is too small, it is possible that the search will not even be complete, i.e., a solution may not be found even if one exits.

Generate-and-test is a depth-first procedure that has been proposed in various forms for solving complex problems. Simmons and Dixon [1983] describe a variant called Design-Redesign for use in mechanical design problems. A simplistic version of generate-and-test is given below.

If the generation of possible solutions is done systematically, then this procedure will find a solution eventually, if one exists. Unfortunately, if the problem space is very large, this may take a very long time.

This search procedure is sometimes called the British Museum Algorithm, a reference to the fact that if a sufficient number of chimpanzees were placed in front of typewriters and left alone long enough, they would generate all the books the museum contained.

Although it is impossible, in general, to prevent reaching the same state twice, search algorithms can be modified to stop the search once a repeated state has been reached. This can be performed in a number of ways such as (1) not allowing paths that cause cycles or (2) not expanding states that have already been reached.

A variation of generate-and-test is one called constraint satisfaction. The difference here is that one might not know the exact form of the goal state, except that certain constraints must be satisfied.

Informed search strategies (Russell & Norvig [1995: 73]) are those in which some information about the number of steps or the path cost from the current state to the goal state is known. One form of informed search is heuristic search. These strategies require some kind of evaluation function that returns information concerning the desirability of following a certain path.

Hill climbing is a variant of generate-and-test in which feedback from the test procedure is used to help the generator decide which direction to move in the search space. In a pure generate and test procedure, the test function responds with only a yes or no. But if the test function is augmented with a heuristic evaluation function that provides an estimate of how close a given state is to a goal state, the generate procedure can exploit it as shown in the procedure below.

1. Generate the first proposed solution in the same way as any generate-and-test procedure. See if it is a solution. If so , quit. Else continue.
2. From this solution, apply some number of applicable rules to generate a new set of proposed solutions.
3. From each element of the set do the following:

a). Send it to the test function. If it is a solution, quit.

b). If not, see if it is the closest to a solution of any of the elements tested so far. If it is, remember it. If it is not forget it.

4. Take the best element found above and use it as the next proposed solution. This step corresponds to a move through the problem space in the direction that appears to be leading the most quickly toward a goal.
5. Go back to step 2.

This is analogous to hill-climbing in numerical optimization. As with numerical optimization, there are important events that could happen.

local maxima is a local peak but not as high as the highest mountain top.

plateau is a flat area of the search space, in which a whole set of neighboring states have the same value. On a plateau, it is not possible to determine the best direction in which to move by making a local comparison.

A ridge is an area of the search space that is higher than surrounding areas, but that cannot be traversed by single moves in any one direction.

How to avoid a nonoptimal stationary point?

Problems: Hill-Climbing is a local technique. You might find the right hill and never know that you have climbed the wrong mountain. It is not very useful if it is a problem with many hills (or in the words of optimization, if it has lots of local minima)

See Dym & Levitt [1991: 53-56].

The A* algorithm minimizes the estimate of the total path cost, which is defined in two parts:

f(n) = g(n) + h(n)

where g(n) is the cost of the path to node n and h(n) is the estimated cost to the goal from node n. With the A* algorithm the strategy is to first expand nodes with the lowest value of f. If one can show that h(n) never overestimates the cost to reach the goal, then it can be shown that the A* algorithm is both complete and optimal. For more detail see Russell & Norvig [1995: 96-101] and Rich [1983: 78-84].

We have been starting with the initial state and tried to activate rules in order to achieve our goal node. This is an example of forward reasoning. With forward reasoning, we want to design a computer program that will match the left side of the rules with the root node (or initial state) and use the right hand side to create a new "root" state.

We could have started with the goal and worked backwards, keeping track of the sequence of rules that leads to the initial state. That would be an example of backward reasoning. For backward reasoning, we want to design a computer program that will match the right hand side of each rule with the goal and find new "goal" states. Continue the process until the initial state is generated.

The decision to use backward or forward reasoning depends on the topology of the problem. Elaine Rich [1983:58] lists three factors:

• How do you do? Please tell me your problem.

• Your AI lecture tomorrow?

• You seem to be quite positive

• Is it because you are not positive that you came to me?

• You say you just said that.

• Let's discuss further why your AI lecture tomorrow.

• Don't you really know whether you should tell them the truth about I?

• You don't seem quite certain.

• How long have you been afraid I or you might make a mistake?

• I am not sure I understand you fully.

• Why are you concerned over my right?

• Why do you ask?

• Does that question interest you?

• Do you believe it is normal to be getting bored with I?