Overview and Examples of Real-Time Search in Unknown or Nondeterministic Domains

Real-time search methods were devised as alternatives to more traditional search methods for searching known deter-ministic domains. We argue that real-time search methods have additional advantages for searching unknown or non-deterministic domains. Instead of planning for every con-tingency, real-time search methods execute the partial plan obtained after a bounded amount of planning, observe the resulting successor state, and then plan for only the resulting successorstate, not for all states that could have resulted from the execution of the plan. In this paper, we give two examples for how real-time search can be used in unknown or nonde-terministic domains, namely for goal-directed navigation and localization in the presence of initial pose uncertainty and for exploring unknown environments