Hierarchical State Machine Framework for leJOS

This is where you talk about the NXJ software itself, installation issues, and programming talk.

Moderators: 99jonathan, roger, imaqine

Hierarchical State Machine Framework for leJOS

Postby mimarox » Wed Jul 06, 2011 12:36 pm

Hi,

as leJOS currently offers no native support for developing robot applications based on state machines I recently sat down to implement a framework filling that gap.

This framework is currently in beta state ready for being tested and improved as necessary. One question in that regard is how to make the sources available to the leJOS community.

The features supported include:

States:
  • Hierarchical states, e.g. each state can extend another state inhereting its transitions
  • Actions can be performed at state entry and state exit
  • States determine which events they accept and whether one or several events are necessary for a certain transition

Transitions:
  • Transitions have a guarding method that can prevent the transition from being carried out
  • Actions can be executed during a transition
  • Transitions can be triggered by one event or a set of events

Events:
  • Each event has a type which is a member of some enum
  • Each event can have parameters. The event type determines what names, types and value ranges those parameters might have for a specific event

I'm looking forward to your comments and ideas for improvements.

Matthias
mimarox
New User
 
Posts: 11
Joined: Wed Jun 22, 2011 9:17 am

Re: Hierarchical State Machine Framework for leJOS

Postby lawrie » Fri Jul 08, 2011 12:56 pm

Did you ever see http://lejos.sourceforge.net/forum/viewtopic.php?t=675.?

It is rather old now and probably does not work on the latest version of leJOS, but looked very impressive. It generated leJOS from a graphical diagram of a state machine.
lawrie
leJOS Team Member
 
Posts: 909
Joined: Mon Feb 05, 2007 1:27 pm

Re: Hierarchical State Machine Framework for leJOS

Postby lawrie » Fri Jul 08, 2011 1:02 pm

If your framework in general purpose enough, we could make in part of leJOS, e.g. in the lejos.utils package. Could you post an example program, to show what the API looks like. How complicated is the fremework? Is it just a few classes or something more substantial?
lawrie
leJOS Team Member
 
Posts: 909
Joined: Mon Feb 05, 2007 1:27 pm

Re: Hierarchical State Machine Framework for leJOS

Postby mimarox » Mon Jul 11, 2011 3:50 pm

Hi,

I wasn't aware of the Eclipse Plug-In for leJOS state machines. It does look quite impressive, but I haven't yet checked whether it actually still works.

The framework currently consists of 7 types (4 classes, 1 abstract class, 1 interface, 1 enum). 6 of them are to be used by implementing code, the enum is private to the framework.

The API of the actual state machine is rather simple. It consists of the constructor taking a list of state instances, the class of the initial state, a list of classes of terminal states and optionally an event rejection handler object instance, and four life cycle methods. They are start(), handleEvent(Event<?> event), kill(), and shutDown(). They should be self-explaining. The difference between kill and shutDown is that kill destroys the state machine instantly while shutDown clears the state stack letting each state perform its exit action. If no event rejection handler object is given the default implementation is used which does just nothing about unhandled events.

Event creation is done by implementing code. The Event class acts as a container for an event type and its associated payload data. The event types for a specific implementation need to be defined in an enum implementing the EventType interface. This interface defines a single method isAcceptablePayloadItem(String key, Object value). Implementing this method allows each event type to define which payload items can be associated with it in terms of item name, type and value range. An enum defining event types may look like this:

Code: Select all
package com.matthiasrothe.robotics;

import com.matthiasrothe.lejos.lhsm.EventType;

public enum EventTypes implements EventType {
   BATTERY_EMPTY {
      @Override
      public boolean isAcceptablePayloadItem(String key, Object value) {
         return false; // doesn't accept any payload
      }
   },
   
   APPROACHING_OBSTACLE {
      @Override
      public boolean isAcceptablePayloadItem(String key, Object value) {
         if ("angle".equals(key) && value instanceof Float &&
               (Float) value >= -45 && (Float) value <= 45) {
            return true;
         }
         
         if ("distance".equals(key) && value instanceof Float &&
               (Float) value >= 0 && (Float) value <= 5) {
            return true;
         }
         
         return false;
      }
   };
}


An event to be handled might than be created by

Code: Select all
stateMachine.handleEvent(new Event<EventTypes>(EventTypes.BATTERY_EMPTY));


or

Code: Select all
Event<EventTypes> event = new Event<EventTypes>(EventTypes.APPROACHING_OBSTACLE);
event.addPayloadItem("angle", 10.0f);
event.addPayloadItem("distance", 4.0f);
stateMachine.handleEvent(event);


The most extensive API is the State class. This is the only abstract class and implementations need to implement at least the abstract methods isAcceptableEvent(Event<?> event) and getCurrentTransition(). Furthermore they can override the default implementations of various life cycle methods. These are getExtendedState() (allowing for hierachical states), waitForAnotherEvent() and discardAllExceptedEvents() (allowing for several events for a single transition), performEntryAction() and performExitAction() (providing hooks for the actual application code). The default implementations of these methods provide basic support for non-hierarchical states accepting only a single event per transition and doing nothing on entry and exit. Depending on the needs of the actual application implementing the states can therefore be very simple like

Code: Select all
package com.matthiasrothe.robotics;

import com.matthiasrothe.lejos.lhsm.Event;
import com.matthiasrothe.lejos.lhsm.State;
import com.matthiasrothe.lejos.lhsm.Transition;

public class BatteryConsumingState extends State {
   private static final Transition TRANSITION = new Transition(BatteryLoadingState.class);
   
   @Override
   protected boolean isAcceptableEvent(Event<?> event) {
      if (event.getEventType() == EventTypes.BATTERY_EMPTY) {
         return true;
      } else {
         return false;
      }
   }

   @Override
   protected Transition getCurrentTransition() {
      return TRANSITION;
   }
}


or rather complicated.

Last but not least the Transition class has two methods that can be overridden: canProceed() and performTransitionAction(). The first method acts as a transition guard. The transition is only executed if this method returns true. The default implementation always returns true. The latter provides a hook for application code to be executed during the transition. The default implementation does just nothing. If the defaults suffice the Transition class can be used as it is. Instances would than be created by using the constructor taking the class of the target state as seen in the last code example.

I hope these explanations enlighten you and am looking forward to reading your feedback. :-)
mimarox
New User
 
Posts: 11
Joined: Wed Jun 22, 2011 9:17 am

Re: Hierarchical State Machine Framework for leJOS

Postby lawrie » Thu Jul 14, 2011 11:44 am

Is there anything leJOS specific about this framework, or anything specific to robotics? It looks as if it could be used for any Java program that wants to use a hierarchical state machine.

It looks like it has a similar role to the lejos.robotics.subsumption package. That package is also not specific to leJOS but behavior programming is usually considered a technique that is specific to robotics, whereas I would guess that hierachical state machine have wider applicability.

If we did include it in lejos in would probably be a package such as lejos.robotics.lhsm, although it would be good to have a more meaningful name - hierachicalstatemachine is a bit long.

I would quite like to see a complete (but simple) program written using it, to see how simple the API is to use, and what sort of program it is useful for.

If we did include it as part of leJOS, we would need a tutorial page and one or more sample programs.
lawrie
leJOS Team Member
 
Posts: 909
Joined: Mon Feb 05, 2007 1:27 pm

Re: Hierarchical State Machine Framework for leJOS

Postby mimarox » Thu Jul 14, 2011 3:48 pm

Is there anything leJOS specific about this framework, or anything specific to robotics? It looks as if it could be used for any Java program that wants to use a hierarchical state machine.


It does indeed look like it's generally usable. And yet it is leJOS specific in the way that its implemented to cope with several limitations posed by leJOS. These include:

  • Lack of XML parser and limitations on the available storage size on a NXT
  • Lack of reflection
  • Lack of runtime annotation inspection

A real general purpose implementation of a hierarchical state machine framework / container is IMHO best implemented taking advantage of all of the above. There are a number of features that can only be implemented or are best implemented that way. Have a look at http://sourceforge.net/apps/trac/redroo/wiki/container/1.0/devdoc/spec/overview/features/AcceptedFeatures for a list of features I would expect from a full fledged general purpose implementation. Obviously that takes a lot longer to implement, which is why the RedRoo project is still in prealpha state. ;-)

The very least that should definitely be supported is XML as that allows for a far more concise way to describe the static parts of a state machine. Take the following as an example:

Code: Select all
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE fsm SYSTEM "fsm.dtd">
<fsm>
<!-- Generic Super State -->
   <state name="finishable">
      <transition event="finishGame" substate="gameFinished" />
   </state>
   
<!-- Game Status Settings -->
   <state name="gameInitialized" extends="finishable">
      <transition event="setupGame" substate="gameSetup" />   
   </state>
   <state name="gameSetup" extends="finishable">
      <transition event="joinedGame" substate="gameStarted" />   
   </state>
   <state name="gameStarted" extends="finishable">
      <transition event="firstRound" substate="roundInitialized" visibility="private" />
      <transition event="timeUp" substate="gameTimeUp" />
      <transition event="roundsUp" substate="gameRoundsUp" />
      <transition event="shutDown" substate="gameCancelled" />
   </state>
   <state name="gameTimeUp" extends="finishable" />
   <state name="gameRoundsUp" extends="finishable" />
   <state name="gameCancelled" extends="finishable" />
   <state name="gameFinished" />

<!-- Round Status Settings -->
   <state name="roundInitialized" extends="gameStarted">
      <transition event="proponentStartRound" substate="proponentRoundStarted" />
      <transition event="opponentStartRound" substate="opponentRoundStarted" />
   </state>
   <state name="proponentRoundStarted" extends="gameStarted">
      <transition event="opponentStartRound" substate="roundRunning" />
   </state>
   <state name="opponentRoundStarted" extends="gameStarted">
      <transition event="proponentStartRound" substate="roundRunning" />
   </state>
   <state name="roundRunning" extends="gameStarted">
      <transition event="activateProponent" substate="proponentActive" visibility="private" />
      <transition event="activateOpponent" substate="opponentActive" visibility="private" />
      <transition event="finishRound" substate="roundFinished" />
   </state>
   <state name="roundFinished" extends="gameStarted">
      <transition event="nextRound" substate="roundInitialized" />
   </state>

<!-- Player Status Settings -->
   <state name="proponentActive" extends="roundRunning">
      <transition event="activateOpponent" substate="opponentActive" />
   </state>
   <state name="opponentActive" extends="roundRunning">
      <transition event="activateProponent" substate="proponentActive" />
   </state>
</fsm>


Describing all of the above in Java means that it will all be spread out over a number of classes. Therefore it will be a lot harder to see all the connections between states in terms of inheritance and transitions. The upside of course is that doing it all in Java means a lot smaller memory footprint, which is crucial for embedded environments like leJOS.

It looks like it has a similar role to the lejos.robotics.subsumption package.


That was actually the intention. I wanted to create a framework to go alongside the behavior framework already in place. Actually I wouldn't mind them sitting next to each other within the subsumption package, each in its own subpackage like subsumption.behavior and subsumption.states. They might even benefit from each other as each behavior might be internally governed by a state machine. I implemented the kill method with that in mind, so a behavior could easily stop its state machine and hand the control over to the next behavior demanding it.

The sample program is in the making, I'm expecting to have it done until the end of the month. It would be no problem (apart from the time needed ;-)) to provide the necessary documentation.
mimarox
New User
 
Posts: 11
Joined: Wed Jun 22, 2011 9:17 am

Re: Hierarchical State Machine Framework for leJOS

Postby lawrie » Fri Jul 15, 2011 10:00 pm

The development version of leJOS has some support for XML parsing. This will be in the 0.9.1 release. It supports a subset of javax.xml.stream. Is that of any use to you? Would you use XML if it was available, or do you still think is is better to avoid it on leJOS.

Have you looked at the sample programs Subsumption1 and 2? They implement a subsumption architecture using finit state machines. They were written for the RCX version of leJOS. We used to have some classes that supported this variant of the subsumption architecture, but deleted them some time ago as it was confusing having two variants of subsumption.

I think I would prefer subsumption and HSM in separate packages but I am interested in seeing how they could be combined.
lawrie
leJOS Team Member
 
Posts: 909
Joined: Mon Feb 05, 2007 1:27 pm

Re: Hierarchical State Machine Framework for leJOS

Postby mimarox » Wed Jul 20, 2011 3:56 pm

Good to know some support for XML is coming. It might be of use for the hsm use case. As there is no reflection available the matching of the states and transitions defined in the XML file to the classes implementing them might be done by embedded domain specific language-like commands as

Code: Select all
bind("<state name>").to(State state)
fromState(Class<? extends State> stateClass).toState(Class<? extends State> stateClass).useTransition(Transition transition)


On the other hand it might also be possible to define the whole thing using an eDSL along the lines

Code: Select all
state(State state).hasTransitions(onEvent(EventType eventType).transitionTo(Class<? extends State> stateClass).using(Transition transition))

state(State state).isFinal().hasTransitions(onEvent(EventType eventType).transitionTo(Class<? extends State> stateClass).using(Transition transition))

state(State state).isAbstract().hasTransitions(onEvent(EventType eventType).transitionTo(Class<? extends State> stateClass).using(Transition transition))

state(State state).extending(Class<? extends State> stateClass).isFinal().hasTransitions(onEvent(EventType eventType).transitionTo(Class<? extends State> stateClass).using(Transition transition))

state(State state).extending(Class<? extends State> stateClass).isAbstract().hasTransitions(onEvent(EventType eventType).transitionTo(Class<? extends State> stateClass).using(Transition transition))


Looking at it, the XML way seems to be more concise and clear. In any case the whole framework would become substantially more complex. There would be processing of the XML and / or eDSL definitions, an execution meta model and the like. Whether this is feasible within the target environment would need to be explored.

At the end of the day, it might turn out that it would actually be best to use the lightweight framework described in previous posts due to memory footprint and execution time.
mimarox
New User
 
Posts: 11
Joined: Wed Jun 22, 2011 9:17 am

Re: Hierarchical State Machine Framework for leJOS

Postby mimarox » Tue Aug 02, 2011 12:25 pm

Are there actually any users of leJOS interested in using a default implementation of a hierarchical state machine as proposed within this thread to write their robot applications? If so, please raise your hand.
mimarox
New User
 
Posts: 11
Joined: Wed Jun 22, 2011 9:17 am

Re: Hierarchical State Machine Framework for leJOS

Postby TechnoX » Tue Aug 02, 2011 8:25 pm

Yes! If you provide an tutorial on how to start I'm really interested!
I want to learn new technologies and lejos is a perfect tool for doing that!

*Raise my arm*
TechnoX
Novice
 
Posts: 52
Joined: Tue May 03, 2011 5:57 pm
Location: Sweden

Re: Hierarchical State Machine Framework for leJOS

Postby maniac » Mon Aug 22, 2011 12:55 am

I'm interested in that for my current robot (I havent find programming with behavior much intuitive), but not sure how it will fit in default leJOS disto.

Could you just share the code, so anyone could use it and see that for themselves?
maniac
New User
 
Posts: 1
Joined: Mon Aug 22, 2011 12:52 am

Re: Hierarchical State Machine Framework for leJOS

Postby mimarox » Mon Aug 22, 2011 12:57 pm

Hi,

as I'm currently real busy it'll still take a while until I can release a sample app and a tutorial for the hierarchical state machine framework.

However I've just uploaded a zip file containing the complete Eclipse project and a built jar file of the framework. You may download it from http://www.matthiasrothe.com/lejos/lhsm.zip. The main entry point is the StateMachine class. Your main objectives will be to define event types, write classes extending the State class reacting to the event types and code actually pushing event objects into the state machine. Javadoc is provided with most classes, this should help you getting started.

Have fun experimenting with the framework and should any questions arise, please go ahead and ask.
mimarox
New User
 
Posts: 11
Joined: Wed Jun 22, 2011 9:17 am

Re: Hierarchical State Machine Framework for leJOS

Postby esmetaman » Wed Oct 12, 2011 7:57 am

Interesting project HSM, offer many advantages to model behaviours in Robot projects.

I will test your implementation.
Juan Antonio Breña Moral
http://www.juanantonio.info/lejos-ebook/
http://www.iloveneutrinos.com/
User avatar
esmetaman
Advanced Member
 
Posts: 290
Joined: Wed Sep 13, 2006 12:16 am
Location: Madrid, Spain

Re: Hierarchical State Machine Framework for leJOS

Postby esmetaman » Wed Oct 12, 2011 8:57 pm

Hi Mimarox,

do you have some example to model behaviours with your set of classes?

I downloaded your classes, but I would like to test the concepts with a real robot.

Cheers
Juan Antonio Breña Moral
http://www.juanantonio.info/lejos-ebook/
http://www.iloveneutrinos.com/
User avatar
esmetaman
Advanced Member
 
Posts: 290
Joined: Wed Sep 13, 2006 12:16 am
Location: Madrid, Spain

Re: Hierarchical State Machine Framework for leJOS

Postby mimarox » Mon Oct 31, 2011 3:48 pm

Hi esmetaman,

thanks for getting in touch (here and in PM) and your interest in the HSM. For the benefit of all other users I'll post the reply publicly.

Unfortunately I haven't got any examples for using the HSM - and am still too busy to create one.

The general purpose should be quite clear: modelling the robots behaviour as states and the transitions between them triggered by events. So if you want to try the HSM you'd probably best define the states, event types, events and transitions composing the robot's behaviour first - on paper or with a modelling application. The types of events would then be implemented as an enum implementing the EventType interface. The states would be implemented as subclasses of the State class. If your transitions need guards and / or actions you would implement them as subclasses of the Transition class. Otherwise you would just use that as it is. The provided Javadoc should help you to take the first steps. If any more questions come up, feel free to post them.

Kind regards,
Matt
mimarox
New User
 
Posts: 11
Joined: Wed Jun 22, 2011 9:17 am

Next

Return to NXJ Software

Who is online

Users browsing this forum: No registered users and 3 guests

more stuff