Select a style sheet:
Autonomous Walking Robots: A Modular Approach

Terry 'Mongoose' Hendrix II <stu7440@westga.edu>

    Designing autonomous walking robots requires the use of modularization. The problems involved with making an autonomous walker break into several groups of functionally. Trying to build a single grand model that fits your idea of a walker is difficult at best. It's fortunate that like almost all complex problems, it reduces to more manageable smaller problems. Making a single finite state machine to control the robot and all of it's motors, data collection methods, and planning would be very difficult to implement. It would also be very hard to debug the robot when errors occurred during testing. The use of modules also makes it easier to scale your project quickly, allow for division of labor during production, and can be more resistant to failures.

    This paper will break down a project that used a modular approach, and was featured in Dr. Dobb's Journal, February 1997. In the article Robots and Finite-State Machines, Everett F. Carter, Jr. goes in great detail of hardware components used in his design. This paper will deal only with the design aspects and general hardware specifications. This article is intended for lay persons interested in design issues of robotics, and it is assumed the reader may not have an electronics or artificial intelligence background. There will follow a break down of the principals of walking, a beginners guide to finite state machines, the hardware/software interaction, and finish up with the module interaction.


The Walking Machine Overview

The robot built was a six-legged autonomous walker: 22 inches long, 10 inches wide, and had 7 inch long legs. It had an array of sensors: a pair of ultrasonic sonars for finding and mapping objects 9 inches to 30 feet away, active infrared (IR) detectors for finding closer objects at about 14 inches, and final collision detection is handled by 8 inch long whiskers. To be clear, the whiskers detect actual contact with an object. The sensors are mounted on a movable head that can pitch 45 degrees up and down as well as pivot 45 degrees side to side. The reason for mounting the sensors on a central location is to cut costs. A costly ring of sensors can be simulated by rotating the head, while keeping up with the head position relative to the body. Three types of sensors are used to provide redundancy, since each detection method has a different range and uses a different physical principal.

    The walking system has a simple design. The robot doesn't need to actively balance itself, which is referred to as dynamically stable. The robot is statically stable, it uses special gait sequences to compensate for varying terrain texture and sloping. Each gait sequence varies the order of which leg moves relative to the other legs. Each leg in the gait does the following during it's cycle:

1. Raise the leg.
2. Swing the leg forward or backward a certain amount.
3. Lower the leg back to the ground.
4. Push or pull the leg back to the center position.

    The two major types of gaits are periodic and nonperiodic. The machines using nonperiodic gaits are better for complex terrain, yet require foot contact and pressure feedback. Periodic gaits, which always repeat the sequence of leg orders, are easier to implement. There are subsets of this gait type discussed by the designer. Backward wave gaits are the most stable and are similar to animal's biomechanics, on each side the front legs move first then the back legs move. Equal-phase on the other hand, aren't as natural, but distribute the placement and movement of legs evenly over the act of walking. Equal phase gaits are also very energy efficient, due to its distribution method. The gait type used for this machine used both equal-phase (1, 4, 5, 2, 3, 6) and the backward wave gait (1, 2, 3, 4, 5, 6). Note that legs are numbered front to back, with odd numbers on the left and even on the right.




Finite State Machine Overview

A finite state machine (FSM) is a data model that allows a programmer to represent a list of rules in the forms of states, conditions, and transitions. Every FSM can be represented with a graph, much like a rail road map. States, the function-like component, can be thought of like a rail depot. Transitions, the movement between state to state, can be thought of as the railroad tracks. Conditions are things that must be satisfied to do a transition, like a switch to change tracks. To reach one state from another the railway must be transversed in an set order.

    Here is an example using the FSM in Figure 1 with a possible scenario. In the state "Bump Scan", the robot reads input from it's left and right whiskers. If the condition "Right Contact" is true, then a transition from the state "Bump Scan" to the state "Right Bump" will occur. ( "Right Contact" is true when the right whisker touches something. ) Inside the state "Right Bump", the robot tries backing up and turning to avoid the collision it detected in the state "Bump Scan". Once the condition to make a transition from "Bump Right" to "Bump End" is satisfied by a time out or the turn is complete, the transition is made to the new state "Bump End". The state "Bump End" will enter a sleep or wait, freeing the CPU for another FSM to run. When it's the Bump Machine's turn for the CPU again the timer in "Bump End" will expire and make the transition to the "Bump Scan" state. The "Bump Scan" state will now check the whiskers again. I should note that this isn't a textbook model of a FSM, where a they wouldn't allow a timer event. However, real world controls require event driven models to be able to be preempted and other cases lead to having to augment computer science model.




Software/Hardware interaction

The language used to implement the software modules was FORTH. FORTH is a language of choice among many microrobotics designers and hobbiest, since it can be incrementally compiled and tested per module.

    The robot's high level (the part that make decisions like turn left) system is a single board MC68332 based system board, and it's different your PC in several ways. Their is an on board FORTH compiler/interpreter, which acts as the operating system as well as the programming language. The only user interaction with the machine is via the built in RS-232 interface, which is used to load the software onto the system. In abstract, this is much like a PC user downloading software to execute on their machine, or uploading a web page. Once the program is loaded on the robot it's completely autonomous, and needs no user interaction. Also during testing, a designer can actively control the robot by this interface for debugging software or hardware modules.

    The robot also used the IsoMax system, which is a finite state machine engine that runs on top of the FORTH compiler. It allows you to work on the high level problems and not worry about writing and testing an entire FSM per module. Four steps to make a FSM with IsoMax:

1. Append the list of states to the machine.

Here we have the machine PROXIMITY composed of five states.

STATE-MACHINE PROXIMITY
   APPEND-STATE   IR_SCAN
   APPEND-STATE   LEFT_IR
   APPEND-STATE   RIGHT_IR
   APPEND-STATE   BOTH_IR
   APPEND-STATE   END_IR

2. For each state append conditions for its transition to another state.

Here we see the state IR_SCAN. If both IR sensors detect and object, the word BOTH_IR will be true. If BOTH_IR is true then the words between CAUSES and THEN-STATE are ran. Here that would call the ARBITRATE word to make the robot back up from the object. The scope of the state is from IN-STATE to TO-HAPPEN, all other conditions leave the state unchanged from their previous value.

IN-STATE IR_SCAN
   CONDITION BOTH_IR?
   CAUSES PROXIMITY_VEC
      SET_REVERSE ARBITRATE
   THEN-STATE BOTH_IR
TO-HAPPEN

3. Now all the machines are linked into a composite machine.

In IsoMax priority isn't given by the order the machines are listed. Priority was given in the robot by calling the word ARBITRATE from state transitions. This word arbitrates, by selecting the nest machine to run based on priority. Notice the machine PROXIMITY is just a word here. 

MACHINE-CHAIN ROBOT
   SENSOR
   WALKER
   CONTACT
   PROXIMITY
   EXPLORE
END-MACHINE-CHAIN

4. Before running the machine chain, machines must define an initial state.

WALK_FORWARD	SET-STATE
IR_SCAN		SET-STATE
BUMP_SCAN       SET-STATE
IDLE		SET-STATE
IDLE_MOTION	SET-STATE



The FSM Modules

    The robot is driven by several FSM modules wrapped in an arbitration layer as you have seen, now let's see tasks of each module. These modules are free of each other and don't share any critical sections, as they defer to the arbitrator and other modules. You could consider these as objects in an object oriented language, since all they do is message passing.

SENSORS
runs all the robot's environmental input devices, and also initialized all subsystems when the robot is activated and when deactivated shuts down the robot.

WALKER
this implements the gait of the robot. It defines which leg order to use, and how to move each leg. It normally cycles through all the legs idles then repeats. True to it's periodic gait design. Stopping for emergencies is well defined to ensure it won't topple over.

EXPLORE
is the roaming artificial intelligence of the robot. It uses the sonar to determine an open path or clear area, then advances to that position. The direction explore decides can influence the WALKER gait sequence.

PROXIMITY
uses the IR sensors to avoid collisions. It can override EXPLORE directives to WALKER. When it senses an obstacle, it will pass a message to WALKER to turn.

CONTACT
monitors input originating from the whiskers. When it senses a collision it calls WALKER and backs up several steps, then turns. This machine has the highest priority of the three high level machines.

ARBITRATE
isn't a machine, it's merely a routine. However it's very important in that it allows all the other machines to interact with well defined priorities.


ARBITRATE
   CONTACT_VEC     @ DUP IF EXECUTE EXIT ELSE DROP THEN	 
   PROXIMITY_VEC   @ DUP IF EXECUTE EXIT ELSE DROP THEN
   EXPLORE_VEC     @ DUP IF EXECUTE EXIT ELSE DROP THEN
   WALK_VEC        @ DUP IF EXECUTE EXIT ELSE DROP THEN

Put simply this sets the priority of each machine by it's order in the test condition. For example if CONTACT_VEC and PROXIMITY_VEC were active, CONTACT_VEC would be the one to get the CPU and be handled first.




Wrapping Up

The modular approach let's the designer focus on each part fully, and make design issues of module interaction less of a hassle. It also allows for a designer or groups to develop a module at a time and speed a long production. System failures are more manageable and it's easier to implement the design. Next time you design a program or robot, think modular.