{"id":54,"date":"2012-01-30T19:50:33","date_gmt":"2012-01-31T00:50:33","guid":{"rendered":"http:\/\/www.mcgurrin.com\/robots\/?p=54"},"modified":"2012-01-30T19:55:18","modified_gmt":"2012-01-31T00:55:18","slug":"an-introduction-and-example-of-finite-state-machines","status":"publish","type":"post","link":"https:\/\/www.mcgurrin.info\/robots\/54\/","title":{"rendered":"An Introduction and Example of Finite State Machines"},"content":{"rendered":"

Finite State Machines (FSM) are often an excellent design pattern<\/a> for robot control software. As I was developing my first robotic vehicle, I started with just modifying and expanding upon some sample code I found online.\u00a0 This worked for a robot moving around at random, avoiding obstacles.\u00a0 But once I wanted to add positioning and navigation, it became difficult to keep track of where the logic should be at each step and each time the main control loop executed.\u00a0 I realized that a state machine approach was the solution, and it’s worked out beautifully.<\/p>\n

What is a Finite State Machine?\u00a0 You can find the formal definition here <\/a>at Wikipedia, but as David Stonier-Gibson puts it in his tutorial<\/a>:<\/p>\n

The formal, mathematical definition of an FSM is such brain numbing, eye popping mumbo jumbo I feel certain that 9 out of 10 electronic engineering and IT students switch off in the first 5 minutes of the FSM lecture series, never to ever benefit from the power of FSMs in their work. This is not difficult stuff, it’s just made to look difficult by the academics!<\/em><\/p><\/blockquote>\n

The basic concept of an FSM is that the system is, at any time, in a specific, pre-defined state.\u00a0 Multiple states are defined, along with the internal or external events that cause the system to transition from one state to another.\u00a0 The functions that need to be performed for each transition from one state to another are then determined, and, of course, you have functions to be performed when in a given state.\u00a0 Not all events trigger a state transition, some are processed and handled with the system staying in the same state.\u00a0 It’s easiest to explain by example.\u00a0 A good, short tutorial with examples can be found in the online article Application Design Patterns: State Machines<\/a>, along with some useful design hints.\u00a0 Below, I use the state-machine model I developed for my MARV-1 autonomous dead-reckoning vehicle as an example.<\/p>\n

State Machines can be represented in several ways.\u00a0 One approach is a state transition matrix.\u00a0 Below is the matrix for the code for my MARV-1 autonomous vehicle:<\/p>\n

\"State<\/a><\/p>\n

The topmost row shows the seven states that the robot can be in.\u00a0 The leftmost column shows the internal and external events that can cause a change from one state to another.\u00a0 For example, “Button 1 pressed” is an external event.\u00a0 If MARV-1 is currently in the Off state, it transitions to the Orienting state.\u00a0 If it’s in any other state, it transitions to Off.\u00a0 “Completed calculating next heading” would be an internal event that causes a transition from the Orienting state to the Turning state.\u00a0 If, instead, the last waypoint in the list had already been processed, then there would be a transition from the Orienting to the Off state.<\/p>\n

In C\/C++\/Arduino code, states are typically coded using the Switch command.\u00a0 Each Case ends with a break;, since the system can only be in one state at a time.\u00a0 There can be code to run each time a state is entered for the first time and code to run when you exit a particular state.\u00a0 This code can be dependent on the specific transition, e.g., the exit code from Orienting to Off is different than from Orienting to Turning.\u00a0 I found it easier to use exit code rather than entrance code wherever possible, because then I didn’t have to set a flag and check each time through the main loop to determined if I was entering a state for the first time or not.<\/p>\n

In fact, 95 percent of the code in the main Loop for my MARV-1 vehicle is inside a single Switch statement.\u00a0 The exceptions are checking for the Button 1 press, since that must be done in every state, and updating position and orientation, since, with the exception of the Off state, that must always be done.<\/p>\n

You’ll notice that most of the cells in the state transition matrix are empty.\u00a0 That’s because most events only affect one or two states.\u00a0 That means that you don’t need to check for those events when in any of the other states.\u00a0\u00a0 The state machine design pattern makes coding simpler and much, much easier to follow.\u00a0 It also\u00a0 allows you to change out the details within a state (inside a specific case in your code) without affecting the rest of your code.\u00a0 The exception to this is the transition triggers themselves and the exit processing code.<\/p>\n

Another way of designing or documenting your Finite State Machine is with a state machine diagram.\u00a0 Here’s the same information for MARV-1, presented in pictorial form:<\/p>\n

\"State<\/a><\/p>\n

In the case of MARV-1, I started my planning figuring on an Off state and an On state.\u00a0 Of course, the On state quickly was subdivided into more.\u00a0 Since MARV-1 uses tank-style turns and always either moves in a straight line or turns in place, it was logical to have a Turning state and a Traveling state.\u00a0 As I worked on the code, I found it made sense to break out the Orienting from the Turning, even though the Orienting is just some calculations that complete in a single pass through the main Loop.\u00a0 Similarly, it became easier to code to break the obstacle avoidance maneuvering into 3 states, one for each step in the 3 step obstacle avoidance approach I decided on:\u00a0 Back up, turn right, go forward a ways, hopefully clearing the original obstacle.\u00a0 As you can see from the table or picture, if MARV-1 is still pointing towards an obstacle after turning, it goes back to the Avoid:Backing state, as it does if it detects an obstacle while moving forward.<\/p>\n

Finite State Machines are a simple and effective concept for robot software, and I encourage you to plan out your next project using this approach.<\/p>\n","protected":false},"excerpt":{"rendered":"

Finite State Machines (FSM) are often an excellent design pattern for robot control software. As I was developing my first robotic vehicle, I started with just modifying and expanding upon some sample code I found online.\u00a0 This worked for a … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[3,12,4],"_links":{"self":[{"href":"https:\/\/www.mcgurrin.info\/robots\/wp-json\/wp\/v2\/posts\/54"}],"collection":[{"href":"https:\/\/www.mcgurrin.info\/robots\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.mcgurrin.info\/robots\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.mcgurrin.info\/robots\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mcgurrin.info\/robots\/wp-json\/wp\/v2\/comments?post=54"}],"version-history":[{"count":5,"href":"https:\/\/www.mcgurrin.info\/robots\/wp-json\/wp\/v2\/posts\/54\/revisions"}],"predecessor-version":[{"id":197,"href":"https:\/\/www.mcgurrin.info\/robots\/wp-json\/wp\/v2\/posts\/54\/revisions\/197"}],"wp:attachment":[{"href":"https:\/\/www.mcgurrin.info\/robots\/wp-json\/wp\/v2\/media?parent=54"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.mcgurrin.info\/robots\/wp-json\/wp\/v2\/categories?post=54"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.mcgurrin.info\/robots\/wp-json\/wp\/v2\/tags?post=54"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}