Using Parallel States to Avoid a Combinatorial Explosion of States

Assume that you wanted to model a set of mutually exclusive properties of a car in a single state machine. Let's say the properties we are interested in are Clean vs Dirty, and Moving vs Not moving. It would take four mutually exclusive states and eight transitions to be able to represent and freely move between all possible combinations.

If we added a third property (say, Red vs Blue), the total number of states would double, to eight; and if we added a fourth property (say, Enclosed vs Convertible), the total number of states would double again, to 16.

Using parallel states, the total number of states and transitions grows linearly as we add more properties, instead of exponentially. Furthermore, states can be added to or removed from the parallel state without affecting any of their sibling states.

To create a parallel state group, allocate a ParallelState structure.

    StateMachine* statemachine = allocStateMachine(NULL, NULL);
    ParallelState* s1 = allocateParallelState(statemachine, 2, statemachine, NULL);
    // s11 and s12 will be entered in parallel
    State *s11 = allocateState(s1, NULL, stateMachine);
    State *s12 = allocateState(s1, NULL, stateMachine);

When a parallel state group is entered, all its child states will be simultaneously entered. Transitions within the individual child states operate normally. However, any of the child states may take a transition which exits the parent state. When this happens, the parent state and all of its child states are exited.

The order in which the states are exited follow a complex logic. The first state that is exited is the state that has triggered the transition (or one of its child if it has some). Then, all of its parents are exited until a parallel state is reached. After that, every 'remaining actives branches' of the parallel state are exited. For each branch the first state to be exited is the deepest and then its parent until the parallel state is once again reached. Then, the system process the next branch.

To go further, let's have a look on this state machine:

Here is the code:

    StateMachine* stateMachine;
    ParallelState *PS1_1, *PS2_2, *PS11_3, *PS1132_1;
    State *MS1, *MS2, *S1_2, *S2_1, *S11_1, *MS11_2, *S22_1, *S22_2, *S112_1, *S112_2, *S113_1, *MS113_2, *S11321_1, *S11321_2;
    
    stateMachine = allocStateMachine("myParallelStateMachine", "[PSM]");
    MS1 = allocateState(stateMachine, "MS1", stateMachine);
    MS2 = allocateState(stateMachine, "MS2", stateMachine);
    PS1_1 = allocateParallelState(MS1, 3, stateMachine, "PS1_1");
    S1_2 = allocateState(MS1, "S1_2", stateMachine);
    S2_1 = allocateState(MS2, "S2_1", stateMachine);
    PS2_2 = allocateParallelState(MS2, 2, stateMachine, "PS2_2");
    S11_1 = allocateState(PS1_1, "S11_1", stateMachine);
    MS11_2 = allocateState(PS1_1, "MS11_2", stateMachine);
    PS11_3 = allocateParallelState(PS1_1, 2, stateMachine, "PS11_3");
    S22_1 = allocateState(PS2_2, "S22_1", stateMachine);
    S22_2 = allocateState(PS2_2, "S22_2", stateMachine);
    S112_1 = allocateState(MS11_2, "S112_1", stateMachine);
    S112_2 = allocateState(MS11_2, "S112_2", stateMachine);
    S113_1 = allocateState(PS11_3, "S113_1", stateMachine);
    MS113_2 = allocateState(PS11_3, "MS113_2", stateMachine);
    PS1132_1 = allocateParallelState(MS113_2, 2, stateMachine, "PS1132_1");
    S11321_1 = allocateState(PS1132_1, "S11321_1", stateMachine);
    S11321_2 = allocateState(PS1132_1, "S11321_2", stateMachine);

So when we start the state machine with the STATE_WORK_DBG debug flag we can see:

[PSM] In state machine myParallelStateMachine, state MS1 is entered
[PSM] In state machine myParallelStateMachine, Parallel state PS1_1 is entered
[PSM] In state machine myParallelStateMachine, state S11_1 is entered
[PSM] In state machine myParallelStateMachine, state MS11_2 is entered
[PSM] In state machine myParallelStateMachine, state S112_1 is entered
[PSM] In state machine myParallelStateMachine, Parallel state PS11_3 is entered
[PSM] In state machine myParallelStateMachine, state S113_1 is entered
[PSM] In state machine myParallelStateMachine, state MS113_2 is entered
[PSM] In state machine myParallelStateMachine, Parallel state PS1132_1 is entered
[PSM] In state machine myParallelStateMachine, state S11321_1 is entered
[PSM] In state machine myParallelStateMachine, state S11321_2 is entered

The actives states are:

[PSM] State machine myParallelStateMachine is on state S11_1
[PSM] State machine myParallelStateMachine is on state S112_1
[PSM] State machine myParallelStateMachine is on state S113_1
[PSM] State machine myParallelStateMachine is on state S11321_1
[PSM] State machine myParallelStateMachine is on state S11321_2

Now if a transition on event 1 exists between state S11321_1 and state S22_2 the order in which the states will be exited or entered is:

[PSM] State machine myParallelStateMachine received event 1
[PSM] In state machine myParallelStateMachine, state S11321_1 is exited
[PSM] In state machine myParallelStateMachine, state S11321_2 is exited
[PSM] In state machine myParallelStateMachine, Parallel state PS1132_1 is exited
[PSM] In state machine myParallelStateMachine, state MS113_2 is exited
[PSM] In state machine myParallelStateMachine, state S113_1 is exited
[PSM] In state machine myParallelStateMachine, Parallel state PS11_3 is exited
[PSM] In state machine myParallelStateMachine, state S11_1 is exited
[PSM] In state machine myParallelStateMachine, state S112_1 is exited
[PSM] In state machine myParallelStateMachine, state MS11_2 is exited
[PSM] In state machine myParallelStateMachine, Parallel state PS1_1 is exited
[PSM] In state machine myParallelStateMachine, state MS1 is exited
[PSM] In state machine myParallelStateMachine, state MS2 is entered
[PSM] In state machine myParallelStateMachine, Parallel state PS2_2 is entered
[PSM] In state machine myParallelStateMachine, state S22_1 is entered
[PSM] In state machine myParallelStateMachine, state S22_2 is entered

Not so hard isn't it ?

Next: How to put the debug system in good use.

Previous : Basic explaination of a state machine