What is a finite state machine and when should I use one?

A Finite State Machine (FSM) is a state machine with a finite number of states that can be in one state at a time and transition to a different state when an event occurs . FSMs are often used in programming to enable more complex series of actions, especially when multiple tasks need to run concurrently and depend on each other's execution in a non-linear way .

FSMs are the appropriate tool when a robot needs to perform multiple tasks simultaneously, such as having automation in teleop while still allowing control over the drivetrain . This approach helps avoid issues that arise when teleop executes in a loop and servo logic includes sleep commands . Instead, FSMs allow for asynchronous code execution, where tasks are performed concurrently, and each task's state is checked without halting other tasks .

An example of a useful application is automating a scoring lift and dumper servo in teleop, where the robot extends a lift, angles a servo, waits, resets the servo, and retracts the lift, all while the driver can still control the drivetrain . This asynchronous pattern, where code repeatedly checks for state transitions in a loop() function, prevents the code from blocking other operations like drivetrain control .

It is not advisable to implement FSMs in a linear fashion for autonomous programs using a large switch statement, as this offers no significant benefit over simply using functions and can make debugging more difficult . Such "naive" implementations often struggle to react to stop requests because the code executes linearly .

Was this right?

Sources6

Finite State Machines

Game Manual 0·CC BY-NC 4.0

Finite State Machines (FSM) are often used while programming in order to allow for more complex series of actions. This is especially useful when one needs multiple tasks to run at the same time, because it allows for tasks to depend on each other's execution in a non-linear fashion.

Open Game Manual 0

Finite State Machines > What is a Finite State Machine?

Game Manual 0·CC BY-NC 4.0

The name of a finite state machine is very descriptive; it's a state machine, with a finite number of states. It can be in one state at a time, and can transition to a different state once something happens. The Wikipedia (https://en.wikipedia.org/wiki/Finite-state_machine#Example:_coin-operated_turnstile) example of a turnstile explains the concept very well.

Open Game Manual 0

Finite State Machines > Implementation > Useful Implementation

Game Manual 0·CC BY-NC 4.0

FSMs are the right tool to use when a robot needs to complete multiple tasks at once; a common example of this is when a robot should have automation in teleop, but still have control over the drivetrain.

Often times, teams have issues because their teleop executes in a loop and their servo logic has sleeps in it. But, we can avoid this if we write code in an asynchronous fashion - where instead of waiting for a task to complete before doing the next one, tasks are performed at the same time, and each task's state is checked without stopping the other tasks from executing.

An example of this would be that if one had a robot similar to Gluten Free's Rover Ruckus Robot (https://www.youtube.com/watch?v=NQvhvYJXVMA), and one wanted to automate the scoring lift so that the drivers don't have to think while the bot deposits the minerals. There are two parts of the bot that are relevant to us in this exercise: the angled scoring lift, and the servo that tips the dumper so the minerals fall out. The goal is to be able to push a button, and then the bot will:

extend the lift,
at full lift extension, angle the mineral bucket servo to deposit the minerals,
wait for the minerals to fall out,
reset the servo to the original position
retract the lift

If the drivers press a specific other button, we will stop executing the actions above as a failsafe - in case the robot is breaking somehow and the drivers need to take manual control. All the while, the drivers should still be able to control our drivetrain so we can make adjustments. Now, of course, this is a bit simplified (and probably not entirely what GF did), but it will do for now.

Before anything is programmed, it may be useful draw out the state diagram for this to get a better understanding of what we the robot should actually be doing. This can also add to a Control Award submission.

Notice how resetting the dump servo and retracting the lift share a state. That's because the robot doesn't need to wait for the servo to reset before moving the lift down; they can both happen at once.

Open Game Manual 0

Finite State Machines > Implementation > Useful Implementation

Game Manual 0·CC BY-NC 4.0

Now, let's get into actually implementing the code for this. In a traditional OpMode, which is commonly used for teleop, code runs repeatedly in a loop() function, so instead of waiting for a state transition to happen directly, the code will repeatedly check on each loop() call if it should perform a state transition. This kind of "update our state" pattern keeps code from blocking the rest of the loop() code from running, such as the drivetrain.

Open Game Manual 0

Finite State Machines > Implementation > Naive Implementation

Game Manual 0·CC BY-NC 4.0

When first learning about FSMs, it is quite common for programmers to try and use them. Often times, they try to apply an FSM to their autonomous programs by segmenting their autonomous into a giant switch statement, and it often looks something like this:

while (opModeIsActive()) {
    switch (state) {
        case DETECT_SKYSTONE:
            // skystone detection code here
            int position = detectSkystone();

            if (position == 0) {
                state = SKYSTONE_POS_0;
            }
            else if (position == 1) {
                state = SKYSTONE_POS_1;
            }
            else {
                state = SKYSTONE_POS_2;
            }
            break;
        case SKYSTONE_POS_0:
            // skystone position 0 here
            doSkystone(0);
            state = MOVE_FOUNDATION;
            break;
        case SKYSTONE_POS_1:
        case SKYSTONE_POS_2:
            // etc etc
            break;
        case MOVE_FOUNDATION:
            // foundation move code
            state = PARK;
            break;
        case PARK:
            // park the bot
            break;
     }
}

This however does not really have any benefits compared to if the programmer had simply put each of the code's segments into functions, and executed them in order. In fact, often times, programmers will structure their code like this instead of splitting their code up into functions. The result is an autonomous that's more difficult to debug, and ultimately harder to fix on the fly during a competition or other time crunch.

If one drew out the state transition diagram for each of the states, for the autonomus above it'd be very linear, and the state transitions always occur because the section of the code finished:

In fact, in many implementations, making state transitions for any other reason is often difficult because the code executes linearly and is only in a loop to rerun the switch statements. (Often times, this means the code has a hard time reacting to a stop request in the middle of autonomous.)

Warning: It is unadvisable to write code like this. If your autonomous is synchronous, it is preferable to split your code up into functions and run them in order, as this will be easier to understand and edit on the fly.

Open Game Manual 0

Fundamental Concepts of Programming > Important Control Structures

Game Manual 0·CC BY-NC 4.0

Be sure to familiarize yourself with basic control structures (if/else statements, for loops, while loops, and for-each loops). These control structures are by far the most commonly encountered, and thus, familiarizing yourself with these principles is extremely important (not just for FTC, but programming in general). However, there are a few control structures that are far less common that are extremely useful in FTC; namely /docs/software/concepts/finite-state-machines.

Open Game Manual 0