State Machine Options (Library, Framework, Generator, Compiler, etc)

[dagar]

I've been casually looking for a good solution to handle state machines throughout the system.

• commander rewrite #7055
• PX4 Flight Stack Structure Proposal  #7318
• How to handle custom flight tasks? #10235

Requirements

• declarative
• generate documentation (either tables or a graph)
  • SCXML would also be nice
• if a generator or compiler it needs to be easily accessible, cross platform, and have an acceptable license
• likely need to support HSM (TBD)
• entry and exit Actions
• transition guards
• error handling/reporting (think about feedback from denied arming or mode change)

Options

• State Machine Compiler (http://smc.sourceforge.net/)
  • large java app
  • state machine defined in files then generates source code and documentation
  • doesn't support hierarchical state machines
• [Boost].SML (State Machine Language) (https://github.com/boost-experimental/sml)
  • no documentation generation
  • don't be afraid of Boost in the name (it's standalone)
  • NEGATIVE: c++14 required (blocked by qurt toolchain)
• ROS Decision Making (http://wiki.ros.org/decision_making)
  • can generate SCXML
  • would need a PX4 port (subset of features)
  • NEGATIVE: MACRO based
• Microsoft P Language
  • https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-8.pdf
  • can generate C code
  • commander rewrite #7055 (comment)
• TinyFSM (https://github.com/digint/tinyfsm)
• Statecharts classbased (https://www.youtube.com/watch?v=fHWDBCoTnAg)
  • https://github.com/rosbacke/serial_net/tree/master/src/statechart
  • https://github.com/rosbacke/MCU-tools/tree/master/src/statecharts_classbased
  • create state machine at runtime
• Behavior Trees ()
  • https://github.com/BehaviorTree/BehaviorTree.CPP
• ESTELLE ()
  • http://www-lor.int-evry.fr/idemcop/uk/est-lang/download/estelle-tutorial-slides.pdf
• HFSM2 (https://github.com/andrew-gresyk/HFSM2)
  • Header-only heriarchical FSM framework in C++14, with fully statically-defined structure (no dynamic allocations), built with variadic templates.
  • Visualizations: https://gresyk.dev/features/2018/01/15/hfsm-magic.html
• SMACC (https://github.com/reelrbtx/SMACC/)
  • https://discourse.ros.org/t/introducing-the-smacc-state-machine-library/14963/2

[dagar]

FYI @simonegu @julianoes

[tstellanova]

FWIW, Yakindu statechart tools can be run headless (without running Eclipse UI), and moving charts between Qt and Yakindu somewhat works.
https://github.com/Yakindu/statecharts

[dakejahl]

@dagar I made a dumb little example in PX4 that uses this library https://github.com/amaiorano/hsm
See https://github.com/PX4/Firmware/tree/hsm_example

It's essentially the state_args.cpp with a few modifications. I wouldn't even know where to begin with trying to implement this in something like Commander... Hopefully this is somewhat helpful.

make px4_sitl_default jmavsim
pxh > hsm_example

Right now the plotHsm.py doesn't work, but I was able to manually generate the chart:

python $PX4_DIR/src/lib/hsm/tools/hsmToDot.py $PX4_DIR/src/modules/hsm_example/hsm_example.h > hsm_example.dot
dot hsm_example.dot -Tpng -o hsm_example.png

Output

pxh> hsm_example
HSM_1_TestHsm: Init    : Alive
HSM_1_TestHsm:  Entry   : Locomotion
HSM_1_TestHsm:   Entry   : Stand
HSM_2_TestHsm:   Pop     : Stand
HSM_1_TestHsm:   Sibling : Move
HSM_2_TestHsm:   Pop     : Move
HSM_2_TestHsm:  Pop     : Locomotion
HSM_1_TestHsm:  Sibling : Attack
>>> Attacking: 0
>>> Attacking: 0
>>> Attacking: 0
HSM_2_TestHsm:  Pop     : Attack
HSM_1_TestHsm:  Sibling : Attack
>>> Attacking: 1
>>> Attacking: 1
>>> Attacking: 1
HSM_2_TestHsm:  Pop     : Attack
HSM_1_TestHsm:  Sibling : Attack
>>> Attacking: 2
>>> Attacking: 2
>>> Attacking: 2
>>> Attacking: 2

I have the debug level set to diagnostic, so you can see all state transitions and their relationships.

[dagar]

Julian's state machine in PX4/avoidance. PX4/PX4-Avoidance#418

[julianoes]

Thanks @dakejahl and @jkflying. That's helpful, however, I still believe the hard part is capturing the intended behaviour and put it into a diagram than to actually implement the state machine. I have implemented a state machine like this in the past as well but was struggling with formulating the actual behaviour without having to do it using hierarchical state machines.

[jkflying]

Maybe a first step would be drawing a high level state transition diagram and refactoring into that, even if inside the different states there is still a lot of ad-hoc implicit state code?

[AuterionWrikeBot]

➤ David Sidrane commented:

Have a look at https://www.visual-paradigm.com/
It is a great tool and there is a comunity edition

[dagar]

I have implemented a state machine like this in the past as well but was struggling with formulating the actual behaviour without having to do it using hierarchical state machines.

Why without hierarchical state machines?

[julianoes]

Right so for hierarchical state machines you either need to extend the implementations or combine them manually.

[dagar]

Added https://github.com/andrew-gresyk/HFSM2 to the list to investigate.

[wluker]

You might consider a language @fsantanna created called ceu. http://ceu-lang.org/index.html

It generates C code that you would have to integrate into an event loop.

It's not a state machine generator, but I find the semantics easier on my brain than state machines, even hierarchical.

[Pedro-Roque]

Option used by NASA Astrobee: https://github.com/nasa/astrobee/blob/bb0fc3e4110a14929bd4cf35c12b3c169bc6c756/shared/ff_util/include/ff_util/ff_fsm.h

with
https://github.com/nasa/astrobee/blob/bb0fc3e4110a14929bd4cf35c12b3c169bc6c756/gnc/ctl/statemachine.dot

(not generated automatically)

[dinomani]

@dagar
Anybotic uses something like that to switch the robot to and from different modes with safety fallback.
https://docs.leggedrobotics.com/rocoma_doc/page_features.html