2 Background

2 Background

The Mobile Robotics Laboratory at the University of Washington has two identical commercially-produced mobile robots from Denning Mobile Robotics named Miss Marple and Hercule Poirot. In addition, the laboratory has access to a number of workstations that are running Gensymís G2 expert system. This expert system interfaces with the robots through either a radio link or an RS-232 wired connection. These robots and the expert system are the focus of research into autonomous systems. Undergraduate courses have been developed to teach students the fundamentals of mobile robots. The students are given the opportunity to help develop autonomous systems using the expert system tools and the two mobile robots. Some students move on to graduate research in the field of mobile robotics and autonomous systems. Figure 2.1 shows Miss Marple in the hallway next to the Robot Development Laboratory, or RDL. Figure 2.2 shows Hercule Poirot in the Robot Proving Grounds, or RPG, the site of the old Nuclear Reactor Building.

Fig 2.1. Robot in Hallway. Miss Marple negotiating a hallway adjacent to the RDL.

Fig 2.2. Robot in the Robot Proving Grounds. Hercule Poirot exploring the RPG region.

Description of the Denning Mobile Robot

The Denning Mobile Robot has a cylindrical body with three wheels placed on the vertices of an equilateral triangle. The wheels turn in concert to enable the robot to translate. In order to turn, a separate motor rotates the wheel assemblies around each assemblyís vertical axis. This allows the robot to change its desired direction of travel without translation, or "turn on a dime" if you will. The two motors, one to drive, the other to steer, can rotate forwards or reverse. Figure 2.3 shows the robotís configuration.


Fig 2.3. The Denning Mobile Robot. The cylindrical body remains stationary while the head and wheels turn together. The ultrasonics are located around the body.

The base of the robot does not turn with the exception of some slight precession effects. Twenty four ultrasonic transducers are mounted on the base, spaced equidistant and firing radially from the robot. The head of the robot turns with the wheel assemblies, thus sensors can be placed such that they are always facing the direction of motion. The beacon and laser sensors are placed on the head. The Denning Product Manual contains more information on specific hardware issues (Denning 1988?).

Original System and Reasons for a New Control System

The current research at the Mobile Robotics Lab does not involve designing hardware such as motor controllers since these features are provided by Denning, manufacturer of these robots. Denning also provides a real-time multitasking operating system, OS-9 from Microware, to interface with the various robot sub-systems. In addition, Denning provides an application program, DMRMRV, that communicates with the hardware control modules, henceforth referred to as expert modules. This application program also provides a user interface for controlling the robot and obtaining sensor information.

The DMRMRV software is effective in demonstrating the capabilities of the robot; however, it has two major drawbacks when used within the autonomous agent framework:

1) The user interface provides display formatting which makes the product "user friendly," but unfortunately reduces data throughput. Since the formatting information would be transmitted along with the data in a radio or RS-232 link, a performance penalty is incurred. This problem has been solved by Denning with the introduction of MRV-Bridge.

2) The control interface is suitable for experimentation but is inadequate for research. For example, it is not possible to efficiently give a "move" command and then poll the motor until it is done. Each poll of the motor must pass through the radio or RS-232 link. In effect, it is not possible for a user to place a custom program into DMRMRV without first consulting and requesting an update from Denning.

Since the second problem is a major hindrance for serious research, requirements for new robot-resident control software was proposed. Some of the requirements for new software included improving the data-flow protocol at the expense of a user interface, allowing for software enhancements to be made in-house, and incorporating a programming language. These requirements place a greater processing burden on the robotís operating system. While formulating the requirements, it became apparent that the new robot control system would need to use the multitasking capabilities of OS-9. It was determined that the desired improvements would not tax the OS-9 system excessively.


Designing an efficient message passing protocol for robot-to-expert system communication requires more than just a redesign of DMRMRV. A means of encoding a sequence of commands into a single instruction is needed-in effect, an on-line programming language. Programming languages by necessity provide an "encapsulation of control" feature whereby a complex action is executed through a simplified reference at the expense of flexibility. Commonly referred to as sub-programs, functions or macros, these references have the potential advantage of reducing data flow and improving system performance. To simplify the control scheme, the programming language must not have the capability to accept inputs from G2; this task is delegated to the controller. Thus, the macro may only act on stack parameters and produce output reports.

Modifying the existing software (the source code was available by agreement with Denning) would have created unnecessary complications in the design and so the new robot control system was designed from scratch. The Mobile Robotics Lab obtained a C compiler from Microware for an IBM-PC clone to create the new on-board control system.

After serious consideration, it was determined that the on-board control system would incorporate the processing capabilities of the OS-9 multitasking environment. Certain menial tasks that should not be performed in the expert system could be handled in a parallel environment. For example, the expert system should have a "pilot" that receives trajectory requests from the "planner." The pilot translates these requests to a form acceptable by the low-level system which then executes the trajectory request using its own trajectory algorithm. This algorithm is contained within the "controller," an entity that communicates with the pilot. As further commands arrive from G2, the trajectory algorithm will be executing in the background as a parallel task. If DMRMRV were used, the expert system would have to concern itself with the details of trajectory execution; a very inefficient proposition.

Message Passing

Designing an autonomous mobile robot system composed of two separate computing systems requires some method of exchanging meaningful information. Semantics could be defined for the exchange of information between these systems. Since data passes in a serial manner between these systems, a stream-based approach is used. A control language and protocol based on these semantics was designed which would identify and operate upon the incoming message stream. Each incoming word is considered an operator. An operator has certain attributes that define its use in LLAMA and G2. A token is a symbolic representation for an operator. A command interpreter and parser operates upon legal combinations of tokens that arrive in the message stream. Additionally, messages can be considered units of information that flow between two computing systems in the message stream. The message exchange must be understood by both computing systems, but in a robotic system where one computing system controls the other this understanding is unidirectional. For example, control messages would never flow to the controlling computing system.

The controlling computing system shall be referred to as the supervisor (the G2 expert system) and the controlled system the implementor (LLAMA). In this system there exist three types of messages:

Commands-Commands are sent from supervisor to implementor. These are messages that instruct the robot to perform some action. A command is an operator directed to LLAMA.

Solicited Reports-Reports are sent from implementor to supervisor. These are condition and sensor messages from the robot that arrive directly as a result of a command.

Unsolicited Reports-In a complex robot control system condition and sensor messages from the robot may arrive at any time and are thus considered unsolicited reports.

Message Elements

Messages are composed of three types of elements:

Identifiers-An identifier is a piece of information that will directly affect the state of the system to which it is sent. Identifiers may or may not be associated with data (see below). An example of an identifier would be the command "move." A token is an identifier or data but not a delimiter (see below).

Data-Data is a piece of information that is associated with an identifier and may change each time it appears with that identifier. Some examples of data: numbers, such as 122 or -3, words, such as "on," "yes."

Delimiters-Delimiters are usually blank spaces and are used to separate identifiers and data. In a compacted messaging system delimiters are not needed.

Representation Scheme

Once the quality of the message passing approach was determined, the actual representing mechanism was defined. Since the existing communications system relied on 8-bit serial data, the standard ASCII character set was chosen as the basis for the message elements. Using the ASCII character set is convenient because any terminal screen can be used to display the messages. In addition, a terminal can be used by the developer to quickly validate commands and reports. This approach was used for initial development of the robot controller while the G2 interface was being developed.

The trade-off in using the standard ASCII character set for message passing is that messages are not coded in the most efficient format. However, during development messages must readable; they should have a mnemonic quality. A compromise was reached: messages would be encoded in text-like phrases; a compressed format, used in high speed communications systems, would not be used. Efficiency is related to how many binary bits are used to represent each message element; the fewer, the better. This remark is based on Shannonís theories on communication bandwidth and is covered in detail in chapter seven of Lew (Lew 1985). Nevertheless, the gain in understanding outweighs the loss in efficiency of data transmission. In the future, a "data compressor" could be added to compress and decompress the data if the utmost in efficiency is desired.

Post-Fix Notation and Threaded Interpreter Languages

The next decision was to use a stack-based architecture for the robot controller. Post-fix notation was chosen since instructions are not "tied" to their arguments. What this implies is that other instructions may operate on the desired instructionís arguments by manipulating the stack. These instructions can be referred to in the general sense as stack operators. The graphic arts language PostScript and the general control language FORTH are bases upon which the LLAMA system was developed.

The FORTH implementation is a marriage of various desirable system behaviors and contents: The stack provides a location for fast number manipulation, an interpreter and compiler provide facilities for rapid prototyping and the threaded interpreter produces easily compiled and efficiently executed program code. Loeliger provides a succinct explanation of a threaded interpreter:

"A threaded code interpreter produces a fully analyzed internal form. The internal form consists of a list of addresses of previously defined internal forms [macros]. The list is threaded together during the first translation phase. The first phase is remarkably similar to that of a compiler and is generally called the compile mode. During execution the interpreter executes consecutive internal forms without performing any analyses or searches, since both were completed before execution was evoked" [emphasis Loeliger] (Loeliger 1979, 2).

Operators and Tokens

Languages which execute in a threaded interpreter typically use post-fix notation. Such languages have two very important qualities:

Quality 1-Command elements can be described as operators and are composed only of instructions and numbers. These are referred to as objects in PostScript (Adobe Systems Incorporated 1988, 4).

Quality 2-Each operator is separated by at least one delimiter. When viewed as a message element, an operator is referred to as a token.

In LLAMA and FORTH instructions are composed of macros and primitives. Macros are an ordered sequence of primitives, other macros, and/or numbers. To facilitate reporting of information, LLAMA has what are known as report elements, which are composed of report identifiers and report data.


Why was FORTH chosen as a base for the command interpreter? Brodie, in his book on the philosophy of FORTH, notes the following:

"FORTH exhibits . . . mnemonic value, abstraction, power, structured control operators, strong functional binding, limited coupling, and modularity. But regarding modularity, we encounter what may be FORTHís most significant breakthrough: ĎThe smallest atom of a FORTH program is not a module or subroutine or a procedure, but a word.í Furthermore, there are no subroutines, main programs, utilities, or executives, each of which must be invoked differently. Everything in FORTH is a word" [emphasis Brodie] (Brodie 1984, 19).

LLAMA retains this singular trait but enhances it with non-FORTH constructs such as implementing FORTH words as C language subroutines. This deviation from the "FORTH philosophy" will be explained and expanded upon shortly.

Background on Robot Control Languages

There appear to be two major problems in the field of robot language design. The first problem is a question of whether it would be more efficient (in development and operation) to adapt an existing language for robot control than to develop a language from scratch. The second problem is the lack of unity in the approach to designing robot control languages. The second problem materializes when, for example, two different brands of robot arms are controlled from the same software.

It would seem that an efficient and capable robot control language could be created from scratch rather than choose an existing language. The new language could be made efficient since it would not be adapted from an existing base but would be made specifically for use in robot control. Rock, in his paper that surveys robot programming languages, concludes that "[N]o current language forms an adequate base for intelligent robot programming languages. What is needed as a base is a language for use in the artificial intelligence domain, that incorporates real-time facilities" (Rock 1989, 71). Although not explicitly stated in his paper, Rock is referring to manipulators; however, this argument also applies to certain classes of mobile robots, including the G2/Denning system.

Referring to robot arms, Rembold states: "[T]here exist more than 100 different kinds of robot programming languages" (Rembold 1987, 5). It would not be a great extrapolation to say this may one day apply to mobile robots. However, what applies to robot arms does not necessarily apply to mobile robots: Brooksí subsumption architecture does not rely on an explicit programming language. The question remains: does a mobile robot need a control language?

Reasons for a Mobile Robot Programming and Control Language

Mobile robotic research usually approaches a problem in one of two ways: (1) "task specific," to meet certain application requirements, such as Evansí hospital aid robot (Evans, et al. 1992); (2) "adaptable in a local frame," where a complex problem such as obstacle avoidance is solved without concern for global issues such as adaptive path planning and sensor fusion. Brooks uses both approaches but has limited himself to the constraints posed by his subsumption architecture, such as avoiding the use of traditional data structures to represent meaning. Borenstein and Koren use data structures to their advantage and claim their vector field histogram approach to obstacle avoidance is more stable than Brooksí (Borenstein and Koren 1991, 279). However, Borenstein and Koren do not present any interface specifications. Current research veils the interface details under the premise that the robot control systemís algorithm will provide the necessary end result.

The danger lies in extending such an approach to problems that are too complex to solve in an algorithmic manner. A complex robot system contains many algorithms and their interaction is of prime importance. Brooks points out, "if you notice that a particular interface is starting to rival in complexity the components it connects, then either the interface needs to be rethought or the decomposition of the system needs redoing" (Brooks 1986, 15). If the interface between modules, and perhaps also between algorithms, is well designed and part of the overall system design scheme, then the patchwork that accompanies the enhancement of one algorithm is removed.

Evansí hospital aid robot is impressive in its accomplishments and shows that various robot subsystems can be integrated effectively to create a working semi-autonomous robot. It is apparent, however, that changing the environment from hospital to, say, a warehouse would place different burdens on the robot system. The robot may be restricted to certain corridors or may have to traverse large open areas. This would change the original algorithm, and might change the hardware, resulting in more design and troubleshooting work. Referring to the current project, if the interfaces were general enough and specialized algorithms could be developed, then the autonomous system could be rapidly reconfigured for use in different environments. By noticing environmental and robot-specific constraints, the system could be tuned to the application, resulting in a packaged autonomous system. If hardware could be added to the system and the interface configured without significant impact on the system as a whole, then the new hardware could be integrated into the autonomous system fairly rapidly. Assembling modular systems with specific interface requirements is a problem that industry views as well-defined. The LLAMA control system has the elements that can make it part of such a system.

If a mobile robot control and programming language were developed that could be improved incrementally and if a high-level system could operate upon this language in a consistent manner, then creating a mobile robot programming language is justified. In fact the language would be part of the mobile robot system where the high-level component could generate new constructs in this programming language. In this case the autonomous system would be self-programming. In the context of the previous paragraph and assuming the low level system has a limited set of commands available directly then note the following: If the userís configuration of the autonomous system needed certain macros, such as a door traversal, to execute on board the robot, they could be downloaded, compiled and executed as needed at run-time.

While developing such systems, a monitor could be inserted between the high and low-level systems and the behavior of the overall autonomous system could be observed with ease. The high-level system would be given tools to create simple skills from the available commands. These skills could be placed in a data base and recalled to generate complex skills called performances. See Albrechtís explanations for details of the overall system (Albrecht 1992). Ultimately, such a system could translate a command from a user: "Go to my office," and the robot would perform the associated complex action.

The need for a robot control and programming language has been established in the context of a reconfigurable system. Such a system would not be limited to simple functions but would allow for complex behaviors, such as obstacle avoidance. A function could be implemented either within a macro or in a called function, which is usually referred to as a primitive (only in the sense that it is not a list execution device such as the macro). A complex primitive shall be referred to as a virtual function, since its behavior cannot be defined as an equivalent macro.

FORTH Used as a Real-Time Robot Control Language

The choice of FORTH as the fundamental programming language for the implementor portion of the autonomous system is based on its inherent efficiency of operation. FORTH uses a threaded interpreter to execute complex sequences of instructions. FORTH is simple and efficient because there is little execution overhead: A macro is a sequence of operators whose start addresses are contained in a sequential list. To execute a program (macro) it is a matter of going through the list one instruction at a time. An instruction may call another list, and thus allows the design of complex programs. Looping constructs are available, thus making FORTH suitable as a general purpose programming language.

It may be argued that the language is difficult to follow: "Programming in FORTH is a very personal activity and the code that is produced invariably is not maintainable. . . . There is also a problem when projects of size are required" (Rock, 1989, 74). We claim that these traditional complaints are ungrounded in the context of our autonomous system. If a high-level system can be given enough information about each primitive in FORTH, then an automatic code generator can be developed, delegating code maintainability to the high-level system. Such issues are discussed in chapter 5 and chapter 6 . LLAMA implements many of the basic FORTH operators, either as macros or primitives. Each operator was chosen to be useful and applicable in developing structured macros, thus ensuring consistent operation of the system.

The LLAMA System

LLAMA is the name given to the new robot control language and control system. It is used in the form of a software package that executes on a Denning Mobile Robotís OS-9 multitasking operating system. It was decided that LLAMA should contain an interpreter and a coordinator. The interpreter would be based on FORTH and would contain a subset of the common FORTH primitives and macros. Any non-FORTH primitives added to the system must conform to FORTH usage, such as allowing stack access and compilability. The coordinator would provide a high-speed blackboard that any parallel process may access. The coordinator would also provide a command queue for incoming control requests.

So Why is LLAMA Not FORTH?

LLAMA was chosen to mimic FORTH since the compiler and interpreter are accessed from the same interface. The philosophy of "rapid prototyping" is fundamental to FORTH, and applies to LLAMA. Compiling a definition into a macro typically takes less than one second. This speed results because macros within a definition have been previously compiled and the tree-like structure of macro calls lends itself to short macro definitions. However, FORTH is designed from the ground-up, which means that the language is created from certain fundamental primitives. With the vast repertoire of commands available in standard versions of FORTH, a programmer can create virtually any desired program, be it an interface controller or a floating point emulator. The penalty is understanding how each command operates. An additional problem is that FORTH control statements anticipate a properly organized memory space, which includes the macro lists, stacks, etc., in a special format. Such organization prevents the merging of FORTH with C functions in the OS-9 system unless elaborate system configuration measures are taken. The result is a near-complete lack of control statements in LLAMA. In this case Rockís warning regarding the maintainability of large FORTH constructs is an apt assessment. Naimoli presents a FORTH that is composed entirely of C code (Naimoli, 1988, 98). It is interesting to note that he did not include standard FORTH control statements. Naimoliís approach was not implemented in LLAMA since that C implementation is not efficient.

By delegating certain processing functions to C programs, FORTH-like functions could be created on short-order in the C language and called within LLAMA as any other primitive. By eliminating FORTHís control structure, new functions can be written that require less debugging. Also, most engineering students know how to program in C. A student adding a function to the LLAMA system would need not learn every detail of programming in FORTH.

Building Applications for Autonomy

FORTH is a well-behaved language. It is consistent and qualifies as a structured language. LLAMA retains these qualities, yet it is not just a programming language but also a real-time controller. This additional capability places a burden on quantifying the language. For example, a motion command may return a value before physically completing its motion whereas a simple calculation will result in a value only after it has completed. This topic will be covered in chapter 5 and chapter 6 .

Once the language is quantified, a skill generator can be developed in the expert system that will combine LLAMA primitives and macros into meaningful commands. Skills can be combined to form performances which are then packaged into performance orders. The performance orders are eventually transmitted to LLAMA. Skills may come from different agents in the expert systemís knowledge base (Albrecht 1992). Skills that are themselves logically consistent are not necessarily consistent when assembled into a performance. A consistency evaluator would be needed to "catch" any problems that may have arisen in building the performances.

Since a person building applications will not have to read FORTH code directly, but will simply call existing skills, the issue of maintainability is resolved. As will be shown, if a performance order is accepted after a consistency evaluation then the expert system becomes its own maintainer of software! Also, chapter 6 suggests a possible method of reducing the programming burden by using a visual programming technique for LLAMA from within G2.

Report Specifications

Since FORTH has no specifications on solicited or unsolicited reports, any appropriate, well defined, scheme can be used to generate reports. The chosen scheme is as follows: A report identifier is followed by at least one delimited report datum. This report element is sent to the high-level expert system. Note that this is a pre-fix arrangement if the report data consists of numbers. Pre-fix notation was chosen to simplify the expert system interface.

With these specifications, the system will already surpass the DMRMRV program in terms of efficiency. To truly complete the picture, multi-tasking is needed within LLAMA: New macros could be downloaded as a sequence of tokens while an existing macro executes in the background.

Writing the Code

The biggest issue in creating a new robot control system was how to write the program. LLAMA was to have been based on actual FORTH source code for a 68000 processor; the problem was obtaining code that would also work within the constraints of OS-9 and allow interfacing to C programs. Research into obtaining an existing product that would meet the specifications was unsuccessful. Since FORTH is usually implemented in the processorís assembly language for reasons of efficiency, the issue of how to implement the stack-based system became very important. Initial attempts to write a simple compiler and stack based system in C were remarkably successful and the performance penalties were deemed insignificant (C tends to be somewhat slower than pure assembly language). Since the issue of maintainability was important and it was known that C would give results, as it had in Denningís DMRMRV, the new robot control system was written in C.

Implementing Multi-tasking Capabilities

Another important consideration was the merits of implementing multi-tasking features into the robot control system. Denningís DMRMRV did not take advantage of the multitasking capabilities of the OS-9 operating system, probably due to the extra complexity that multitasking presented to the system. If multitasking was to be implemented it had to be reliable. OS-9 has proved to be a reliable operating system in other applications and it was well suited to the task of parallel processing in systems with limited memory. A new FORTH construct, a context switch to parallel mode, was developed which allowed any sequence of LLAMA macros, primitives (with some restrictions), or numbers to be executed concurrently. Another issue was simplicity and the ability to describe the behavior of the system effectively; chapter 5 , chapter 6 and appendix B explore this topic by approximating the behavior of the system using finite state machines.


The robot can be enhanced in its capabilities by installing various hardware from the manufacturer, however, custom-built systems were not supported. Part of this research involved designing a speech synthesizer that would interface with the communications channel for the subsystems. This required identifying the protocol used and implementing the subsystem host as assembly code for a micro-controller. Chapter 8 discusses some of the issue in designing such a system. The micro-controller manages the flow of data to the speech synthesizer. The project was successful and has become a spring-board for future additions such as an inclinometer, CCD camera interface, gyrocompass, sensor directional controllers, and many other possibilities.

Return to Thesis Index