5 The LLAMA Control Language

5 The LLAMA Control Language

Ideally, a mobile robot programming language should provide access to all sensors and effectors. It should also provide a means of scheduling commands. LLAMA provides access to sensors and effectors through a variety of primitive functions directly accessible through the command interpreter. LLAMA includes a macro compiler, a concurrent process generator, conditional expressions, scheduling primitives and many of the elements found in general programming languages. These provisions ensure that nearly any desired robot behavior can be executed (or at least approximated) without resorting to special non-LLAMA functions. If complex behavior is desired, special functions can be developed in C and executed from the command interpreter.

Programming and Control Languages

A programming language for the purposes of this discussion is an allowable ordering of a set of symbols, known as semantics, typically used to implement algorithms. An algorithm usually contains conditional and looping primitives. To be a programming language in a practical sense, the language must be implemented on a computing device (difference engine, digital electronic computer, neural network, etc.) and must accept arguments (inputs) and produce results (outputs). A programming languageís physical instantiation usually takes the form of a program compiler or program interpreter, usually referred to without the "program" preface.

Symbols (sometimes referred to as instructions) in a programming language are arranged according to the programming languageís semantics to form a program. Most programs, including FORTH and LLAMA programs, can be expressed as a linear sequence of symbols. Programs for massively parallel or rule-based systems may not have such a simple ordering. We define a program as an ordered set of symbols from a programming language to describe the execution of (an) algorithm(s). Programs and their interpreters and compilers are abstract entities which become useful when mapped into the electrical states of a binary computer. These programs manipulate other abstract entities typically numerical data.

If a symbol in a programming language represents an action on the part of some physical device and if such an action would cause some desired change in the immediate environment of the device, then that symbol is a control symbol. If an interpreter permits a control symbolís associated action to take place, then the programming language becomes known by the extension, control language. For our purposes, a control language contains symbols much like a programming language except that certain symbols are chosen to manipulate physical objects, rather that abstract entities.

Physical changes in the environment are usually represented by both their physical and temporal relationships, for example, the velocity of an object is the derivative of the objectís position with respect to time. Many of the robotís actions are governed by such relationships. Scheduling instructions are used to regulate the temporal behavior of the mobile robot.

In some cases a control language may not include conditional branching if the robot is used for straightforward tasks. Variations of control language structure are frequently encountered in robotics. A "teach-box" is a robot interface that allows a user to program a sequence of instructions for a robot to perform. The sequence is linear in that conditional branches in the programís flow are not allowed. Typically, as each instruction is programmed, the robot performs corresponding physical motion, giving the programmer instant feedback on the success or failure of the program. Teach-boxes are typically used with robot manipulator arms. A teach-box could be enhanced if the control language included conditional branching and scheduling. This gives the system a greater potential for control. It would allow a robot arm to perform one task a number of times without duplicating sections of the program. A feedback system could be coded using conditional primitives. The rapid development and test cycle inherent in the LLAMA system nearly qualifies it as a variation of the teach-box.

A complete programming or control language will include a means of manipulating numbers. A variable can be used for storing results of computations or sensor readings. LLAMA implements a number stack, also known as a Last-In First-Out (LIFO) buffer. In addition to variables, many LLAMA and FORTH instructions place and receive values to and from the stack. Once numbers can be manipulated easily in a control language, many different programs become possible. For example, an obstacle avoidance program might request the direction of the farthest ultrasonic range reading. If the ultrasonic values were placed on the stack and compared using some maximizing algorithm, a direction corresponding to the direction of the maximized reading could be obtained. The program would use stack manipulations and occasional use of variables to continuously update the desired direction of travel. Figure 5.1 shows the relationship of control and other languages to LLAMA.

Figure 5.1 Control Languages - Relationships of LLAMA to standard robot languages.

Compilers and Interpreters

Compilers take a linear symbolic representation of a program and translate it into a more efficient and executable version of the program. Most compilers generate machine-executable code, obviating a need for further compilation or interpretation. Compilers usually produce the most efficient program code, in terms of speed. An interpreter, which is generally less efficient at executing a program than a compiler, operates on each instruction in a linear symbolic representation of a program. A command interpreter executes either a compiled version of a program or interprets and then executes the sub-programs. FORTH implements a command interpreter that can compile and execute programs. LLAMAís command interpreter includes a program that compiles references to sub-programs (primitives or macros) into a list. This list is not directly executable by the system but is processed in a very efficient manner to simulate compiled program execution. In LLAMA, such a list is called a macro.

The three most common methods for executing robot control programs are as follows: compiled, directly interpreted, and interpreted including an on-line compiler. A teach-box is an interpreted including an on- line compiler program execution system as is LLAMA and FORTH. Denningís DMRMRV programs are directly interpreted meaning that the program must reside elsewhere (the external program could include looping constructs, but the response time would be abysmally slow). For reasons of program speed, many mobile robot software control systems use compiled programs. To help determine the kind of system in use, the following aid is helpful: If algorithms can be defined and executed at run-time, it is an interpreted including an on-line compiler system; if a program must be down-loaded or entered each time it is used, then the system is directly interpreted. If a program has to be compiled prior to use, it is a compiler-based system.

Temporal Binding

When a programming language is extended or adapted into a control language, the execution of a program becomes dependent on the state of the environment. Programs that implement computational algorithms execute at their leisure. If a more powerful computer were used to execute the program the programís results would be the same but would be computed sooner than with the original computer. In a control language, events are scheduled for a certain time, irrespective of the computerís power or speed (unless the computer is so weak that the processing overhead could not keep up with the scheduling requests). Certainly, a programís execution must respond to these scheduled events, otherwise chaos is bound to ensue. For example, a one second delay might be needed in the program to meet some scheduling criteria. A program that waits for one second also halts for one second. Such a delay may be implemented by setting a system alarm interrupt that wakes the program when the requisite time has elapsed. Alternatively, a counter that advances to a known value, representing a one second delay, could also be used (unless the computer speed were increased, in which case the delay would be less).

Control languages are usually implemented on real-time computing platforms to meet scheduling demands. OS-9 is a real-time operating system. Burns and Wellings quote Young who defines a real-time system to be: "any information processing activity or system which has to respond to externally-generated stimuli within a finite and specified period" (Burns and Wellings 1989, 2). We use the above to define a real-time control system and extend the definition to include "internally-generated stimuli" since program flow may depend on some internal system condition such as the setting and reading of a variable.

A scheduled program will execute in bursts. A program that waits for some system hardware response can be expected to cause a delay in the program flow. For example, a program might wait for a robot to move two feet. The program would wait for the desired outcome (moved two feet) and then continue executing further instructions. Here the program does not wait for a scheduled event but a conditional event and would be implemented using conditional branch statements. In both the conditional and scheduled cases, the program has become temporally bound. Temporal binding occurs whenever a program halts for some external condition even though the program may not contain explicit temporal control instructions. In some cases, a program may be temporally bound forever. If a program instructs the robot to move one foot forward at a speed of zero feet per second and then wait until the motion completes, the program becomes temporally bound forever. Although such an example may seem contrived, it would be possible to accidentally generate a zero velocity parameter as a result of some previously errant algorithm.

LLAMA is a temporally bound control language, however, in the interest of efficiency, certain instructions, such as "move" are not temporally bound. If a programmer is not aware of such a distinction, his or her programs will very likely fail, or at best misbehave. When a "move" instruction is sent to the expert module that controls the drive motors, the expert module becomes available for further instructions such as "stop"; if "move" were temporally bound and could not be overridden during its execution, robot control would be lost. But: a sequence of "move" instructions must be sent to the expert module one at a time, waiting for the previous instruction to complete, which contradicts the previous argument. A "drstop" macro was developed that would wait for the move to complete. If two "move" commands are sent in succession without a "drstop", the second will immediately supersede the first and destroy the intent of the sequence. A "move" followed by a "drstop" form a temporal binding for the move motion.

The contradiction mentioned in the previous paragraph can be resolved by using a construct known as a "spawned interpreter". A spawned interpreter can execute a program as a parallel process in LLAMA. Only the system interpreter, a command interpreter, accepts input from G2. It not only compiles programs, but also can execute individual instructions. Instructions that cause a temporal binding that lasts forever can be overridden by other instructions if the former are executed by a spawned interpreter and the latter by the system interpreter.

When instructions are sent to a spawned interpreter, the system interpreter becomes available the moment the spawned interpreter program begins execution. Starting a spawned interpreter is a temporally disconnected process when viewed from the command interpreter. Each spawned interpreter can execute nearly all of the commands available to the system interpreter. If the spawned interpreter program becomes temporally bound forever, G2 can send an instruction through the system interpreter that will stop and remove the halted process; thus, a "drstop" executing in a spawned interpreter can be terminated by a "stop" followed by an "exit" command in the system (or other spawned) interpreter. The program that executes in the spawned interpreter may or may not be temporally bound, or could be both.

Constants and Variables

The LLAMA system uses a very simple method of creating and using variables, however, the multitasking nature exposes some limitation in their use. A variable or constant may be defined in the system interpreter. Any interpreter may access these constants and variables. A problem may occur if one interpreter accesses a variable while another is writing to it as a parallel process. This problem can be avoided by ensuring that at most one parallel process (interpreter) may write to these variables. Such restrictions can be handled by appropriate scheduling of tasks from G2.

By limiting access to variables, G2 can use global variables as if they were local variables. By building constraints into the use of variables, it is possible to overcome limitations inherent to the LLAMA system. Local variables could be implemented in the system, but they would have to be explicitly coded into the LLAMA C code, which would affect a number of LLAMA C functions.


Return to Thesis Index