When to Commit to an Action in Online Planning and Search


  • Tianyi Gu University of New Hampshire
  • Wheeler Ruml University of New Hampshire
  • Shahaf S. Shperberg Ben-Gurion University of the Negev University of Texas at Austin
  • Eyal Solomon Shimony Ben-Gurion University of the Negev
  • Erez Karpas Technion




Meta Reasoning And Search, Real-time Search, Combinatorial Puzzles, Problem Solving Using Search


In online planning, search is concurrent with execution. Under the formulation of planning as heuristic search, when a planner commits to an action, it re-roots its search tree at the node representing the outcome of that action. For the system to remain controlled, the planner must commit to a new action (perhaps a no-op) before the previously chosen action completes. This time pressure results in a real-time search. In this time-bounded setting, it can be beneficial to commit early, in order to perform more lookahead search focused below an upcoming state. In this paper, we propose a principled method for making this commitment decision. Our experimental evaluation shows that our scheme can outperform previously-proposed fixed strategies.