All of our team members are from the University of Virginia. We are:
Frank Brill (me!) Grad. Student brill@virginia.edu
John Taylor Grad. Student jrt2q@virginia.edu
Tom Olson Asst. Prof. olson@virginia.edu
Our robot was named "Bottom Feeder", and came in second place in the
"Escape From the Office" event; we didn't enter the other event for
reasons which will become obvious. This report begins with a
"philosophy" section (which you can probably skip if you're so
inclined), followed by a description of our robot. Then there is a
section on how we fared in the contest, and the report wraps up with a
few observations.
Turn right 90 degrees
Go forward 24 inches
Turn left 90 degrees
Go forward 18 inches
Turn left 90 degrees
Go forward 36 inches
Turn right 90 degrees
Go forward 12 inches and into home
The above plan only works for configurations where the robot starts in
the office on the right and the side door is open; it can easily be
made to work for a left sided starting position by inverting the lefts
and rights. It must be preceded by a strategy for determining whether
the front or side door is open; if it is the side, the above plan is
invoked, otherwise the alternate "front-door" plan is used, which
probably consists of nothing more than "go directly to the goal."
Please correct me if I'm wrong, but I believe most robots entered used
a variant on the strategy above, augmented by homing in on the beacon
at the goal to attempt to verify position after each step is executed.In an relatively simple event such as this where it's feasible, dead-reckoning is often the most effective strategy; certainly it's the prettiest, when it works. But when dead-reckoning fails, it fails badly. The problem is that whereas the plan steps are specified in degrees and inches, they are implemented by turning on the motors at a given speed for a given amount of time. Hopefully, this corresponds to degrees and inches, but it doesn't always, due to various real-world nasties like friction and imperfect surfaces. (You can of course use shaft encoders. Did anyone actually do that?) If these realities cause you to deviate from the plan far enough to, say, run into a wall, it's difficult to recover.
We were more interested in trying a layered approach in the style of Brooks et al. In this approach, low level "reactive" behaviors are built and debugged, and are then overlaid with additional behaviors. The combination of the layered behaviors form the overall behavior of the robot. In Brooksian robots, the lowest level behavior is usually a "stay-away-from-things" module, which causes the robot to move towards the middle of the room. Layered over this is a "wander" behavior that causes the robot to pick a random heading and start moving in that direction. The "wander" behavior "subsumes" the "stay-away-from-things" behavior when the robot isn't in imminent danger of running into something. Next is an "explore" module that makes the robot go to far away places. Over all of this are specific behaviors such as "go-to-a-dark-place" or "find-a-coke-can."
The "go-to-the-IR-beacon" behavior was implemented in two parts: a servo-controlled "head" process which tried to point a steerable head at the IR beacon, and a motor-control process that tried to align the body with the head. These processes communicated solely via the proprioceptive sense of the head position.
front
| |
| |
| |
^^|^^|^^
-- -- --
|IR|IR|IR|
-- -- --
Bottom Feeder's Head
Sensors detecting IR | Head Process Action
--------------------------------------------
Left only | Turn hard right
Left and center | Turn slightly right
All three | Hold position
Right and center | Turn slightly left
Right only | Turn hard left
None | Wag head from side-to-side
Anything else | You're lost, proceed as for "None"
The Behavior of the Head Process
The primary function of the "go-to-the-light" process was to set the turn-speed to a value proportional to the deviation of the head angle from straight ahead and move forward at half-speed. This, in combination with the head's behavior, caused the robot to "go-to-the-light", wherever it was. I think that this behavior made Bottom Feeder's movements seem more smooth and less "robotic" looking than many of the other entries. The head swiveled smoothly and the body rounded corners gently.
With both the "head" and "go-to-the-light" processes running, Bottom Feeder could be led around the room with a hand-held IR beacon. The head swivelled rapidly to follow movements of the beacon, and the body turned more slowly to keep moving in the right direction.
Avoid-obstacles was our highest priority process. Whenever a contact sensor was pushed, avoid-obstacles killed any currently running "avoid" process and launched a new avoid process whose action was determined by the contact switch values. Usually the action consisted of backing and turning. The avoid process set the desired motor speeds in the high-priority slots, slept for the requested amount of time, and finally cleared the high-priority slots and exited. This scheme had the nice property that if a collision occurred while an avoid behavior was in progress, we were still prepared to react appropriately by killing the old process and starting a new one.
Bottom Feeder had a lego "bumper" in the front, and several of the long metal contact switches in the front corners and along the sides. These long push buttons looked like catfish whiskers, and gave Bottom Feeder its name. There were also push buttons in the rear, although they weren't needed very often. Each of these sets of sensors invoked a unique appropriate behavior by calling a "back-up-and-turn" procedure with the appropriate parameters.
The "go-out-the-side-door" behavior was implemented by subsuming the default behavior of "go-to-the-light". Normally "go-to-the-light" tries to orient the body so that the head is pointing straight forward. "Go-out-the-side-door" simply changed the head/body angle maintained by "go-to-the-light" from 0 degrees to +/-90 degrees, depending on which office we start in. This has the effect of causing the robot to maintain a course normal to the direction of the beacon, circling around the wall and out the door in a large arc. When we exit the door (as determined by dead-reckoning, unfortunately) this behavior is terminated by resetting the base angle to zero, allowing the default "go-to-the-light" behavior to resume. (Actually, we then set the angles to "slightly outward" for a while, followed by "slightly inward" for a while in an attempt to avoid the corners.)
I was ready to throw in the towel, and in fact told Tom and John we were sunk. Then, about twenty minutes before the competition began, Lynn told me I could have another board. Bottom Feeder underwent a complete brain-transplant; the first rounds of the competition were starting when the transplant was completed and debugged. Then the intermittent resetting started again. I was crushed.
Luckily, Tom showed up (he'd eaten breakfast and gone to a conference session, can you believe it?) just as the transplant was completing. Having had the presence of mind to go to sleep the night before, Tom was able to diagnose the problem. The IR sensors were wired with stranded copper wire, and a few whiskers had escaped the solder ball. When the head moved in a particular way, they'd short across the IR sensor. That pulled down the power supply and caused a reset. Tom trimmed off the whiskers, and presto, no more resets. (I later found out that this is the first rev of the 6.270 board that detects low-power conditions and resets. Previous versions of the board would not have behaved nearly as well with this particular bug; it simply would have scrambled memory.)
In the first round, neither Bottom Feeder nor its opponent escaped from the office (Bottom Feeder lost the beacon while trying to go out the side door), and they were about the same distance from the goal. But since the other robot failed to stop after the required 60 seconds, Bottom Feeder won by default. I was pleased that it had started at all, but didn't expect to do much better on the next round.
I'm not sure of the exact sequence of what happened in the rest of the rounds, but here's a sketch of Bottom Feeder's runs. In all of the three other rounds before the finals, we drew the side-door configuration. In one of these, both Bottom Feeder and its opponent headed out the side door, rounded the turn too quickly, and wedged against the end of the wall. After straining against the wall for a while however, eventually one of Bottom Feeder's push buttons made contact. It bounced off the end of the wall a few times and eventually made it by, heading for the goal. Bottom Feeder then ran into the wall immediately to the side of the goal, and began what Dave Miller described as its "characteristic behavior." It hit the wall and fired off a back-and-turn process. When the process exited, Bottom Feeder homed in on the beacon and headed straight for it, causing it to run right back into the wall. It didn't run exactly into the same place, however; it moved slightly along the wall. The net result was a wall following behavior (although it looked pretty stupid). After bouncing off the wall for what must have been 8 or 10 times, Bottom Feeder rounded the corner and achieved the goal. Its opponent remained wedged to the end of the round.
In another round, Bottom Feeder actually lost the beacon while going to the side, and spent some time bouncing around hunting for it. In the meantime, the opponent robot quickly exited the office headed for the goal. Inches short of the goal, however, it just stopped dead, presumably a victim of hardware failure. While it sat there, Bottom Feeder continued thrashing around, eventually re-acquiring the beacon and escaping from the office. The crowd and I were amused to see Bottom Feeder come plodding up from behind; it was such a tortoise-and-hare situation. Just before reaching the goal, Bottom Feeder launched into its characteristic behavior, eventually making it around the corner and into the goal.
At the end of the third round, we were amazed to find that Bottom Feeder was one of only two robots entering the fourth round undefeated (DeathStar, the eventual winner, was the other). Bottom Feeder won its fourth round match; escaping from the office properly and displaying its "characteristic behavior."
The finals were between Bottom Feeder and DeathStar. Since it was a double elimination tournament, and both of these robots were undefeated, it was a best two out of three match. The first run was Bottom Feeder's only front door contest; it headed straight for the beacon as planned. It glanced off the edge of the door and the corner of the wall near the goal, but the avoid-objects reactions initiated by touching the "feelers" compensated perfectly, and Bottom Feeder won handily. It looked too easy, but of course, it wasn't. DeathStar headed directly for the beacon, but that angle takes you too close to the edge of the door, and instead of bouncing off, DeathStar jammed.
The final two runs were both side door contests. On both occasions, Bottom Feeder lost the beacon and wasted time thrashing around looking for it, while DeathStar forged smoothly ahead to win.
Congratulations to the DeathStar team (from Bell Labs) on their most excellent robot. Even during the early stages of the building process, it was obvious that they were the team to beat--they were testing a mechanically sound robot within hours of entering the lab. We were doing major structural rebuilds the day before the competition. This is probably a good lesson: fix it in software. It actually says that in the manual somewhere; we just had some trouble following that advice.
Mechanical design matters too. Bottom Feeder was studded all over with contact sensors, so it could almost always tell when it had hit something. Many robots lost because they hit a wall in a 'blind spot', and sat there heating their motors for the rest of the round.
I'm sorry we didn't enter the "coffee pot" event; we know from other people's posts that "office" software doesn't do so badly on the coffee pot task, and again I think that good reactive layers would have gotten us pretty far. We were pretty strung out by our hardware woes, and didn't realize until late in the game that Bottom Feeder was actually a pretty strong player.
Tom was an EE undergrad, and kept insisting that "hardware problems don't happen; it's always the software". That may be true for systems without moving parts, but for robots it's dead wrong (which Tom now admits). I spent the last seven hours before the contest tracking the IR sensor and spontaneous reset problems. If we'd been able to put that time into the software, I think we could have fixed the loss-of-track and 'characteristic behavior' problems. I don't know if we'd have beaten DeathStar -- it's a slick design, and proved very robust -- but we'd have given it a run for the money.
The 6.270 board is great, and in conjunction with IC, you almost feel like you could do anything. I am now over my initial fear of building physical robots, and for that reason alone I'd recommend the course to anybody. I learned a lot too, especially about sensors, motors, and other nuts and bolts electronic stuff.
The multiprocessing in IC is indispensable. It's really a major feat that it's there at all, but I'd like to see it extended. More process control besides start and kill would be good, e.g., suspend, resume, and set-priority. The multiprocessing that comes with Lucid Lisp might serve as a good model here. Also, implementing interprocess communication via global variables is asking for trouble. It gave us a few headaches, and I noticed in a different group's report that they had some trouble with it as well. It'd be really neat if IC supported subsumption directly, with input lines and side taps for each process.
I wish there had been more opportunity for interaction between the groups. I think it was a combination of the "competition" aspect and the very limited time that made us keep to ourselves. There may not be any way around this, but it is unfortunate. In particular, I'd like to know how other people architected their systems. Did other people rely as heavily on dynamic process creation/destruction as we did? Did other people use explicit process priorities?
All in all, it was a great experience. Every undergraduate computer science program ought to have a 6.270 course. Thanks a lot to Lynn and Dave (the event organizers), to Karsten, Carol and Matt (the TAs), and to the 6.270 founders and maintainers.