= Incremental belief-state search
An <incremental belief-state search> initially plans for a small <subset> $B_0$ of the possible initial states, then tests the candidate <plan> on the full initial <belief state> $B$. If a state in $B$ makes an action inapplicable or fails the final <goal test>, add that counterexample to $B_0$ and solve the enlarged problem. The new search may need to revise the entire <plan>, rather than append actions to the previous candidate.
With finitely many initial states and a complete finite-model solver for each restricted problem, at most $|B|$ state additions are required. Failure to find a <plan> even for a restricted <subset> proves that none can work for the whole <belief state>. A candidate that passes full validation is a genuine <plan> for <sensorless planning>. The advantage is selective tracking: a small number of representative initial states may force a universally successful <plan> without constructing the full <power set> search space.
Back to article page
