A fundamental concern in real-time planning is the presence of dead-ends in
the state space, from which no goal is reachable. Recently, the SafeRTS
algorithm was proposed for searching in such spaces. SafeRTS exploits a
user-provided predicate to identify safe states, from which a goal is likely
reachable, and attempts to maintain a backup plan for reaching a safe state at
all times. In this paper, we study the SafeRTS approach, identify certain
properties of its behavior, and design an improved framework for safe real-time
search. We prove that the new approach performs at least as well as SafeRTS and
present experimental results showing that its promise is fulfilled in practice.
