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

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Volume

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Contents

Real-time search methods were devised as alternatives to more traditional search methods for searching known deterministic domains. We argue that real-time search methods have additional advantages for searching unknown or nondeterministic domains. Instead of planning for every contingency, 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 nondeterministic domains, namely for goal-directed navigation and localization in the presence of initial pose uncertainty and for exploring unknown environments.