What is Subsumption?

A likely story! What did you really do with all those parts? Where's my tinfoil hat?

Well, we missed you Saturday. Nobody could do even the simplest exercise -- too much debating, not enough building. I handed out some "I can turn my robot on!" awards.

cheers, dpa

I've done that. With time running out on the deadline, and my hair turning grey on the spot, I've removed the fuse and claimed massive electronics failure. But, of course, Randy doesn't use fuses.

I'm rather late in this discussion and would like to add a few comments about subsumption in addition to those already given.

1. Brook's caused a revolution in robotics in the mid 1980's with his subsumption architecture because his robots were the only ones that could run in real environments in real time.

1. The current three level architectures essential use the basis of the subsumption architecture, tight coupling of sensor and actuators, some times termed reactive, in the "lowest" layer.

2. The subsumption architecture was supposed to be stateless and not use reperesentation; it did however use "augmented" FSM; the augmentation was a time out, so in a sense the state had a short "memory"

1. Most of the posts talk about some feature of implementation and some of the likely problems with interrupting behaviors. I think the "augmentation feature" may ameliorate that.

2. Also most people who implement subsumption do it on a single processor and this seems to create its own problems. I started a hardware implementation. I wanted to have each behavior use its own microcontroller, no interrupts The arbiter "merely" needs to know, for mobility, two motor commands. In order for each behavior to communicate its output to the arbiter without using interrupts or networks, I used a priority encoder and a data selector. When a behavior has completed its cycle and wants to send motor commands to the arbiter, it sets its activity line to the priority encoder high. The output of the encoder (3 its to negotiate eight behaviors in this case) goes to the data selector which then selects the motor commands, which come in serially from the behavior, and sends it to the arbiter. The arbiter monitors its serial input for the commands. A behavior will keep sending its commands, with a frequency depending on long it takes it to process its sensor inputs, as long as it is active. This may result in the arbiter serial line having a command from one behavior interrupted by that from another. However, the arbiter looks for a valid start character followed by valid commands. As long as it can do this fast enough to prevent input buffer overflows, all is well.

I tried this out using five BasicX microcontrollers running five different loops with different time scales; one was triggered by a button press. The output of the arbiter was connected to a motor controller turning wheels on a real robot, albeit on a stand. All seemed to work as planned - the motors changing direction and speed according to the various loops. Each BasicX would light an LED when its behavior was active so that the wheel motion could be compared to the behavior in that micro. Unfortunately, I haven't yet implemented behaviors on the robot. Work in progress.

John-

Actually, by then, more centralized robots were working in real time, but not many of them. The "plan, then execute" people were still influential back then, and many of the planners weren't real time.

That's really just hierarchial control. Most industrial control systems are hierarchical in that sense.

The stateless thing was more of a Connell thing. For his PhD thesis, he built a robot to find empty soda cans and dispose of them. The thing had very little internal state; if the hand had a can in it, the goal was to find the trash can; if the hand was empty, the goal was to find another can. This was to explore the limits of stateless systems, his PhD topic. It wasn't really a useful direction.

The "no representation" thing was a major feature of subsumption architectures. But back then, mapping systems weren't very good, although Moravec at CMU had done some good work. Now that the "simultaneous localization and mapping" problem has been to some extent solved, mapping is working much better.

The basic problem with the "no representation" approach is that you'll never get beyond insect-level AI that way. It's just too dumb.

Conflict between behaviors is tough, if you're trying to do anything complicated. If you have some hysteresis in the behavior switching, things work better.

Brooks had one M68000 CPU per leg, communicating using an I2C loop.

John Nagle Animats

This is the main problem that Randy and I were discussing. Although the built-in timeout feature will cause an "individual" state to be vacated after a short time, many of the behavior examples shown in Jones' books were built using FSMs with a "number" of sequential states, which were cycled through on a timed basis.

Therefore, if such a behavior had been begun, and shortly thereafter was interrupted by a higher priority behavior, the interrupting behavior would execute and complete, but then the machine would return again into the "middle" of the sequence of the interrupted behavior. However, this would probably no longer be appropriate.

Eg, BEH1 = the machine is bending over to pick up a block or something. BEH2 interrupts and causes the machine to turn 90-degrees. BEH2 finishes, and BEH1 resumes from where it left off, but this is no longer relevant to the new machine orientation, as it is no longer pointed at the block.

You can partly get out of this dilemma by using a very fine partitioning of behavior actions, such that none involves an actual "sequence of operations', but rather each is just a simple movement. But then the machine is very whimsical.

Randy and I were discussing that it seems the correct way to get out of the problem described is to have BEH1 reset back to its state-0 when interrupted, so it will not resume later in the middle of the sequence. However, this feature of resetting to state-0 didn't seem to appear anywheres in Jones' example discussions in his books.

IOW, if you actually want the machine to perform something more sophisticated than finely-parititioned behaviors, then you need something else superimposed on top of the basic subsumption scheme.

Exactly.

Are you speaking from experience? If so, what task did you attempt?

Or have you just not been able to envision how it might be done?

Just curious. I hear this sentiment offered a lot, but never with any evidence. So I'd be very interested to hear of your actual experience, if that is the basis of your opinion.

best regards, dpa

Well, I did run a DARPA Grand Challenge team, Team Overbot.

John Nagle

John Nagle wrote

Hi John,

Yes, I followed the progress of team Overbot. I think one of our DPRG members, Ed Okerson, was also involved in some way?

If I understand your reply, you are saying the DARPA GC is the task that you attempted to solve with a subsumption-style architecture and were unable.

Do you think the DARPA GC task requires more than "insect-level AI?" If so, why?

best, dpa

I can't speak for John, but if you look at what Thrun and the stanford guys did, they built up several different "internal maps" of the road ahead, using different types of sensors, and overlaid these maps to "predict" the best course.

This falls under the caveat of "building internal representations", and is exactly the opposite to the sorts of things that Brooks was advocating in his many papers on subsumption and reactive architectecture.

As I've mentioned a couple of times, when you are asking what cannot be done using subsumption techniques, you are really talking about "extensions" to subsumption, not the original thing. That's how I see it. To me, subsumption per se is just the lowest foundation level in a hierarchical chain on the way to building real intelligence.

Hi Dan,

Thanks for the reply.

To be clear, are you replying to the question:

And as a teaser I included a link that describes the migration of monarch butterflies, that perform a much more complex task than the DARPA GC, and are, after all, working with "insect-level AI"

Also might be useful to google "honeybee navigation" as an example of what "inset-level AI" can do.

Dan, can you address this question specifically? And John as well?

thanks dpa

dan michaels wrote:

Now, you're kind of mixing things. Is there an implicit assumption you're making that insects are simple Brooksian-style subsumption machines? I seriously doubt it. They are much more than that. They have memory, and their perceptual systems are somewhat more advanced than we might give them credit for. They probably have internal representations - sensory maps.

This is regards more complex insects and arachnids. The very simple bugs are probably more on a par with Brooksian subsumption ideas.

Regards the Darpa challenge, from what I've seen of Thrun's solution, it was a specific solution intended to solve a specific problem, and probably wouldn't work in more "general" situations. EG, to solve the next Darpa challenge, of negotiating busy city streets, will take a lot of additional work on top of the existing system.

One thing both old and new DCs involve is predictive capabilities far beyond that any insects need. Eg, if you're driving down a road or busy city street at 30 MPH, you need to predict both the road ahead and actions of other moving objects for the next few seconds into the future. Some predatory arthropods, like hunting spiders for instance and probably dragon flies, can do some of this, but they don't do it 100 yards and 5-10 seconds into the future. The Darpa vehicles will need much more sophisticated perceptual systems, and internal maps and processing power for this. You wouldn't want a bee driving your car in rush-hour traffic, with your baby in the back seat.

Not at all. I was replying to your own post:

that posits that "no representation" and "insect-level AI" are associated, and consequently "too dumb" to do any compex task, to which you repled:

which led me to think that you agreed. Am I misunderstanding something here?

I asked for an example of a task that insect-level AI was "too dumb" to solve, and the example offered was the DARPA GC.

So I was asking now if you believe the DARPA GC requires more than insect-level AI, and why. If I understand your reply, you believe that it does.

I find that astounding. The monarch butterflies previously referenced fly a journey twice a year of thousands of miles between two exact geographical locations over many weeks. They land each night and forge for fuel. They avoid predators (I don't remember that part of the Grand Challenge!) and deal with headwinds and crosswinds that blow them hundreds of miles off course. And you wish to suggest that this is a LESS difficult autonomous task than the GC?

I supposed we'll have to agree to disagree here. But it seems to me that you are insufficiently impressed with the capabilities of our little insect friends.

best regards, dpa

Trapped. No way out. So, I'll have to put the blame on John for implying that Brooksian subsumption is essentially the same as insect neurology.

Actually, as I indicated last time, and to qualify my comments so more, Brooksian subsumption seems more on a par with the **simplest** of insects, not the more advanced forms. Eg, I have been reading up on jumping spider vision lately, and they have totally incredible visual systems. Their main eyes have vertical slit retinas that they "pan" back and forth horizontally inside the head using muscles to produce what amounts to a 2-D image. The lens is fixed to the carapace, but the retina moves behind the lens.

This gives them visual acuity which is on the order of 800x800, and touted to be about half that of humans, yet there entire brains have less than 100,000 neurons. Their visual systems have 3 successive processing centers in sequence, with retinotopic maps on each. Now, that's pretty incredible.

You must not have read my comment about more advanced versus simple insects from last time. Hunting spiders track down their prey in 3-dimensions, visually. Butterflies migrate. Most bugs aren't so clever.

Regards Thrun's Darpa solution, I already discussed that. It was a narrow solution for a narrow problem, and even so, they used the kind of internal representational maps that Brooks totally rejected.

Plus, they'll have to go one step better to plot a course through city traffic. Much better mapping, and much better analysis and predictive capabilities. IOW, another level up in perceptual capabilities. Do you really want a butterfly as your taxi driver? Bugs are those things you find smashed on your windshield in Texas.

If the taxi had the intelligenc of a butterfly, it would be the most sophisticated robot on the planet. We're nowhere near to that level with robotics and AI.

So yes, I think that is where we're going. A robot as smart as a honeybee will be a very challenging thing, a truly "grand" challenge.

They do pretty well in their own environment.

And don't forget that humans end up smashed on windshields every day, too, lest we get too prideful about our own abilities...

On a related note, I was thinking about interrupting ballastic behaviors as you and Randy were discussing, and it brought to mind something I'd read by Douglas Hofstadter about the behavior of the Sphex Wasp. Here's a brief description,

which says in part:

taking provisions into the nest, the Sphex first inspects the nest, leaving the prey outside. During the wasp's inspection of the nest an experimenter can move the prey a few inches away from the opening of the nest. When the Sphex emerges from the nest ready to drag in the prey, it finds the prey missing. The Sphex quickly locates the moved prey, but now its behavioral "program" has been reset. After dragging the prey back to the opening of the nest, once again the Sphex is compelled to inspect the nest, so the prey is again dropped and left outside during another stereotypical inspection of the nest. This iteration can be repeated again and again, with the Sphex never seeming to notice what is going on, never able to escape from its genetically-programmed[citation needed] sequence of behaviors. Douglas Hofstadter and Daniel Dennett have used this mechanistic behavior as an example of how seemingly thoughtful behavior can actually be quite mindless, the opposite of human behavioral flexibility that we experience as free will (or, as Hofstadter described it, antisphexishness).

It seems like the wasp has a series of "ballastic" behaviors which, when interrupted, reset to the beginning, as you (Randy?) suggested.

It occurred to me that the bumper behaviors on a couple of my robots do the same thing. An interrupted ballastic bumper behavior just resets from the beginning, and the ballastic pattern starts over.

So I think perhaps you're on to something here. Maybe this is a general principle for interrupted "ballastic" behaviors? As you have observed, what other response makes sense?

best, dpa

Your cabby for today is Mr. Bfly. but you still wouldn't want it driving the taxi you're stting in, or the one that coming from the other direction either. It needs to advance a bit beyond the B.Fly stage, before you're gonna get in the cab.

Exactly, and this isn't sitting in a class on calculus or driving in traffic, either.

Pound for pound, you find more philosophers involved in car accidents than common folk. I just made that up. Actually, physical grounding - as opposed to not paying attention - is a critical matter.

Before taking provisions into the nest, the Sphex first inspects the nest, leaving the prey outside. During the wasp's inspection of the nest an experimenter can move the prey a few inches away from the opening of the nest. When the Sphex emerges from the nest ready to drag in the prey, it finds the prey missing. The Sphex quickly locates the moved prey, but now its behavioral "program" has been reset. After dragging the prey back to the opening of the nest, once again the Sphex is compelled to inspect the nest, so the prey is again dropped and left outside during another stereotypical inspection of the nest. This iteration can be repeated again and again, with the Sphex never seeming to notice what is going on, never able to escape from its genetically-programmed[citation needed] sequence of behaviors. Douglas Hofstadter and Daniel Dennett have used this mechanistic behavior as an example of how seemingly thoughtful behavior can actually be quite mindless, the opposite of human behavioral flexibility that we experience as free will (or, as Hofstadter described it, antisphexishness).

What the wasp doesn't have is the kind of Minsky B-Brain I mentioned in the past, whose job it is to monitor the A-brain [execution module] and critically ascertain when it's going in repetitive loops, or other simple forms of pathological behavior.

If you were to analyze what you have "actually" implemented, as opposed to what you thought you were implementing, you might find it differs somewhat from what Brooks actually described.

Also, I was actually discussing more complex behaviors, eg, where an individual behavior is set up as a "sequence" of timed states in an augmented-FSM, and the sequence is interrupted in the middle, but it's a general problem that needs be addressed to produce more intelligent behavior, through use of planning modules, for instance. Simple subsumption bots don't plan or predict, rather they react, by definition.

You need memory + overseers to deal with pathologic loops, and memory + internal representations, coupled with good perceptual systems, to produce predictions.

Yes, very much as the Sphex wasp is doing. I thought I was agreeing with you here. ;)

Not completely true. For example, a Kalman filter used to balance a two-wheeled robot, such as my "purely reactive" nBot robot, makes predictions as part of the sensing process. That's how a Kalman filter works. These distinctions are not as cut and dried as you seem to suggest, but more on this below:

Go back and re-read the references in Jones' "Robot B ehavior" book in which he describes how to use a "leaky integrator" to control various robot functions.

I use these throughout my robot code. This is essentially an analog form of memory, that contains information not only about what the robot is doing now, but also about what it has done in the past.

These are used in much the same way as the "B mind" you describe, to monitor other behaviors and switch modes when needed. Jones does not seem to think that this information and technique are outside of the definition of subsumption What is your disagreement with Jones? Why do you believe that "leaky interators" are part of the standard subsumption model for Jones? But not for you?

Perhaps more to the point, If you'll indulge me, I'd like to quote Brooks hisownself one more time, from "Cambrian Intelligence" (pp 64), where, most fundamentally, he concludes 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."

It does not seem that you believe this is true.

Now, at the riisk of sounding pompous, I have a robot that I believe is capable of considerably more complex navigation tasks than the DARPA GC, is a purely reactive robot, including reactive waypoint navigation, and which is also considerably l ess intelligent than a honeybee. Hence my skepticism.

So all this is what led to my original query, which is, have you actually tried to accomplish a compex task with subsumtion and failed, and that is the basis of your belief? If so what task? If the GC is the task, then I simply disagree that it is not solvable with simple subsumption.

best, dpa

Yeah, the wasp seems to reset its behavior, rather than pick up again in the middle of the previous sequence. So, that part is good [and not part of Brooksian subs, as I see it]. The bad part is that it doesn't have something like a B-brain to keep from "mindlessly" repeating the same behaviot again and again.

Well, I was thinking of more long-range prediction, like predicting where a car that is 100 yeards ahead and traveling at 60 mph will go. That takes a lot more capability. EG, just in order to recognize it's a car, and then where it'll be going.

I'll check this when I'm back home.

This is actually the point I have been trying to make for weeks. What is "competent manner", and what is the level of the task being executed? EG, ask what was the most complex task one of Brooks' bots ever did?

Of course, I do, but you need to put it into perspective of what was being accomplished.

Well, you should brag, but also ask whether it really is a purely reactive bot, and if it is, how far can you really take the technology. That's where our real disagreement is.

Alternately, you might ask how far Brooks actually got along the path towards creating truly intelligent bots since 1985 or so.

Ok, do the next one. Driving a normal speed in heavy city traffic. Finding your way from one end of Dallas to the other. Reading the names off the store fronts as you go along. Noting that store X has a new display in the window. Going down to campus and taking a calculus test. Why aren't Brooks' bots doing these things? That's what you should be asking.

There is an appendix "C" in my copy of Jones "Robot Programming" titled "Frequently Used Functions" that covers the leaky integrator and also how to implement running averages, another form of "memory."

I think that's probably do-able.

My current little robot can find it's way from one end of the SMU campus and back, avoiding students and such along the way, and across Fairpark in Dallas. So, just send money...

Now that's silly.

Why indeed? Why not sing, dance, play the clarinet, write the great American novel and bake apple pies like-a my momma? I think Brooks' and Jones' goals are much more modest. I know mine are.

Brooks, in "Cambrian Intelligence," while acknowledging mobility and navigation as subsets of more sophisticated robot functions, describes the inherent tasks of sensing, vision, navigation, and goal seeking that remain unique and vexing problems on the way to more general purpose robotics. He uses this biological analogy:

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

It seems to me that insect level intelligence is a _lofty_ goal for our robots, and one that we are a long way from achieving.

Read up about the honey bee. "The Honey Bee" by Gould and Gould, (Sci. Amer Press) is a little dated but a good starting place. Or just google "honey bee." Gould&Gould say it's the "most studied insect"

Enjoy your holiday feast, dpa