There's nothing I'm going to tell you today that you absolutely have to know in order to pass this course. But I'm going to assume that you're not taking this course just to pass it.
The RCX computer combined with the legOS kernel, API and programming environment is simple when compared with, say, a Sparc Ultra 10 combined with Solaris 5.7. But it's about as complex a combination as you'll ever be able to understand completely.
As a class, you have diverse computer science backgrounds. My lecture today tries to teach all of you something and provide each of you with pointers to additional sources so you can go as far as you want.
I could easily spend an entire semester expanding on the material in this one lecture. But for some of you an hour will be quite enough. The references at the end of the web page for today's lecture should suffice for those of you who want to take the next steps.
So, why is what I'm going to say today important to "Building Intelligent Robots"? The answer is that building robots is all about timing, about doing several things at once and about interfacing with a dynamic and unpredictable world.
In programming the RCX, you will have to make use of a single sequence of instructions, a single thread of computation to simulate multiple threads of time-critical control implemented as tight feedback loops.
We need to start with a commonly-understood base model. Something we can ground our subsequent discussion on. For our present purposes, this means a computational model that provides all of the basic primitives for understanding legOS. I'm going to assume that the first part of today's lecture is a quick review of basic material.
What do you think of when you hear the words "computational model?" A Turing Machine perhaps? I'll bet it's not a non-deterministic, one-way, finite-state machine? It may be that these sorts of abstract models don't provide you with an appropriately "high level" of abstraction to help you in thinking constructively about real-world programming problems. It's important to note, however, that we all use abstract models of one sort or another; the trick is to make the abstractions work for you by emphasizing the important aspects of the problems you're trying to solve and hiding the messy details that just get in the way. (I know this is tangential but I can't resist an aside. The book entitled Alan Turing: the Enigma written by Andrew Hodges is interesting for a number of reasons not the least being its discussions of Turing's contributions to computer architecture. Turing was a lot more practical than most computer scientists give him credit.)
An alternative model (but still pretty low level) is the machine defined by the so-called "von Neumann architecture" (named after the mathematician John von Neumann). Most of you have seen this architecture in one or more of your courses, as it is the standard abstract model used to describe most modern computers. We won't actually use the von Neumann model as a basis for thinking about robot programs but it will provide an intermediate level of abstraction for developing an appropriately high level model for programming robots. The computational model corresponding to the von Neumann architecture consists of the following components:
Though not often included in the classic formulation, we usually also assume that there is some way to get data into and out of the computer.
The standard architecture assumes the notion of a program counter which is just a register used to store the location of the next instruction in memory and an instruction set that defines the set of primitive operations that can be performed by the ALU. You learned early in your computer science education that arithmetic and symbolic operations can be implemented in terms of boolean operations on binary data. Here is the sequence of steps repeatedly carried out in this model:
1. Fetch the next instruction from memory.
2. Increment the program counter by 1.
3. Decode the instruction and instruct the control unit to carry out the appropriate operation. This operation could change the contents of registers (including the program counter) thereby allowing loops and conditional branches.
4. Return to Step 1.
What else might you want to add to the above abstraction to have a reasonable computational model for thinking about robots and real-time control? Well, for one thing you might want to have some way of measuring the passage of time. (Note that if you knew how much time each instruction took or could assume that each instruction takes the same amount of time you could create a clock of sorts but it would be rather clumsy to use.) List some of the reasons that a clock would be useful in programming robots.
Another addition that often comes in handy is the notion of an interrupt. Interrupts simplify writing programs that perform other operations while waiting for events (both internal and external). Interrupts and timers together provide the machinery for implementing efficient multi-threaded control (e.g., preemptive multi tasking) which will prove particularly useful in building robot programs.
There are other components that we might add to enhance the standard model. For example, peripheral components that map analog sensors to digital data or visa versa and abstractions such as direct memory access (DMA) that allow us to think of sensor data as magically appearing in designated locations in RAM. You might think however that we are getting hopelessly low level in providing a practical computational model for programming and, indeed, there is reason to build a layer of abstraction that that hides some of these details from the programmer.
The answer to this question depends in part on how much pain you're willing to endure. Given a loader for the H8 Microcontroller you could directly load H8 machine code to the RCX and run machine code programs. Somewhat less painful, you could use a text editor to write H8 assembly code, an assembler to produce machine code and then a loader to load the machine code to the RCX. The following HC6811 assembly program flashes the motor LEDs on a Handy Board back and forth indefinitely from green to red (adapted from [Martin, 2001] Appendix A.2):
org $8000 ; define the program origin at address $8000 start lds #$ffff ; define the program stack at the top of memory again ldaa #$f0 ; load the value of $f0 (red) in the A register staa $7000 ; store the A register to $7000, the motor port jsr delay ; jump to the delay subroutine ldaa #$ff ; load the value of $ff (green) in the A register staa $7000 ; store the A register to $7000, the motor port jsr delay ; jump to the delay subroutine bra again ; branch back to the beginning of the loop delay ldx #0 ; put zero into the X register delayp dex ; decrement 1 from the X register bne delayp ; loop until zero again (65536 times) rts ; return from the delay subroutine org $bffe ; location of the 68HC11 "reset" vector fdb start ; "form a double byte" to start of program end
I should note that even in the simple assembly program above, we've deviated somewhat from the simple model described above. The instruction jsr is a jump to subroutine call. Apart from the fact that this is assembly and not machine language and delay is a symbolic and not numeric address, what is special about the jsr instruction? The answer is that when you jump to a subroutine you have to push the address of the instruction immediately following the jsr instruction onto the stack so that you can restore this address in order to return from the subroutine call. You could get away without the jsr instruction, but would you really want to? You could do the bookkeeping yourself but the abstraction built into the jump-to-subroutine instruction makes your life a lot easier. (Later we'll want to invoke a similar abstraction whose implementation requires that we push not only the program counter but the contents of all the registers onto the stack when we switch (contexts) between processes.)
If you're interested, Martin  has a nice introduction to the architecture and assembly language of the 68HCll MPU in Appendix A.1 of your textbook: everything you wanted to know about memory maps, addressing modes, interrupts and the like. Martin talks about subroutine calls and the method of passing arguments to and returning results from subroutine calls by manipulating the stack (with appropriate warnings of the attendant dangers of relying on the programmer to keep track of such low-level bookkeeping details). Jones and Flynn [Jones and Flynn, 1993] also provide a nice discussion of these issues (see Section 3.5: The Hardware Software Interface).
Indeed, you could do all of your robot programming in assembly or machine code. Most robot programmers, however, prefer to have some reasonably high-level abstractions between them and the nitty gritty details of the microprocessor and the supporting low-level circuitry controlling their robots. These abstractions are typically in the form of a programming language along with libraries and APIs for interfacing with sensors, motors and I/O devices.
Most programming languages depend on various operations provided by an operating system. The operating system along with its various conventions for handling files, performing I/0 and managing memory and processes provides an abstract model of computation that underlies the various programming languages supported by the OS. Before we get into the details of the Lego RCX let's consider what sorts of things we generally expect from operating systems.
Here are the basic operations that a programmer (or programming language designer) typically expects of a modern operating system (adapted from [Silberschatz, Galvin and Gagne, 2001]):
To get us thinking about what sorts of languages and abstractions are useful for programming robots, here is a simple robot problem and some proposed pseudo code for its solution. Suppose that we have a wheeled or tracked robot with two sensors: a downward pointing light sensor that can detect colors on a playing surface and a forward pointing bump sensor that can detect collisions with vertical surfaces. The robot is located on a square playing field surrounded by walls of an appropriate height. In the center of the playing field is a cylindrical object of the same height as the surrounding walls; this object is the "goal post" of the playing field. The playing surface is divided into a central circular area which is colored red and the rest of the playing surface which is colored green. We will assume that the robot's downward pointing light sensor can distinguish between these two colors. (It's worth noting, however, that just because you can discern the difference between these two obviously different hues, it doesn't follow that your particular light sensor will be able to make such distinctions. This is an instance of a more general lesson that roboticists learn over and over again in a multitude of guises.) The robot is supposed to remain within the central red area and to make contact with the goal post. If the robot remains in the green area for more than a specified duration, then the game is over and the robot "fails". If the robot hits the goal post before failing, then the robot "succeeds" and its score is the time elapsed from when the game began. We'll require that the robot demonstrate that it "knows" that it has succeeded by signaling with a distinctive tone and stopping its motion. Here's a graphic depicting the playing field.
Now how would you think about organizing a program to compete in this simple game. Here are some component behaviors which, working together, might provide a reasonable solution.
Now, there are all sorts of problems with the above sketch but it's not a bad start and it does illustrate some of the problems and requirements that you're likely to encounter in designing robot programs. First, you'll often have subroutines that repeatedly check for some condition signaled by a change in sensor values. Second, you'll often want to do several things at once ("chew gum and walk at the same time") in order to contend with the demands of a dynamic environment. Finally, a lot of low-level robotics can be characterized in terms of tight feedback loops that repeatedly sense some aspect of the environment, compare the most recent sensor reading with some desired target value, and then use the difference (called the error signal) to determine what response to make; in the case above, the desired target is "seeing red". (Often, an appropriate response depends on many factors ("seeing red" and "not having hit the goal post") and hence the heart of the controller often consists of a "bunch of logic" to sort out the various circumstances and their corresponding appropriate responses.) Now let's reconsider these operations with the requirements for controlling mobile robots in mind:
Alright already! Let's take a look at the RCX Programmable Brick and the Hitachi H8 Microcontroller (MCU). Kekoa Proudfoot has saved us the trouble (and expense) of taking apart one of the Lego bricks. His web page (see below) provides a glimpse into the hardware and core resident software (referred to as "firmware" in this case) of the RCX. My web page from Spring of 2001 explains some of the issues concerning various firmware alternatives and the programming languages that they support. Last year we programmed in "Not Quite C" (NQC) which depends on the standard firmware that comes with the Lego Mindstorms robot kit. This year we'll be programming using a subset of the C programming language supported by the legOS which is a very simple operating system that depends on its own special firmware.
So what is it that legOS provides us that NQC (plus the standard firmware) doesn't? First, the language is closer to the real C programming language! (What could we possibly mean by that and why should anybody care?) Second, legOS lets us use standard compilers and programming tools to develop RCX code. (Why is this an advantage?) Third, using legOS we run "compiled" rather than "interpreted" code. (What's the difference and why should anybody care? Isn't FORTH an interpreted language that is widely used in embedded control systems?) And, as long as we're posing all these parenthetical questions, you might be wondering about a particularly obvious question. (Why didn't we just use interactive C, the language described in Fred Martin's text book?) Let's start by considering exactly what it is that legOS provides us with and we'll try to answer these questions in the context of explaining what legOS is.
In the next lab, you'll learn the nuts and bolts of compiling and downloading legOS programs. In this lecture, we're still thinking in terms of abstractions: what it is that we want and need in a programming language and how legOS supports these needs.
Here is a quick glimpse of the APIs for motors, sensors and the LCD display:
We assume you're familiar with the standard flow of control constructs such as while, until, if, then and else. Lightweight processes or threads are an important notion in designing embedded control systems and while they exist in standard C, it's probably worth looking at them a little more carefully. (What's the difference between "regular" processes and "lightweight" processes (threads) when programming in C for a POSIX compliant OS?) Here are the basic constructs for creating and managing processes:
If you took CS167, you might recall the lectures on process and lightweight thread management; specifically, look at the slides titled Weenix II. To learn more about how threads are handled in legOS, check out the code in "kernel/tm.c" in the legOS source directory. This file contains the task switcher and scheduler as well as the library functions relating to task management (hence the file name "tm"). Note that this file, like several of the other files in the legOS kernel, contains embedded assembly code subroutines. In the case of "tm.c", these assembly routines are called, when a time slice ends and an interrupt is called signaling that it's time to switch to another thread. These assembly-code routines provide low-level services such as those required in context switching. When a process (thread) is halted, the contents of its registers and program counter are saved to a particular location in memory and the previously saved contents of the registers and program counter for some other process are restored; this shuffling of register contents is called context switching. The task switcher is also called when the currently running thread executes a sleep or yield instruction.
Even if you didn't take CS167 you should be able to figure out some scheme to map your understanding of threads and thread switching onto the von Neumann architecture presented earlier. Note what's happening here; the functions built into legOS for sensors, motors and threads provide a new abstraction that replaces the more primitive von Neumann abstractions. There are times, however, when it is valuable to be able to map back to the more primitive abstraction in order to understand anomalies that can't be easily explained at the higher level. Another good source for learning about threads and processes, is to review the chapters that comprise "Part 2: Process Management" of [Silberschatz, Galvin and Gagne, 2001].
There are a number of sources of useful information about legOS. Markus Noga who designed the first version of legOS describes some of his contributions in [Noga, 1999]. Noga's legOS page is a good source of pointers and articles. [Nielsson, 2000] provides a very readable introduction to the legOS kernel. There's also an online discussion group lugnet.robotics.rcx.legos that provides a wealth of legOS-related information. I managed to find online version of most of the articles listed below either using Google or NEC ResearchIndex (CiteSeer). LegOS is a moving target and soon after a problem is discovered generally you'll find a solution posted to one of the newsgroups.
[Pedersen et al., 2000b] identified some problems with early versions of the legOS task manager. They provide a fix that makes legOS (specifically, the event handlers that respond to changes in sensor readings) more responsive to transitory sensor events, e.g., using a downward pointing light sensor to notice when a wheeled robot rolls over a painted line. Here's a diagram showing how the task manager proposed in their solution tests the conditions of processes waiting on event handlers.
As another example of efforts to make legOS more robust, [Pedersen et al., 2000a] (a different Pedersen (Michael Haugaard) than the Pedersen (Soren Toft) in [Pedersen et al., 2000b]) describe a problem that occurs when a higher priority process is blocked by a lower priority process when both processes share access to a resource gated by semaphores. If you've taken a course in operating systems (e.g., CS167) you should find this article accessible.
There's a lot more to writing robot programs in legOS. Later we'll learn about specialized sensors like the rotation and sonar sensor. You'll also learn how to use sounds and legOS infrared communication protocols. It's not hard to master the syntax; the trick is getting the robot to do what you want it to do and that is what makes robot programming so interesting and challenging.
|[Nielsson, 2000]||Stig Nielsson, "Introduction to the legOS kernel," September, 2000.|
|[Noga, 1999]||Noga, M. L., "Designing the legOS multitasking operating system", Dr. Dobb's Journal, November, 1999.|
|[Jones and Flynn, 1993]||Jones, J.L., Flynn, A.M., Mobile Robots: Inspiration to Implementation, A K Peters, 1993.|
|[Martin, 2001]||Martin, F., Robotic Explorations: A Hands-On Introduction to Engineering, Prentice-Hall, 2001.|
|[Silberschatz et al., 2001]||Abraham Silberschatz, Peter Baer Galvin, Greg Gagne, Operating System Concepts Sixth Edition, John Wiley & Sons, Inc., 2001, [see their web page].|
|[Pedersen et al., 2000a]||Michael Haugaard Pedersen, Morten Klitgaard Christiansen, Thomas Glaesner, "Solving the Priority Inversion Problem in legOS", Technical Report. Computer Science University of Aalborg, May, 2000.|
|[Pedersen et al., 2000b]||Pedersen, S. T., Christensen, L., and Rasmussen, E. B., "Prioritized interrupts in legOS", Unpublished Project Paper Submitted to the Institute for Computer Science at Aalborg, 2000.|
|[Villa, 2000]||Luis Villa, "LegOS HOWTO", 200, [a printable version is available at legos.sourceforge.net].|