Until about the early 1970s, most ai research dealt with what seymour Papert called “toy” problems – programs that solved puzzles or games – or the researchers pursued projects that were staged in highly controlled laboratory settings. (Of course, there were some notable exceptions – machine translation, DENDRAL, and LUNAR, for example.) However, soon after, AI efforts began a definite shift toward applications work, confronting problems of real-world importance. Inevitably, successful applications work encouraged specialization into sub-disciplines such as natural language processing, expert systems, and computer vision.

One reason for the increasing interest in applications was that the power of AI methods had increased to the point where realistic applications seemed within reach. But perhaps more importantly, the sponsors of AI research in the U.S. Department of Defense (DoD) had to deal with the constraints imposed on them by the 1969 “Mansfield Amendment,” which required that basic research be relevant to military needs. As one example of the increased emphasis on applications, the Information Sciences Institute (USC-ISI) was formed in 1972 specifically to pursue them. Located in Marina Del Rey, California, it is affiliated with the University of Southern California and received much of its initial support from DARPA. Other large corporations also began to explore AI's commercial potential.

The Setting

Up until about the mid-1970s, DARPA managers were able to cushion the impact of the Mansfield Amendment (which required that Defense Department research be relevant to military needs) by describing computer research programs in a way that emphasized applications. Larry Roberts, the Director of DARPA's IPTO during the late 1960s and early 1970s, wrote

Cordell Green, working under Roberts at IPTO, wrote

Generally speaking, anything that came along in the AI field that we thought looked good was Supported…

Artificial intelligence (AI) may lack an agreed-upon definition, but someone writing about its history must have some kind of definition in mind. For me, artificial intelligence is that activity devoted to making machines intelligent, and intelligence is that quality that enables an entity to function appropriately and with foresight in its environment. According to that definition, lots of things – humans, animals, and some machines – are intelligent. Machines, such as “smart cameras,” and many animals are at the primitive end of the extended continuum along which entities with various degrees of intelligence are arrayed. At the other end are humans, who are able to reason, achieve goals, understand and generate language, perceive and respond to sensory inputs, prove mathematical theorems, play challenging games, synthesize and summarize information, create art and music, and even write histories. Because “functioning appropriately and with foresight” requires so many different capabilities, depending on the environment, we actually have several continua of intelligences with no particularly sharp discontinuities in any of them. For these reasons, I take a rather generous view of what constitutes AI. That means that my history of the subject will, at times, include some control engineering, some electrical engineering, some statistics, some linguistics, some logic, and some computer science.

There have been other histories of AI, but time marches on, as has AI, so a new history needs to be written. I have participated in the quest for artificial intelligence for fifty years – all of my professional life and nearly all of the life of the field.

Most of the attendees of the dartmouth summer project were interested in mimicking the higher levels of human thought. Their work benefitted from a certain amount of introspection about how humans solve problems. Yet, many of our mental abilities are beyond our power of introspection. We don't know how we recognize speech sounds, read cursive script, distinguish a cup from a plate, or identify faces. We just do these things automatically without thinking about them. Lacking clues from introspection, early researchers interested in automating some of our perceptual abilities based their work instead on intuitive ideas about how to proceed, on networks of simple models of neurons, and on statistical techniques. Later, workers gained additional insights from neurophysiological studies of animal vision.

In this chapter, I'll describe work during the 1950s and 1960s on what is called “pattern recognition.” This phrase refers to the process of analyzing an input image, a segment of speech, an electronic signal, or any other sample of data and classifying it into one of several categories. For character recognition, for example, the categories would correspond to the several dozen or so alphanumeric characters.

Most of the pattern-recognition work in this period dealt with two-dimensional material, such as printed pages or photographs. It was already possible to scan images to convert them into arrays of numbers (later called “pixels”), which could then be processed by computer programs such as those of Dinneen and Selfridge.

In today's world, the magic of ai is everywhere – maybe it's not “full ai” but there are significant parts. Allen Newell foresaw these bits and pieces as part of an “enchanted land.” In an address given in 1976, he called computers the “technology of enchantment.” He noted two ingredients that made it so:

Let's see some examples of how AI is already inhabiting the “nooks and crannies of our world.” I'll start with our houses and some of the things in and around them.

Ai technology has matured markedly in the past couple of decades and now includes an impressive array of powerful computational tools. These can be deployed with great effectiveness because of the increasing power of relatively inexpensive computers, the availability of large databases, and the growth of the World Wide Web. Today's AI programs are capable of approximating many human cognitive abilities, automating some of them completely, and even bettering what humans can do in others. Because AI is now capable of contributing to the solution of many real-world problems, many graduates who have specialized in AI studies go to work for companies and start-ups instead of pursuing academic AI research. Google and Microsoft, just to name two examples, have hired many of these graduates.

Just as other branches of engineering gradually develop a number of subspecialties, so has AI. For example, the July 2009 International Joint Conference on Artificial Intelligence (IJCAI) had papers in the following “theme” areas: Agent-based and Multi-agent Systems; Constraint, Satisfiability, and Search; Knowledge Representation, Reasoning, and Logic; Machine Learning; Multidisciplinary Topics and Applications; Natural-Language Processing; Planning and Scheduling; Robotics and Vision; Uncertainty in AI; and Web and Knowledge-based Information Systems. (Note that many of the theme areas combine two or more broad topics, and the topics themselves are further articulated in the call for papers.) Of course, many of these subspecialties draw on each other so the field as a whole stays connected.

The quest for artificial intelligence (ai) begins with dreams – as all quests do. People have long imagined machines with human abilities – automata that move and devices that reason. Human-like machines are described in many stories and are pictured in sculptures, paintings, and drawings.

You may be familiar with many of these, but let me mention a few. The Iliad of Homer talks about self-propelled chairs called “tripods” and golden “attendants” constructed by Hephaistos, the lame blacksmith god, to help him get around. And, in the ancient Greek myth as retold by Ovid in his Metamorphoses, Pygmalian sculpts an ivory statue of a beautiful maiden, Galatea, which Venus brings to life:

The ancient Greek philosopher Aristotle (384–322 BCE) dreamed of automation also, but apparently he thought it an impossible fantasy – thus making slavery necessary if people were to enjoy leisure. In his The Politics, he wrote.

Beginning aroud 1970 computer vision research grew into a highly developed subspecialty of AI, joining other specialized areas such as natural language processing, robotics, knowledge representation, and reasoning (to name just a few of them). In this chapter, I'll describe some of the important advances in computer vision during this period. Some of these were made in pursuit of specific applications in several fields such as aerial reconnaissance, cartography, robotics, medicine, document analysis, and surveillance.

Beyond Line-Finding

In an earlier chapter, I described some filtering techniques for enhancing image quality and for extracting edges and lines in images. But much more can be done to extract properties of a scene using specific information about the conditions under which images are obtained and general information about the properties of objects likely to be in the scene.

Shape from Shading

In what has been called a “back-to-basics” movement, researchers began investigating how information about the physics and geometry of light reflection from surfaces could be used to reveal three-dimensional properties of a scene from a single two-dimensional image. A leader in this study was Berthold K. P. Horn (1943-; Fig. 20.1). His MIT Ph.D. dissertation derived mathematical methods for determining the shape of an object from its shading.

Speech Processing

The NLP systems I have already described required that their English input be in text format. Yet, there are several instances in which speaking to a computer would be preferable to typing at one. People can generally speak faster than they can type (about three words per second versus about one word per second), and they can speak while they are moving about. Also, speaking does not tie up hands or eyes.

In discussing the problem of computer processing of speech, it is important to make some distinctions. One involves the difference between recognizing an isolated spoken word versus processing a continuous stream of speech. Most AI research has concentrated on the second and harder of these problems. Another distinction is between speech recognition and speech understanding.

By speech recognition is meant the process of converting an acoustic stream of speech input, as gathered by a microphone and associated electronic equipment, into a text representation of its component words. This process is difficult because many acoustic streams sound similar but are composed of quite different words. (Consider, for example, the spoken versions of “There are many ways to recognize speech,” and “There are many ways to wreck a nice beach.”) Speech understanding, in contrast, requires that what is spoken be understood. An utterance can be said to be understood if it elicits an appropriate action or response, and this might even be possible without recognizing all of its words.

Automated data-gathering techniques, together with inexpensive mass memory storage apparatus, have allowed the acquisition and retention of prodigious amounts of data. Point-of-sale customer purchases, temperature and pressure readings (along with other weather data), news feeds, financial transactions of all sorts, Web pages, and Web interaction records are just a few of numerous examples. But the great volume of raw data calls for efficient “data-mining” techniques for classifying, quantifying, and extracting useful information. Machine learning methods are playing an increasingly important role in data analysis because they can deal with massive amounts of data. In fact, the more data the better.

Most machine learning methods construct hypotheses from data. So (to use a classic example), if a large set of data contains several instances of swans being white and no instances of swans being of other colors, then a machine learning algorithm might make the inference that “all swans are white.” Such an inference is “inductive” rather than “deductive.” Deductive inferences follow necessarily and logically from their premisses, whereas inductive ones are hypotheses, which are always subject to falsification by additional data. (There may still be an undiscovered island of black swans.) Still, inductive inferences, based on large amounts of data, are extremely useful. Indeed, science itself is based on inductive inferences.

Sighted humans get much of their information through vision. that part of AI called “computer vision” (or, sometimes, “machine vision”) deals with giving computers this ability. Most computer vision work is based on processing two-dimensional images gathered from a three-dimensional world – images gathered by one or more television cameras, for example. Because the images are two-dimensional projections of a three-dimensional scene, the imaging process loses information. That is, different three-dimensional scenes might produce the same two-dimensional image. Thus, the problem of reconstructing the scene faithfully from an image is impossible in principle.

Yet, people and other animals manage very well in a three-dimensional world. They seem to be able to interpret the two-dimensional images formed on their retinas in a way that gives them reasonably accurate and useful information about their environments.

Stereo vision, using two eyes, helps provide depth information. Computer vision too can use “stereopsis” by employing two or more differently located cameras looking at the same scene. (The same effect can be achieved by having one camera move to different positions.) When two cameras are used, for example, the images formed by them are slightly displaced with respect to each other, and this displacement can be used to calculate distances to various parts of the scene. The computation involves comparing the relative locations in the images that correspond to the objects in the scene for which depth measurements are desired. This “correspondence problem” has been solved in various ways, one of which is to seek high correlations between small areas in one image with small areas in the other.

Beyond pattern recognition of individual alphanumeric characters, whether they be of fixed font or handwritten, lies the problem of understanding strings of characters that form words, sentences, or larger assemblages of text in a “natural” language, such as English. To distinguish languages such as English from the languages used by computers, the former are usually called “natural languages.” In artificial intelligence, “understanding” natural language input usually means either converting it to some kind of memory model (such as the one used by Raphael in his SIR system or the semantic network used by Quillian) or the evocation of some action appropriate to the input.

Natural languages are spoken as well as written. And, because speech sounds are not as well segmented as are the characters printed on a page, speech understanding presents additional difficulties, which I'll describe in a later chapter.

The inverse of understanding natural language input is generating natural language output – both written and spoken. Translating from one language to another involves both understanding and generation. So does carrying on a conversation. All of these problems – understanding, generation, translation, and conversing – fall under the general heading of “natural language processing” (sometimes abbreviated as NLP).

Linguistic Levels

Linguists and others who study language recognize several levels at which language can be analyzed. These levels can be arranged in a sort of hierarchy, starting with those dealing with the most basic components of language (sounds and word parts) and proceeding upward to levels dealing with sequences of sentences. If speech is being dealt with, there are the levels of phonetics (language sounds) and phonology (organization of sounds into words).

Evem though the mansfield amendment and the lighthill report caused difficulties for basic AI research during the 1970s, the promise of important applications sustained overall funding levels from both government and industry. Excitement, especially about expert systems, reached a peak during the mid-1980s.

I think of the decade of roughly 1975–1985 as “boomtimes” for AI. Even though the boom was followed by a period of retrenchment, its accomplishments were many and important. It saw the founding in 1980 of the American Association for Artificial Intelligence (AAAI – now called the Association for the Advancement of Artificial Intelligence), with annual conferences, workshops, and symposia. (Figure 21.1 shows a scene from one of the many trade shows during this era.) Several other national and regional AI organizations were also formed. The Arpanet, which had its beginnings at a few research sites in the late 1960s, gradually evolved into the Internet, linking computers worldwide.

Various versions of the LISP programming language coalesced into INTERLISP, which continued as the predominant language for both AI research and applications (although PROLOG was a popular competitor in Europe, Canada, and Japan). Researchers and students at MIT designed work-station-style computers, called Lisp machines, that ran LISP programs efficiently. Lisp Machines, Inc., and Symbolics were two companies that built and sold these machines. They enjoyed initial success but gradually lost out to other providers of workstations.

Many other AI companies joined the expert systems companies and the Lisp machine companies. For example, in 1978 Earl Sacerdoti andCharles Rosen founded Machine Intelligence Company to market robot vision systems.

I have already mentioned attempts to program computers to play borad games, such as chess and checkers. The most successful of these was Arthur Samuel's checker-playing program. In 1967, Samuel published a paper describing an improved version of his program. He had refined the program's search procedure and incorporated better “book-learning” capabilities, and instead of calculating the estimated value of a position by adding up weighted feature values, he used hierarchically organized tables. According to Richard Sutton, “This version learned to play much better than the 1959 program, though still not at a master level.”

Between 1959 and 1962, a group of MIT students, advised by John McCarthy, developed a chess-playing program. It was based on earlier programs for the IBM 704 written by McCarthy. One of the group members, Alan Kotok (1941–2006) described the program in his MIT bachelor's thesis. The program was written in a combination of FORTRAN and machine (assembly) code and ran on the IBM 7090 computer at MIT. It used the alpha–beta procedure (as discussed earlier) to avoid generating branches of the search tree that could be eliminated without altering the final result. Kotok claimed that his program did not complete any games but “played four long game fragments in which it played chess comparable to an amateur with about 100 games experience…. Most of the machine's moves are neither brilliant nor stupid. It must be admitted that it occasionally blunders.” When McCarthy moved to Stanford, he took the program along with him and continued to work on it.

Solving Constraint Satisfaction Problems

In addition to reasoning methods based on logic or semantic networks, several other techniques have been explored. In this section, I'll describe a class of problems called constraint satisfaction problems (or assignment problems) and methods for solving them. In these problems, we have a set of objects that must be assigned values that satisfy a set of constraints. We have already seen one example of an assignment problem – that of assigning labels to lines in an image. In that problem, the constraint is that each line in the image can be assigned one and only one label.

Constraints can be expressed in the form of database relations, logical formulas, equations, or inequalities. Thus, constraint satisfaction problems arise naturally in many settings including scheduling, simulation, computer vision, and robotics. (A spreadsheet is a simple constraint satisfaction system, for example.) Fortunately, there are some general-purpose solution methods for these problems that are independent of the application. I'll illustrate one such method with a small example.

Consider the problem of placing four queens on a 4 × 4 chessboard in such a way that no queen can capture any other. In the Four-Queens problem, we have four objects, c1, c2, c3, and c4, representing the columns 1 through 4, respectively, in which a queen might be placed. Each of these objects can have one of four values, 1, 2, 3, or 4, corresponding to the row numbers. So, for example, when c3 has value 2, a queen is placed in the second row of the third column.

The Fifth-Generation Computer Systems Project

In 1982, Japan's Ministry of International Trade and Industry (MITI) launched a joint government and industry project to developwhat they called “Fifth Generation Computer Systems” (FGCS). Its goal was to produce computers that could perform AI-style inferences from large data and knowledge bases and communicate with humans using natural language. As one of the reports about the project put it, “These systems are expected to have advanced capabilities of judgement based on inference and knowledge-base functions, and capabilities of flexible interaction through an intelligent interface function.”

The phrase “Fifth Generation” was meant to emphasize dramatic progress beyond previous “generations” of computer technology. The first generation, developed during and after World War II, used vacuum tubes. Around 1959, transistors replaced vacuum tubes – giving rise to the second generation – although the transistors, like the vacuum tubes before them, were still connected to each other and to other circuit components using copperwires. During the 1960s, transistors and other components were fabricated on single silicon wafer “chips,” and the several chips comprising a computer were connected together by wires. Computers using this so-called smallscale integration (SSI) technology comprised the third generation. In the late 1970s, entire microprocessors could be put on a single chip using “very large-scale integration” (VLSI) technology – the fourth generation. The Japanese fifth generation, besides its sophisticated software, was to involve many parallel processors using “ultra large-scale integration” (ULSI).

MITI planned to develop a prototype machine, in the form of what computer scientists were beginning to call a “workstation,” which was to consist of several processors running in parallel and accessing multiple data and knowledge bases.

After ed feigenbaum moved from uc berkeley to stanford in 1965, he became interested in “creating models of the thinking processes of scientists, especially the processes of empirical induction by which hypotheses and theories were inferred from data.” As he put it, “What I needed was a specific task environment in which to study these issues concretely.” Feigenbaum recalls attending a Behavioral Sciences workshop at Stanford and hearing a talk by Joshua Lederberg (1925–2008; Fig. 15.1), a Nobel Prize–winning geneticist and founder of the Stanford Department of Genetics. Lederberg talked about the problem of discerning the structure of a chemical compound from knowledge of its atomic constituents and from its mass spectrogram. This sounded like the kind of problem Feigenbaum was looking for, and he and Lederberg soon agreed to collaborate on it.

Chemical molecules are described by formulas that give their atomic constituents. For example, the formula for propane is C3H8, indicating that it consists of three carbon atoms and eight hydrogen atoms. But there is more to know about a compound than what atoms it is made of. The atoms composing a molecule are arranged in a geometric structure, and chemists want to know what that structure is. The three carbon atoms in propane, for example, are attached together in a chain. The two carbon atoms at the ends of the chain each have three hydrogen atoms attached to them, and the single carbon atom in the middle of the chain has two hydrogen atoms attached to it.

During the 1960s and well into the 1970s, ai research blossomed and progress seemed rapid. The laboratories established at MIT, Carnegie Mellon, Stanford, SRI, and Edinburgh expanded, and several new groups got started at other universities and companies. Achievements during the preceding years, even though modest in retrospect, were exciting and full of promise, which enticed several new people into the field, myself included. Many of us were just as optimistic about success as Herb Simon and Marvin Minsky were when they made their predictions about rapid progress.

AI entered a period of flowering that led to many new and important inventions. Several ideas originated in the context of Ph.D. dissertation research projects. Others emerged from research laboratories and from individual investigators wrestling with theoretical problems. In this part, I'll highlight some of the important projects and research results. Although not a complete account, they typify much of what was going on in AI during the period. I'll begin with work in computer vision.

As mentioned previously, the problems of understanding, generating, and translating material in ordinary human (rather than computer) languages fall under the heading of natural language processing. During the “early explorations” phase of AI research, some good beginnings were made on NLP problems. In the subsequent phase, the late 1960s to early 1970s, new work built on these foundations, as I'll describe in this part of the book.

Machine Translation

W. John Hutchins, who has written extensively about the history of machine translation (MT), has called the period 1967 to 1976, “the quiet decade.” Inactivity in the field during this period is due in part to the ALPAC report, which, as I have already said, was pessimistic about the prospects for machine translation. Hutchins claimed “The influence of the ALPAC report was profound. It brought a virtual end to MT research in the USA for over a decade and MT was for many years perceived as a complete failure.… The focus of MT activity switched from the United States to Canada and to Europe.”

One exception to this decade-long lull in the United States was the development of the Systran (System Translator) translating program by Petr Toma, a Hungarian-born computer scientist and linguistics researcher who had worked on the Georgetown Russian-to-English translation system. In 1968, Toma set up a company called Latsec, Inc., in La Jolla, California, to continue the Systran development work he had begun earlier in Germany. The U.S. Air Force gave the company a contract to develop a Russian-to-English translation system.