Behavior-based Robotics and AI

Posted 17 Aug 2004 at 16:57 UTC by steve

David P. Anderson of the Dallas Personal Robotics Group has written a combined review of two books recently added to the DPRG library, "Cambrian Intelligence The Early History of the New AI" by Rodney A. Brooks and "Introduction to Autonomous Mobile Robots" by Roland Siegwart and Illah R. Nourbakhsh. One of the books is based on the traditional artificial intelligence approach to robotics while the other presents Brook's behavior-based subsumption approach. This difference makes them ideal for a comparative review. Readers may also wish to read the review of the Siegwart and Nourbakhsh book posted last month here on robots.net. Readers wishing to learn more about Brook's ideas should visit his online archive of papers. Read on for the full review.

Review by: David P. Anderson

Help support robots.net by purchasing these books from Amazon.com. Click on each book's title below to purchase it from Amazon.com.

Title: Introduction to Autonomous Mobile Robots
Authors: Roland Siegwart and Illah R. Nourbakhsh
ISBN Number: 0-262-19502-X
Publication Date: 2004
Publisher: The MIT Press

Title: Cambrian Intelligence The Early History of the New AI
Author: Rodney A. Brooks
ISBN Number: 0-262-02468-3
Publication Date: 1999
Publisher: The MIT Press

1. Introduction

Both of these are Bradford Books from MIT Press. Siegwart & Nourbakhsh are researchers at the Swiss Federal Institute of Technology Lausanne (EPFL), and Carnegie Mellon University's Robotics Institute (CMU). Their book is primarily a technical survey book, heavy on math, well developed and detailed: a classic engineering textbook.

Brooks is Director of the Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory (CSAIL). His book is a collection of previously published papers, part technical (though not highly so), and part philosophical, with new introductions by the author.

1.1 Two Approaches to AI

In their treatment of the field of robotics and artificial intelligence, these two books represent radically different approaches. The Siegwart & Nourbakhsh book examines the traditional AI techniques for robotics, with only a cursory (and dismissive) acknowledgment of the behavior-based paradigm which is the fundamental theme of Brooks' "New AI."

Brooks, on the other hand, dedicates over half of his book to a systematic indictment of the shortcomings of traditional AI, which he sees as stemming from the nature of the assumptions that are built into the research. He concludes with an encyclopedic summary of the history of AI and its application to the field of robotics.

1.2 Mobile Robot Navigation

Both books focus primarily on the problems of autonomous mobile robot locomotion and navigation. And herein lies the crux of the disparity of the two approaches. Traditional AI assumes the existence of an internal model of the world, and does its planning and execution based on that model. The New AI paradigm asserts that "the world is its own best model" and attempts to map sensor inputs directly to actions, with no intermediating internal representations.

While acknowledging mobility and navigation as subsets of more sophisticated robot behaviors, the inherent tasks of sensing, vision, navigation, and goal orientation remain unique and vexing problems on the way to more general purpose robotics.

Brooks describes these problems with a biological analogy:

Evolution took 3 billion years to get from single cells to insects, and only another 500 million years to get from there to humans. This statement is not intended as a prediction of our future performance, but rather to indicate the nontrivial nature of insect level intelligence.

Hence the title of his book, "Cambrian Intelligence."

1.3 Experimental Evidence

Both books rely heavily on examples from experimental robotics; Brooks primarily at the MIT-CSAIL, and Siegwart & Nourbakhsh primarily EPFL and CMU. Both books draw extensively on the history of modern mobile robots, and especially the "Shakey" robot developed at the Stanford Research Institute in the late 1960s.

Siegwart & Nourbakhsh see Shakey as the archetypal mobile robot: one able to sense its (simple and carefully controlled) environment with enough fidelity to build useful models for subsequent planning and execution. Brooks sees Shakey as the beginning of a long detour away from true real-world and real-time autonomy, through simulations and overly simplistic, and therefore misleading, problem sets.

The Siegwart & Nourbakhsh book is highly theoretical and mathematical. Most of the examples and references given involve computer simulations and robots in highly artificial environments. Brooks' book is more prosaic, with little formal math, and most of the examples given are of robots designed to operate in unstructured, though usually, but not always, indoor environments.

2. Annoyances

2.1 Cambrian Intelligence

The Brooks book has a surprisingly large number of typos, misspelled words, and what appear to be randomly scattered extra periods. throughout. the text. This is quite unexpected for papers that have been published in reviewed scientific journals.

For example, Brooks remarks that one of the papers, "Learning a Distributed Map Representation Based on Navigation Behaviors," by Maja J. Matac and Rodney Brooks, is "very confusing to many people." Indeed, I found this paper the most poorly written of the collection, with the highest density of errors, and the least clear prose. Given that the topic itself is difficult, the poor proof reading and editing certainly doesn't contribute to the enhancement of understanding.

Further, perhaps because these papers were originally published in specialized journals, many of the acronyms are never defined or explained in the course of the text. Though this may be a reflection of the poor education of this reader, it is nonetheless annoying.

(I did, with great timidity, send a brief note to Dr. Brooks expressing appreciation for his work, with an attached list of the typos and errors encountered. But I got no reply...)

2.2 Introduction to Autonomous Mobile Robots

The Siegwart & Nourbakhsh book is not for the mathematically faint-of-heart. The reader should be comfortable with vector math and calculus and have a passing familiarity with information theory and statistics. I found it useful to have a pad of paper and a pencil nearby. The book also struck me as excessively wordy, a difficult read when contrasted with Brooks' more readily flowing prose. Mark Twain's famous advice to young writers came to mind as I toiled my way through their lengthy descriptions and analysis: "Brevity enhances lucidity."

More bothersome in the context of this dual book review, Siegwart & Nourbakhsh, in their brief treatment of the "behavior-based" paradigm of modern robotics, seem not to understand the approach they are so ready to dismiss.

For example, in their introductory chapter, they describe one of the famous robots from Brooks' lab at MIT: Genghis.

2.2.1 Genghis

Genghis is a commercially available hobby robot that has six legs, each of which has two degrees of freedom provided by hobby servos... Such a robot, which consists only of hip flexion and hip abduction, has less maneuverability in rough terrain but performs quite well on flat ground. Because it consists of a straightforward arrangement of servomotors and straight legs, such robots can be readily built by a robot hobbyist. [S&N p28]

Now, ignoring for the moment the implied slight to the skills of robot hobbyists, this paragraph is not accurate. Genghis is not a "commercially available hobby robot." Its design demonstrated one of the first examples of truly complex behaviors (i.e., multi-legged walking gaits) emerging from a simple set of distributed control structures.

Compare their description with that of Brooks himself:

Genghis (Brooks 1989) is a 1Kg six legged robot which walks under subsumption control and has an extremely distributed control system. The robot successfully walks over rough terrain using 12 motors, 12 force sensors, 6 pyroelectric sensors, one inclinometer, and two whiskers... It directly implements walking through many very tight couplings of sensors to actuators...and we believe its robustness in handling rough terrain comes from this distributed form of control. [Brooks p122-123]

Genghis now resides in the Smithsonian Air and Space Museum.

2.2.2 Subsumption

Similarly, the authors brief attempt at a description and subsequent critique of Brooks' layered "subsumption architecture" seems also inaccurate. For example, in their chapter on robot localization, they state:

...the addition of each new behavior forces the robot designer to retune all of the existing behaviors again to ensure that the new interactions with the freshly introduced behavior are all stable. [S&N p192]

But as Brooks explains his behavior-based approach to robotics, he takes great pains to define a methodology which builds intelligence as a series of independent layers of control. And he stresses that new layers are added WITHOUT the necessity of modifying the existing layers. Unlike the traditional AI monolithic approach to robot intelligence, this is one of the great strengths of the layered subsumption paradigm.

The Brooks chapter entitled "Robust Layered Control" defines this methodology informally in the following way:

The key idea of levels of competence is that we can build layers of a control system corresponding to each level of competence and simply add a new layer to an existing set to move to the next higher level of overall competence. We start by building a complete robot control system which achieves level 0 competence. It is debugged thoroughly. We never alter that system. [Brooks p10]

My own experience with subsumption vs. monolithic robotic control systems tends to bear this out.

2.2.3 Straw Men

In rhetoric, that type of argument is termed a "straw man." The authors setup a misrepresentation of an idea, and then refute the misrepresentation.

Their other criticisms of the behavior-based paradigm are equally weak. For example, they state that "the navigation code is location specific," and "the method does not directly scale to other environments." This is not only wrong, but the opposite is actually more true of the behavior-based approach.

Indeed, it is the traditional AI map-dependent and feature-dependent robot navigation algorithms, based on internal representations, that tend to be tightly coupled to specific and highly artificial environments, as the authors themselves acknowledge in their final chapter:

Of course, as the complexity of a robot increases (e.g., large degree of freedom non-holonomics) and, particularly, as environment dynamics become more significant, then the path planning techniques described above become inadequate for grappling with the full scope of the problem. [S&N p271-272]

To paraphrase: when a real robot constrained by real wheels and motors and physics is removed from its simplified artificial environment and placed in the real world, these complex algorithms don't actually work.

3. Praise

3.1 Siegwart & Nourbakhsh

The most informative chapters of this book were the detailed descriptions of robot platforms and sensor technologies.

3.1.1 Platforms

Siegwart & Nourbakhsh present an almost complete overview of mobile robot platforms and their kinematics. With examples and mathematical expressions defining each mode of locomotion, they describe various strengths and weaknesses of a variety of physical approaches to mobility, treaded, wheeled and legged.

I say "almost complete" because I was amazed and dismayed to see my own interest, two-wheeled dynamically balancing robots, not mentioned at all.

(See http://www.geology.smu.edu/~dpa-www/robo/nbot).

I assume this oversight reflects lack of knowledge rather than overt antipathy. It also may be that researchers within a given field don't often look outside of that field and its conferences and journals.

3.1.2 Sensors

The authors present an excellent overview of the most common robot sensors and concepts in sensing and perception. There is an in-depth analysis of sensor errors and noise and methods of modeling and offsetting measurement uncertainties, complete with equations and references.

3.1.3 Vision

Especially useful is their summary of computer vision and imaging processing methods, with a detailed set of references for each technique described, along with strengths and weaknesses.

Although the subject of computer vision encompasses much more than can be included in an introductory book on robotics, the authors do an excellent job of covering the main elements of the field and providing multiple references for readers interested in a more in-depth study. Great stuff.

3.1.4 Navigation

The sections on robot localization and navigation are really the meat of this book, and are quite complex. In light of the arguments that Brooks presents against such an approach, it is an enlightening look into why these techniques may not have produced more in the way of real-world fruit.

In particular, these sections are likely to scare away timid robot builders, and convince others that the problems are so difficult as to be insurmountable. Brooks would probably say that they are indeed insurmountable.

3.1.5 Obstacle avoidance

On the other hand, the authors' coverage of the "Bug" obstacle avoidance algorithm, along with other common approaches to obstacle avoidance, provide a simple and well documented starting place for real-time methods of robot navigation.

Taken together with their suggested improvements on the basic techniques, they supply a very useful and pragmatic tutorial in the midst of an otherwise highly theoretical manuscript.

3.2 Brooks

The technical articles which make up the first half of "Cambrian Intelligence" describe Brooks' behavior-based paradigm and the underlying "subsumption" architecture. They are really needed to lay the groundwork for the philosophical papers that follow. It is in the second half of the book that Brooks' ideas are most powerfully manifest.

3.2.1 Biological Systems

In these papers he argues that the approaches of traditional AI research have stalled because of incorrect assumptions on which this research is based. Specifically, that "traditional Artificial Intelligence offers solutions to intelligence which bear almost no resemblance at all to how biological systems work." [Brooks p135]

3.2.2 Representation

In the chapter entitled "Intelligence Without Representation" he further states:

Artificial Intelligence research has foundered on the issue of representation. When intelligence is approached in an incremental manner, with strict reliance on interfacing to the real world through perception and action, reliance on representation disappears.

and he observes with some irony and humor that:

Representation has been the central issue in artificial intelligence work over the last 15 years only because it has provided an interface between otherwise isolated modules and conference papers. [Brooks pp79,81]

Additionally, he suggests that some recent progress in traditional AI has been illusory, based more on increases in computing power than advances in the field.

Most fundamentally, he posits that "internal world models which are complete representations of the external environment, besides being impossible to obtain, are not at all necessary for agents to act in a competent manner." [Brooks, p64]

3.2.3 Robots in the Real World

This observation has far-reaching consequences for robot design and implementation. For example, robot hobby clubs have in general fallen into the same mindset that Brooks attributes to the AI community in general. "The problem with this approach is that the solutions to the "puzzles" [i.e., robot contests - dpa] become so domain specific that it is hard to see how they might generalize to other domains."

It is disastrous to fall into the temptation of testing ... in a simplified world first, even with the best intentions of later transferring activity to an unsimplified world. With a simplified world (matte painted walls, rectangular vertices everywhere, colored blocks as the only obstacles) it is very easy to accidentally build a submodule of the system which happens to rely on some of those simplified properties. This reliance can then easily be reflected in the requirements on the interfaces between the submodule and others. The disease spreads and the complete system depends in a subtle way on the simplified world. When it comes time to move to the real world, we gradually and painfully realize that every piece of the system needs to be rebuilt. Worse than that, we may need to rethink the whole design as the issues may change completely. [Brooks p91]

Sound familiar?

Several of the hobby robotics societies have recently made strides in moving away from such specialized environments. The Portland Area Robotics Society announced plans for a contest to navigate the hallways of a large building. The Seattle Robotics Society has a new contest which moves the robots outdoors, although they have not been able to totally let go of artificially designated targets, and the robots thus produced will still be dependent on the presence of specialized markers to achieve their goals. More recently the Dallas Personal Robotics Group has discussed an outdoor contest to circumnavigate The Science Place at Fair Park.

All of these new events rest on the realization that specialized contests have not led to generalized solutions, but rather to more and more specialized solutions: robots that can operate nowhere outside of their specialized contest courses.

Siegwart & Nourbakhsh observations to the contrary notwithstanding, their location and navigation examples all depend on highly optimized environments without clutter or moving obstacles and with clearly defined features and landmarks.

Brooks argues instead for "Situatedness" and "Embodiment" in the real world as necessary elements for any artificial intelligence, robotic and otherwise, to succeed, and offers examples from his own work at the MIT Artificial Intelligence Laboratory in evidence.

Essentially these twin concepts mitigate against robotics research which is highly dependent on simulations and stylized problem sets. It argues for robots which exists as actual agents in the real world, interfacing with all the complexities, surprises, and history that the real world implies.

3.2.4 Intelligence without Reason

The final paper in the collection, titled "Intelligence without Reason" is a masterful summation of the field of AI from its earliest pioneers to the present day. It defines in a detailed way why Brooks believes that traditional AI approaches have not and cannot succeed. Included are reflections on robotics, computer science, biology, ethology (animal behavior), psychology, neuroscience, and philosophy.

Brooks concludes with a set of definitions and axioms of the "New AI" which he offers as a window into his own work, and as a guide for the future of research in robotics and artificial intelligence:

• The world is its own best model.
• The world grounds regress.
• Intelligence is determined by the dynamics of interaction with the world.
• Intelligence is in the eye of the observer.

An excellent and persuasive read.

4.0 Conclusions

These two books are in a sense complementary. Each demarcates an area of robotics research that has seen vast amounts of energy and resources invested over the years. Each argues for the effectiveness of its own approach to problem solving, and suggests possible new areas of exploration.

My own biases tend to align with the approaches championed by Brooks and his "New AI" paradigms, in part because of previous successes I have had with these methods.

The future of AI and robotics probably lies somewhere in the middle, as both books eventually conclude in one way or another.

16 August 2004
Denton, Texas
dpa