Warning: strlen() expects parameter 1 to be string, array given in /home/sharpr6/public_html/wp-content/themes/starscape/code/starscape.php on line 450
Methodologies | SharpRobotica.com - Sharp ideas for the software side of robotics
Posts Tagged ‘Methodologies’

Using State Diagrams to Express Robot Behaviors & Transitions

datePosted on 16:48, April 22nd, 2011 by Billy McCafferty

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

Using O-MaSE Methodology for Goal Modeling

datePosted on 22:43, April 21st, 2011 by Billy McCafferty

O-MaSE is an agent-oriented analysis & design (AOAD) methodology.  I have found it to be a particularly powerful tool, in the development of project work, due to its flexibility of use and ability to handle single and multi-agent domains equally well.  For example, unlike many other methodologies (which I’ll leave nameless to avoid stoking any fires), O-MaSE is very adaptable to be easily slimmed down for smaller projects while having requirements and analysis support for quite complicated, multi-agent domains (e.g., RoboCup teams).  Additionally, O-MaSE’s initial requirement phases focus more on system goals, rather than agent goals.  In doing so, it is easier to model multi-agent domains without becoming prematurely bogged down in the details of which responsibilities belong to which agent.

As I’ve discussed this methodology, and resources for learning more about it, in a previous post, I’d like to instead share an example of how I’ve used it for a  proof-of-concept project I’m putting together as a stepping stone towards higher aspirations.  This first step in O-MaSE is goal modeling.  The methodology defines a goal as an overall function of the organization; a goal could be seen as a desirable situation or the objective of a computational process.  The “Model Goal” task focuses on transforming system requirements into goals and sub-goals represented as an AND/OR decomposition/goal tree.

An AND/OR goal tree is simply a class diagram where each class is stereotyped as “<< goal >>” and sub-goals are shown hierarchically.  It is an AND/OR tree because while some goals may require all of its sub-goals to be completed in order to be satisfied, other goals may only require one of its subgoals to be completed to be satisfied.  The UML relationship aggregation notation is used to note that all sub-goals must be satisfied to consider the parent goal satisfied, while the UML generalization (inheritance) notations is used to note that only one sub-goal must be satisfied.

It’s certainly easier to understand by looking at an example.  The proof-of-concept project that I’m working is an assisted capture the flag game.  The idea is that a mobile robot must follow a person to a particular room and search the room for a flag, then returning to its initial location to report the results.  Below is the AND/OR goal tree that I put together to represent the goals of the system, using Enterprise Architect.  (Click the image to see it full-size.)

As indicated, the overall system goal is “Find Flag.”  To achieve this, the goal is broken down again and again into sub-goals.  The level of granularity to which you take the decomposition is certainly subjective, but it should continue to be done until the decomposition process is no longer resulting in new information, or is beginning to express how goals are to be achieved.  Once you cross the threshhold of defining how the goals are to be achieved, rather then simply defining the goals themselves, you’re switching gears from goal-modeling to plan-modeling.  In fact, even in this example, the line between goals and plans becomes gray after the third tier; e.g., “Identify Person to Follow,” “Follow Person,” and “SLAM Path Taken” could be argued as being closer to plans than goals.  That was a clear indication to me that I had gone “far enough” and should now turn attentions towards analyzing plans for achieving the goals presented.

Billy McCafferty

Agent-Oriented Methodology Selection: O-MaSE

datePosted on 18:03, January 7th, 2011 by Billy McCafferty

In selecting an appropriate agent-oriented analysis & design (AOAD) methodology, the project delivery team must carefully consider the ramifications of the methodology on the final solution and if the methodology’s presumed architectural paradigm, if there is one, is in line with the team’s goals for the project.  With traditional object-oriented analysis & design (OOAD) methodologies – e.g., Domain Driven Design, Model Driven Engineering, Larman’s Applying UML and Patterns – the OOAD methodologies don’t typically have much presumption on the final architectural solution; one could use almost any OOAD methodology while resulting in a wide array of architectural implementations.  Conversely, because AOAD methodologies not only assume a behavioral focus but often assume how those behaviors are organized, the selected AOAD methodology can have a significant impact on the architectural solution.

For example, choosing the 4D/RCS methodology, and following it to a tee, will result in a purely hierarchical architecture; the Australian AI Institute (AAII) methodology results in a Procedural Reasoning System (PRS) architecture; while the Multi-Agent Scenario-Based (MASB) results in a more reactive architecture.  Accordingly, for the project at hand, I’m interested in a methodology which supports an architecture with the following attributes:

  • The architectural solution must support deliberative planning to consider resource and environmental constraints and plan, accordingly.
  • It must support reactive agents that will leverage a finite state machine to transition between behaviors.
  • It must support interaction with other agents for cooperation and reactive coordination.

These basic architectural assumptions suggest a methodology which will result in a hybrid architecture supporting multi-agent coordination and interaction.  (It’s already sounding like an InteRRaP or AllianceL-Alliance agent architecture to support these needs.)

Ideally, I want to avoid picking a methodology which will dictate the agent architecture without negating the methodology’s usefulness. Accordingly, three general agent-oriented methodologies, which do not mandate a particular agent-architecture, were considered in detail:  Tropos, MaSE (Multiagent System Engineering) & O-MaSE, and Gaia.  Gaia was eliminated due to the fact that while it supports high-level design, it does not provide much guidance for detailed and lower-level implementation design.  Both Tropos and MaSE provide good project life-cycle guidance and support high-level and detailed design.  A major plus to Tropos is Formal Tropos, which includes support for symbolic model checking with T-Tool.  It’s also built upon Eric Yu’s i* framework described in Agent-Oriented Modeling: Software versus the World.  But ultimately, MaSE was selected as the methodology of choice for the following reasons:

  • MaSE exhibits the same benefits as the other considered architectures:  good project life-cycle support, open-ended agent-architecture, models and guidance for both high-level and detailed design.
  • MaSE is in active development with the recent extension O-MaSE and appears to widely referenced in various publications.
  • MaSE has a positively-reviewed, design tool available as agentTool III.
  • MaSE has been proven in cooperative, multi-agent robotics (reference below).

Resource summary for MaSE and O-MaSE:

Resources which helped me make this decision include:

So with the methodology selected, it’s time to look at picking an architectural approach to the multi-agent system in the next post.  A major advantage of the O-MaSE methodology is that it is built upon the premise of being a flexible methodology allowing one to pick and choose a number of techniques to assist in defining requirements.  Accordingly, by knowing more about the intended architectural approach, we’ll be able to customize the O-MaSE methodology to better align the efforts with the end result.

Billy McCafferty

This post is one in a series for the commercial development of a multi-agent, robotic, bell pepper picking team with scalable planning, supporting unstructured, outdoor horticulture.  If you’d like to follow along, be sure to subscribe to SharpRobotica.com.  In addition to commenting on posts, feel free to contact me anytime if you would like to discuss collaboration or funding prospects.

Methodologies for the Design of Robotic and Multi-Agent Systems

datePosted on 14:05, January 4th, 2011 by Billy McCafferty

Object oriented analysis and design (OOAD) methodologies are well established, offering a plethora of methodologies depending on the needs of the project and the skills of the development team; e.g., eXtreme Programming, Domain Driven Design, Agile Modeling, and Crystal Clear.  (Scrum is omitted as it lacks adequate direction for OOAD; albeit, it’s a terrific project management methodology.)  Indeed, a pivotal element of any successful software development endeavor is the careful selection of a methodology for defining project requirements and designing the solution.  A challenge with applying traditional OOAD methodology to robot and multi-agent control systems is the traditional methodologies’ bias towards defining the structure and properties of objects and applying behaviors to those objects as a secondary concern.  But in the world of robotics, the emphasis needs to be squarely placed on behavior as the centerpiece of design.  This does not imply that the methodology will result in a behavior-based, subsumption architecture, but instead that the robot’s goal-driven and event-driven behavior is at the very core of what is being modeled.  Accordingly, a number of agent-oriented analysis and design (AOAD) methodologies have emerged over the years in response to this disconnect between traditional OOAD methodologies and the needs of agent-oriented systems.

What follows is a brief listing of a few notable AOAD methodologies representing a wide cross-section of approaches:

  • Australian AI Institute (AAII) (now defunct) developed a methodology for designing Procedural Reasoning Systems (PRS) built on a belief-desire-intention, logic paradigm.  This methodology is concisely described in Michael Wooldrige’s Introduction to MultiAgent Systems.  AAII’s methodology is strongly rooted in OOAD with extensions for agent-based design.
  • The Tropos methodology is a full project life-cycle methodology based on actors, goals, plans, resources, dependencies, capabilities, and beliefs.  A Tropos project begins by defining the actor and dependency models which reflect “who” is involved and the dependencies between the actors.  Project design continues by defining a goal model and a respective plan model for describing “canned plans” for achieving the goals.
  • Lightly defined methodologies for the design of reactive/behavioral systems (those that Brooks likes) are defined in Introduction to AI Robotics by Robin Murphy (pg. 163) and in Behavior-Based Robotics by Ronald Arkin (pg. 155).
  • The 4D/RCS methodology describes a comprehensive methodology for the design of systems built upon the guidance of the 4D/RCS reference architecture.  Incidentally, although intended for 4D/RCS projects, the methodology itself is quite compatible with other layered architectures, such as 3T and other hybrid architectural solutions.
  • Although more of an architectural model than a methodology, Jörg Müller’s The Design of Intelligent Agents includes a couple of case studies on defining requirements for various layers of an InteRRaP architectural solution.  These complement any methodology you may pick as further examples of taking an agent-oriented approach to requirements definition.
  • Other notable methodologies, still frequently used, include Gaia, Prometheus, and MaSE.

If you’d like to learn more about other agent-oriented methodologies, an almost comprehensive survey of options, with a good introduction to each, has been put together by the University of British Columbia in Analysis and Design of Agent-Oriented Information Systems (AOIS); or, if you’re willing to shell out some cash, see Federico Bergenti’s Methodologies and Software Engineering for Agent Systems.

In the next post, we’ll examine some of the architectural constraints of our project and determine which AOAD methodology will be right.

Billy McCafferty

This post is one in a series for the commercial development of a multi-agent, robotic, bell pepper picking team with scalable planning, supporting unstructured, outdoor horticulture.  If you’d like to follow along, be sure to subscribe to SharpRobotica.com.  In addition to commenting on posts, feel free to contact me anytime if you would like to discuss collaboration or funding prospects.

© 2011-2014 Codai, Inc. All Rights Reserved