Shop OBEX P1 Docs P2 Docs Learn Events
Finite State Machines — Parallax Forums

Finite State Machines

AImanAIman Posts: 531
edited 2006-08-17 17:17 in Robotics
Does anyone know where I can get material on Finite State Machines (FSM)? I read about an article on a different website citing Parallax and FSM, the Toddler documents discuss it but I can't find where it went into an example of using a loop or function of any sort (chapter 8).

Are there materials somewhere that deal with understanding FSM or getting into FSM?

If possible examples of coding with an explination?

I can do simple Do While stuff but thats only what was figured out the hard way.

turn.gif·

Comments

  • Chris SavageChris Savage Parallax Engineering Posts: 14,406
    edited 2006-08-09 22:29
    Dr. Tracy Allen has a page on his site devoted to this very topic.· I hope this helps.

    http://www.emesystems.com/BS2fsm.htm

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    Chris Savage
    Parallax Tech Support
    csavage@parallax.com
  • AImanAIman Posts: 531
    edited 2006-08-10 02:26
    Thanks muchyeah.gif
  • AImanAIman Posts: 531
    edited 2006-08-10 13:30
    I read the link and found one more brief bit on a differnt site. They are rather skillfully laid out and I had to pay attention when I read, however the point was made.

    If people can answer this I have a question.

    A FSM is for the purpose of running more then one function by use of operators that allow a secondary state to "sleep" until needed. The two specifics I saw were based on conditions were there was a priority order in functions, or a function that happened when needed meaning that if condition 1 is violated go immediatly to condition 2 and using operators that keep the two conditions·opposite (one false the other true).

    For example a robot that works with·sonar detection·that moves left to right·would look something as follows. (Yes I know its not stampese)

    Condition 1 - If object is·then or equal to 5 feet away keep going forward

    Condition 2 -·If object is less then 5 feet away avoid it.

    While condition 1 Xor condition 2 equals true

    ···Send pulses to sonar

    ·· Check distance to object

    ······· If distance is less then 5 feet goto avoidance

    End While

    Did I get that right?
  • AImanAIman Posts: 531
    edited 2006-08-10 14:58
    I don't think I worded that clearly.

    Programing a FSM is like using ctrl-alt-delete because all three are doing something at once. Or in an application its like saying to the computer, do this while the screen clock doesn't equal zero and if it does then do something else.

    Correct?
  • allanlane5allanlane5 Posts: 3,815
    edited 2006-08-10 15:59
    Typically, Finite State Machines were implemented with hardware -- flip-flops, gate arrays, that sort of thing. When you implement them in software, the basic idea behind them is that there are a few 'state variables' that hold what 'state' your program is in. And for each 'state', your program can do something different. So, typically, you'll have a 'state variable' to hold that 'state', and let you make decisions against it. For now, I'll call it "CurState", for current state.

    Thus, you start out in "CurState = 1" (what you called 'condition 1' above) when your robot is in the 'state' of being more than 5 feet from any object. The 'action' you take in that 'state' is to keep going forward, AND keep checking to see if it gets less than 5 feet from an object.

    When you get less than 5 feet from an object, you now change "CurState" to 2. The 'action' you take in that 'state' is to take avoidance actions, until you're greater than 5 feet from an object. At that point, you change "CurState" to 1 again.

    So: Pseudo-code for that would be:

    CurState = 1
    Main:
    · IF CurState = 1 THEN
    ··· Move_Forward
    ··· Find_Obj_Distance
    ··· IF Obj_Distance < 5 feet THEN
    ····· CurState = 2
    ··· END IF· ' Otherwise, stay in 'State 1'
    · END IF

    · IF CurState = 2 THEN
    ··· Avoid_Obstacle
    ··· Find_Obj_Distance
    ··· IF Obj_Distance >= 5 feet THEN
    ······ CurState = 1
    ··· END IF· ' Otherwise, stay in 'State 2'
    · END IF
    · ' Note, with this approach, you can add new 'state' clauses
    · ' (IF CurState = ...) easily, without damaging earlier clauses.
    GOTO MAIN
  • AImanAIman Posts: 531
    edited 2006-08-10 17:44
    Thanks much for the pointers.

    Let me see if I have this straight.

    If Curstate = 1 then

    ·· move forward

    ·· check distance

    ······ If distance < 5 then State = 2

    ······ End if

    End if

    Why the end if and a second if? Why not an else if? Does a second if add speed and keep code clean?

    If I am correct, the reason for changing the state from 1 to 2 is so that the state will run until the distance·to change to state 1 is reached. Once it is reached it flips back to state one or whatever state is dictated.

    Clearly the purpose for the IF-Then loop is so it will stay in a state until a change in state occurs. The change in state for the second·IF comes about when the distance increases enough to return to state one.

    Cool, that makes sense.· roll.gif

    To clarify:

    Set a sub to read distance and make that a variable·called Curstate where Curstate = 1 if >= 5ft·distance and 2 if < 5ft distance.

    Did I get this straight?
  • allanlane5allanlane5 Posts: 3,815
    edited 2006-08-10 18:18
    Close.

    The purpose of the "state variable" (here CurState) is to hold what state you are in, and to be used to decide what code to execute for a particular state.

    The 'action' you take for a particular state belongs inside the 'IF' that has determined what state you are in.
    The 'state change' code that changes the value of CurState (and thus, what 'state' you'll be in next) also belongs inside that IF.

    It was very intentional that I had a third variable, "Obj_Distance", that I could make a decision about, to make it very clear WHY the state changed. So you should set a sub called "Find_Obj_Distance" which sets a variable called "Obj_Distance", which you then use to determine what next state you want to go to.

    In this very limited example, with only two states, you COULD have used an 'ELSE' -- but if you go to three states (backing up from collision, for instance) then you'd have to remove the ELSE. Having multiple, relatively independent "IF Curstate = ..." clauses makes the code easy to maintain and upgrade.
  • AImanAIman Posts: 531
    edited 2006-08-10 20:34
    Thanks for all the help.

    To recap -

    Use seperate if statements for each state to allow for ease of reading and updates later.

    Obj_Distance gets its value from a sub call Find_Obj_Distance. Obj_Distance is used to set the state.

    Each if statment must show what that state will do before the statements that would send it elsewhere.


    My robot has 7 places assigned for sonar around its body (forms a circle) with 2 IR - one for edge detection and one for clearance detection. To do an english form of this it would read something like:

    State 1
    move forward
    Check distance for each sonar and IR
    If distance is to close then switch to state 2
    If distance can't be detected then switch to state 3
    if distance on side that is to close is same as other side switch to state 4.
    Recheck distance

    Is that correct?

    Also, do you know of any good books or sources I could get from the library?

    Thanks again for all the help.
  • allanlane5allanlane5 Posts: 3,815
    edited 2006-08-10 21:50
    7 Sonar sensors, you say. Wow.

    Well, you're going to have to decide (in your own mind) how you want your robot to respond with different combinations and permutations of those sensors.

    The first step does seem to be -- read the conditions around you.

    With all those sensors, it sounds like the 'states' the robot can be in could include:
    1. Looking for the other robot.
    2. Too close to the edge.
    3. Pushing the other robot.
    4. Approaching the other robot.
    5. Turning toward the other robot.
    6. Running away from the other robot.

    I assume you're doing a 'Sumo' application, with that "edge detection" IR. So following lines, or following walls, or avoiding obstacles while it maps a room, or getting stuck in corners, are not part of what this robot will be doing.

    Now, for each 'state' the robot can be in, it probably wants to read all those sensors. Then, based on what the sensors tell you, you'll want to take some action -- turn a bit, move forward a bit, back up a bit, whatever. But it's probably not going to be as simple as "Sensor 1 says he's close. Go to state 1". More likely it's "All sensors say the other robot is right in front of me, and the edge detector says I'm not on the edge. Therefore, go to state 4 (where I'll be approaching the other robot).

    So each 'decision' clause (deciding to stay in current state, or what state should be next) will be made on more than one sensor. Sounds like a cool project, actually.
  • AImanAIman Posts: 531
    edited 2006-08-11 13:25
    allanlane5,

    ·· Your help in explaining how to use FSM·is greatly appreciated.

    Truth is I am working on a robot to help my wife do some housework, things like sweep and·vaccum. Edge detection is because our livingroom has a single step and the clearance detection is so it can go under things like the·kitchen table. With the·two IR for the front it makes me wonder if·two more for the back would be a good idea.

    The coding is already roughed out for what to do so what is below is fairly close to being put·togther and field tested. Nothing like debugging.·I think programming should be renamed debugging...

    I figured it would need to have 7 sonar to get a good all around idea of its enviorment without running into sonar overlap.·Basically·the robot·reads things in terms of distance and speed relative to the robots direction of travel and speed. So if something is out of range it is ignored, if something is in range but doesn't violate the minimum safe distance it is ignored unless it is moving towards the robot. Obviously a new robot will mean debugging the code again, but its much easier when using the same stamp. I have a second BS2 that will be slaved in to take over most of the sensor functions and·am seriously contemplating getting a third.

    The sensors are based on rotating through each one with 5 readings off each and then being averaged to get a more accurate reading. My smaller robot runs with encoder wheel but this one will run off Sonar readings so that will need to change.

    At this point I am debating between a tether and a battery. A tether solves a lot of power problems but a battery eliminates cords. The thought of a retractable extension cord like they sell in hardware stores came to mind, but what about people stepping on the cord or it getting wrapped around something? Maybe a hook on the ceiling with a tall pole on the robot would work with a tether.

    My orignal program has been written based on order of priority.

    1) Do what you can to get out of harms way

    2) Check power and if low go to starting point with LED flashing

    3) Complete tasks but if·something is in the way check for movement and clearnace and edges·to avoid object and injury.

    4) If tasks are done go to docking station, back in and go to sleep. (This is strickly so it doesn't get stepped on.)

    ·· I have a gripper that is designed to move clothes so that will have to be worked in. Right now my proptype will move faster then my reaction speed and has about a 5 lb strength. It is meant to have either sonar or IR attached to the gripper so that if it trys to pick something up it will watch to see if the object moves or not. There are some ideas I have for checking weight and still haven't decided exactly how that should work.

    Given the amount of data to·decision it became very clear to me that understanding FSM would be a very good thing. Right now·code is·written with a combination of IF-Then and Do-While loops. For example



    Sweeping:

    Do while sensors 1-7 are >= 5 inches.

    ·· If sensors 1-7 are < 5 inches then

    ······ Goto Self_Preservation· 'A sub that gets the robot out of danger

    ··········· if object does not move goto 1 inch away

    ··········· Sweep

    ··········· End if

    ···End if

    Loop

    Given what you discussed that will change somewhat to read

    If sensor 1 is >= 5 inches away then state = 1

    ·· If state 1 then

    ···· Goto Sweep

    ····· If sensor 2 >= 5 inches away then

    ······· State = 2

    ····· End if

    ·· End if

    ·· If state 2 then

    ···· Do whatever

    ···End if

    End if



    The hard part is going to be getting the combanations in place. For example if sensor 1 and 2 <= 5 then state = 11. This will of course require thinking not just about the state for each·seonsor or combination of sensors·but also the state of the sensor/s on the opposite side.

    Its going to be complex but a few minutes a day gets the program done and working on a sub routine for everything is much easier then making one large program.
  • Tom WalkerTom Walker Posts: 509
    edited 2006-08-11 13:42
    FSMs are usually a little more complicated than a simple "top loop jumping to different routines based on the current sensor situation" (I know I'm over-simplifying a little, but please bear with me). Picture this scenario: Bot is looking for a opponent (state 1 from your previous message) and sees the edge. Now it sees the edge (state 2) so it executes a certain response (let's say back straight up). So far, so good. Suddenly, you find the opponent and approach (state 4) until you start pushing (state 3). What happens while you are pushing and the other bot has a slight advantage and you get pushed closer and closer to the edge? With your simple state scenario, your bot wouldn't "think" to react to the edge. And if you programmed it to keep looking (perhaps using some subsumptive programming or the such-like), should the bot react the same way if it is being pushed as it does if it is just free-roaming? I suppose you could just set up another state in your architecture that means "being pushed and seeing the edge", but you can see that this could lead to having to figure out multiple combinations...not to mention that it only checks the state within your main loop.

    I realize that my questions might imply that some really ingenious AI needs to be written, but Dr. Tracy Allen does a whole lot better job of explaining the concept.

    I'm going to go get some caffeine, now.

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    Truly Understand the Fundamentals and the Path will be so much easier...
  • Kevin WoodKevin Wood Posts: 1,266
    edited 2006-08-11 15:48
    If you're thinking about using several stamp modules, you might want to consider using the Propeller chip instead.

    It has 8 processor cores, giving you many configuration options.
  • AImanAIman Posts: 531
    edited 2006-08-11 18:35
    I couldn't find a chart of how the Propeller and BS2 compare. It did indicate that it used Spin as a high level language.

    Does anyone know where I can find out how Spin and Pbasic relate and how the Prop chip and the BS2 compare?

    If the Propeller·is comprable it is most certainly worth the time.





    On the FSM questions; perhaps I was assuming what I meant would be clear. If any sensor gets its saftey area invaded it takes over to get it away from an edge or object.

    Also if I am doing multipule items with sensors and states then don't the subs have to be written with AND as the main function? For example if sonar 1 and sonar 7 are <= 5 inches then state = 8. Couldn't this·be listed as a set of xor where it would read something like:

    If Sonar1 and Sonar2 <= 5 inches xor Sonar1 and Sonar7 <= 5 inches then state = 8

    ·
  • Kevin WoodKevin Wood Posts: 1,266
    edited 2006-08-11 23:47
    I can't answer the XOR question, but I do have some comments.

    If you were to create scheme where (sensor 7 < 5) AND (sensor 1 < 5) = state 8, what you are essentially saying is that in the common condition of being less than 5 inches, 7+1 = 8. If you extrapolate this, you would have to account for things like this:

    7 + 1 = 8
    6 + 2 = 8
    5 + 3 = 8
    5 + 2 + 1 = 8
    4 + 3 + 1 = 8
    Etc...

    So here is an example where several conditions all equal the same state, but may need to perform different actions depending on the sensor readings.

    So for your robot, using movement as an example, you could reduce that to a minimum of 2 states - moving or not moving.

    If you want to get more detailed, you could have moving forward, moving backward, or not moving - 3 states.

    You could also add turning, and track it as seperate states such as turning or not turning, or combine it with moving, and get something like:

    moving forward
    moving forward right
    moving forward left
    moving rearward
    moving rearward right
    moving rearward left
    not moving

    For a 1 to 1 sensor to state mapping, the simplest mapping is front & rear for forward & rearward. If you added 4 more sensors, at 45 degree angles from forward & rearward, you could map those to the turn directions.

    So what you need to do is define your states based on some action that your robot will be performing - moving, sweeping, checking input, reading sensors, etc. If your robot can only be in one state at a time, such as moving or not moving, things are fairly simple. But when your robot can be in multiple states at once, things get complicated. For example, your robot needs to monitor the sensors, and can do it while moving or not moving.

    So the more states you have to track, the more difficult the task becomes. One solution that you have mentioned is to use multiple processors, which is where the Propeller would probably work well, especially since the communication pipeline between cogs within the Propeller is built-in and well designed.

    Just to let you know, I'm not trying to sell you on the Propeller. I'm working on a similar project with a BS2, and as I was reading this post I started thinking about how the Propeller would make things easier. Since a Propeller cog is a discrete processor, you could still create the machine using one cog, but you could use 1 cog for sensors and 1 for motion control, leaving you 6 for whatever else. Again, the same concept as using multiple BS2s, but designed & integrated as a single unit.

    The differences between the Propeller & BS2 are considerable. Probably the best way to see some of the differences would be to download the Basic Stamp Manual & Propeller Manual, and do some comparisons. You can also ask on the Propeller forum.
  • LoopyBytelooseLoopyByteloose Posts: 12,537
    edited 2006-08-12 19:33
    THE PROPELLER IS 'ALMOST' LIKE HAVING 8 BASIC STAMPS IN ONE PACKAGE.

    Of course that is a vast oversimplification. It also runs faster, has video abilities, and can use a keyboard and a mouse.

    The 8 microprocessors share an Input/Output bus of 32 pins. But otherwise, they can start and stop as independent units. For a State Machine approach, you really have the opportunity for simultaneous operations. It is eight 32 bit processors versus one 8 bit processor.

    Why buy 4 Stamps to do the job at $50 each when you can buy 4 Propeller chips for $25 each? Or maybe only one or two.

    Yes, there are differences. The Propeller is a 3.3volt system that requires adaptation to 5 volt I/O. And, if you do buy the chip, you have to add on your own EEPROM, 3.3v voltage regulator, and a serial interface. it still come in at less than One stamp.

    If you buy the PropStik, it is still less than two stamps. And everything is provided. It is a kit.
    Nonetheless, these are not big obstacles to someone who wants to build a robot with the ability to clean and so forth. And the fact that the cost is so reasonable, just makes it a joy.

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    "If you want more fiber, eat the package.· Not enough?· Eat the manual."········
    ···················· Tropical regards,····· G. Herzog [noparse][[/noparse]·黃鶴 ]·in Taiwan
  • Kevin WoodKevin Wood Posts: 1,266
    edited 2006-08-13 06:26
    Another good deal is the Propeller Robot Controller kit, found here:

    www.wulfden.org/PRC/

    Complete kit prices are at the bottom of the page.
  • AImanAIman Posts: 531
    edited 2006-08-17 17:17
    I posted on the propeller forum and got some useful info about Propeller v BS2. It would appear at this point that using two of the 16-servo controllers with a few Propellers - probably two - will be the most benifical.

    Out of my previous robots and those sold commercially for vaccuming and lawn mowing, I know everything my robot is intended to do can be done. This robot will be big, no question about that, but the fun is in building it. It will probably take longer to build then I figure (best guess is·12 months) because of trouble locating and building parts for a larger robot.

    I have located a lot of useful resources and thought people might want to see whats out there. So heres a brief summary of what is going to happen.

    My home computer has been set up with speech recognition and the more I use it the better it gets, eventually that will become a voice command program.·Most places that handle software for blind people deal with voice recognition and its fairly good and reliable. If memory serves Parallax has a voice recognition unit as well.

    Popular Science has an articale from a few years ago about a 'Guy who turned his girlfriend into a robot' and·PS sites facial recognition software that is supposed to be cutting edge. Don't recall the company off the top of my head.
    One of the computer stores has a game where you hook up a camera to the computer and you can play against the figure on the tv. Its a kids karate game, but the demo worked pretty well.
    Parallax has the CMU so that might be a useable option for my intentions.

    IR and Sonar are pretty basic, so they won't be much hassel and will make good object and edge detection systems.

    There are several surplus stores, hobby stores, computer stores·and a few farm stores within driving distance so I can get gears, small and large motors, rubber for feet and lots of different size batteries, spacers, wires, screws, nuts, bolts... Home Depot, Menards, Lowes, Ace hardware - they are good places to wonder through and look for small metal bars and tubing that can be used for body and legs and the bolts and small bars make good axels. The internet is also a·good resource, I looked up remote controlled cars and airplans to find gears transmitters and a wide range of servo's. Another place for gears is gopherbearing.com

    In short, getting all this together will be a chore. So to overcome obvious problems I am making sub routines and small programs to be called and monitored as needed (much easier then a big one).


    ······ idea.gif
    ·
Sign In or Register to comment.