Exercise - State Transition Diagrams

A common problem in Finch programming is switching between sequences of actions based on human or sensor input. The simplest case in a linear script sequence in which each cue simply advances to the next movement. But as soon as the robot program start choosing between alternatives, it can be useful to diagram the logic as a state transition graph.

State Transition Graphs and State Machines

The basic idea is that at any given moment, the program exists in one discrete state, but can transition to other states based on specific conditions. In the diagram, states are illustrated as ovals and transitions as directed arcs with arrowheads. Each state is a mode with actions defining the behavior in that state. Each transition has a predicate, i.e a true-or-false rule, which can be evaluated based on the sensor and interface inputs and determines whether to change state. The combination of the state and transition definitions is known as a state machine.

There are many possible ways of implementing a given state machine in code. Diagramming out the logic can help separate the conceptual thinking from the details of coding.

digraph input_matching { node [fontsize=10] edge [fontsize=8] dpi="144" size="7,7!" // declare all nodes START [ label = "START\nwait briefly"] EXPLORE [ label = "EXPLORE\ndrive forward"] REVERSE [ label = "REVERSE\ndrive backwards"] TURNLEFT [ label = "TURNLEFT\nsmall turn"] TURNRIGHT [ label = "TURNRIGHT\nsmall turn"] BACKTRACK [ label = "BACKTRACK\nescape backwards"] SPIN [ label = "SPIN\nturn around"] PAUSE [ label = "PAUSE\nwait briefly"] // declare all edges with labels START -> EXPLORE [ label = "two seconds elapsed"] EXPLORE -> BACKTRACK [ label = "obstacle in front"] EXPLORE -> REVERSE [ label = "five seconds elapsed"] REVERSE -> TURNLEFT [ label = "two seconds elapsed\nAND random = 1"] REVERSE -> TURNRIGHT [ label = "two seconds elapsed\nAND random = 2"] BACKTRACK -> SPIN [ label = "one second elapsed"] TURNLEFT -> EXPLORE [ label = "0.5 seconds elapsed"] TURNRIGHT -> EXPLORE [ label = "0.5 seconds elapsed"] SPIN -> PAUSE [ label = "one second elapsed"] PAUSE -> BACKTRACK [ label = "one second elapsed\nAND obstacle in front"] PAUSE -> EXPLORE [ label = "one second elapsed\nAND no obstacle"] label = "Finch Robot Exploration\nState Transition Diagram" }

State Machine Example

The example state transition graph shown illustrates an exploratory behavior controlled by the obstacle sensor input and clock time. The basic purpose is to wander around a space without getting stuck. Most of the time the Finch drives forward. If it sees an obstacle, it enters BACKTRACK to rapidly escape backwards and then choose a new direction. If it doesn’t see any obstacles within a short time, it backs up slightly using REVERSE and randomly changes direction. This can help move the Finch away from any obstacles that it cannot see with its sensors.

Try it out!

Please try the sample implementation of the state machine in a Snap sketch. The code is structured as one large polling loop. On each iteration, it evaluates a specific case corresponding to a single state (e.g. an oval in this graph), applying the actions and deciding whether to transition. The current state value is kept as a string in a global variable. This is an idiomatic programming structure which allows any state to transition to any other state.

Challenges

  1. What failure modes can you observe, e.g., where the robot gets stuck? Can you add states or transitions to avoid this? Do they create new failure modes?
  2. How could you use the orientation input to navigate different terrain?
  3. Can you simplify the code by creating some new blocks for common operations?
  4. Can you make the code more efficient by only issuing each robot command once when entering the state? The example implementation keeps sending the identical robot commands again and again, which in many cases is not needed.

Garth Zeglin, Personal Robotics Lab, Carnegie Mellon University