|
|
|
 |
|
|
|
|
|
Guide to Finite State Machine Programming and Subsumption
Architecture |
|
|
|
<= What is a Finite State Machine? A Finite State Machine, abbreviated FSM, is a method of programming. It uses "states" that you can think of like steps you might be following from assembly instructions to build something. For example, let's say you are assembling a new robot and are at step 4. In step 4 you will put the wheels on and go to step 5. Later, you are at step 50. Step 50 directs you to tighten the last screw of the assembly. You are now ready to go to the next step to program your new robot. If you have a Windows PC you go to step 51, If DOS, step 62, or Apple based, go to step 75. You can consider these steps as various "states" you are in. Think of it as "If I am in state 50 I do XYZ (tighten the last screw) and then go to state XX (here 51), YY (here 62), or ZZ (here 75) depending on certain conditions (in this case my OS)". What about the rest of the fancy words? Since the end result is accomplishing something, it is called a "machine". Actually computer people have referred to computers as "machines" for a long time. Finite? Well, there are a limited or "finite" number of states you can be in. You might argue that you can instruct the computer to do something forever. Is that an "Infinite State Machine"? Actually it wouldn't be. The state of doing something, even forever, is only one state. So there you have it, a Finite State Machine. <= Let's do something useful with an FSM. A simple program to flash LED lights can show some of the FSM's power. Let's do it first without using an FSM. We'll use PBASIC and a BASIC Stamp® to flash 3 LEDs. A simple program could be Flasher1 Now let's make it a little harder. The LEDs have to each flash at their own rate! The on and off times must also be separately adjustable in 200 ms increments. When the flashing stops being simple multiples of each other, our simple programming technique starts to fall apart. You were waiting for it, let's try a Finite State Machine approach. In Flasher2 there are 3 state machines, one for each LED. An "X" will replace the actual channel number in the following. The current state for each FSM is held in the StateX variables. If the LED is to be kept off because of the enable (ControlX = 0), it stays in stateX = 0. If the LED is to be on (ControlX = 1), the state machine alternates between stateX = 1 and stateX = 2. The times for LEDX to be on and off are counted by CntrX. On_cntX and Off_cntX initialize CntrX with values for the on and off times. Each state machine is started by decrementing the CntrX. States 1 and 2 look at the value of that counter but do nothing until it hits zero. When the counter hits zero, the wait for that state is expired and the system is set up for the next state. Other test conditions make sure that the enable (ControlX) gets the state machine correctly into and out of state 0. Notice how the FSMs disconnect the LEDs flashing rates from each other. This isolating effect can vastly simplify a program. The only factors affecting the FSM for LED1 are contained in the state machine for LED1. These state machines are relatively simple but can still take some thought. FSMs can get very complicated and there is a graphical way to express what happens in each state and the flow between states. This is shown in an article linked to later. First read the next sections on Subsumption Architecture. The article slides right into it from Finite State Machines so it doesn't hurt to have a little intro on Subsumption first. <= What's Subsumption? Subsumption is a programming technique that is based on reflex types of reaction to sensor inputs. Essentially, if a higher priority stimulus is present, it takes control over the lower priority one. In other words, it is more important to react to bumping into something now rather than the fact that you are seeing something you might bump into later! <= How does Subsumption work? One easy way to program a Subsumption engine is to have a subroutine for each behavior. Define an action variable; let's call it "GO". Each subroutine (behavior) decides what it wants to do with GO and writes into the variable if (and ONLY IF) it needs some action. The subroutines are executed from lowest priority first to highest priority last. Since each subroutine has written into the same variable, the last one that wrote (the highest priority one that needed action) will actually determine the final value of GO. When done the subroutines, the program decodes what do based on the GO value. Let's look at a really simple Subsumption program. For it, we'll go back to Flasher1 for a start and add some easy behaviors. Again we'll skip the complexity of the code that determines overall system function so we can concentrate on the subsumption part of the program. Some part of the system reports errors that the LEDs are supposed to indicate. We need only the most critical to be shown to the operator for immediate action. In this program, instead of a single variable "GO", we will use the 3 enable bits for the LEDs. If we have Error3, dangerous vibration, we want to block the light (LED1) that was only going to show routine maintenance needed. We still need to show the over-temp LED (LED2) in the case of vibration so it will stay. Here is Flasher3. Notice where behavior2 subsumes behavior1 if Error3 is active. <= Mix FSMs and Subsumption? Look at Flasher4 to see the two techniques combined. Notice how handy it is to have the different flashing speeds for the different urgencies. Checking for actual inputs for the errors was also added. Although a little advanced, you should read this article (14 pp - PDF - 107KB) on programming robotic behavior. It was written by Dennis L. Clark for Parallax and their BoE-Bot and is posted here with the kind permission of Parallax Inc. In it, Dennis gets into the issue of trying to do more than one thing at a time with a BASIC Stamp® based robot and some ways to help. The article is worth reading because he describes FSM and Subsumption programming in some detail. If you looked at Dennis' article and feel clueless, don't worry! Parallax has excellent texts that can be downloaded for free on the web. <= It can't be that easy! Dennis' article also covers some of the issues that come up when trying to extend the performance of the Stamp to any added assignments. The primary issues you run into are - First, you really don't know how long the various sections of your code take to run so it becomes a matter of chance to get the servo refresh times right. Second, each servo also takes 5-10% of the processing power of a Stamp - even the fastest one, the 2p40, like we use in our controller board. Third, there is no way to tell a Stamp to "wait some milliseconds" without stopping its processing completely. These issues are all solved by adding our Co-Processor! To learn about how it handles subsumption, look at the section on its Subsumption Engine. <= Back to Tech Center <= Back to Co-Processor page |
Blue Bell Design Inc. Post Office Box 446 Gwynedd Valley, PA 19437-0446 USA 215-643-7012 email us harry@bluebelldesign.com on the web www.bluebelldesign.com BASIC Stamp® is a registered trademark of Parallax, Inc.
|
