When to Commit to an Action in Online Planning and Search

SOCS-22 Volume 15

Volume

Vol. 15 No. 1 (2022): Fifteenth International Symposium on Combinatorial Search

Long Papers

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.

10.1609/socs.v15i1.21755