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.
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?).
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.
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.
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.
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.
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.
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).
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.
"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.
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?
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.
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.
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.
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.
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.
Return to Thesis Index