= Solution
Use <incremental belief-state search> to find only the initial possibilities needed to constrain a successful <plan>. Choose one possible initial state, or a small <subset> $B_0$ of the full initial <belief state> $B$. Find an action <sequence> solving this restricted problem, then simulate it from every state in $B$.
If validation succeeds, return the candidate. Otherwise choose a state that makes some action inapplicable or ends outside the goal, add it to $B_0$, and search again for a <plan> that works for every selected state. Replanning can revise the earlier <sequence>; merely appending a repair to one arbitrary candidate can miss solutions. For a finite initial <belief state>, there are at most $|B|$ additions before every initial possibility has been included. If a complete restricted solver proves that even the selected <subset> is unsolvable, part (g) shows that the full problem is unsolvable.
The benefits are smaller intermediate <belief states>, fewer states propagated through candidate actions, and avoidance of unnecessary portions of the full <power set> search space. One physical-state counterexample can eliminate many invalid candidates. The worst case can still require all initial states; the method exploits instances where a few representative possibilities already force a <plan> that passes universal validation.
Back to article page
