Sane unless one of the paths is actually substantially shorter, in which case it’s a waste of time that feels efficient.
There are psychological aspects to all of this too. There are several routes from my bus stop to my house right now, and while they all have the same length (Manhattan distance = x+y, i.e. right angles) certain paths feel shorter… I think it’s mostly number-of-turns. When I walk straight down the street I live on, it seems really long, but when I walk partway down the adjacent street, then a block sideways, then the rest of the way, it seems somewhat shorter.
Well, imagine a planning algorithm that has no memory—then a heuristic like that (maybe with some amount of randomness to avoid cycles and such) might be your best bet.
Wow, that actually describes a pretty sane heuristic.
Sane unless one of the paths is actually substantially shorter, in which case it’s a waste of time that feels efficient.
There are psychological aspects to all of this too. There are several routes from my bus stop to my house right now, and while they all have the same length (Manhattan distance = x+y, i.e. right angles) certain paths feel shorter… I think it’s mostly number-of-turns. When I walk straight down the street I live on, it seems really long, but when I walk partway down the adjacent street, then a block sideways, then the rest of the way, it seems somewhat shorter.
Well, imagine a planning algorithm that has no memory—then a heuristic like that (maybe with some amount of randomness to avoid cycles and such) might be your best bet.