SHOP2: An HTN Planning System

Task resolution is performed in the order tasks will be performed. So a current world state includes previous decisions and the ramifications of those decisions.

Primitive task: a task which can be performed by an operator.

Compound task: a task which must be broken down in to smaller tasks using a method.

Method: a replacement grammar that attempts to replace a compound task with more concrete steps.

Precondition: attributes of the world state which must be true for this method to be relevant.

SHOP2 walks over symbols in the current plan and predicted world state. It looks for the first method in a list that can resolve the compound task and the preconditions are considered satisfied. It does this until every compound task in the plan is solved or reaches a failure state.

The paper does not handle optimal outcomes; but you can add backtracking and memoization to attempt to handle planning failures.

"Branch and bound": keeping track of the best plan found so far. Then continuing to walk trees trying different methods at different levels