HOW ROBOTS BEING PROGRAMMED?

Programming Robots

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.

Basic computational models

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.)

What is a useful computational model for programming robots?

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:

• memory - random access memory (RAM) that serves as storage for program instructions and data
• arithmetic and logic unit - (ALU) that includes a set of registers and circuitry for performing primitive calculations
• control unit - responsible for fetching and decoding instructions and arguments so as to perform appropriate operations
• bus - various internal pathways for transferring instructions and data to and from memory, registers and the ALU

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.

• input/output - (I/O) subsystems that allows the computer to communicate with the outside world including mass storage devices such as tape and disk

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.