Finite State Machines
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.
·
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.
·
Comments
http://www.emesystems.com/BS2fsm.htm
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Chris Savage
Parallax Tech Support
csavage@parallax.com
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?
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?
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
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.·
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?
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.
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.
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.
·· 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.
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...
It has 8 processor cores, giving you many configuration options.
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
·
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.
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."········
www.wulfden.org/PRC/
Complete kit prices are at the bottom of the page.
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).
······
·