To simplify robot control on the early stages of development, TeamUR's
behavior has been defined using non-deterministic(1)
Finite State Machine (FSM) technique.
This approach has been employed already in TeamUR
the First as in TeamUR the Third. You can see
the practical implementation of the algorithm in Tmr003.02.
The machine has the following states:
- Start - initial state
- Move_forward
- Move_back
- Obstacle - robot has detected an obstacle
- Turn_left
- Turn_right
The outputs are represented by motor control signals.
Output values:
- Left_motor: Stop, Forward, Reverse
- Right_motor: Stop, Forward, Reverse
The output values are generated according to Moore Machine type(2).
Moore Machine is a type of FSM where the outputs are products of the state.
Outputs depend on state:
| State |
Left motor |
Right motor |
| Start |
Stop |
Stop |
| Move_forward |
Forward |
Forward |
| Move_back |
Reverse |
Reverse |
| Obstacle |
Stop |
Stop |
| Move_back |
Reverse |
Reverse |
| Turn_left |
Reverse |
Froward |
| Turn_right |
Froward |
Reverse |
The transition from one state to another can be triggered by an event.
Generally there are two types of events: external (from machine's environment
received by sensors) and the internal (from machine subsystems like timers).
External event triggers:
- Obstacle_detector: obstacle_detected=0, no_obstacle_detected=1
Internal event triggers:
- Timer_100ms
- Rnd_num_generator
The transitions between the states are defined by set of the the rules:
| From state |
To state |
Rule |
| Start |
Move_forward |
(Timer=3s elapsed) |
| Move_forward |
Obstacle |
(Obstacle_detector=True) |
| Obstacle |
Move_back |
(Timer=0.5s elapsed) |
| Move_back |
Turn_Left |
(Timer=0.5s elapsed) and (Rnd_num_generator = 1) |
| Move_back |
Turn_right |
(Timer=0.5s elapsed) and (Rnd_num_generator = 0) |
| Turn_left |
Move_forward |
(Timer=0.5s elapsed) and (Obstacle_detector=False) |
| Turn_right |
Move_forward |
(Timer=0.5s elapsed) and (Obstacle_detector=False) |
This approach proved expected advantages:
- Simple and easy to implement. The model can be directly implemented
as big case/switch statement.
- Predictable: suitable for testing purposes (in our case disabled random number generator makes the FSM
deterministic)
- Effective because of low processor overhead. Allows execute only the code for the current state.
- Easy to implement in time sharing systems.
Finite State Machines
Making simple work of complex functions
David Gibson, SPLat Controls Pty Ltd
http://www.microconsultants.com/tips/fsm/fsmartcl.htm
Interesting text about FSM in video games, which convinced us to write
this document: http://ai-depot.com/FiniteStateMachines/
(1) The difference between non-deterministic and deterministic FSM is in the fact that the state transition rule is generated randomly.
In this case we are generating randomly turn direction.
(2) There is another type of FSM:
Mealy Machine, which is opposite to Moore Machine because it generates the outputs as products of the transition between states. | 
