Say that you are in a US city with streets arranged in a grid, and your destination is i blocks to the North and j blocks to the East of your current location: which path will you pick to go there? There are (i+j choose i) different routes that all have the same length, but you may or may not have to wait at intersections before crossing. The shortest path is, among the paths with minimum total length, the one that minimizes waiting time.
Whenever you reach an intersection, you are able to cross without waiting, in at least one of the two directions North and East, as long as i and j are both positive. But if i is zero, there is only one shortest path and you are stuck just going East for j blocks, forced to wait at intersections whenever the light is red for pedestrians. So, the best way is to avoid reaching the point where i or j is zero.
This means that, if you have just finished crossing at one intersection, finding yourself at the North-East corner, and now have a choice between walking East for one block or North for one block, you should always choose the direction that decreases max(i,j).
Say that you are at the North-West corner of an intersection, and that the light is red for pedestrians to go East. Should you wait for the light to change so that you can cross to the East side, or walk North for one block, hoping to be luckier at the next intersection? It depends on whether you got there by walking East for one block, or by walking North for one block and crossing the intersection from South to North: in the first case your waiting time is completely random and there is no point in waiting at this spot rather than walking North for one block and hoping to get lucky at the next intersection. In the second case, the answer is not completely clear. Since it has already been a while since the light last changed, on average you will wait less at the current intersection that at the next intersection. However you should also take into account how close min(i,j) is to zero, or perhaps how small |i-j| is: maybe you are in no hurry to go East, because i is large compared to j and you will have many other opportunities to cross going East.
I realized at my last trip to the Boston financial district that I use that algorithm without even thinking about it, relying on some gut feeling for the last case, and automatically applying the above rules for the other cases. I wonder: does everybody do that? Or at least, every computer scientist? Do people do it consciously or deliberately? Is this actually the best path, or is there a better way?
Aren't you assuming that the traffic lights, as Boolean random variables, are independent? It seems to me that if you get a green at one end of a block, and walk at a certain pace, then the other light is correlated - often negatively (you walk much slower than cars).
ReplyDeleteSomething that I noticed is the "hysteresis" in paths: if there are two roughly parallel streets and one has to use a cross street to move from one to the other, then one tends, instinctively, to use the earliest cross-street, which leads to using different paths on the way in and back. (Experimented between rue d'Ulm and rue Saint Jacques.)
I always do this; I started doing it subconsciously before realizing that this is what I was doing when I stopped to think about it. I imagine it's the 'natural' algorithm that would occur to a computer scientist (or at least a theorist).
ReplyDeleteDM: The walking time from one block to the other is partially random too when taking into account the crowd (or, if you are rollerblading/unicycling in a 3rd world country, the state of the sidewalk). If the variance of the block crossing time is superior to the period of the traffic light, then those can be considered independant for all practical concern.
ReplyDeleteWhat about the following algorithm: When i is much larger than j, go into the direction corresponding to i if encountering a red light, and obviously cross otherwise. When i is within a factor of 2 of each other, use the amount of people waiting to estimate how long the light has been red. Of course on narrow streets (i.e. street crossing time shorter than half period of the trafic light), you should cross outside of the sidewalk when the cars are stopped by their own red light!
As about putting algorithmics into daily life: I remember people of LRI (theory and not) laughing at the idea of optimizing the path to cross in diagonal the parking lot according to the relative density of cars left and right of the diagonal.