In the last post, I wrote briefly on how the goal modeling task – described by the O-MaSE agent-oriented design methodology – is useful for laying out a birds eye view of what you want your (multi-agent) robot(s) to accomplish.  The simple act of decomposing high level goals into sub-goals goes a long way towards defining the overall scope of what your project is aiming to achieve.  But the goal modeling exercise is only one tool among many other analysis & design techniques.

Another technique that I find incredibly valuable, is the use of UML State Diagrams to visually express robot behaviors and transitions among behaviors.  If you’re unfamiliar with them, state diagrams are a quick and easy way to document states a system may be in and how the system progresses (or regresses) from one state to another.  It’s also very effective at describing which behaviors can be run concurrently and which require sole attention before moving on.  Furthermore, state diagrams aren’t just for simple projects; indeed, they’re simplicity scales well to capture even quite sophisticated domains, such as autonomous unmanned vehicles.  Reading through Junior: The Stanford Entry in the Urban Challenge, the authors define the behavior states which the vehicle can be in and how each state transitions to other states.

As another example, I’ve put together a state diagram of a proof-of-concept project I’m working on which I’m calling “Assisted Capture the Flag.”  The project requirements are as follows:

After receiving a command (received as a Joint Architecture for Unmanned Systems (JAUS) command message), an autonomous, mobile robot must follow a person to a “flag room.”  The robot must enter the room and search for a “flag.”  The flag is an object of which the robot will have a priori knowledge; i.e., the robot will know what it’s looking for before starting on its quest.  After finding and identifying the location of the flag, the robot will return to its initial location and report its finding via a JAUS message.

Although I’ve described the project at a high level, it’s difficult to visualize what’s happening and when.  This is where state diagrams come into play.  What follows is a state diagram describing the states and state transition that the robot may go through while attempting to achieve the overall goal of the project, finding and reporting upon the flag’s location.

I won’t go into too much detail of the state transition diagram above, but there are a few things I’d like to point out.

Immediately under the initial state of the system, the state forks into two concurrently running behaviors, localizing itself within the environment and awaiting/parsing a JAUS command for execution.  After both of those complete, the system then, and only then, joins and progresses to the next state of “Locate Person to Follow.”

There are two “composite states” shown:  “Find Flag Room” and “Find Flag.”  Each of these contain concurrent behaviors in order to achieve the objective of the composite state.  What makes these different than forks/joins, is that A) not all states must “complete” before progressing to the next state, and B) there exist multiple exit points to “short circuit” the entire composite state.

A key element, to ensure that the state diagram doesn’t get too bogged down with detail, is to focus on expressing behavior and avoiding how the behavior is to be accomplished.  For example, one could hypothetically break the “Locate Flag” down into many sub-states, such as “Search for Flag with Dominant Orientation Templates (DOT).”  Although this is a technique the project will likely include, breaking the state diagram down to this level goes beyond behavior, instead describing how a behavior is to be achieved.

Ideally, a behavior should be something that an external observer note the robot is doing, regardless of how it’s pulling it off.  (Think about having to watch some squirrels for a few hours and note distinct behaviors…there’s a fun family activity for ya this weekend.)  For example, the “Enter Doorway” state exemplifies this principle; an observer could easily note that the robot is working on getting through a doorway as  an overall behavior of the robot.  On the other hand, the “SLAM Path” state is not something that an observer would likely know the robot is doing while within the composite state “Find the Flag Room”; yet, it’s a concurrent, internalized behavior which must occur in order to return to its initial location at a later time.  One justification of its inclusion in the diagram is its placement within a composite state; thereby, encapsulating it within an externally observable behavior.  But, regardless, especially in mobile robotics, if you’re adding a state which cannot be easily discerned by an external observer, you should ask yourself if it is truly a separate state or if it is simply describing a detail of how the state is being carried out.  Keeping the state diagram clear of such details makes it easier to adapt to implementation changes later in the process.  But as with all rules of thumb in software development, “it depends.”

Billy McCafferty