Artificial Intelligence Tutorial Review   home

Developed and compiled by Eyal Reingold and Johnathan Nightingale

Welcome to the PSY371 Artificial Intelligence tutorial review. These pages were developed for the use of psychology students interested in the field of Artificial Intelligence, especially as it relates to the ongoing investigations in psychology aimed at understanding the human mind. This review is meant to be treated as a unified whole since there is a great deal of interconnection between the topics, and since later chapters may depend to some extent on earlier readings.

This review has been designed with the expectation that its readers are new to the area, and care is taken to explain concepts fully. The review should provide an interesting and accessible introduction for beginners, but may be somewhat redundant for readers with more background in the area. Nevertheless, more advanced readers may find interesting links and demonstrations throughout the review. Also, in hopes of keeping the tutorial accessible, many of the more technical issues in AI have been simplified or avoided, with more emphasis being put on conceptual developments and interactive examples. For readers interested in implementation issues, and a computer science perspective, see the University of Nottingham's AI Methods (AIM) course.

 home

1) Early Work in AI
2) Can Machines Think?
     2.1) Turing Test
     2.2) Chinese Room
     2.3) Can Computers be Creative?
     2.4) Can Computers possess Emotional Intelligence?
     2.5) Consciousness in AI
3) Symbolic AI
     3.1) Common Sense Knowledge Problem
     3.2) CYC
     3.3) Expert Systems
     3.4) Game Playing: Man vs. Machine
4) Artificial Neural Networks
     4.1) Brainwave Neural Net Tutorial
5) Robotics and Computer Vision
6) Artificial Life
7) Additional Resources

 

Early Work in AI

Back to index
 home

 

Prehistory of AI

   For centuries, if not millenia, humanity has concerned itself - in fiction and often in engineering - with the creation of devices meant to mimic human behaviour, or to behave in a seemingly intelligent way. Even before science fiction brought the ideas of superhuman robots and megalomaniacal computers to the masses, people built bowing statues, letter-writing dolls, and player pianos in an effort to make the inanimate seem somehow more human.

   Once fiction got ahold of the idea, bookshelves filled with ideas that until recently, were entirely speculative, with no hope of being realised. Bruce Mazlish, at Stanford university, has written an excellent article (if link fails, click here for a local copy) that further discusses the history of automata and other AI in culture and literature. This article helps the reader to appreciate what a vast cultural impact work in AI can have on society. It is well researched and documented, as well as being an interesting read.

The Modern Birth of AI

   Like many technological advances of this century, the development of computer science began as a military effort. In the early 1940's, both Germany and the United States were racing to produce electronic computers that could be used in ballistics calculations, or in deciphering coded messages. It wasn't until after the war that computing facilities, often several rooms in size, could be spared for less essential tasks. The excess computing power after the war, coupled with some major advances in the design of the machines provided a fertile ground for exploring some more esoteric ideas for computing.

   Among the first researchers to attempt to build intelligent programs were Newell and Simon. Their first well known program, Logic Theorist, was a program that proved (or attempted to prove) statements using the accepted rules of logic and a problem solving program of their own design. Their results were promising: not only could Logic Theorist reproduce many of the proofs that humans had developed, but in the case of one theorem, it actually produced a better (i.e. shorter, more direct) proof than the one commonly found in logic textbooks.

   The fury of enthusiasm that emerged out of Logic Theorist's humble accomplishments was astounding. In the summer of 1956, within a year of Newell and Simon's accomplishment, John McCarthy organised "The Dartmouth summer research project on Artificial Intelligence" (McCarthy actually coined the term 'Artificial Intelligence'). This conference is considered an important milestone in the development of AI.

Early Successes... and failures

Hubert Dreyfus, a prominent critic of the AI movement, notes that almost all early work in AI was concerned with one of three areas: Language Translation, Problem Solving, or Pattern Recognition. In each area, significant early successes were produced. Language translation was an early leader, Dreyfus estimates that in the first 10 years of the research program (that is, from 1955-1965) five governments spent over $20 million on its development. By the late fifties, programs existed that could do a passable job of translating technical documents and it was seen as only a matter of extra databases and more computing power to apply the techniques to less formal, more ambiguous texts. In reality, the programs simply could not scale up in the expected ways.

In spite of journalistic claims at various moments that machine translation was at last operational, this research produced primarily a much deeper knowledge of the unsuspected complexity of syntax and semantics. Hubert Dreyfus, in "What Computers Can't Do", p92.

One fundamental problem was the inability to mimic the human capacity to use context to disambiguate the meanings of words and sentences. By the mid-sixties, the program had been substantially scaled down. Although current research in this area has produced recent success, it is still considered one of the great failures of early AI, one of the first signs of over-optimism.

   Work in Problem solving followed the same course of early success and eventual failure that Dreyfus later argued was at the heart of almost every AI attempt. Most problem solving work revolved around the work of Newell, Shaw and Simon, on the General Problem Solver or GPS. The general problem solver employed abstract problem solving rules (e.g. "If you can, always try to reduce differences between your current state, and your goal state") to solve a wide variety of problems. The rules, most of which were heuristic in nature (i.e. they were good rules-of-thumb, rather than perfect, tedious algorithms) were postulated to be the same as those employed by human problem solvers. Over-optimism was also pervasive in this area. Unfortunately, the GPS did not fulfill its promise, and not because of some simple lack of computing capacity, but rather, because of deep theoretical problems. While it could solve some problems with its general techniques, any but the simplest eluded it. The fundamental problem is that general problem solving strategies are limited. People use domain-specific knowledge and skills to solve problems in different contexts. In general, domain specific skills and knowledge do not generalize across areas. For example, knowledge relevant to chess will not be useful in the area of physics. What the GPS had were broad, weak strategies. Strengthening its abilities would mean adding domain-specific knowledge for all possible problem areas - an impossible task. In 1967, roughly 10 years after it began, Newell announced that the GPS program was being abandoned.

   The last of the three early areas of AI was pattern recognition. Once again, there were some early successes. Computers were built that could handle morse code, if there was very little line noise, and the sender was another computer or a very efficient and precise human operator. There were even programs that could, with a reasonable (though not human level) degree of accuracy decipher handwriting (or at least the letter 'A') in various styles and orientations. None, however, did so by way of some fundamental discovery in pattern recognition. Instead, they used ultra-specific and inflexible templates, and were defeated by any significant distortion of the data. They were also incapable of resolving ambiguity or utilizing context.

   From overwhelming optimism, the field was reduced to expressions like the following, from Vincent Giuliano, a researcher in the area.

Alas! I feel that many of the hoped-for objectives may well be porcelain eggs; they will never hatch, no matter how long heat is applied to them, because they require pattern discovery purely on the part of machines working alone. The tasks of discovery demand human qualities. (As cited by Dreyfus)

Back to index

Can Machines Think?

Why do we care?

   The initial successes of computers in replicating seemingly intelligent behaviour quickly led to argument and speculation about what it would mean for a computer to be 'intelligent'. As any psychology student knows, intelligence is a very controversial topic -- making the classification of a man-made machine as intelligent even harder. In terms of raw calculation power, even computers of the mid 1950's could beat human counterparts. The brute force calculations of programs like Newell & Simon's Logic Theorist had already produced results that, had a human produced them, would be unwaveringly accepted as intelligent. Still the debate raged on. The argument focused on the fact that there was no ingenuity, no insight, the computer merely followed human-programmed rules mindlessly until it reached a conclusion. The other side countered that an argument like that was moot, since the results were intelligent and meaningful, the computer has produced proof of intelligence.

   The developers of AI were claiming more than just replication of intelligent products though, they claimed the replication of the intelligence process (this has come to be known as the Strong AI position, a term coined by philosopher John Searle). In other words, they were beginning to claim not only that computers were intelligent, but that they were intelligent in the same way as people are intelligent. Suddenly the debate became more than just a philosophical one, psychology entered the picture. If intelligent computers were produced, could they be considered a working model of human intelligence? All the computers to date, systems like the GPS (see previous section for more details) were mindless rule-followers, what did that say about human intelligence? If we accept them as intelligent, does it necessarily follow they must be intelligent in the way that we are? These were significant questions for psychologists and philosophers, as well as computer scientists.

   Each side found its supporters quite quickly. Critics like Hubert Dreyfus (author of "What Computers Can't Do" and later, "What Computers Still Can't Do") argued not only that current machines were not intelligent, but that no computer could ever be. Supporters like Marvin Minsky offered remarkable optimism with quotes like "Within 10 years the problems of artificial intelligence will be substantially solved," and later, "Within 10 years computers won't even keep us as pets." The important thing to recognize is that when people started asking "Can Machines Think", psychology became inextricably tied to the AI movement. A position it has held, and strengthened in the 50 years since. Time lends focus, so it is not surprising that by the 1980s, Minsky's optimism had thinned, even if he remained hopeful. The two papers assigned, one from Minsky, and the other from Dreyfus, present some of the more typical arguments and refutations in the field.

Back to index

 

The Turing Test

Alan Turing and the Imitation Game

   Alan Turing, in a 1951 paper, proposed a test called "The Imitation Game" that might finally settle the issue of machine intelligence. The first version of the game he explained involved no computer intelligence whatsoever. Imagine three rooms, each connected via computer screen and keyboard to the others. In one room sits a man, in the second a woman, and in the third sits a person - call him or her the "judge". The judge's job is to decide which of the two people talking to him through the computer is the man. The man will attempt to help the judge, offering whatever evidence he can (the computer terminals are used so that physical clues cannot be used) to prove his man-hood. The woman's job is to trick the judge, so she will attempt to deceive him, and counteract her opponent's claims, in hopes that the judge will erroneously identify her as the male.

   What does any of this have to do with machine intelligence? Turing then proposed a modification of the game, in which instead of a man and a woman as contestants, there was a human, of either gender, and a computer at the other terminal. Now the judge's job is to decide which of the contestants is human, and which the machine. Turing proposed that if, under these conditions, a judge were less than 50% accurate, that is, if a judge is as likely to pick either human or computer, then the computer must be a passable simulation of a human being and hence, intelligent. The game has been recently modified so that there is only one contestant, and the judge's job is not to choose between two contestants, but simply to decide whether the single contestant is human or machine.

   The Encyclopedia Britannica's entry on the Turing Test (click here) is short, but very clearly stated. A longer, but point-form review of the imitation game and its modifications written by Larry Hauser, click here (if link fails, click here for a local copy) is also available. Hauser's page may not contain enough detail to explain the test, but it is an excellent reference or study guide and contains some helpful diagrams for understanding the interplay of contestant and judge. The page also makes reference to John Searle's Chinese Room, a thought experiment developed as an attack on the Turing test and similar "behavioural" intelligence tests. We will discuss the Chinese Room in the next section.

Back to index


Natural Language Processing (NLP)

   Partly out of an attempt to pass Turing's test, and partly just for the fun of it, there arose, largely in the 1970s, a group of programs that tried to cross the first human-computer barrier: language. These programs, often fairly simple in design, employed small databases of (usually English) language combined with a series of rules for forming intelligent sentences. While most were woefully inadequate, some grew to tremendous popularity. Perhaps the most famous such program was Joseph Weizenbaum's ELIZA. Written in 1966 it was one of the first and remained for quite a while one of the most convincing. ELIZA simulates a Rogerian psychotherapist (the Rogerian therapist is empathic, but passive, asking leading questions, but doing very little talking. e.g. "Tell me more about that," or "How does that make you feel?") and does so quite convincingly, for a while. There is no hint of intelligence in ELIZA's code, it simply scans for keywords like "Mother" or "Depressed" and then asks suitable questions from a large database. Failing that, it generates something generic in an attempt to elicit further conversation. Most programs since have relied on similar principles of keyword matching, paired with basic knowledge of sentence structure. There is however, no better way to see what they are capable of than to try them yourself. We have compiled a set of links to some of the more famous attempts at NLP. Students are encouraged to interact with these programs in order to get a feeling for their strengths and weaknesses, but many of the pages provided here link to dozens of such programs, don't get lost among the artificial people.

Back to index

 

Online Examples of NLP

   A series of online demos (many are Java applets, so be sure you are using a Java-capable browser) of some of the more famous NLP programs.

Back to index

 

The Loebner Prize

   Although Turing proposed his test in 1951, it was not until 40 years later, in 1991, that the test was first really implemented. Dr. Hugh Loebner, a professor very much interested in seeing AI succeed, pledged $100,000 to the first entrant that could pass the test. The 1991 contest had some serious problems though, (perhaps most notable was that the judges were all computer science specialists, and knew exactly what kind of questions might trip up a computer) and it was not until 1995 that the contest was re-opened. Since then, there has been an annual competition, which has yet to find a winner. While small prizes are given out to the most "human-like" computer, no program has had the 50% success Turing aimed for.

Validity of the Turing Test

   Alan Turing's imitation game has fueled 40 years of controversy, with little sign of slowing. On one side of the argument, human-like interaction is seen as absolutely essential to human-like intelligence. A successful AI is worthless if its intelligence lies trapped in an unresponsive program. Some have even extended the Turing Test. Steven Harnad (see below) has proposed the "Total Turing Test", where instead of language, the machine must interact in all areas of human endeavor, and instead of a five minute conversation, the duration of the test is a lifetime. James Sennett has proposed a similar extension (if link fails, click here for a local copy) to the Turing Test that challenges AI to mimic not only human thought but also personhood as a whole. To illustrate his points, the author uses Star Trek: The Next Generation's character 'Data'.

   Opponents of Turing's behavioural criterion of intelligence argue that it is either not sufficient, or perhaps not even relevant at all. What is important, they argue, is that the computer demonstrates cognitive ability, regardless of behaviour. It is not necessary that a program speak in order for it to be intelligent. There are humans that would fail the Turing test, and unintelligent computers that might pass. The test is neither necessary nor sufficient for intelligence, they argue. In hopes of illuminating the debate, we have assigned two papers that deal with the Turing Test from very different points of view. The first is a criticism of the test, the second comes to its defense.

Additional Resources

   Students interested in more information on the Turing test and the surrounding controversy may find the links below helpful. Each is a compilation of Turing Test related material, the first dealing with the more applied issues, the Loebner prize and NLP programs in general; the second with the philosophical issues surrounding the Test and its variations.

Back to index

The Chinese Room


The Motivation

   The Turing Test (discussed in the previous section) was the first attempt at resolving the question of machine intelligence. It was a behavioural test, judging intelligence based not on inner processes, or faithfulness to neuronal structure, but purely on a computer's ability to verbally communicate. This approach elicited numerous objections: Why should behaviour be the final test on intelligence, hadn't psychology moved away from behaviorism? How can behavior suffice if the internal mechanisms controlling it are nothing like a human being's? How can a conversation capture all of human intelligence? These questions essentially reduced themselves to the question of whether one could pass the Turing Test, that is, produce passable conversational speech, while still possessing no 'real' intelligence. This argument has been stated in numerous ways, but perhaps none more eloquent than John Searle's Chinese Room metaphor.

Back to index

 

The Thought Experiment (An Adaptation of Searle's Original)

    Searle asks the reader to imagine a room, with a man trapped inside. The man speaks no Chinese, nor could he even confidently distinguish Chinese characters from random lines of similar structure. One day, as he is sitting in the room, someone slips a piece of paper under the door with (what he assumes to be) Chinese writing on it. Having puzzled over it for a moment, he notices that there is a book in the room titled "What to do if someone slides some Chinese writing under the door." Having nothing better to do, the man proceeds to open the book and begin reading. The book, he finds, is actually an enormous set of instructions for producing new Chinese symbols based on what comes in. The rules instruct him on how to produce new Chinese symbols, based on the ones received. They are all if-then type statements describing a pattern in the text and the appropriate action or response. He follows these rules, using the piece of paper handed to him, and produces a new sheet, which he slides back under the door. The next day, another sheet comes in, he again opens the rule book, finds out which symbols to write and in which order, and passes the completed sheet back out. At no time does the man understand what he's doing as anything more than symbol manipulation, he does not understand the words coming in, or the words going out, he isn't even sure they ARE words - but it's more exciting than doing nothing, so he continues. What the man in the room does not know, is that the symbols coming in are questions, written in Chinese, and that the symbols he produces in turn are answers to those questions. What's more, the book of instructions has been written so well that his answers are not only proper Chinese, but they make sense, and are indistinguishable from an actual Chinese speaker. Outside, the world is amazed that this room can actually understand Chinese, that the room is intelligent. Inside though, we know that the man understands no Chinese whatsoever!

The Conclusion

   What Searle describes is a system that produces intelligent, meaningful output, in the absence of true understanding. If you accept this counter-example, then the Turing Test is doomed. The Chinese Room would pass the Turing test, even though it lacks understanding and intelligence. Searle's argument has, naturally, produced its own share of furious debate, and several strong counter-arguments have been levelled at it. The adaptation presented here is meant to familiarize students with the ideas Searle is trying to convey, but the thought experiment and the debate surrounding it deserve a more thorough analysis. Thus, two readings are provided for further elaboration of the argument and its replies.

Back to index

 

Additional Resources

Back to index

Can Computers Be Creative?


Theory

   Historically, human creativity has been a neglected topic in psychology in general and intelligence testing in particular. Despite this, creativity is considered by most to be an essential component of human intelligence. Consequently, in attempting to answer the question of whether computers can think, it is only natural to ask whether computers can think creatively. Many feel, in fact, that whereas computers can excel in well-structured areas of problem solving - e.g. logic, algebra, etc. - they have little hope of ever producing truly creative work. For a work to be creative, it must be novel and useful- this represents an enormous challenge for AI.

   The first two links below provide readers with general background on human creativity. The next two deal specifically with creativity in the context of AI.

Back to index

 

Practice

   If AI is famous for anything, it's the so-called "engineering end-run". The idea that resources should not be spent over philosophical debates, instead focus should be on building actual engineering solutions. Later when we find an implementation that works, it can form the basis of more adequate theory. Many in the field of AI will remind you that this is precisely the strategy that worked quite well for aviation. After almost a century of debate on whether a flying machine would be possible, the first machine was constructed, the debate was solved, and a wealth of new data was produced. With that in mind, there have been several attempts to build creative computers, despite the lack of conceptual and theoretical consensus. The most impressive of these is AARON, a painting program that produces both abstract and lifelike works. How are we to judge whether such works of art are truly creative? Is it sufficient to judge the products or is the process by which they were created the determining factor? Below are two pages which do a particularly good job of summarizing the current applied work in computer creativity. Read the articles, look at the illustrations, and ask yourself if you would ever doubt, under normal circumstances, that the pictures were produced by an intelligent mind.

Back to index

 

Can Computers Possess Emotional Intelligence?


Rationale

   The rationale for attempting to mimic emotional intelligence in a computer is not immediately clear. Star Trek fans will remember the difficulties Commander Data felt with the introduction of his emotion chip. In fact, classic Western views of intelligence often pitted emotion and reason against each other. Emotion was seen as a disorganizing factor, harmful to reasoning and logic. However, with the recent introduction of the concept of emotional intelligence, the many positive contributions of emotional factors to intellectual functioning were highlighted. Furthermore, understanding emotion (and to a lesser extent, exhibiting it) may prove essential to any system that is designed to interact with human beings. Of course, the implementation of such a system represents an enormous challenge.

   So why is understanding emotions crucial? The most direct reason, and the obvious one after a moments introspection, is that emotion is inextricably tied to everything we say and do. In more concrete terms, let us consider the advantages of having a computer that understood emotion. First of all, it could provide vastly improved interactions with users. More importantly though, emotional intelligence would be an enormous leap forward for systems attempting to learn about people, and the world in which they live.

   Also of interest to AI research, and psychology, is the idea of simulating emotion in computers. These simulations can be either internal, external, or both, depending on the motivations of those designing the system. External simulation, that is, exhibiting emotion purely for the benefit of those interacting with the system, is more difficult than it may seem. While psychologists have known for some time that there are a good deal of physical correlates to emotion - voice changes, blushing, pupil dilation, etc. - reproducing them proves difficult. Often the effect is exaggerated, so much so that the emotional device becomes obvious. For an example of the type of work being done, click here for a link to Janet Cahn's master's thesis work, generating expression in synthesized speech. There is also work being done on internal emotion, that is, programming a computer to actually 'experience emotions'. Emotion provides us with a motivation and drive, with a set of personal preferences, with a uniqueness that is desirable in a sophisticated AI. In some cases, most notably MIT's 'Kismet', the two (internal and external emotions) are combined into a robot that seems to possess and display emotion. For more information, click here to access Kismet's homepage (this page is of a moderately technical level). Both Cahn's work, and Kismet are part of the MIT Media Lab's research program. Students are encouraged to explore the various research projects being pursued at MIT -- its lab is at the forefront of AI and emotional AI research.

Back to index

AI and Consciousness

 

   Consciousness is perhaps one of the most controversial areas of research in psychology. Currently, there is no general consensus as to how to define or measure conscious awareness. Despite this, both researchers and lay-persons alike feel that consciousness is a fundamental determinant of what it means to be human. Not surprisingly, in the field of AI, consciousness is just as controversial.

   One fundamental issue is whether or not conscious awareness is simply a by-product of complex intelligent systems. Those who assume that consciousness is simply a by-product or an emergent property argue as follows. In humans, a single neuron has nothing resembling intelligence. Yet in combination, billions of neurons combine to form a mind that does possess intelligence. It would appear then, that the brain is more than the sum of its parts. Intelligence emerges with sufficient configural complexity of neurons. So it is not inconceivable that other attributes such as consciousness, creativity and emotionality may emerge as a by-product of complex artificially intelligent systems. In general then, the idea is that consciousness is just a by-product of any sufficiently complex brain, and AI engineers need not try to isolate and recreate it specifically, it will emerge automatically as needed.

   If one assumes, on the other hand, that consciousness is not such a by-product, then an additional question is whether or not it is possible to computationally define, and simulate it. Thus, in asking whether computers can think, we must inevitably turn to the question of whether thinking computers would actually be conscious? In other words, at some point in the enterprise of AI it becomes important to define the relationship between consciousness and intelligence. For example, is consciousness a necessary condition for intelligent systems or would intelligent systems necessarily display consciousness?

   Skeptics point out that a fundamental component of consciousness is subjective phenomenal experience which may be beyond the scope of computational simulation. To illustrate this distinction, imagine a person, totally colourblind from birth, who as a result, has never experienced the colour red as any different from an equally bright grey, or green. Then imagine that the person studies colour theory, physics, psychology of perception and the biology of the eye. Imagine that the person becomes totally knowledgeable about all aspects of the colour red. Skeptics argue that in studying all of this factual information, our person is learning the type of thing a computer might learn: wavelengths, frequencies, etc. However, what the person is not learning is what red really looks like - she can't see it, so her experience is lacking something. The argument then is that no amount of factual information - the kind you would give a computer - can give them the subjective experience of red, or anything else. What makes the argument significant is that the same skeptics argue that the subjective, personal, phenomenological experiences are what make up conciousness and thus without them, an AI cannot be conscious.

Back to index

Symbolic AI

 

   The work started by projects like the General Problem Solver (see Early Work in AI) and other rule-based reasoning systems (like Logic Theorist, mentioned in the same chapter) became the foundation for almost 40 years of research. Symbolic AI (or Classical AI) is the branch of artificial intelligence research that concerns itself with attempting to explicitly represent human knowledge in a declarative form (i.e. facts and rules). If such an approach is to be successful in producing human-like intelligence then it is necessary to translate often implicit or procedural knowledge (i.e. knowledge and skills which are not readily accessible to conscious awareness) possessed by humans into an explicit form using symbols and rules for their manipulation. Symbolic AI has had some impressive successes. Artificial systems mimicking human expertise (Expert Systems, discussed later) are emerging in a variety of fields which constitute narrow but deep knowledge domains. Game playing programs are being written now that challenge the best human experts. The difficulties encountered by symbolic AI have however, been deep, possibly unresolvable ones. One difficult problem encountered by symbolic AI pioneers came to be known as the common sense knowledge problem (discussed in the next chapter). In addition, areas which rely on procedural or implicit knowledge such as sensory/motor processes, are much more difficult to handle within the Symbolic AI framework. In these fields, Symbolic AI has had limited success, and by and large has left the field to neural network architectures (discussed in a later chapter) which are more suitable for such tasks. In sections to follow we will elaborate on important sub-areas of Symbolic AI as well as difficulties encountered by this approach.

Back to index

 

The common sense Knowledge Problem


The Problem

   In Early Work in AI we saw that AI's reach quickly exceeded its grasp when trying to build universal machines. One of the fundamental problems encountered became known as the general knowledge problem or the common sense knowledge problem. While researchers were aware that in an AI system, knowledge would have to be explicitly represented, they did not anticipate the vast amount of implicit knowledge we all share about the world and ourselves. Designers of AI systems did not consider producing rules like "If President Clinton is in Washington, then his left foot is also in Washington," or "If a father has a son, then the son is younger than the father and remains younger for his entire life." In retrospect, this is perhaps not surprising, because the implicit nature of this knowledge in humans means that we all take it for granted, and never have to state it or consider it explicitly.

   Once the problem was acknowledged, it soon became clear that it represented an enormous hurdle for the development of general purpose intelligent systems. One hope or perhaps wishful thinking on the part of AI developers, was that all that was needed was a decent learning program, and this knowledge would be acquired by computers as automatically as it is acquired by humans. A central part of the common sense knowledge problem has to do with the issue of knowledge representation in artificial systems. What is the best approach to represent knowledge? Are dictionary- or encyclopedia-like entries the best approach? Should everything be formulated as a series of if-then rules? Should multiple forms of representation be used? It is clear that not all human knowledge is represented in such an explicit or declarative form. The implicit nature of knowledge applies not only to common sense knowledge, but also to a wide variety of expertise and skills we possess. Such domain-specific knowledge is often represented as procedures, rather than facts and rules (these difficulties will be discussed further in the section on Expert Systems). The article below discusses some of the issues relevant to knowledge representation in both humans and computers.

Back to index

CYC

 

   In the absence of a learning machine that can acquire common sense facts on its own, there would seem to be only one option left. That is, manually programming in the millions of general knowledge items that we take entirely for granted. The CYC research project has actually undertaken this mammoth task.

The Most Ambitious AI Project Ever?

   Decide for yourself: CYC is a $25 million, 20 year project in Artificial Intelligence. Aimed at beating the common sense knowledge problem outlined in the last chapter, the project employs workers whose full time occupation consists of entering volumes of common sense data into the ever-growing AI. Its database, at the time of writing, contains over 1,000,000 of these hand-entered facts, and is maintained in an entire room full of computers. The CYC programmers designed a representation scheme that claims to be standardized enough to be useful, while being flexible enough to represent almost any fact. In short, the project headed by Douglas Lenat and already 15 years running is one of the most impressive AI undertakings ever.

Why?

   The companies that eventually funded CYC must have been presented with the same staggering statistics that we have just presented to you: millions of dollars, decades of work, massive computing requirements. Yet companies chose to invest, not governments or academic institutions, private for-profit corporations. What benefits could outweigh those costs?

   However large the task is, if successfully completed, think of the contribution to computing. Cycorp (the corporation in charge of CYC's construction) will be able to license the world's only common sense knowledge base out to other companies. There might be a common sense search engine on the web that actually finds you the links you want, instead of semi-randomly looking for keywords. Whatever the cost, CYC has the potential to revolutionize "intelligent" computing. No one, though, can better explain CYC's potential and successes than Cycorp themselves. We have included three readings, all written by Douglas Lenat and other members of the Cycorp team and all (naturally) beaming about the project's prospects.

Objections

   Of course, not everyone is as full of enthusiasm as Doug Lenat. Several critics (among them Hubert Dreyfus, the critic mentioned in earlier chapters) point out that while it makes for an interesting exercise in programming, it falls short of the mark as strong AI. Strong AI claims to duplicate not only human-like intelligent products, but also human-like intelligent process. As explained in the previous section, human knowledge is often implicit, procedural, and domain specific, rather than explicit, declarative, and general purpose. However, the focus of the CYC project is not Strong AI, or modeling human intelligence. Rather, it is an example of an 'engineering end-run' attempt to produce general purpose, intelligent machines.

   Lenat may, however, have overstepped his bounds at one point, and critics have taken him to task on it. In his enthusiasm for the project, Lenat has been found to hold some lofty ambitions: Cyc teaching schoolchildren, advising public policy, and even dispensing justice. These predictions if they came to pass, would certainly reflect great confidence in AI research, but critics warn that the results could be catastrophic, as the paper below argues.

Back to index

Expert Systems

 

   Given the common sense knowledge problem, and the difficulty in creating general purpose intelligent machines, an alternative approach developed which attempted to mimic human performance within restricted domains of knowledge.

   The first serious attempt at applying this alternate approach came to be known as "Microworlds". The theory behind Microworlds was that the first step in AI ought to be producing intelligence in a restricted environment. Once that had been solved, one could gradually increase the complexity of the environment, and the AI, until eventually AI arrived at a level that could cope with real-world situations. It was a scaling theory, from specificity towards generality without loss of strength. The most famous microworlds project was Terry Winnograd's SHRDLU (SHRDLU is just the 7th to 12th most common letters in English, he got the name from a Mad Magazine article). SHRDLU lived in a world called Blocks World. It had in its memory descriptions of various blocks: shapes, colours, sizes and positions. It also had a robotic arm (actually, the entire thing was a simulation, so neither the blocks, nor the arm actually existed) that could move the blocks. Finally, its intelligence programming included two components: the first was a problem solver that could look at the world, gather information, and make changes when possible, such as moving a block; the second was a natural language program that interacted with users while manipulating the blocks world. Within its world, SHRDLU was impressive. You could tell it to move the green block and it could do so. It would even ask clarifying questions like "By the green block, I assume you mean the green cube on the blue cube," or "To move the green block, I will have to move the red pyramid."

   The problem with microworlds projects like SHRDLU was that they failed to scale up as the original strategy called for. Nevertheless, it provided a proof that AI systems designed to operate within domains of knowledge that are narrow, but deep, could be highly effective. This realization inspired the creation of one of the most successful sub-areas of AI - the field of expert systems. The basic idea is that if one can codify human expertise within a narrow domain as a hierarchical series of if-then rules, then an AI system can be created that mimics or perhaps even exceeds the performance of a human expert. One problem which was encountered early in this enterprise was that experts cannot always explicitly state the rules which guide their performance. Even when experts do state rules explicitly, when such rules were implemented, the performance obtained was inferior to that of the expert providing the rules, indicating there is insufficiency. This is the problem of implicit knowledge which was discussed previously. Given that domain specific knowledge is often implicit and procedural, one of the challenges of expert system developers was to find a way of interrogating experts and collecting information about expert performance in order to clarify the rules being used. The new occupation of "Knowledge Engineer" emerged to fill that purpose. Knowledge engineers spend a lot of time with human experts during the design stage of an expert system, as well as during multiple feedback and improvement cycles. Currently expert systems represent one of the major financial successes of AI with an industry exceeding $1 billion.

   We have assembled two sets of links below. The first discuss expert systems in more detail than they have been described here. The second set are actual expert systems available for online interaction or study. Students should be aware that of the three Introduction and Discussion sites linked to, only the first is written for a lay audience. The second and third are accessible, but were written for students of artificial intelligence and as such, tend to move through material at a quicker pace.

Back to index

 

Introduction and Discussion

Illustrations and Demos

Back to index

Game Playing

 

   Ever since the beginning of AI, there has been a great fascination in pitting the human expert against the computer. Game playing provided a high-visibility platform for this contest. It is important to note, however, that the performance of the human expert and the AI game-playing program reflect qualitatively different processes. More specifically, as mentioned earlier, the performance of the human expert utilizes a vast amount of domain specific knowledge and procedures. Such knowledge allows the human expert to generate a few promising moves for each game situation (irrelevant moves are never considered). In contrast, when selecting the best move, the game playing program exploits brute-force computational speed to explore as many alternative moves and consequences as possible. As the computational speed of modern computers increases, the contest of knowledge vs. speed is tilting more and more in the computers favour, accounting for recent triumphs like Deep Blue's win over Gary Kasparov.

   Readings for this section have been organised into two groups. In the first are two papers that discuss game playing in general - describing certain attempts, and certain techniques common to the area. The second deal specifically with Deep Blue's success, and its implications both for AI, and for society.

Game Playing

Deep Blue

Back to index

Artificial Neural Networks


What They Are

   A neural network is, in essence, an attempt to simulate the brain. Neural network theory revolves around the idea that certain key properties of biological neurons can be extracted and applied to simulations, thus creating a simulated (and very much simplified) brain. The first important thing to understand then, is that the components of an artificial neural network are an attempt to recreate the computing potential of the brain. The second important thing to understand, however, is that no one has ever claimed to simulate anything as complex as an actual brain. Whereas the human brain is estimated to have something on the order of ten to a hundred billion neurons, a typical artificial neural network (ANN) is not likely to have more than 1,000 artificial neurons.

   Before discussing the specifics of artificial neural nets though, let us examine what makes real neural nets - brains - function the way they do. Perhaps the single most important concept in neural net research is the idea of connection strength. Neuroscience has given us good evidence for the idea that connection strengths - that is, how strongly one neuron influences those neurons connected to it - are the real information holders in the brain. Learning, repetition of a task, even exposure to a new or continuing stimulus can cause the brain's connection strengths to change, some synaptic connections becoming reinforced and new ones are being created, others weakening or in some cases disappearing altogether. The second essential element of neural connectivity is the excitation/inhibition distinction. In human brains, each neuron is either excitatory or inhibitory, which is to say that its activation will either increase the firing rates of connected neurons, or decrease the rate, respectively. The amount of excitation or inhibition produced is of course, dependent on the connection strength - a stronger connection means more inhibition or excitation, a weaker connection means less. The third important component in determining a neuron's response is called the transfer function. Without getting into more technical detail, the transfer function describes how a neuron's firing rate varies with the input it receives. A very sensitive neuron may fire with very little input, for example. A neuron may have a threshold, and fire rarely below threshold, and vigorously above it. A neuron may have a bell-curve style firing pattern, increasing its firing rate up to a maximum, and then levelling off or decreasing when over-stimulated. A neuron may sum its inputs, or average them, or something entirely more complicated. Each of these behaviours can be represented mathematically, and that representation is called the transfer function. It is often convenient to forget the transfer function, and think of the neurons as being simple addition machines, more activity in equals more activity out. This is not really accurate though, and to develop a good understanding of an artificial neural network, the transfer function must be taken into account.

   Armed with these three concepts: Connection Strength, Inhibition/Excitation, and the Transfer Function, we can now look at how artificial neural nets are constructed. In theory, an artificial neuron (often called a 'node') captures all the important elements of a biological one. Nodes are connected to each other and the strength of that connection is normally given a numeric value between -1.0 for maximum inhibition, to +1.0 for maximum excitation. All values between the two are acceptable, with higher magnitude values indicating stronger connection strength. The transfer function in artificial neurons whether in a computer simulation, or actual microchips wired together, is typically built right into the nodes' design.

   Perhaps the most significant difference between artificial and biological neural nets is their organization. While many types of artificial neural nets exist, most are organized according to the same basic structure (see diagram). There are three components to this organization: a set of input nodes, one or more layers of 'hidden' nodes, and a set of output nodes. The input nodes take in information, and are akin to sensory organs. Whether the information is in the form of a digitised picture, or a series of stock values, or just about any other form that can be numerically expressed, this is where the net gets its initial data. The information is supplied as activation values, that is, each node is given a number, higher numbers representing greater activation. This is just like human neurons except that rather than conveying their activation level by firing more frequently, as biological neurons do, artificial neurons indicate activation by passing this activation value to connected nodes. After receiving this initial activation, information is then passed through the network. Connection strengths, inhibition/excitation conditions, and transfer functions determine how much of the activation value is passed on to the next node. Each node sums the activation values it receives, arrives at its own activation value, and then passes that along to the next nodes in the network (after modifying its activation level according to its transfer function). Thus the activation flows through the net in one direction, from input nodes, through the hidden layers, until eventually the output nodes are activated. If a network is properly trained, this output should reflect the input in some meaningful way. For instance, a gender recognition net might be presented with a picture of a man or woman at its input nodes and must set an output node to 0.0 if the picture depicts a man, or 1.0 for a woman. In this way, the network communicates its knowledge to the outside world.

Back to index

 

How They Learn

   Having explained that connection strengths are storehouses of knowledge in neural net architectures, it should come as no surprise that learning in neural nets is primarily a process of adjusting connection strengths. In neural nets of the type described so far, the most popular method of learning is called Back-Propagation. To begin, the network is initialised, all the connection strength are set randomly, and the network sits as a blank slate. The network is then presented with some information, let us suppose that we are designing the "gender detector" mentioned earlier, and that the input nodes are receiving a digitised version of a photograph. The activation flows through the net (albeit haphazardly since we have not yet set the connection strengths to anything but random values). And eventually the output node registers an activation level. However, since the net has not yet been trained, its responses will initially be random. This is where back-propagation steps in. The net's response is compared with the correct response for that picture (i.e. 0.0 for male, 1.0 for female). Then working backwards from the output node, each connection strength is adjusted so that next time it's shown that picture, its answer will be closer to the desired one (the process by which each node is adjusted involves mathematics more complicated than this course requires. Students who are interested will find that some of the papers provided at the bottom of this chapter will discuss these methods in more detail).

   This whole process: input, processing, comparing output with correct answer, and adjusting connection strengths is called one 'back-propagation cycle', or often just one 'iteration'. The net is then presented with another picture and its answer is compared with the correct answer, the connection strengths adjusted where needed. This process can often take hundreds or thousands of iterations. Eventually, the net should become fairly proficient at identifying males and females. There is always a risk however, that the net has not learned to discriminate males from females, but rather that it has effectively memorized the response for each picture. To test for this, the pictures (or whatever input is being used) should be divided into two groups: The training set, and the transfer set. The training set is used during back-propagation cycles, and the transfer set is used once learning is complete. If the net performs as well on the novel transfer stimuli as it did on the training set, then we conclude that learning has occured.

Back to index

 

Successes and Failures

   It's fine in theory to talk about neural nets that tell males from females, but if that was all they were useful for, they would be a sad project indeed. In fact, neural nets have been enjoying growing success in a number of fields, and significantly: their successes tend to be in fields that posed large difficulties for symbolic AI. Neural networks are, by design, pattern processors - they can identify trends and important features, even in relatively complex information. What's more, they can work with less-than-perfect information, such as blurry or static-filled pictures, which has been an insurmountable difficulty for symbolic AI systems. Discerning patterns allows neural nets to read handwriting, detect potential sites for new mining and oil extraction, predict the stock market, and even learn to drive.

   Interestingly, neural nets seem to be good at the same things we are, and struggle with the same things we struggle with. Symbolic AI is very good at producing machines that play grandmaster-level chess, that deduce logic theorems, and that compute complex mathematical functions. But Symbolic AI has enormous difficulty with things like processing a visual scene (discussed in a later chapter), dealing with noisy or imperfect data, and adapting to change. Neural nets are almost the exact reverse - their strength lies in the complex, fault-tolerant, parallel processing involved in vision, and their weaknesses are in formal reasoning and rule-following. Although humans are capable of both forms of intellectual functioning, it is generally thought that humans possess exceptional pattern recognition ability. In contrast, the limited capacity of human information processing systems often makes us less-than-perfect in tasks requiring abstract reasoning and logic.

   Critics charge that a neural net's inability to learn something like logic, which has distinct and unbreakable rules, proves that neural nets cannot be an explanation of how the mind works. Neural net advocates have countered that a large part of the problem is that abstract rule-following ability requires many more nodes than current artificial neural nets implement. Some attempts are now being made at producing larger networks, but the computational load increases dramatically as nodes are added, making larger networks very difficult. Another set of critics charge that neural nets are too simplistic to be considered accurate models of human brain function. While artificial neural networks do contain some neuron-like attributes (connection strengths, inhibition/excitation, etc.) they overlook many other factors which may be significant to the brain's functioning. The nervous system uses many different neurotransmitters, for instance, and artificial neural nets do not account for those differences. Different neurons have different conduction velocities, different energy supplies, even different spatial locations, which may be significant. Moreover, brains do not start as a jumbled, randomised set of connection strengths, there is a great deal of organization present even during fetal development. Any or all of these can be seen as absolutely essential to the functioning of the brain, and without their inclusion in the artificial neural network models, it is possible that the models end up oversimplified.

   One of the fundamental objections that has been raised towards back-propogation style networks like the ones discussed here is that humans seem to learn even in the absence of an explicit 'teacher' which corrects our outputs and models the response. For neural networks to succeed as a model of cognition, it is imperative that they produce a more biologically (or psychologically) plausible simulation of learning. In fact, research is being conducted with a new type of neural net, known as an 'Unsupervised Neural Net', which appears to successfully learn in the absence of an external teacher.

Back to index

 

Introductory Papers

   These papers have been assembled to provide students with a more developed understanding of neural net architectures, and the current issues in research. The first three articles should be read by all students, they are clear and well explained. They avoid some of the more technical detail, but provide an excellent beginner's understanding of the field. The remaining three are included for students interested in more technical details. Students interested in neural networks are encouraged to read them for a more thorough understanding, but some calculus and computer science will be introduced that is beyond the scope of this course.

Links

Demos

Back to index

BrainWave Neural Net Simulator Tutorial

Introduction

   The BrainWave neural network simulator is an excellent online resource for students interested in an in-depth understanding of neural network architecture. It was written by Simon Dennis and Devin McAuley, with contributions from Raymond Smith, Janet Wiles and Rachael Gibson as a tool to help undergraduate students taking a neural networking course at the University of Queensland, Australia. This allowed them to produce an excellent, complex system that is nonetheless accessible to undergraduate students without much background in neural networks.

   Our tutorial is designed to introduce readers to the BrainWave program in a step-by-step fashion by exploring two of the sample networks. To run BrainWave you will need a Java enabled browser (Netscape 3.0 or higher, or Internet Explorer 3.0 or higher, for example). It is recommended that you keep this tutorial available to you while working with the program, either in another window, or in print form (to open the BrainWave page in a new window, without closing this one, click here).

Getting Started

   The page that loads contains some information about the Brainwave simulations, as well as the program itself. If you do not see the program upon first loading the page, don't worry, it can take a few minutes to load. In some browsers (including Netscape) the page may even appear to stop loading (your browser may report that it is finished, or the animation indicating that loading is in progress may stop) but even in these cases, the load is still in progress. When the load does finish, you will see a window in the middle of the page with a rather complicated looking tangle of squares and lines connecting them, this is the neural net. Before we can understand this network, we need to discuss the idea of distributed representation.

Distributed Representation (and Content Addressability)

   One dominant metaphor for human memory is that of a library. That is, memories are stored in some vast database and recall is a process of searching the database for a specific item. Likewise, Symbolic AI stores human knowledge as a list of statements and if-then rules. Knowledge retrieval involves searching entries until the correct one is found. In order to accomodate for the possiblity of large databases, just as a library must, knowledge has to be indexed or sorted (much like the phone book is organised alphabetically so that you need not read 2 million names before finding the one you want). In contrast, connectionism uses a distributed representation scheme, with content-addressable retrieval. In a distributed representation, the same set of neurons can be used to represent multiple concepts or facts. For example, if we have three neurons, A, B, and C, one set of activity levels (e.g. A=0.5, B=1.0, C=-0.176) can represent one idea, while the very same neurons, with different activation levels (e.g. A=0.0, B=-0.8, C=0.45) can represent something totally different. Thus, it is no longer necessary to dedicate a group of neurons for each distinct idea or fact in the database (as in the metaphor of distinct books in a library). Instead, if the connection strengths between neurons are set up properly, many ideas and facts can be represented as distributed activation patterns across the same set neurons. A distributed representation possesses another interesting property referred to as content-addressability. If part of the activation pattern is specified, it is often possible to retrieve the pattern as a whole. In fact, for every concept or fact, numerous partial activation patterns exist which will allow retrieval of this knowledge item. Consequently, there is no need to sort the stored knowledge according to any key or index (as would be required by a library style organisation).

Jets and Sharks

   The Jets and Sharks network is an attempt by James McClelland and David Rumelhart to show that distributed representation (that is, storing many memories as pattern of activation over the same set of neurons) and content-addressability (that is, accessing a given memory from any of its component parts) are not just theoretically possible in networks, but can actually be built. The jets and sharks network stores information about two rival gangs, the jets and the sharks. Unlike the back-Propagation style networks discussed so far in the Neural Nets tutorial, Jets and Sharks is an Interactive Activation and Competition (IAC) net. IAC nets do not have discrete input and output nodes, and information does not flow in one particular direction. Instead, the nodes are labeled with particular attributes (e.g. Marital Status: Single/Married/Divorced) and interconnected in such a way that activation flows between certain nodes, and competes with (or inhibits) others. To understand how the net works, here is the information we have about the Jets and Sharks (taken from the BrainWave information page):

Name

Gang

Age

Education

Marital Status

Occupation

Art

Jets

40's

J.H.

Single

Pusher

Rick

Sharks

30's

H.S.

Divorced

Burglar

Sam

Jets

20's

College

Single

Bookie

Ralph

Jets

30's

J.H.

Single

Pusher

Lance

Jets

20's

J.H.

Married

Burglar


Now look at the BrainWave simulator window. Notice that each of the pieces of information (e.g. Marital Status, Education, etc.) has its own cluster of nodes in the network, and that each possible value is given its own node. Next notice the arrows connecting nodes. In general, red lines seem to connect nodes in different groups, and blue lines connect nodes from the same group. The red lines are excitatory, and the blue inhibitory, for reasons we'll get in to later. Since IAC nets do not have any obvious input nodes, interacting with them is different than in other nets. In IAC nets, the idea is to activate certain nodes, then watch the activation spread in hopes of gaining new information. Remember, this net is a distributed representation, content-addressable memory, stored within its connection strengths is all the information in the table provided above. To engage it, we set some nodes to a high level of activation and watch as activation spreads to the other nodes. To familiarize you with the network, let's try an actual interaction.

   Let's say we are trying to solve a burglary. Police know the man was in his 20's, and wearing a Jets jacket, but that's all. Now if our memory was stored in library format, sorted say, by name, then we would be lost, our only hope would be to examine every memory until we found what we wanted. If our memory system is content addressable though, any part of the memory (e.g. his age, and gang affiliation) should be enough to activate the other parts. To represent what we know in the simulator, click on the box marked "Burglar". The burglar box should fill itself in red, this is the program's way of indicating its activation, the more activation, the larger the red box. Now do the same with the Jets box, click on it to activate it fully. Now to watch the activation spread we have to cycle the network. A cycle is a step in the activation-spreading process. In each cycle, each node's activation is broadcast to all nodes connected to it, and each node's activation is recalculated based on the inputs it receives. In the bottom left corner of the program screen, there is a button labeled cycle. By default, this performs 30 cycles which is fine for our purposes, click the cycle button and watch what happens. Several nodes we have not touched have become activated! What's more, the nodes that are activated correspond to all of Lance's attributes, his age, marital status, education, etc. are all activated and none of the other attributes are activated at all. Even better - Lance is the only person on the list that fits the description of the suspect. This pattern of activation is what's meant when we talk about distributed representation - these nodes, being activated in the particular way they are represent our memory of Lance. A different activation would represent someone else, or maybe no one at all. To see the effect again, click on "Zero Units". This resets every node to an activation level of 0, returning the net to its initial state. This time, activate the name Sam. Then cycle it twice, that is, click cycle, allow the 30 cycles to complete, then click cycle again. Over the 60 cycles, we see activation spreading to only those nodes connected to Sam - the network knows Sam's education level, marital status and age. Feel free to experiment more with the program and see what emerges, remember that some patterns may take more than one click on "cycle" to appear.

   What you may notice is that certain nodes never get co-activated. For instance, no activation pattern will result in both Married and Single becoming strongly activated. In fact, if you intentionally activate Married and Single, they cancel each other out until one or the other wins (try it). That seems clear enough to us, no person can be both Married and Single, but how does the network know? Remember that blue lines represent inhibition, and remember that this network is called an Interactive Activation and Competition network. Those blue lines are there because attributes from the same class compete with one another - they cannot co-exist. In this sense the net is very much like a human as well - if I asked you to name one of your friends or family that was both married and single, you too would have great difficulty.

   The BrainWave homepage also contains some thorough documentation of its own written at a more technical level. Students interested in learning more about neural nets are encouraged to read the discussion and self-study topics provided at the bottom of the Brainwave page. These exercises require that you register with the site (click on "Individual Register" from the left hand menu bar), but registration is free and the provided material is of very high quality. For more information on the program itself, consult the BrainWave Reference Guide.

Back to index

Robotics and Computer Vision


Building a human shell

   An intelligent computer system can go a long way in reducing human labour. But if such a system can be provided with a method of actually interacting with the physical world, its usefulness is greatly increased. Robotics gives AI the means to exhibit real-world intelligence by directly manipulating their environment. That is, robotics gives the artificial mind a body.

   An essential component of robotics has to do with artificial sensory systems in general, and artificial vision in particular. While it is true that robotics systems exist (including many successful industrial robots) that have no sensory equipment (or very limited sensors) they tend to be very brittle systems. They need to have their work area perfectly lit, with no shadows or mess. They must have the parts needed in precisely the right position and orientation, and if they are moved to a new location, they may require hours of recalibration. If a system could be developed that could make sense out of a visual scene it would greatly enhance the potential for robotics applications. It is therefore not surprising that the study of artificial vision and robotics go hand-in-hand.

   The links gathered below fall into two categories. The first deal with both computer vision and robotics, and discuss current research in the areas (including their integration with each other). The second portion, for interest's sake, includes links to some commercial attempts to bring robots into the mainstream.

Research

Back to index

 

Commercial Robots

Back to index

Artificial Life

   Artificial Life relates to Biology in much the same fashion that Artificial Intelligence relates to Psychology. The goal of artificial life, or ALife, is to provide a different focus for researchers in biology. Rather than emphasize an analytic approach - attempting to understand the complex phenomena of life by breaking them down into simpler units - ALife offers a synthetic perspective - it begins with simple rules and concepts, and combines them to see what complex phenomena are produced. What is surprising, and what has helped legitimize ALife as a research pursuit, is how accurately computer models developed through this methodology have reflected our observations of biological life. An example may help clarify what it is we mean when we talk about combining simple rules in computer simulation to acheive life-like results.


Boids

   In 1986, Craig Reynolds developed a computer program which, while not the first of its kind, became nonetheless an immensely popular example of ALife. His program was a simulation of a flock of birds, though it has been adapted to look like a herd of zebra, or a school of fish, as well. Each bird was guided by a few very simple rules:

  1. Separation: steer to avoid crowding local flockmates.
  2. Alignment: steer towards the average heading of local flockmates.
  3. Cohesion: steer to move toward the average position of local flockmates.
  4. Avoidance: steer to avoid any physical obstacles

 

   Using these four intuitive rules, Reynolds created the bird/zebra/fish creatures, which he called 'Boids'. What makes the boids so appealing to ALife researchers though, is that the behaviour generated is strikingly lifelike. In order to see this for yourself, we have provided links to Java applets which recreate the boids program, as well as movies made by ALife researchers, of actual animal groups engaged in similar flocking/schooling behaviour. ALife researchers point to these similarities as a proof that ALife can produce meaningful results. It allows science to ask whether biological animals are indeed following similar rules and if so, conventional biology can begin looking for the origins of this behaviour.

   As a further interesting note, the same flocking ideas were used by Disney animators in the making of their hit movie: The Lion King. Early in the story, a wildebeest stampede kills the old king. This stampede was computer animated, and each of the wildebeests followed Reynolds' four rules.


Boids and Flocking Links


Evolution

   We have seen now that ALife can provide interesting and potentially fruitful models of animal behaviour through computer simulation. An area that may prove equally fruitful though, is the reverse process - applying biological principles to computers. ALife researchers have been the ones to develop this reverse concept known now as Evolutionary Computing, and the related discipline of Genetic Algorithms (GA), which uses evolutionary principles to build smarter computer programs. Researchers observed that in the realm of biology, individuals develop very complex and successful structures and behaviours with only the rule of Survival of the Fittest to guide them. They reasoned that perhaps a similar process could be applied to computers, where programs or simulations are allowed to mutate and breed, and the best individual traits combine to form more and more successful individuals. Like the boids, a simple idea has spawned some complex, and exciting results.

   A very straightforward example of this idea is some work done by Jeffrey Vantrella in his Sexual Swimmers project. Here he was not using Evolutionary computing to solve a real world problem, his work is more a demonstration that simulating evolution is possible. He created a simulated pond and in it placed a bunch of randomly generated creatures made up simply of several lines and the ability to move them. Food was scattered through the pond, and the creatures had to acquire it in order to gain the necessary energy to move, live and reproduce. This simple environment would thus favour creatures that could move efficiently, since they would find more food sources and mates, and waste less energy. Indeed, Vantrella found that the poorly designed swimmers died off quickly, and after several generations, the swimmers were sleek and efficient. The article itself covers a lot of material that may not be of interest to casual readers, but Section 7 (if link fails, click here for local copy) details the evolution of the swimmers, including several helpful illustrations.

   A real-world example of this is the work done by Peter Senecal at the University of Wisconsin. His work centered around the job of developing a better design for an internal combustion engine. Such engines have thousands of variables that can be manipulated, and finding a better combination of factors has until recently been a very time consuming and complex enterprise. What Senecal did was extract 6 key features of an engine's design, and put evolutionary computing to work in finding a good combination. Just like Vantrella did with his swimmers, Senecal developed a simulated engine, and did extensive tests to ensure that the simulation matched the performance of a real world engine closely. He started with 5 individuals (where Ventrella's initial populations were in the hundreds), 4 of which had just been given random values for the 6 factors, and the 5th of which was a representation of the best current engine design available. Using his simulation, he then evaluated the five, and allowed the best two to 'breed', combining their values, and producing offspring that resembled their parents, with some mutations introduced as well. The process was then repeated with the new population, and then again with their offspring, and so on. Just as in biological evolution, each population was tested, the fittest surviving, the failures dying off. What makes the results so impressive is that after running this evolution of engines simulation for just a few weeks, it produced an engine that "reduced nitric oxide emissions by three-fold and soot emissions by 50 percent over the best available technology. At the same time, the model reduced fuel consumption by 15 percent." Evolutionary computing is no computer scientist's toy, it is a powerful way to find good solutions. For an article describing Senecal's work, click here (if link fails, click here for local copy).

Back to index


More Evolutionary Computing Resources

Back to index

Additional Resources

 

   Linked here are a variety of additional resources that may be of interest to any visitor looking for more information on specific topics in AI.

Large Sites - Collections

Dictionaries

Online Manuscripts

Back to index
 home