Finite State Machines

A finite state machine describes behavior as a set of states, such as patrolling or charging, and rules for when to switch, such as "battery low" or "noise heard". The robot is always in exactly one state. It is the simplest way to organize robot behavior, and still one of the most common.

States and transitions

An FSM has a set of states $S$, a set of events $E$, and a transition function that gives the next state:

$$\delta : S \times E \to S \qquad s_{t+1} = \delta(s_t,\ e_t)$$

Events that have no transition from the current state are simply ignored.

What to notice

Press "Battery low" in any state and the robot heads to its dock, because that transition is drawn from every working state. Press "Noise heard" while charging and nothing happens, since charging has no such transition. FSMs are easy to read and test, but as behaviors grow, the number of arrows explodes, and adding one new state can mean adding arrows from every other state. Behavior trees, next, were invented largely to fix that.