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 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. Real-time heuristic search methods interleave planning and plan execution and plan only in the part of the domain around the current state of the agents, which is the part of the domain that is immediately relevant for the agents in their current situation. Real-time search methods have been shown to be efficient alternatives to traditional search methods in known deterministic domains such as slidingtile puzzles (Korf 1993) and STRIPS-type planning domains (Bonet etal. 1997). However, many domains from robotics, control, and scheduling are either not completely known in advance or nondeterministic. Planning in unknown or nondeterministic domains is often more difficult than planning in known deterministic domains because the state spaces explode more quickly. Consequently, it is even more important that agents take their planning time into account to solve planning tasks efficiently. For single-instance planning tasks, for example, they should attempt to minimize the sum of planning and plan-execution time. Finding plans that minimize the plan-execution time is often intractable. Interleaving planning and plan execution is a general principle that can reduce the planning time and thus also the sum of planning and plan execution time for sufficiently fast-acting agents in unknown or nondeterministic domains. Without interleaving planning and plan execution, the agents have to find a large conditional plan that solves the planning task. When interleaving planning and plan execution, on the other hand, the agents have to find only the beginning of such a plan. After the execution of this subplan, the agents repeat the process from the state that actually resulted from the execution of the subplan instead of all states that could have resulted from its execution. Consequently, one advantage of interleaving planning and plan execution in unknown or nondeterministic domains is that it allows agents to gather information early. This information can be used to resolve some of the uncertainty caused by nondeterminism and thus reduce the amount of planning done for unencountered situations. Since actions are executed before their complete consequences are known, the agents are likely to incur some overhead in terms of the number of actions executed, but this is often outweighed by the computational savings gained. We demonstrate this advantage of real-time search and its broad applicability using two simplified robot-navigation tasks in gridworlds, namely goal-directed navigation and localization in the presence of initial pose uncertainty and exploring unknown environments.