Interesting Bump and Wander

Why a drunken robot can be so interesting.

Purpose

This little tutorial will present how we build up an occam program to implement interesting behavior that takes significantly more effort in languages without a natural model of concurrency. In particular, we'll implement what we call the "interesting bump-n-wander," where a robot bumps at the front, and backs up until something is hit or a fixed amount of time goes by.

Background

In 2005, we submitted a paper to the ACM SIGCSE conference (Special Interest Group Computer Science Education) entitled Towards concrete concurrency: occam-pi on the LEGO Mindstorms (PDF). The paper is not required background reading for this tutorial, but it does provide some of the pedagogic motivation for our work, as well as a description of the problem we're implementing a solution for. This tutorial will take place on our RoboDeb virtual machine (no longer supported). The RoboDeb environment allowed us to prototype robotic ideas without having to recharge the batteries for the RCX, build a robot, and promptly run it off the table.

A little, virtual Pioneer3 in a virtual world.

By running a Pioneer3 in the RoboDeb virtual machine, we can quickly prototype ideas in occam-pi that can be copied directly onto our department's Pioneer3, as well as down onto the RCX. Of course, we have to swap out some processes in our network to handle different sensors, but the layout of our program remains fundamentally the same.

The Problem

We want our robot (we'll call him "Johnny0" to wander around the room, and behave as follows:

If something is bumped in the front, back up.
If backing up, and something gets too close, go forwards again.
If backing up for too long, start going forward again.

There are a number of ways we could implement this---it could be a strictly subsumptive solution, but for now, we'll implement a process network that is tailored to the problem. In short, we'll follow the solution we presented in our SIGCSE paper.

Wandering around

First things first. Lets get our Pioneer wandering around. I'm not going to implement a random walk; for now, we'll just move forward, blindly.

Johnny0: laser deployed, sonar at the ready.

#INCLUDE "player.inc"
#INCLUDE "pioneerutils.occ"

PROC main (CHAN BYTE kyb, scr, err)
  CHAN MOTORS moto:
  CHAN LASER sick:
  CHAN SONAR devan:
  PAR
    brain.stem(moto?, sick!, devan!, 6665)
    WHILE TRUE
      moto ! 10 ; 0 ; 0
:

Code to drive us straight forward

We do two important things: declare channels for communication, and declare processes that will execute. The channels (moto, sick, and devan) are necessary connections to the brain.stem of our robot. Then, we launch two processes, both of which will run forever: brain.stem, and a little process that sends commands down the motor channel.

Refactoring a trivial program

Now, typically, one would not refactor a trivial program like this. However, it is easier to depict what is going on in our programs if we give names to processes. So, I'm going to pull out the infinite loop from the process main, and instead create a new process, called motor.control. For now, it will only have one channel connected to it, which will be the motor control channel.

The code, after refactoring, looks like this:

#INCLUDE "player.inc"
#INCLUDE "pioneerutils.occ"

PROC motor.control(CHAN MOTORS moto!)
  WHILE TRUE
    moto ! 10 ; 0 ; 0
:

PROC main (CHAN BYTE kyb, scr, err)
  CHAN MOTORS moto:
  CHAN LASER sick:
  CHAN SONAR devan:
  CHAN INT nums:
  PAR
    brain.stem(moto?, sick!, devan!, 6665)
    motor.control(moto!)
:

Same code, refactored

Now, it's easier to draw a process network. That way, we can see the processes in our program and the connections between them.

Our initial network

In this initial network, we can see we have two processes, which are connected by a single channel called moto. Notice how brain.stem has two dangling channel ends; those represent the data coming out of the laser rangefinder and ultrasonic rangefinders; we'll have to connect those up, somewhere, if we're going to detect walls (they'll be our "bump" sensors). And, in truth, we should draw a big box around both of these called main, as that is the process that sets both of these running. However, since we are not actively using the keyboard, screen, or error channels provided by main, I'm going to leave it out of the diagrams for now.

Detecting a bump in the front

While it seems like we've done a lot of nothing so far, that isn't exactly true. We're currently running two processes in parallel: one which generates commands for the motors on our robot, and one which manages gathering data and shipping it out to our program while responding to motor commands. We wrote the first one, and the second (brain.stem) has been provided in a library.

Now, we'll plug in our front bump sensor. We'll use the laser rangefinder as our "bumper", and we'll use a library procedure from the Pioneer Sensor Library for grabbing the minimum value from the middle 60 degrees of the laser's sweep. This will involve two new processes, the first of which I'll call front.bumper, and the second (from the library) is laser.min.slice.

front.bumper

This process, surprisingly, won't consume the laser data itself; instead, we'll take the output of the laser, plug it into a process that grabs the minimum value from a portion of the data, and use another process to look for values that are less than 100; this would mean we're within 100cm, or 1m, of a wall. With a robot that costs as much as a Pioneer3, one meter is close enough for my tastes. Because laser.min.slice is doing the work for us, there won't be much to do here. Our only goal is to detect when we're too close to something, and send a boolean value down a channel. Otherwise, we'll be silent.

#INCLUDE "player.inc"
#INCLUDE "pioneerutils.occ"


PROC front.bumper(CHAN INT laser.min?,
                  CHAN BOOL too.close!)
  WHILE TRUE
    INT current.value:
    SEQ
      -- Read in the current value
      laser.min ? current.value
      -- If we are too close to the wall, shout!
      -- Otherwise, do nothing.
      IF
        current.value < 100
          too.close ! TRUE
        TRUE
          SKIP
:

PROC motor.control(CHAN MOTORS moto!)
  WHILE TRUE
    moto ! 10 ; 0 ; 0
:

PROC main (CHAN BYTE kyb, scr, err)
  CHAN MOTORS moto:
  CHAN LASER sick:
  CHAN SONAR devan:
  CHAN INT laser.min:
  CHAN BOOL front.too.close:
  PAR
    brain.stem(moto?, sick!, devan!, 6665)
    motor.control(moto!)
    laser.min.slice(sick?, laser.min!, 60, 60)
    front.bumper(laser.min?, front.too.close!)
:

Adding in front.bumper

In a picture, our network now looks like this:

Our network evolves.

Livelock!

If we run our network at this point, we'll run into an interesting problem: livelock! You see, our robot will run, and appear to be fine, but that is only because our motor.control process is happily sending data to the brain.stem. Our laser data handling isn't nearly so effective; unfortunately, the laser data gets pushed from the brain.stem to the slicer; this finds the minimum in the slice defined, and passes on that value to the next process. Everything is fine with front.bumper until it tries to report that it has moved too close to the wall. At this point, we learn something interesting about CSP (and therefore occam-pi) channel communications.

The communications between processes in occam-pi are point-to-point and synchronous. This means that any communication can only take place between two processes, and never more. Second, it means that any send of information over a channel (using the ! operator) will block until the corresponding read operation (using the ? operator) is executed. In this case, we end up with a string of writes and reads that ultimately block in front.bumper. When we get to close, it will sit, forever, waiting for someone to read from the channel called front.too.close.

So, we need to finish up some more of our network before we can run things. That, or write a process that consumes those values blindly (a black.hole, for example). For now, we'll push on.

Backing up

We could just plug the dangling channel called front.too.close into our motor.control process; we could let it make the critical decisions about what to do with the information given to it. This isn't an entirely unreasonable proposition.

Furthermore, we'll add some logic; if we detect something as being too close on the channel front.too.close, we'll start backing up. This will have to change in a moment, but it will allow our robot to exhibit some interesting behavior.

The network is good, but there's a problem in one of the processes.

#INCLUDE "player.inc"

#INCLUDE "pioneerutils.occ"

PROC front.bumper(CHAN INT laser.min?,
                  CHAN BOOL too.close!)
  WHILE TRUE
    INT current.value:
    SEQ
      -- Read in the current value
      laser.min ? current.value
      -- If we are too close to the wall, shout!
      -- Otherwise, do nothing.
      IF
        current.value < 100
          too.close ! TRUE
        TRUE
          SKIP
:

PROC motor.control(CHAN MOTORS moto!,
                   CHAN BOOL front.too.close?)
  WHILE TRUE
    BOOL front.status:
    SEQ
      front.too.close ? front.status
      IF
        front.status
          moto ! -10 ; 0 ; 0
        TRUE
          moto ! 10 ; 0 ; 0
:

PROC main (CHAN BYTE kyb, scr, err)
  CHAN MOTORS moto:
  CHAN LASER sick:
  CHAN SONAR devan:
  CHAN INT laser.min:
  CHAN BOOL front.too.close:
  PAR
    brain.stem(moto?, sick!, devan!, 6665)
    motor.control(moto!, front.too.close?)
    laser.min.slice(sick?, laser.min!, 60, 60)
    front.bumper(laser.min?, front.too.close!)
:

Despite being fully connected, there is still a problem.

Fixing livelock with ALTernation

If you were to remove the motor processes, the Transterpreter would die, and yell "Deadlock!". However, this is a small network; we can find the blockage that is still causing livelock.

The laser data leaves the stem, goes through the slicer, into the bumper, and then to the motor control. that's the idea, anyway. If we look at the front.bumper process, you'll notice something odd: it only sends a message when something is too close! This is, we think, good behavior, so perhaps it should be left that way. The problem, instead, should be solved in motor.control. And, we'll solve that problem with one of the most interesting ideas in occam: ALTernation.

Instead of blocking on a read, and asking if the value sent over the channel was (in this case) TRUE or FALSE, we could instead ask "Is this channel ready?" Then, if it is, we can take some action. Otherwise, we can implement a default action.

Below is a rewritten motor.control process that makes use of ALT. From this point forward, all the interesting things in our tutorial will take place here, in about five lines of code.

PROC motor.control(CHAN MOTORS moto!,
                   CHAN BOOL front.too.close?)
  WHILE TRUE
    ALT
      BOOL front.status:
      front.too.close ? front.status
        moto ! -10 ; 0 ; 0 
      SKIP
        moto ! 10 ; 0 ; 0
:

Now motor.control works correctly.

The ALT construct lets us look at a number of input channels, and read from the first one that is ready. Now, as we loop infinitely in this process, we ignore the front.too.close channel most of the time; it sends us messages very infrequently. Or, it should be said, it only sends us messages when our laser rangefinder detects something within 1m almost directly ahead of us.

You could, at this point, drop this program into your RoboDeb environment, and run it. Johnny0 will drive towards the wall until he gets within one meter; he'll back up (until he is more than a meter away), and then start driving forwards again. It's really, really, fascinating.

Backing up and turning, watching our rear

At this point, all the interesting work has been done. All we need to do is add something that watches the back sonar sensors, makes sure we're not too close to something, and sends a message to motor.control if we are. In short, it will be a little more network that looks almost exactly like the code we already developed for the laser.

I've gone ahead and added this in, wholesale.


#INCLUDE "player.inc"
#INCLUDE "pioneerutils.occ"

PROC bumper(CHAN INT min?, CHAN BOOL too.close!)
  WHILE TRUE
    INT current.value:
    SEQ
      -- Read in the current value
      min ? current.value
      -- If we are too close to the wall, shout!
      -- Otherwise, do nothing.
      IF
        current.value < 100
          too.close ! TRUE
        TRUE
          SKIP
:

PROC motor.control(CHAN MOTORS moto!, 
                   CHAN BOOL front.too.close?,
                   CHAN BOOL back.too.close?)
  WHILE TRUE
    ALT
      BOOL front.status:
      front.too.close ? front.status
        moto ! -10 ; 0 ; 0 
      BOOL back.status:
      back.too.close ? back.status
        moto ! 10 ; 0 ; 0 
      SKIP
        moto ! 10 ; 0 ; 0 
:

PROC main (CHAN BYTE kyb, scr, err)
  CHAN MOTORS moto:
  CHAN LASER sick:
  CHAN SONAR devan:
  CHAN INT laser.min.val, sonar.min.val:
  CHAN BOOL front.too.close, back.too.close:
  PAR
    brain.stem(moto?, sick!, devan!, 6665)
    motor.control(moto!, front.too.close?, back.too.close?)
    
    laser.min.slice(sick?, laser.min.val!, 60, 60)
    bumper(laser.min.val?, front.too.close!)
    
    sonar.min(devan?, sonar.back, sonar.min.val!)
    bumper(sonar.min.val?, back.too.close!)
:

A working robot... just one or two tweaks left!

A working network.

Done! Now, the interesting tweaks

There are a few things that our last program demonstrates nicely.

The bumper process we wrote for the front bumper is actually usable for the back bumper as well; it expects to take integers in on one channel, and output booleans on another. Therefore, we can simply instantiate the process more than once in our network, wherever it is needed. I renamed the process front.bumper to bumper, as it is a generic process. You can see where it was instantiated twice in the main process.
Our code didn't grow significantly to add the sonar as a back "bump" sensor. We simply took the data coming from the brain.stem, and put it through the sonar.min process (from the library).
We need to turn while we're backing up; this is just a matter of tweaking the command we send to the motor.
We still need to timeout on the backing up; this is pretty easy, and we'll make that change below.

Both of our "tweaks" come in the motor.control process. Below is the tweaked version. The change to make the robot pivot while backing up is trivial; the protocol we're using for communicating to the motors is simply the forward/backward speed of the pioneer, it's side-to-side speed (which is ignored; Johnny0 can't go sideways!), and the rotational velocity of the robot. We'll tweak that last parameter.

To make our robot timeout on the backup is another beautiful part of the ALT; we simply replace our default, SKIP guard with a TIMER guard. This is safe, non-deterministic concurrency at its best.

Both of these changes have been made below; at this point, we're done with the "interesting bump-and-wander" exercise.


PROC motor.control(CHAN MOTORS moto!, 
                   CHAN BOOL front.too.close?,
                   CHAN BOOL back.too.close?)
  WHILE TRUE
    TIMER tim:
    INT t:
    SEQ
      tim ? t
      ALT
        BOOL front.status:
        front.too.close ? front.status
          moto ! -10 ; 0 ; -10 
        BOOL back.status:
        back.too.close ? back.status
          moto ! 10 ; 0 ; 0 
        tim ? AFTER t PLUS 2000000
          moto ! 10 ; 0 ; 0 
:

motor.control in its final form.

The last line of the ALT now reads: "Execute this branch of the ALT if two seconds go by, and no other channel becomes ready." This is an incredibly powerful way for dealing with communications coming in from multiple sources

And we're done

Our solution is under fifty lines of code, and involves six processes running in parallel. When we had problems, we were easily able to trace where our data was going, and easily reason through what was going wrong. In short, we think this is a pretty nice way to manage the complexity of sensing, navigation, and computation on a robot, be it big, or small.