Hierarchical State Machine in Tree structure with Dictionary

[Markos]

Hi,

I would like to listen the advice of more experienced Tcl programmers about the strategy I'm using.

I'm trying to use the hierarchical State Machine Technique according to the model:

Loading Image...

And to represent this model in a "tree" structure as:

Loading Image...

To do this I'm using a variable of type dictionary called "state" in which the keys and values represent the nodes of the tree as shown in partial diagram:

Loading Image...

I'm using "dict set" command to create the tree structure within the state variable in which each "dict set" define a branch from the root to a leaf as shown in the diagrams:

Loading Image...
Loading Image...

And to find the nodes I'm using the recursion technique with walkState procedure in which from a state and an event (input) I can find the next state.

(state_tree is the dictionary variable)
(state is a node in tree)
(input is an event)

The procedure search on the tree (state_tree) if "input" is a child node of the node "state".

proc walkState { state_tree state input } {

global next_state

if { [ catch { set k [dict keys $state] } ] } {

if { $state_tree == $state } {

puts "$state is a LEAF"

}

return
}

foreach sub_state [dict keys $state_tree] {

puts "sub_state -> $sub_state\n"

if {$sub_state == $state} {

set child_node [dict keys [dict get $state_tree $sub_state]]

puts "Child node of $sub_state -> $child_node"

if { $child_node == $input } {

puts "$input is an event compatible with $sub_state\n"

set next_state [dict get $state_tree $sub_state $child_node]

puts "Next state -> $next_state"

} else {
puts "$input isn't compatible with the state $sub_state"

}

}

if {[dict exists $state_tree $sub_state]} {

set sub_state [dict get $state_tree $sub_state]

walkState $sub_state $state $input
}
}

return $next_state
}


Any comment about the strategy I'm following?

Is goog, is bad?

Thanks for the tips,
Markos

[Brad Lanam]

Post by Markos
http://www.c2o.pro.br/hackaguas/figuras/behaviour_tree_irrigator.png

I think I would set up the initial dictionary as:

dict set irr1 {
connect_state disconnected
config_state invalid
irrigation_state invalid
}

Each state has it's own key and can be easily fetched. Then you
don't have to do any tree walking and will be much more efficient.

A connect event would do:
dict set irr1 connect_state connected
dict set irr1 config_state unconfigured
A disconnect event would do:
dict set irr1 connect_state disconnected
dict set irr1 config_state invalid
dict set irr1 irrigation_state invalid
A configure-start or configure-finish event would have:
if { [dict get $irr1 config_state ne "invalid" } {
...
}
etc.

There are many ways to lay this out. It could be:
dict set irr1 [list disconnected invalid invalid]
lassign [dict get $irr1] connect_state config_state irrigation_state

I'm sure you can come up with something that doesn't require a tree walk.

[Markos]

Post by Brad Lanam

Post by Markos
http://www.c2o.pro.br/hackaguas/figuras/behaviour_tree_irrigator.png

dict set irr1 {
connect_state disconnected
config_state invalid
irrigation_state invalid
}
Each state has it's own key and can be easily fetched. Then you
don't have to do any tree walking and will be much more efficient.
dict set irr1 connect_state connected
dict set irr1 config_state unconfigured
dict set irr1 connect_state disconnected
dict set irr1 config_state invalid
dict set irr1 irrigation_state invalid
if { [dict get $irr1 config_state ne "invalid" } {
...
}
etc.
dict set irr1 [list disconnected invalid invalid]
lassign [dict get $irr1] connect_state config_state irrigation_state
I'm sure you can come up with something that doesn't require a tree walk.

Hi Brad,

Looking for more information about how to implement Hierarchical State Machine I found some information in the tutorial:

http://www.drdobbs.com/hierarchical-state-machine-design-in-c/184402040

Where the author lists the options to implement a state machine:

"
There are many ways to implement state machines, including:

1- Nested switch() statements over all states and over all events.
2- State-transition tables; states on one axis, events on the other, and cells containing a function to execute and the next state.
3- Dynamic tree-like structures traversed at runtime "

I was analyzing your suggestion and I wondered if your proposal fits in one of these alternatives or not.

What do you think?

Thanks for your attention,
Markos

[Brad Lanam]

Post by Markos

Post by Brad Lanam

Post by Markos
http://www.c2o.pro.br/hackaguas/figuras/behaviour_tree_irrigator.png

dict set irr1 {
connect_state disconnected
config_state invalid
irrigation_state invalid
}
Each state has it's own key and can be easily fetched. Then you
don't have to do any tree walking and will be much more efficient.
dict set irr1 connect_state connected
dict set irr1 config_state unconfigured
dict set irr1 connect_state disconnected
dict set irr1 config_state invalid
dict set irr1 irrigation_state invalid
if { [dict get $irr1 config_state ne "invalid" } {
...
}
etc.
dict set irr1 [list disconnected invalid invalid]
lassign [dict get $irr1] connect_state config_state irrigation_state
I'm sure you can come up with something that doesn't require a tree walk.

Hi Brad,
http://www.drdobbs.com/hierarchical-state-machine-design-in-c/184402040
"
1- Nested switch() statements over all states and over all events.
2- State-transition tables; states on one axis, events on the other, and cells containing a function to execute and the next state.
3- Dynamic tree-like structures traversed at runtime "
I was analyzing your suggestion and I wondered if your proposal fits in one of these alternatives or not.
What do you think?
Thanks for your attention,
Markos

The data structure I presented would apply to option (1) or (3).
The change I was suggesting was to make sure all states were pre-initialized
so that no tree walking is necessary. Just fetch the current state.

Personally I think option (1) would create rather hard to read code though
there may be ways to structure it to be readable.

For option (2), I would use a different data structure, and your state tree
would need to be mapped into a single state that represents the
current state of the irrigation system.

Option 2 could use an array set up as:

# statechg array key is <state>,<event>
# the value of the array is the procedure name to call.
# states are: disconnected, unconfigured, configure-inprocess,
# idle, active
set statechg(disconnected,connect) doconnect
set statechg(disconnected,max-connect-timer) dofailconnection
set statechg(disconnected,configure-start) donoconnection
set statechg(disconnected,start-irr) donoconnection
...
set statechg(unconfigured,configure-start) doconfigure
set statechg(configure-inprocess,max-config-timer) doconfiguretimeexceeded
set statechg(configure-inprocess,config-finished) doconfigurefinish
set statechg(configure-inprocess,start-irr) donoconnection
...
set statechg(idle,start-irr) dostartirrigation
...
set statechg(active,irr-finish) doirrigationfinish
set statechg(active,max-irr-timer) doirrigationtimeexceeded

proc handleevent { event } {
global state
global statechg
if { ! [info exists statechg($state,$event)] } {
doinvalidstate
}
set handler $statechg($state,$event)
$handler
}

proc doconnect { } {
global state
set state unconfigured
}
proc doconfigurefinish { } {
global state
set state idle
}
proc donoconnection { } {
# error handling
}

Easy to add new states. The error handling for invalid state/event combinations can be a single generic routine or specific to the state/event
combination. e.g. If the state is current 'active' and a 'disconnect' event
is received, there would probably be some special code to try and
reconnect or some method to force the irrigation to turn off.

[Brad Lanam]

Post by Brad Lanam

Post by Markos

Post by Brad Lanam

Post by Markos
http://www.c2o.pro.br/hackaguas/figuras/behaviour_tree_irrigator.png

dict set irr1 {
connect_state disconnected
config_state invalid
irrigation_state invalid
}
Each state has it's own key and can be easily fetched. Then you
don't have to do any tree walking and will be much more efficient.
dict set irr1 connect_state connected
dict set irr1 config_state unconfigured
dict set irr1 connect_state disconnected
dict set irr1 config_state invalid
dict set irr1 irrigation_state invalid
if { [dict get $irr1 config_state ne "invalid" } {
...
}
etc.
dict set irr1 [list disconnected invalid invalid]
lassign [dict get $irr1] connect_state config_state irrigation_state
I'm sure you can come up with something that doesn't require a tree walk.

Hi Brad,
http://www.drdobbs.com/hierarchical-state-machine-design-in-c/184402040
"
1- Nested switch() statements over all states and over all events.
2- State-transition tables; states on one axis, events on the other, and cells containing a function to execute and the next state.
3- Dynamic tree-like structures traversed at runtime "
I was analyzing your suggestion and I wondered if your proposal fits in one of these alternatives or not.
What do you think?
Thanks for your attention,
Markos

The data structure I presented would apply to option (1) or (3).
The change I was suggesting was to make sure all states were pre-initialized
so that no tree walking is necessary. Just fetch the current state.
Personally I think option (1) would create rather hard to read code though
there may be ways to structure it to be readable.
For option (2), I would use a different data structure, and your state tree
would need to be mapped into a single state that represents the
current state of the irrigation system.
# statechg array key is <state>,<event>
# the value of the array is the procedure name to call.
# states are: disconnected, unconfigured, configure-inprocess,
# idle, active
set statechg(disconnected,connect) doconnect
set statechg(disconnected,max-connect-timer) dofailconnection
set statechg(disconnected,configure-start) donoconnection
set statechg(disconnected,start-irr) donoconnection
...
set statechg(unconfigured,configure-start) doconfigure
set statechg(configure-inprocess,max-config-timer) doconfiguretimeexceeded
set statechg(configure-inprocess,config-finished) doconfigurefinish
set statechg(configure-inprocess,start-irr) donoconnection
...
set statechg(idle,start-irr) dostartirrigation
...
set statechg(active,irr-finish) doirrigationfinish
set statechg(active,max-irr-timer) doirrigationtimeexceeded
proc handleevent { event } {
global state
global statechg
if { ! [info exists statechg($state,$event)] } {
doinvalidstate
}
set handler $statechg($state,$event)
$handler
}
proc doconnect { } {
global state
set state unconfigured
}
proc doconfigurefinish { } {
global state
set state idle
}
proc donoconnection { } {
# error handling
}
Easy to add new states. The error handling for invalid state/event combinations can be a single generic routine or specific to the state/event
combination. e.g. If the state is current 'active' and a 'disconnect' event
is received, there would probably be some special code to try and
reconnect or some method to force the irrigation to turn off.

You could keep the states separated and the array would look like:

# statechg array:
# <connect-state>,<conf-state>,<irr-state>,<event>
set statechg(disconn,inv,inv,connect) doconnect
set statechg(disconn,inv,inv,irr-start) donoconnection
set statechg(conn,unconf,inv,conf-finished) doconfigurefinished

But I think it is simpler to have the 'unconfigured', 'configure-inprocess' 'idle', 'active', etc. states simply assume that the prior states are
connected or connected and configured.

[joheid]

Hi,
have also a look at http://wiki.tcl.tk/8363.
The "engine" of this implementation of R. Suchenwirth ist just:

proc statemachine states {
array set S $states
proc goto label {
uplevel 1 set this $label
return -code continue
}
set this [lindex $states 0]
while 1 {eval $S($this)}
rename goto {}
}

[joheid]

Hi,
have also a look at http://wiki.tcl.tk/8363.
The "engine" of this implementation of R. Suchenwirth ist just:

proc statemachine states {
array set S $states
proc goto label {
uplevel 1 set this $label
return -code continue
}
set this [lindex $states 0]
while 1 {eval $S($this)}
rename goto {}
}