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