It’s 1:47pm according to my smartphone’s clock. By the time I reach Mall St. Matthews I’ll have gained an extra hour by passing between the Central and Eastern timezones. I’ve driven there once or twice before, so my phone is patched into my stereo by a short audio cable. Punk music plays, and intermittently Google Maps’s voice navigation crossfades to the surface.
“In a quarter mile, take the exit on the right.”
It’s a two hour drive from Bowling Green to St. Matthews where I am meeting some friends for the weekend. I spend the time staying awake, and while not drumming against the steering wheel, I occupy myself with a lemma in my thesis project.
Assume that Google Maps presents me with two routes to the mall. The first is more direct, running diagonally across the state along stretches of highway. This is certainly the path that, outside of this hypothetical situation, Maps actually suggests.
The second option is longer, but it—let’s imagine—cuts through an open field. That is to say, whereas the direct route is “fragile” against simple wrecks, the open field is nearly invincible. A series of meteors could fall and, so long as I had time to respond, I could simply steer around them in the ample space that the field provides.
Now, if I were not pressed for time, but instead “pressed for certainty,” then I would in many situations prefer the hypothetical open field over Google Maps’s direct route. But what are the other situations?
- The chance that a wreck or meteor or so on could be negligible, zero percent maybe, so why would I not choose the shortest route?
- The chance that a wreck or meteor could be really, really high, so high that I might as well sign my will and “run for it” on the shortest route.
- The road leading up to and/or out from the open field could be long or in poor condition, effectively countering the certainty that made the field an attractive option in the first place.
- Similarly, the field could be extremely long in its own right, the chance that I end up trapped by a “road network failure” becoming almost certain.
- The state of the field changes, and I learn about it ahead of time.
To illustrate this final point it may be best to reductio ad absurdum.
I’ve just plugged in my destination, and Google Maps has responded with the two routes: the actual result, a direct path; and a longer path cutting through an open field. Assume that the first four of the above cases do not apply.
As I’m turning the key to start the ignition, my phone rings. The ringtone, an antique bell, blasts through my stereo speakers.
“Hello?” I say, answering the phone as I unhook it from the audio cable.
“Hey, it’s Generic Friendname. I’ve some bad news,” my acquaintance replies.
“Big Open Left Field has been flooded.”
“Just the field? Not the roads?”
“Yeah, I have no idea how it happened either.”
“Well, I guess I won’t be going that way then, thanks.”
“Wait! There’s some good news too.”
“Apparently Moses—the one from the Bible—is still around, and when he heard about this flood, he came to the rescue.”
“So he got rid of all the water?”
“Well, no, not exactly. He just split it down the middle, so you can still drive through the field, but only in the one lane where he’s holding it open.”
“Oh. In that case, I’d still prefer to go the shorter way.”
This lemma, albeit absurd, demonstrates a vital detail about the complexity of pathfinding under uncertainty when information about the network can change. Static numbers won’t work.
I can’t assign to each length of road some number that I’ve calculated ahead of time then, while I am traversing the network—of roads or sidewalks or so on—, choose the available next move with the best of these numbers. Why not? Because, although I can still have a path down one road, knowledge about it can ruin it. Knowledge about it can strip away what was originally attractive about that road. Knowledge about it requires that all numbers be run again.
And that is a whole other order of complexity. ∎