A path that buys time to decide where to go

Abstract

This paper considers the problem of planning a path in a circumstance where its origin is given, but its destination is not specified and is to be selected from among a set of candidate destinations during a trip. A situation like this may be experienced by a group of people who have different preferred destinations, as well as by an individual who is simply indecisive about where to go. To resolve such an uncertainty, one may stay at the origin until he decides on a destination, or choose to proceed on some path that does not overly deviate from a shortest path, whichever destination is eventually chosen, and make a decision on the way. The latter action is sensible when the risk of traveling longer is outweighed by the benefit of buying more time for a better destination decision. The problem of finding such a time-buying path is formulated and a simple algorithm is developed for its solution. Some extensions and applications are also discussed.

Keywords:

• decision-support system
• route planning
• uncertainty