I seem to remember that overtaking was also believed to be almost an impossibility, but someone had a bright idea, so there is hope.

Is this a brainstorming question?

Overtaking appears a much more difficult problem, as cars have to decide it, it is not located to one spot. This is different for the right-of-way problem. Don't solve it for the car but for the intersection.

An intersection with traffic lights, that are always green for one direction, unless a car from the other directions arrives at it, then it switches. Unless there is a car on the tile of the prefered direction.

For an intersection of the form:

` | A |`

-- --

B B

-- --

| A |

state (i)

green for direction A--A

red for direction B--B

state (ii)

red for A--A;

green for B--B.

- begin in state (i)
- If there is a car at either A = 1, if not A = 0, same for B.
- If B=1 and A=0 switch to state (ii); return to (i) after
*v* seconds - If B=1 and A=1 remain in state (i) and start a timer,

after *u* seconds switch to state (ii), return to state (i) after *v* seconds

where

*u* is the time a couple of cars need to clear the intersection and

*v* is the time a few cars need to clear the intersection.