Sub Ubi

Jon and Carl have really pulled out all the stops on this one. It could make you weep it’s so beautiful. What you see here is a screenshot of the typical jEdit interface. We use jEdit because it is open source, lightweight, and runs on Windows, Mac, and Linux without too much fuss. The code in the window is actually a near-copy of the original Surveyor firmware, translated into occam-pi. (Click on the images to see big versions…)

The first thing we need to do is fire up the occPlug. This is our plugin for compiling and running occam programs on a number of different platforms. Currently, the Windows release supports the desktop, the Mindstorms RCX, and the Surveyor SRV-1.

Once the occPlug is started, we can hit the compile button, and as you can see, our code is compiled for the Surveyor SRV-1 target. This isn’t the real magic, though…

When I run this code after compiling it, it is uploaded to the Surveyor and kicked off. Note that this is how all user programs are treated; we’ve turned what used to be the only firmware on the Surveyor into just another program. This is important, because it means it is easy for users to extend the default firmware (so to speak) to work with existing tools on the market, as well as incorporate their own algorithms for processing images, or navigation, and so on.

When I hit run, I get connected up to the Surveyor automatically. You see that “Command” area down below? I can type messages in and send them to my SRV-1 with no fuss whatsoever. Type, hit return (or the “Send” button), and my characters are whisked away into the aether through the magic of 802.11g. One of the commands I can send is the I command (meaning, I typed the letter I and hit return). Why “I”? I don’t know; we’d have to ask Howard. The important thing is that the I command sends me an image. And Jon and Carl have done a wonderful job here; when the terminal catches the header for the JPEG-compressed image coming back, it opens up an image pane, and displays what the Surveyor sees. We don’t have to do anything!

Here, I’ve sent the a command followed by I, and the image pane automatically resizes. Because the a command is interpreted to mean to set the image size to 160 x 128, I get a smaller image back. I then sent an A followed by an I…

And you can’t tell exactly, but that’s a really big picture of my kitchen floor in the background. It took a little longer to send than the tiny image, but we love those big pictures for their general awesomeness. The last thing I did was dial the size of the image back, and fired up my laser cannons. Those things are awesome.

How long does it take to compile that firmware? Let me see… I’m running Windows as a VMWare virtual machine on my MacBook Amateur (2×2GHz, 2GB RAM), and it takes roughly “one Mississippi.” How long does it take to upload the program? About as long. That alone has made developing on the Surveyor under occam-pi an absolute joy: no JTAG, no long compilation, just edit, compile, run, explore, tweak, try again… nice and easy.

Now that things are falling into place, we can start doing some very cool things, I believe. Earlier today, I was exploring the YUV colorspace, and wondering how hard it was to see an orange. Well, my first attempt was pretty lame:

As you can see, I’m highlighting pixels that I believe should be orange-colored. Oops. Well, given that I was squinting at a two-dimensional YUV colorspace plot, it wasn’t a bad guestimate. Note that I apparently have a better orange detector than a baseball detector:

Don’t read too much into this, though. I mean, I was mostly figuring out what Carl and Jon had done, and taking the occasional screenshot.

So, what’s the punchline? Jon and Carl have assembled an excellent IDE for exploring occam-pi and robotics on the Surveyor SRV-1. We’re going to be releasing this to students this weekend, and it goes live for laboratories in the Robotics class at Olin on Monday. We’re using the Surveyor to explore challenges of vision-based navigation in conjunction with simple state machines and behavior engines. What’s more, they’ll be learning how to architect these solutions in parallel-safe ways from day one. I think this laboratory (this is only one 2-week lab of four) is part of what makes Olin’s robotics class completely unique in the world today.

And yeah, I’m pretty jazzed that the software that we’ve all worked on for so long is being put to use for the purposes it was intended. That, really, is the awesome part.

Update: Does it work over the wireless? Yes. This is part of what we like about the Blackfin Surveyor—no wires. You write your code, hit compile, hit run, and the code goes through the air to your robot. You can then talk back and forth completely over the WiFi. And to answer the second qusetion: does it work on the Mac?

You tell me? Because everything in the IDE is WiFi and Java, there’s no real platform dependency. We’ve done a Windows build that will be distributed to Olin students momentarily, and want to discover any obvious problems. Once we’ve done that, we’ll do Mac and Linux builds. Doing releases is not a process that we’ve sufficiently streamlined—something that perhaps needs to be improved.

Regardless, yes, the Mac is a full-peer in this enterprise. Given that the Transterpreter was written entirely on Macs, we’re happy to support it.

(That’s a shot from Jon’s Surveyor, which lives in England and gets nice views out over Canterbury.)

I’ve discovered that programming while helping students and working with colleagues (both in the room and across the ocean) is actually distracting enough to prevent you from writing good code.

By coming in around 6AM this morning, I got some good quiet time that I was able to use productively, and in a short amount of time wrapped my head around YUV 4:22 (UYVY), and got some drawing routines ported into our Surveyor package. I have some questions for Carl and Jon about this, but for the moment, I’m glad my explorations are (mostly) over.

Last night, I got as far as wondering why I was able to make my images green:

This morning, I quickly isolated the luma component (Y) of the image:

Then, it was on to drawing. I think he sub-sampling for JPEG conversion is confusing me, but we can reliably draw shapes over the image:

Now, when students start doing image processing, they can circle or box in regions they are interested in, and see if their algorithms are returning values that make sense. (They can also print debugging information back to the PC, which is useful as well.) Between these two modes of interaction, I’d say we have a reasonably rich platform/API developing upon which students can develop parallel-safe robotics applications on the SRV-1 using occam-pi.

We ran into something interesting the other day on the LEGO Mindstorms. In particular, something to do with time.

You see, the LEGO is a 16-bit machine. This means the largest number it can represent is 2^16 - 1, or 65535. This is OK in most cases, but I want to note that the LEGO’s clock runs at millisecond speed. That means that it ticks over once per millisecond. The number of milliseconds we can count before the clock rolls over is… 65,535.

If there are 1000 milliseconds in a second, that means that we can only count up to 65 seconds before the world ends. Now, this is fine for James Bond movies (where the hero always has one minute to accomplish his death-defying task), but we kinda want to be able to measure longer amounts of time than that.

In occam-pi, we can do this in some very cool ways. So, consider this a brief introduction to timers in occam-pi, and more specifically, how we can neatly create timers that ‘tick’ at arbitrary intervals without too much effort. I’ll continue this later in another post that explores how I build up to having timers that let me measure hours, days, weeks, and even months on the LEGO Mindstorms. For the moment, I’ll start with some basics about timers.

To start, occam-pi has a notion of a TIMER built into the language. This is kinda cool. If I wanted to write a process that would delay for some number of milliseconds, it would look like this:

PROC delay (VAL INT timeout)
  TIMER t:
  INT the.time:
  SEQ
    t ? the.time
    t ? AFTER timeout
:

The process takes one argument, which is a timeout value given in milliseconds. The timeout value has a type, which is VAL INT. This means that it is an integer, and furthermore, we cannot change it—any attempt to modify this value will result in a compile-time error. In other words, we’re saying it is a constant within this PROC.

We then declare two local variables: one of type TIMER and one of time INT. In sequence, we then read the current time into the variable ‘the.time’, and then use a funny bit of syntax to do our delay:

t ? AFTER timeout

This is some ugly stuff—something I wish they had done differently in the language. However, occam is over 20 years old, so we’ll cut it some slack. This syntax says “delay until timeout milliseconds have passed.”

And that’s it. What’s nice about this PROC is that it does not block other processes from doing their stuff. So, it effectively says “sleep, but let other people run around and do things.” Very cool.

Now, we can’t use this process to delay for more than 60 seconds or so, because the LEGO Mindstorms is limited by a maximum of roughly 65K milliseconds. Since I want to be able to do nifty things that involve timing out for more than 60 seconds, I want to start by writing a ‘ticker’ process that will generate clock ticks that I can listen for at intervals other than milliseconds.

PROC tick.generator (VAL INT delay, CHAN BOOL tick!)
  TIMER t:
  INT timeout:
  SEQ
    t ? timeout
    WHILE TRUE
      SEQ
        timeout := timeout PLUS delay
        t ? AFTER timeout
        tick ! TRUE
:

This is only slightly bigger than the previous PROC. The tick.generator has two arguments—a constant (VAL INT), and a channel that carries booleans (CHAN BOOL). The channel is an output channel because it has been decorated with a !. (The compiler can figure this out for itself, but good style dictates that we put the ! on the channel end in the PROC definition.)

Again, I declare the local variables t and timeout, read the current time, and then drop into an infinite loop. This loop increments the timeout value, delays, and then outputs a signal on the boolean channel. Now, I can put this and a few other things together to create a complete program. This will execute just fine on your desktop, so if you paste it into your JEdit window, save it as “ticker.occ”, compile, and run, you can see what it does. (Note that I’ve defined constants for SECONDS and MILLIS; on the LEGO, you would redefine MILLIS to be 1.)

VAL INT MILLIS IS 1000:
VAL INT SECONDS IS 1000 * MILLIS:

PROC delay (VAL INT timeout)
  TIMER t:
  INT the.time:
  SEQ
    t ? the.time
    t ? AFTER timeout
:

PROC tick.generator (VAL INT delay, CHAN BOOL tick!)
  TIMER t:
  INT timeout:
  SEQ
    t ? timeout
    WHILE TRUE
      SEQ
        timeout := timeout PLUS delay
        t ? AFTER timeout
        tick ! TRUE
:

PROC tick.seconds (CHAN BOOL tick!)
  tick.generator(1 * SECONDS, tick!)
:

VAL BYTE flush IS 255:
PROC show.seconds.tick(CHAN BYTE kyb, scr, err)
  CHAN BOOL ticker:
  PAR
    tick.seconds(ticker!)
    WHILE TRUE
      SEQ
        BOOL tmp:
        ticker ? tmp
        scr ! ‘x’
        scr ! flush
:

The last process, ’show.seconds.tick’, demonstrates how we don’t always have to name our processes to run them in parallel. First, I declare a channel to carry boolean values (remember, channels are like wires—channels carry information from one process to another.) Then, in parallel, I want to run the process ‘tick.seconds’ and an infinite loop that I’ve written. The process ‘tick.seconds’ gets one end of the channel ‘ticker’—in particular, it gets the end of the channel that will be written to.

In the infinite loop, I do a few things in sequence. First, I declare a temporary variable that is only valid for one line of code. That is, it exists just long enough to read from the ticker channel into the variable ‘tmp’. This is because I don’t actually care about keeping that value, but I have to read from the channel into something. After reading from the channel, I output an ‘x’ to the screen, and then I flush the screen, so that the output is actually shown.

Remember that occam-pi channels are blocking channels. That means that my infinite loop will stop every time it hits the line ‘ticker ? tmp’. It will wait until the process ‘tick.seconds’ has written a value, and then the loop can continue. Also, it is important to remember that every time you see a channel read (eg. ‘ch ? var’) or a channel write (eg. ‘ch ! var’), the Transterpreter deschedules the currently executing process, and goes and runs something else. This way, everyone gets a turn to execute. This is why the delay process I introduced earlier does not block everything running on the system, and why we can write infinite loops as casually as I have here… because each one contains a channel communication.

In my next post, I’ll follow up with how to extend this into timers that can last for days or even weeks on something as small as the LEGO Mindstorms. Also, I still need to follow up on our subsumption code for the Surveyor—but that will come, perhaps, after this timer exploration. In fact, this came up because we were trying to run our code from the Surveyor on the LEGO, and we discovered that having a 32-bit timer (like on the Surveyor SRV-1) is very handy, while having a 16-bit timer (like on the LEGO Mindstorms RCX) is a bit annoying… where “annoying” means “Hey! Our code doesn’t work!”

I recently caught sight of the article Subsumption for the SR04 and jBot Robots over at the Dallas Personal Robotics Group’s webpage. What is sad is that the first thing that David Anderson goes into is technical details regarding their timing loop. Sadly, timing has nothing to do with implementing the subsumption architecture. Our recent explorations on the SRV-1 demonstrate this nicely, I think.

At AAAI, Jon and I implemented code for the mini-robotics-challenge that was hosted in our session. We had to program a robot that would:

1. Wander as far from its start point as possible in 30 seconds, avoiding obstacles
2. Return as close to home in the next 30 seconds.

This is a trivial task, but all the participants were using robotics platforms they had never seen before, and had roughly 1.5 hours to implement their solutions. Having first seen the SRV-1 just a day before, we had ported the Transterpreter to it, and had basic motor control and access to the IR sensors. Using this, we looked at the problem, and tackled it by implementing a three-layer subsumption architecture.

At the lowest level, we wanted our robot to go forward. We wanted a higher-level behavior that would avoid obstacles, and a third, even higher level behavior that would (after 30 seconds) replay the motor commands that had been generated in the previous 30 seconds (causing the robot to retrace its steps). This is a bit odd as subsumption architectures go (having a layer that suppresses everything below it simply to replay previous actions), but it yielded a very clean implementation.

What follows is the network, and a step-by-step decomposition of how it worked.

Each orange box represents an occam-pi process; in some languages, you might call these “threads”. However, in occam-pi, processes have certain properties. First, they are completely sealed, and therefore, no other process can manipulate their state; for example, anything in the “forward” process is completely isolated from the “avoid” process, and visa versa. Also, occam-pi processes are incredibly light-weight: we can run hundreds of these processes on robots the size of a LEGO Mindstorms or the SRV-1, and therefore casually write highly concurrent programs for very small robots.

The arrows in this diagram are channels; they carry data from one process to another. In fact, channels are the only way two processes can communicate with each-other. First, they are unidirectional; you can only talk in one direction down a channel. Second, they are blocking, meaning that once committed to a communication (either a send or a receive), the communicating process deschedules, and waits until the other half of the communication is carried out. This explicit synchronization makes it easy to reason about many different processes taking turns doing computation and communicating between each-other.

Level 0: Going Forward

With this brief background in occam-pi, you can begin to piece together the network. The forward process sends motor commands to a suppressor process (S1), which communicates on to another suppressor process (S2). This then communicates to a delta process (which copies its input to two outputs). One of those outputs flows to the motors, and the other to a process called record, which records all the motor commands sent to it. In the common case, both suppressors are inactive, and motor commands flow around the network as depicted below:

Level 1: An object detected

When an object is detected, the avoid process kicks in. Note that it does not “turn off” or “disable” the forward process—both are always running concurrently. However, suppressor S1 becomes active when the avoid process goes active. It does this when it detects something in front of the robot using the IR sensor. It then begins sending commands to pivot the robot to the left. (This is a pretty dumb robot, really.) These new commands are routed through S1 instead of the commands from forward, and the robot pivots away from the obstacle (and records the pivot as well).

Level 2: Replay!

The trickiest bit of work comes when we begin replaying our movements after 30 seconds have passed. The live portions of the network look like this:

The replay module suppresses the output of both the forward and avoid processes. It also inhibits communications between the delta process and the record process; this is because we definitely do not want to be recording the playback! (We made this error, initially; it yielded very strange robot behaviors, and usually ended in both a crash of hardware and software.)

The replay module requests actions from the record process, and then plays each of those actions down the channel it has to S2; these are routed through to the run.motor process. The end result is that our robot replays all of the actions that were recorded over the previous thirty seconds.

It seems so complex!

It may, or it may not—it depends on how you like to think about control systems for embedded devices (like little robots). I prefer this model, where nowhere in my code am I worrying about timing—instead, I’m just worrying about where my data is flowing. In this case, I’m flowing motor commands from one process to another, and I’ve written special processes (the suppressors and inhibitor) to control how that data flows through the network. The language and runtime are responsible for handling the concurrency—not me.

For a C programmer, this is a completely foreign idea. However, it is (I believe) the case that C is generally useful only for very specific tasks, like hardware interfacing. Handling complex data structures, complex data flows, and any kind of concurrency or parallelism is something that should be left to the compiler, not the programmer. Put another way, we as programmers are too error prone to be left on our own writing complex control loops, and languages like occam-pi are a first step towards managing that complexity.

As always, we encourage you to take a look at RoboDeb if you’re interested in the intersection between robotics and concurrent programming languages. We’re very, very close to releasing the newly revised LEGO Mindstorms runtime, which will let you explore occam-pi on your Mindstorms as well. (Our NXT port will follow that release.)

What about the code?

Most of the code for this was written in the twenty minutes before the robotics competition. I could go into the code here, but for the moment will beg off (it is a beautiful day, and I’d rather be outside). However, you can see the code online in our Subversion repository.

If you want to know more about the code, drop me an email (matt at transterpreter dot org), and I’ll put together a post that goes through it in more detail. You might start with Jon Simpson’s paper Mobile Robot Control: The Subsumption Architecture and occam-pi (PDF), as it goes through a similar process network, and includes code for the inhibitor and suppressor processes. (It will be more readable than anything I hack into the ‘blog, anyway.)

We spent the first three days of last week taking part in the AAAI 2007 Spring Symposium. In particular, we joined the Robotics and Education track with about 50 others interested in using robotics to teach everything from introductory programming to vision, pathfinding/planning, decision making, and all the other tasty bits of artificial intelligence.

Scribbler

Turtle

We saw some very cool projects and platforms. I really liked Roomba Pac-Man (where students program Roombas to wander hallways and vacuum up messes in a pac-man like way), and the Scribbler (while not very aesthetically pleasing) is a cute re-creation of the LOGO turtle. (I’ve provided a side-by-side comparison of what these two robots look like; the original turtle was, I think, far more attractive.)

In terms of platforms, many people are doing “tethered” robotics, where they either physically or wirelessly tether their robot to a PC. This is, I think, unfortunate, as I feel it takes something away from the process of programming the robot—it is a remote control process, as opposed to an autonomous one. However, like many things, it depends on what your pedagogic goals are. However, I do look forward to a few things: I think the Qwerk is a neat (part of the TeRK project) and we hope that we have a chance to work with it sometime in the future. It’s a powerful computational platform with a lot of nice outputs for motor and servo control, as well as managing a host of sensor inputs. Likewise, the Blackfin Handyboard is a very powerful platform, and will also be great to begin exploring, as it provides some very flexible programming options in the form of two Xilinx FPGAs. Fred and Andrew did a very nice job with the board design, and I expect many cool things will be done with this platform.

We also saw David Miller’s XBC/Gameboy combination, which I now have a Gameboy to try this out with (once I have a budget to get the rest of the bits, which is actually the expensive part). However, the really fun new platform was the Surveyor Robotics SRV-1.

Howard wrote about our experiments with the SRV-1 on his weblog, and I’ll add a bit here, and followup in a later post with some more detail. We were given an SRV-1 to borrow on Monday evening, and did very little with it, as we were missing critical software. Tuesday, during coffee breaks and the like, Christian ported the Transterpreter to the SRV-1. In less than two days, we saw a new, ARM7-based robotics platform, and had the Transterpreter running subsumption code on it. In three days (that is, the day after the conference), Christian had vision working.

I went ahead and stole a picture from Howard; here, you can see the end-result of our hacking, which is that we won the AAAI Robotics and Education robotics programming challenge. We did this with the SRV-1 after having seen it for the first time on Monday, having ported our runtime to it on Tuesday, and having seen the challenge on Wednesday morning. We managed a (not-quite-working) 3-layer subsumption network that tackled the challenge in about 20 minutes of furious hacking; I’ll write more in detail about our code (which we’ve subsequently cleaned up and corrected) in a followup post.

For now, we’re still kicking around San Francisco and the Bay area, enjoying two days off before flying back to England on Wednesday.