Subject:
|
Re: Multitasking
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Mon, 19 Jul 2004 23:43:53 GMT
|
Original-From:
|
Steve Baker <sjbaker1@airmailNOSPAM.net>
|
Viewed:
|
960 times
|
| |
|
|
Bert Weber wrote:
> how does BrickOS handle the following situation?
> Its a path follower robot with bumpers to detect an obstacle.
> When the robot starts it seeks the black path and follows it.
> When the robot hits an obstcle, he gets back and turns.
> How do I implement this behavior?
A useful technique (which doesn't really require parallel threads)
is called a "State Machine" (also known as a "Finite State Automaton"
or FSA for short).
The idea is to list all the 'states' the robot can be in and to
assign a number to each state. In this case, that might be:
#define JUST_STARTED 0
#define LINE_FOLLOW_TURNING_LEFT 1
#define LINE_FOLLOW_TURNING_RIGHT 2
#define LINE_FOLLOW_GOING_STRAIGHT 3
#define REVERSING_FROM_OBSTACLE 4
#define TURNING_BACK_AGAIN 5
#define ERROR 999
...and so on.
Then, your main program looks like this:
int state = JUST_STARTED ;
while ( 1 )
{
switch ( state )
{
case JUST_STARTED : ... ; break ;
case LINE_FOLLOW_TURNING_LEFT : ... ; break ;
case LINE_FOLLOW_TURNING_RIGHT : ... ; break ;
case LINE_FOLLOW_GOING_STRAIGHT : ... ; break ;
case REVERSING_FROM_OBSTACLE : ... ; break ;
case TURNING_BACK_AGAIN : ... ; break ;
default:
state = ERROR ;
}
}
Now, everywhere I wrote '...' you have to put in some code. What
you have to do in writing each piece of code is to say stuff like:
case LINE_FOLLOW_GOING_STRAIGHT : /* The robot is going straight, following the line. */
/*
What action should it be doing then?
*/
...turn both wheel motors on 'forwards'...
/*
What could cause us to stop going forwards and
do something else instead?
*/
if ( bump_sensor ) state = REVERSING_FROM_OBSTACLE ; else
if ( left_light_sensor ) state = LINE_FOLLOW_TURNING_RIGHT ; else
if ( right_light_sensor ) state = LINE_FOLLOW_TURNING_LEFT ; else
state = LINE_FOLLOW_GOING_STRAIGHT ;
break ;
...so for each state you could be in, what action do you take while in that
state - and what conditions will take you out of that state and put you into
some different state.
OK so far? Well, unless you are stuck with NQC (and hence no nice arrays and
structures) don't write that code...there is an easier way if you are using
GCC:
Notice that each of those 'case' clauses has a very similar structure.
* If we are in this state.
* Take this action
* If this happens, then the next state is that...else
* If this happens, then the next state is that...else
* If this happens, then the next state is that...else
* the next state is unchanged.
Right - now comes the clever part. When you look at this long set of states, actions, tests
and subsequent states, you can easily see how to turn this into a table:
struct State
{
int left_motor ; /* How to drive the left motor when we are in this state */
int right_motor ; /* How to drive the right motor when we are in this state */
int bump_sensor_state ; /* What state to switch to if the bump sensor just went 'active' */
int left_light_sensor_state ; /* What state to switch to if the left light sensor says 'bright' */
int right_light_sensor_state ; /* What state to switch to if the right light sensor says 'bright' */
} ;
struct State state_table [] =
{
/* State 0 == Idle */
{ ON_FWD, ON_FWD, REVERSING_FROM_OBSTACLE, FOLLOW_LINE_GOING_FORWARD, FOLLOW_LINE_GOING_FORWARD },
/* State 1 == Follow line going forward */
{ ON_FWD, ON_FWD, REVERSING_FROM_OBSTACLE, FOLLOW_LINE_TURNING_RIGHT, FOLLOW_LINE_TURNING_LEFT },
....
} ;
Now, your main program looks like this:
int state = JUST_STARTED ;
while ( 1 )
{
set_left_motor ( state_table [ state ] . left_motor ) ;
set_right_motor ( state_table [ state ] . right_motor ) ;
if ( bump_sensor ) state = state_table [ state ] . bump_sensor_state ; else
if ( left_light_sensor ) state = state_table [ state ] . left_light_sensor_state ; else
if ( right_light_sensor ) state = state_table [ state ] . right_light_sensor_state ;
}
...and that's *it*.
The idea is that the setup of the table describes what the robot should do at every state it can
be in.
This kind of program is very compact (because the actual program is only a dozen lines of code and
all of the actual algorithm is data). It's also fairly easy to debug: Have the program display
the current 'state' on the LCD display and you know all you need to know about what the robot is
doing. If it says it's in state 4 and it does the wrong thing next - then look at the 'struct
State' for array entry number 4 and you'll know immediately why it did what it did.
In some versions of FSA's, instead of the 'action' being directly what to do with the motors, it
might also be the address of a function to call in order to make the action happen...that depends
on the complexity of the algorithm you are trying to deal with.
---------------------------- Steve Baker -------------------------
HomeEmail: <sjbaker1@airmail.net> WorkEmail: <sjbaker@link.com>
HomePage : http://www.sjbaker.org
Projects : http://plib.sf.net http://tuxaqfh.sf.net
http://tuxkart.sf.net http://prettypoly.sf.net
-----BEGIN GEEK CODE BLOCK-----
GCS d-- s:+ a+ C++++$ UL+++$ P--- L++++$ E--- W+++ N o+ K? w--- !O M-
V-- PS++ PE- Y-- PGP-- t+ 5 X R+++ tv b++ DI++ D G+ e++ h--(-) r+++ y++++
-----END GEEK CODE BLOCK-----
|
|
Message has 1 Reply:
 | | Re: Multitasking
|
| (...) Steve, I just want to say thanks for your clear explanation. I have heard the term state machine tossed around a lot, but didn't really know what it was. (Not all of us robotics guys are computer programmers for a living!) I don't need to (...) (20 years ago, 21-Jul-04, to lugnet.robotics)
|
Message is in Reply To:
| | Re: Multitasking
|
| Hi, how does BrickOS handle the following situation? Its a path follower robot with bumpers to detect an obstacle. When the robot starts it seeks the black path and follows it. When the robot hits an obstcle, he gets back and turns. How do I (...) (20 years ago, 18-Jul-04, to lugnet.robotics)
|
5 Messages in This Thread:
  
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
This Message and its Replies on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
