Deadline-Aware Search Using On-Line Measures of Behavior

In many applications of heuristic search, insufficient time isavailable to find provably optimal solutions. We consider thecontract search problem: finding the best solution possible within agiven time limit. The conventional approach to this problem is to usean interruptible anytime algorithm. Such algorithms return a sequenceof improving solutions until interuppted and do not consider theapproaching deadline during the course of the search. We propose anew approach, Deadline Aware Search, that explicitly takes the deadlineinto account and attempts to use all available time to find a singlehigh-quality solution. This algorithm is simple and fully general: itmodifies best-first search with on-line pruning. Empirical results onvariants of gridworld navigation, the sliding tile puzzle, and dynamicrobot navigation show that our method can surpass the leading anytimealgorithms across a wide variety of deadlines.