HTN Replanning from the Middle

Abstract

When an actor executes a plan, action failures and exogenous events may lead to unexpected states that require replanning from the middle of plan execution. In Hierarchical Task Network (HTN) planning, unless the HTN methods have been carefully written to work well in unexpected states, replanning may either fail or produce plans that perform poorly.

To overcome this problem, we introduce IPyHOP, a reentrant version of GTPyhop (a SHOP-like HTN planner), and Run-Lazy-Refineahead, a modification of the Run-Lazy-Lookahead actor that utilizes IPyHOP's reentrant replanning capability to replan during plan execution. In our experiments, Run-Lazy-Refineahead and IPyHOP expend less search effort (fewer decompositions and fewer iterations), find revised plans with fewer actions and lower total action cost, and finish execution with fewer failures.