Past exam of the computer science course of the University of Oxford / 2019 / Artificial intelligence / 1 / h

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.