Heuristic Search When Time Matters

In many applications of shortest-path algorithms, it is impractical to find a provably optimal solution; one can only hope to achieve an appropriate balance between search time and solution cost that respects the user's preferences. Preferences come in many forms; we consider utility functions that linearly trade-off search time and solution cost. Many natural utility functions can be expressed in this form. For example, when solution cost represents the makespan of a plan, equally weighting search time and plan makespan minimizes the time from the arrival of a goal until it is achieved. Current state-of-the-art approaches to optimizing utility functions rely on anytime algorithms, and the use of extensive training data to compute a termination policy. We propose a more direct approach, called Bugsy, that incorporates the utility function directly into the search, obviating the need for a separate termination policy. We describe a new method based on off-line parameter tuning and a novel benchmark domain for planning under time pressure based on platform-style video games. We then present what we believe to be the first empirical study of applying anytime monitoring to heuristic search, and we compare it with our proposals. Our results suggest that the parameter tuning technique can give the best performance if a representative set of training instances is available. If not, then Bugsy is the algorithm of choice, as it performs well and does not require any off-line training. This work extends the tradition of research on metareasoning for search by illustrating the benefits of embedding lightweight reasoning about time into the search algorithm itself.