Object-Oriented State Machines - Embedded.com

Object-Oriented State Machines

State machines are extremely useful in managing the behavior of embedded systems. Here's a C++ framework for implementing them with the greatest of ease.

As part of a project to develop a library of software for programming a six-legged robot , we developed a set of C++ classes and utilities for state machine programming. Our framework makes state machine implementation simple and is applicable to a much wider range of embedded systems than just robots.

RHex

The RHex robot was designed with a preference for simplicity, minimal actuation, and sensing. As a result, it is distinguished among walking robots in its ability to easily negotiate broken terrain and obstacles exceeding its ground clearance at relatively high speeds (see www.rhex.net for more). Slightly different versions of the robot are being developed at several universities by many researchers, each of whom is interested in experimenting with one of various mechanical, sensory, electronic, and behavioral alternatives. RHexLib is an attempt to meet the demands of these researchers by providing a design environment that facilitates this joint development and the exchange of software. It provides a runtime environment that manages the various tasks the robot must perform to sense and actuate in the world. It also serves as an API for programmers to easily code and integrate new behaviors and other components.

One of RHexLib's most useful tools for programming new robot behaviors is its state machine facility. State machines are a useful abstraction, well established in the control community, for systems with discrete states that are engaged based on events sensed in the world. A common example of a state machine is a vending machine, in which transitions between system states are triggered by coin insertions and button presses. Larger systems with discrete state transitions can be complex and difficult to manage; one state machine in the RHex robot has 15 states and 16 events. Furthermore, RHex may run several state machines simultaneously, dramatically increasing the number of states to be managed. We introduced RHexLib's state machine facility to manage these state-event systems, making the code more modular and easier to read and maintain.

In this article, after providing a brief overview of RHexLib, we describe the library's state machine facility in detail. We explain how to represent states and events and how to put them together into a state machine, and we give a detailed example. The ideas are simple and powerful and may be easily adapted to applications other than robot programming, as well as systems not using RHexLib.

RHexLib

The source code for RHexLib, the examples in this article, and complete documentation are all freely available at rhex.sourceforge.net. As supplied, the code will compile and run on an Intel x86 running either Linux or QNX. RHexLib also includes a RHex simulator so you do not need one of the robots to execute the compiled code.

Many of the tasks a robot needs to carry out are periodic and repetitive, for example: reading analog inputs, computing control commands, and updating analog outputs. Consequently, robot control software commonly takes the form of a list of update functions, one for each task, executed at a required frequency.

Examples of tasks in RHex include basic analog and digital I/O, PWM conversion, sensor interpretation, and timing. Higher-level (behavioral) tasks include data logging, sensor filtering, reference trajectory generation, and motor calibration. Most of these tasks are common to all but the simplest robots. An application that uses RHexLib likely needs to manage most of these tasks to support experimental controllers and supervisory machines that activate and deactivate behaviors based on user input from the remote control.

In RHexLib, a task is encoded as a module, which means that it is derived from a C++ abstract base class called Module . The class Module contains five pure virtual methods that must be instantiated by derived classes. These are:

virtual void init(void);
virtual void activate(void);
virtual void update(void);
virtual void deactivate(void);
virtual void uninit(void);

These methods have special meanings to an object called the module manager , which maintains a list of modules and executes their code. The life cycle of a module within the module manager is shown in Figure 1. A module's init and uninit methods are called when it is added to and removed from the module manager using the MMAddModule and MMRemoveModule functions. These methods are used to initialize and clean up the module's data structures, respectively. The activate and deactivate methods are called when the module is activated or deactivated using the MMActivate and MMDeactivate functions. These functions perform activities such as activating and deactivating other modules. The update method is called at a certain (configurable) frequency by the module manager, once the module has been added and activated, and until the module is deactivated. Thus, the module manager acts like a kernel of a simple operating system, with modules essentially encoding separate processes or threads.


Figure 1: The life cycle of a module

Some modules, such as those that send commands to motors, can only be activated and used by one other module at a time. A module that requires such a “single-user” module uses the functions MMGrabModule and MMReleaseModule , which behave similarly to the MMActivate and MMDeactivate functions except that they do not allow more than one module at a time to use the “grabbed” module.

All of the tasks just described are encoded as modules, from low-level hardware tasks to high-level behavior controllers. The basic module interface, however, has some limitations, especially when it comes to event driven controllers with discrete states. Without some organization, the update methods of this type of controller can be quite complicated. RHexLib's state machine facility helps solve this problem by allowing a module's update method to behave differently according to the state of the module.

State machines

State machines are very useful and fundamental objects. They are used, for example, in automated factories and automotive control. Numerous software packages are available for modeling and controlling systems using state machines or similar constructs. Without a general tool for managing the discrete logic of a controller, embedded programmers have to resort to ad hoc coding with multiple if-then-else or switch-case statements, often resulting in programs that are difficult to read and navigate. The good news is that incorporating state machines into your own projects is not difficult.

The most common example of a state machine is the vending machine controller. Such a controller has a number of states, corresponding to the amount of money inserted or the sequence of buttons pressed. It also monitors the occurrence of a number of events, such as whether a certain product is out of stock. In each state, certain events will cause a transition to another state and others will not. So when the machine is in state “no money deposited,” inserting a quarter changes the state to “25 cents deposited.” From the “no money” state, pressing the button for a soda does nothing.

In robotics and manufacturing, state machines behave in essentially the same way, possibly with the added complication that while a state is active, a corresponding continuous controller may be run-as with an automatic garage door that is either closed, open, or in the process of opening (or closing).


Figure 2: An example of a state machine

An example state machine, discussed in detail later, is shown in Figure 2. Before we describe state machines properly, let's see how events and states are represented.

In RHexLib, a state machine is a module that implements the virtual methods described above. State machine controllers are modules derived from the StateMachine class, which is derived from the Module class.

An Event is an abstract base class with one virtual Boolean method, called check , which takes no arguments. Derived classes must implement the check method to return true or false , based on checking some condition in the world. For example, an RHex program may have an event that returns true or false based on whether the robot is upside down or rightside up. Coding events as objects in their own right allows them to be reused and makes the code easy to manage.

A State is an abstract base class with three methods that need to be defined by any derived state. These are:

virtual void entry(void);
virtual void during(void);
virtual void exit(void);

At the time a state becomes activated, the state machine that “owns” it calls its entry method once. This allows the state to perform any one-time set-up procedures it may require. While the state is active, its during method functions as the update method of the state machine, which is itself a module (see Listing 1). The during method is where any activity requiring continuous updates, such as the control of a motor, takes place. When a transition occurs out of a state, its exit method is called once, allowing the state to, for example, release whatever resources it may have been using.

Listing 1 The StateMachine class's activate and update methods

void StateMachine::activate(void) { 	current = initial; 	current->entry();}

void StateMachine::update(void) { Arc * a = current->getActiveArc();

if (a != NULL) { current->exit(); current = a->target; current->entry(); }

current->during();}

Each state also contains a list of outgoing arcs (of class Arc in RHexLib), each of which consists of an event and a target state. A state machine keeps a pointer to a currently active state and continuously checks its outgoing arcs. As soon as one of them becomes active (that is, its event's check method returns true), the current state is set to the target state of the arc.

Now, as we have said, state machines are modules derived from the class StateMachine . This base class implements the init , deactivate , and uninit methods of the base class Module as empty functions. Listing 1 shows how the activate and update methods are implemented. The only other difference between a state machine module and a basic module is that the state machine also contains a pointer to an initial State object. This pointer is usually set up in the state machine's constructor using the initialize method.

A programmer does the following to set up a state machine:

  • Define the event objects
  • Define the state objects
  • Add arcs to the states
  • Set the initial state of the state machine

Listing 2 A text file describing the states and arcs in Figure 2

Transition unCalibrated startCommand calibrating
Transition calibrating calFail unCalibrated
Transition calibrating calSuccess standing
Transition standing doneStanding ready
Transition ready accWalkCommand accelerating
Transition ready walkCommand walking
Transition accelerating upToSpeed walking
Transition accelerating noCommand ready
Transition walking noCommand ready
Transition walking stopCommand decelerating
Transition decelerating doneDecel ready
Initial unCalibrated

Because state machines all have the same basic form, the RHexLib distribution provides a Perl script called sm-setup.pl (in the RHexLib/util directory), which converts a simple textual description (such as Listing 2) of a state machine into corresponding C++ code that defines the machine. The resulting code is intended to be a skeleton of the final code. That is, the methods of Event , State , and StateMachine in the skeleton code need to be augmented with the intended functionality of the state machine.

Example

RHexLib and its state machine facility can produce a wide variety of state-event based controllers; they need not be related to robotics. However, because we program robots, we give a more substantial example of a state machine for the RHex robot to demonstrate how the rest of RHexLib works in conjunction with state machines. The example we consider is the supervisor controller shown in Figure 2 and described in Listing 2. The supervisor starts and stops other controllers based on user input from a remote control and also on events occurring in the world. This supervisor activates three other controller types: one for calibrating the leg motors, one for standing the robot up, and one for walking. These other controllers are all encoded as state machines and are part of the RHexLib distribution.

To code the Supervisor state machine, we create the skeleton code from Listing 2 using the Perl script just discussed. (Due to the length of the resulting skeleton code, we do not list it here. The entirety of the code for this example is included with the RHexLib distribution in the directory /RHexLib/examples/esp .) We add functionality to the skeleton code by changing each event's check definitions and the state's virtual methods. In the subsequent listings, we show the skeleton code in black text and the added code in red. We also add data and methods to the Supervisor prototype and functionality to its activate , deactivate , and init methods.

Our state machine functions starts off in the uncalibrated state. When the user issues a start command (via a remote control unit described shortly), the state machine switches to state calibrating and activates a calibration state machine for each leg. These machines set the zero position of the motor encoders and determine the polarity of the motor drives. The calibration machines are themselves state machines with about 10 states each. Six of these machines are run in parallel in the calibrating state. The simplicity of the code in light of this complex task speaks to the power of state machines.

Listing 3 The entry, during, and exit methods of the Calibrating state

void Supervisor::Calibrating::entry(void) {	for (int i = 0; i < 6;="" i++)="" {="" owner-="">calibMachine[i]->setMode(CalibMachine::GROUND);		MMGrabModule(OWNER->calibMachine[i], owner);	}}

void Supervisor::Calibrating::during(void) {}

void Supervisor::Calibrating::exit(void) {for (int i = 0; i < 6;="" i++)="" {="" mmreleasemodule(owner-="">calibMachine[i], owner); }}

The entry , during , and exit methods of the calibrating state are shown in Listing 3. In the entry method, each calibration machine mode is set to GROUND , meaning that the calibration machine swings its leg until the toe hits the ground and determines where it is. Then, using the MMGrabModule function, the calibration module is activated. The OWNER is a pointer to the Supervisor object that contains the Calibrating event and is assigned when the event object is constructed. The during method of the calibrating state does nothing, although the calibration state machines are running separately. The exit method of the state releases (and thereby deactivates) the calibration machines. RHexLib makes frequent use of this technique.

The calSuccess and calFail events check for the success or failure of each of the calibration machines. Occasionally, calibration fails due to low battery voltage or the presence of obstacles in the environment. If calibration fails for any leg, the unCalibrated state is reentered. If the calibration of each leg succeeds, then the standing state is entered. Listing 4 shows an example of an event::check method where the success of the calibration machines is checked.

Listing 4 The check method of the CalSuccess event

bool Supervisor::CalSuccess::check(void) {for (int i = 0; i < 6;="" i++)="" {="" if="" (owner-="">calibMachine[i]->getStatus() != CalibMachine::SUCCESS)		{			return false;		}	}

return true;

}

Once the standing controller is done, the Supervisor enters the ready state. In this state, the Supervisor waits for input from the remote control. The user may either start the walking controller at full speed via the walkCommand event or start the walk controller at a slower speed and then accelerate to full speed. The latter is accomplished via the accWalkCommand event. These events check the state of the remote control input to RHex.

We presently control the robot remotely using a standard two-joystick, radio frequency (RF) remote controller. On the robot, RF commands are converted into pulse width modulation (PWM) signals and are fed into RHex's processor via an analog input board. In software, the PulseWidth module uses the AnalogInput module to read and convert the PWM signals into floating-point numbers. These numbers are converted into values for each joystick that may be read using the leftStick and rightStick methods of the RemoteControl module. These return a value of NORTH , SOUTH , and so on. For example, as shown in Listing 5, the AccWalkCommand method checks that the left joystick is pushed to the right (WEST ) and that the right joystick is pushed either up (NORTH ) or down (SOUTH ).

Listing 5 The check method of the AccWalkCommand event

bool Supervisor::AccWalkCommand::check(void) {return bool (OWNER->rc->leftStick()  == RemoteControl::WEST 	&& (OWNER->rc->rightStick() == RemoteControl::NORTH 	|| OWNER->rc->rightStick()  == RemoteControl::SOUTH));}

Listing 6 The entry, during, and exit methods of the Accelerating state

void Supervisor::Accelerating::entry(void) {// figure out the direction of the joystickOWNER->setDirection(); 

// set up an acceleration profile OWNER->mark = MMReadTime(); OWNER->accelProfile.setupLinear(OWNER->mark, OWNER->mark + ACCEL_TIME, 1.0, 0.5); OWNER->walkMachine->setTurnCommand(0.0);

// activate the moduleMMGrabModule(OWNER->walkMachine, owner);}

void Supervisor::Accelerating::during(void) {OWNER->walkMachine->setForwardCommand( OWNER->accelProfile.getVal (MMReadTime()) * OWNER->direction);}

void Supervisor::Accelerating::exit(void) {}

The accelerating , walking , and decelerating states grab the walking controller and control its speed as required. For example, in the state accelerating , whose methods are shown in Listing 6, the entry method sets up a profile for the speed of the walking controller so that at the beginning of the state it has speed 1.0 (meaning the legs take 1.0 second per cycle) and at the end of the state it has speed 0.5. The entry method also grabs the walking controller. The during method of this state gets the value of the profile for the current time and sets the speed of the walking controller.

The rest of the state machine events and states are similar. There are also some basic changes to be made to the rest of the skeleton code generated. Interested readers can investigate the full source code of this example, which is available online.

Looking forward

The state machine abstraction is a fundamental tool for discrete event system control. We have described how we implement state machines in RHexLib, providing one representation that happens to fit nicely with the module-based approach. We hope that our ideas and classes may find other applications, in other robots and, more generally, in other embedded applications.

The state machine idea is not limited to RHexLib. The ideas are used in many control software packages. Hopefully, the short description we have given here can serve as a guide to incorporating general state machine tools into any project. The gains in code reusability, ease of maintenance, and elegance are worth the relatively small overhead of thinking in terms of states and events.

Eric Klavins is a postdoctoral scholar in computer science at the California Institute of Technology. His research interests are in robotics, control and distributed systems engineering. He received his MS and PhD degrees in computer science at the University of Michigan and his BS in computer science at San Francisco State University. Contact him at .

Uluc Saranli is currently pursuing his PhD in the computer science department at the University of Michigan. His research focuses on legged robot locomotion, with emphasis on analysis and control. In this context, he has designed and built RHex, a highly mobile six-legged robot. He earned his MS in computer science at the University of Michigan and his BS in electrical engineering at the Middle East Technical University. He can be contacted at .

Acknowledgements

This work was supported in part by a grant from the U.S. government, DARPA/ONR N00014-98-1-0747.

Return to the May Table of Contents

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.