NerdKit Stoplight Project, Week 1

Unfortunately, I had to leave town on business before the NerdKit arrived. Marshall and I had been discussing the Finite State Machine aspect of the traffic light controller. I put together a simple one just based on timers. It only had a handful of states and the only event that triggered a state change was when the timer expired, which we represented using TX. Our simulation is to be based on the temporary traffic signals that are put in place when they rebuild a bridge and restrict traffic to one lane. The signal allows traffic from both directions to share a single lane to cross the bridge.
Our "requirements" are to include weight sensors at each end of the bridge to signal the controller when traffic is waiting to cross the bridge. We decided that we wanted the traffic to have a maximum wait time of 1 minute. We also decided to assume that it took 15 seconds to get from one side of the bridge to the other at the posted work-zone speed limit. Given a 5 second yellow light, that meant that there would be a green light for a maximum of 40 seconds.
Our initial "weightless" state diagram only cared about the position of the lights. The valid states were INIT, GR, YR, CR, RG, RY, and RC. The letters R, Y, and G in the those states represent the color of the light in one of each direction. The letter C, represents a red light in one direction while we wait for traffic to clear. Although we could have used a single RR state that would work for both directions, I was already thinking ahead to the version with weight sensors.
On Monday morning, I made my trip to the airport. I began to work on the FSM diagram, and quickly realized that I couldn't keep track of everything. So I changed direction and began building a spreadsheet. The spread sheet had four columns: current-state, event, action, new-state. The initial state and initial transitions are easy. You start in the state RRNN which represents a red light in both directions and no traffic on either weight sensor. In my initial attempt, there were 5 events that would cause a state transition: T1, N1, T2, N2, and TX. These events correspond to the weight sensor for direction 1 indicating traffic and no traffic, repeating for direction 2, and finally the timer expiring. So my table looked like this:

Current	Event	Action	New State
RRNN	T1	G1,T(40)	GRTN
RRNN	N1	N-A	N-A
RRNN	T2	G2,T(40)	RGNT
RRNN	N2	N-A	N-A
RRNN	TX	N-A	N-A

Note that two of the events never make sense. If the weight sensor indicates that traffic is present, the event corresponding to traffic arriving isn't valid. In the initial state, we aren't waiting for a timer to signal anything, so we are simply waiting for traffic to appear. When it appears, we will give that direction a green light. The action column indicates which light and for which direction as well as "T(40)", meaning we're setting a timer for 40 seconds.

Working through the table, I discovered that there were 12 states for one direction. Double that for both directions and add in the initial state yields 25 states. Thus the table consists of groups of five entries for each state. However, every group had two entries that didn’t apply.

For each state, there were two “events” that really couldn’t occur, and if they did occur, they would yield the same state. For example, the state GRTN represents a Green light in direction 1, a Red light in direction 2, Traffic sensed by the weight sensor for direction 1, and No Traffic sensed by the weight sensor for direction 2. The T1 event would indicate the sensor changing from not sensing weight to sensing weight. That change cannot occur without first generating the N1 event representing the sensor changing to no weight. Further, even if the event were possible, the event would not cause a state transition as the state machine is already in the state indicated by traffic sensed in direction 1. Therefore, I changed the meaning of T1 and T2 to mean Toggle, or change in the value of the weight sensor in direction 1 and 2 respectively. I was then able to remove the N1 and N2 events and shrink the table by 50 integers.

That reminds me of a time early in my Bell career when Linda Lahue made fun of me for worrying about saving a couple of bytes in a structure. I had come from a programming environment where we only had 64K of data available to us. I wasn’t used to working on a machine with a whole 32MB memory! Today, that’s tiny! Of course, on a large midrange computer, 50 bytes won’t matter, but programming a microcontroller with a small amount of memory, you had better be in the habit of maximizing your memory usage.

At first, Marshall didn’t understand why the table even had rows for events that didn’t make sense for a given state. Of course, he doesn’t have any programming experience at all, so this was an opportunity to show him how we can write a very generic programming routine that is driven by the data. The first thing I noticed about the action column of my table was that there are only two types of actions listed. The first was an indication of what light was to be turned on. Although I didn’t list it in the table, there was also an implied light that needed turned off. The other type of action was setting a timer. Given that these were the only actions ever described by the table, I came up with the following structure to represent the states and transitions:

struct stateEntry {

uint8_t lightOn;

uint8_t lightOff;

uint8_t timer;

uint8_t newState;

};

Next I created an array of these structures. The array consists of groups of three of these structures, one for each of the possible events. The start of this array looks like this:

struct stateEntry stateTable[] {

/* RRNN */

/* T1 */ { G1, R1, GT, GRTN },

/* T2 */ { G2, R2, GT, RGNT },

/* TX */ { NA, NA, NA, NA },

/* GRTN */

/* T1 */ { Y1, G1, YT, YRNN },

/* T2 */ { NA, NA, NA, GRTT },

/* TX */ { NA, NA, NA, GRTNX }

The comments indicate the current state and the three events. Each of the values in the array has an associated #define associated with it to give it a value. The lightOn and lightOff values are bit masks corresponding to pins on the microcontroller that need to be turned on or off. Those pins will be connected to LEDs representing our traffic lights. In the real world, they could be connected to relays which would actually control the more power hungry traffic signals. The third column is defined to be the timer length for the appropriate condition. GT stands for green timer and would be defined as 40. YT is the yellow timer and is defined as 5. If we decide we want a different period of time for these lights to be on, we can change the definition instead of having to change the value in each state in which they apply.

Once the table is filled in, the program becomes very simple. Assume we have functions to return an event number (0,1,2) corresponding to the events (T1, T2, TX), functions for setting the timer, and functions for turning lights on and off. The get_next_event function would figure out if the timer expired or if one of the weight sensors had changed values and return the appropriate value corresponding to the event. The main loop would then have the following logic:

current_state = RRNN

LOOP: event = get_next_event()

index = (current_state * 3) + event

entry = stateTable[index]

if (entry.lightOn != -1)

toggleLights(entry.lightOn, entry.lightOff)

if (entry.timer != -1)

setTimer(entry.timer)

if(entry.newtState != -1)

current_state = entry.newState

goto LOOP

Notice how simple the main logic is. For any given state, the set of data corresponding to the 3 possible events are grouped together. To get to the appropriate group, multiply the value of the current_state by three. This gets us to the group of three entries that correspond to the current state. Then add the value for the current event to obtain the appropriate entry for the current event. This forces the programming thought to be pushed into data. It’s not that we can’t create a buggy program, but the logic errors are mostly likely to be found in the state model.

There are still some hardware dependent issues to deal with, like how to actually enable the chip to output a current on the appropriate pins, how to make the timer work, etc. Since I didn’t actually have the NerdKit with me, the best I could do was to read lots of documents while I was away. In fact, the first step when I get home is to get used to wiring the pieces together. My first program will probably attempt to use the watch dog timer (part of the microcontroller) to count in seconds and display the count on the provided LCD. Once that works, it will be a short step to getting the traffic controller operational.