Overhaul traffic light control logic

[alexdarling]

This has been a thorn in our side for a while, and my attempts to patch the problem have just proven how terrible the codebase is. I am going to rip out my current implementation and replace it with something else completely.

Currently in the brainstorming phase. I will submit a sketch of the logic soon.

[alexdarling]

I have come up with a couple simplifying assumptions:

• From a traffic control unit's perspective, these lanes can either be active lanes or inactive lanes. An active array is one where we cannot assume that there is no traffic flowing through hit.
• If a given lane L is active, it is impossible for either of its orthogonal lanes Lo0 or Lo1 to be active. The only lane that could possibly be active is the parallel lane Lp.
• For our model, a given lane L has 2 arrays of traffic, L.left and L.straight.
• Lp is active under 2 conditions:
  • L is active
  • L.left and L.straight are not both currently in use

[alexdarling]

After some additional work on this, I believe it is better to build the entire product together instead of piece by piece. It will increase the risk of bugs and slow down the development process, but I am having too much trouble keeping the requirements in mind while designing the algorithm.

[alexdarling]

Actually, keeping 1 lane active does not seem to make sense. Instead, an active lane will be a lane that the system is considering allowing traffic through. This means there are only 3 possible states of activity in a traffic system:

• North and South lanes are both active
• East and West lanes are both active
• No lanes are active

The current plan for a fixed light pattern depends on a few functions from the lane:

• lane.hasCars() which should return true if 1 or more cars is present in a lane
• lane.hasLeft() and lane.hasStraight(). Similar to the above function, but only for cars present in a specific lane's array

And a functions inside the light control unit lcu:

• lcu.a[], a 1D, 2-element array for holding 2 parallel active lanes
• lcu.i[], a 1D, 2-element array for holding 2 parallel inactive lanes
• lcu.handoff() switches the contents of a with i
• lcu.bothLeft() displays a left turn light in both active lanes
• lcu.bothStraight() displays a straight light in both active lanes
• lcu.singleDisplay(n) displays a left turn light and a straight light to the active lane with index n in the array of active lanes, and a red light in the other active lane with index (n + 1)%2.

My current plan is this:

1. Set two parallel active lanes in a[0] (north / east) and a[1] (south / west)
2. Set the remaining inactive lanes in i[0] and i[1] respectively. These lanes are guaranteed to be parallel to each other and orthogonal to the active lanes.
3. Take a snapshot of hl0 = a[0].hasLeft(), hs0 = a[0].hasStraight(), hl1 = a[1].hasLeft(), hs1 = a[1].hasStraight()
4. if hl0 AND hl1: lcu.bothLeft()
5. if hl0 AND NOT hl1: lcu.singleDisplay(0), THEN lcu.bothStraight()
6. else if NOT hl0 AND hl1: lcu.singleDisplay(1), THEN lcu.bothStraight()
7. else lcu.bothStraight()
8. if (i[0].hasCars() OR i[1].hasCars()): handoff()

This should handle the logic that allows the control unit to swap between lanes.

However, this function is being run over a period of cycles (likely of varying length), and it needs to be able to keep track of what step it's in as needed. I am going to keep brainstorming a solution to this problem.

[alexdarling]

I believe I can simplify Steps 5 and 6 with a hl0 XOR hl1, then determining which index has a left car and using that to call lcu.singleDisplay(n) and ignoring the THEN clause.

Step 7 can be changed to if hs0 or hs1: lcu.bothStraight() so if all the cars are gone after the other cycles, there is no wasted time.

[alexdarling]

The step 7 simplification doesn't actually work because we are choosing our decisions based off traffic snapshots. It may be worth changing Step 7 to something that doesn't use a snapshot, and only using hl0 and hl1.

We do still need those 2 snapshots so we aren't allocating an overly-long amount of time to left turn lights.

[alexdarling]

It appears that all this functionality can be achieved using a queue of function variables which are then called in sequence after certain time intervals.

To do this in a clean way, I am not going to make some of these function calls dependent on the snapshot while others are dependent on present cars. Everything will be snapshotted, the queue will be created, and then that queue will get called over time.

However, this changes the handoff() function, which will need to perform a live check of the cars in i[]. I can achieve this by simply appending handoff to all queues of active functions, and have handoff() repeat the sequence on its own.

[alexdarling]

What is left is to consider how to transition between light states. This queue functionality makes a lot of sense from the light control's perspective, but in between various light states there needs to be a transition state.

For the following key

**R:** Stop
**Y:** Slow
**G:** Straight
**L:** Left
**A:** L & G

If we transition between a state like GRGR to RGRG, we need multiple light states in between, in this sequence:

1. GRGR
2. YRYR
3. RRRR
4. RGRG

The steps 2 and 3 exist to ensure that no cars from Step 4 begin moving while cars from Step 1 are in the intersection. This would cause cars to collide.

I am not sure how to implement this functionality, particularly in a way that "makes sense" for a developer to implement. For instance, I do not want modifications to the system to assume every duration of light must also include N seconds of buffer time to handle states 2 and 3 from the example.

In addition, not all transitions are equivalent. The transition from LRLR to GRGR is:

1. LRLR
2. RRRR
3. GRGR

And step 2 in this case should take about the same amount of time as steps 2 and 3 from the previous example (since it serves the same purpose), but it occurs in a single step. Somehow the traffic light control system needs to know how to split up these wait times so cars don't hit each other and there isn't unneeded delay.

[alexdarling]

After some attempts at creating a fix, I found even more issues.

Not all transition periods even contain the RRRR sequence, such as the transition between ARRR and GRGR:

1. ARRR
2. GRRR
3. GRGR

So we can't build this around RRRR being a common thread.

Next, if we transition from ARRR and then move immediatly into the handoff (for example, 1 left array has 1 car and the rest of the active lanes' arrays are empty), then we are moving from ARRR to RRRR, which gives:

1. ARRR
2. RRRR
3. // anything from the new handoff

The example here contrasts with the example above, because their Step 1s are the same but their Step 2s are different. This means we can't build out transition states as a series of "suffixes".

Another problem is that we may end up with a "transition" from GRGR to GRGR, in which case there should not be any transition state.

This is a really gnarly problem.

[alexdarling]

It appears that we need a handful of rules in order to work out this transition period.

Notes on Input The transition period is based on the from and to light states. If a light's from and to states are equivalent, instead no transition occurs.

Each light at index n in the state is judged individually. Here is my current breakdown:

• f from[n] = to[n], then transition[n] = from[n]
• if from[n] = "R", then transition[n] = "R"
• if from[n] = "L", then transition[n] = "R"
• if from[n] = "A", then there are 2 possible transitions:
  • if to[n] = "R", then transition[n] = "Y"
  • if to[n] = "G", then transition[n] = "G"
• if from[n] = "G", then there are 2 transitions in order:
  • the first is transition[n] = "Y"
  • the second is transition[n] = "R".

[alexdarling]

Resolved in #29. Code is not fully tested, but we don't have infrastructure available to test left turns yet. Once that is in place, we will make a new issue to fix any big problems.