AND-OR search

A search algorithm whose OR nodes represent controllable choices and whose AND nodes require solutions for every possible outcome of a chosen action. In nondeterministic planning, a successful OR choice needs successful continuations for all its AND children. In contingent planning, those children can represent different observations and updated belief states. Cycle handling must match the required solution concept: ignoring a repeated state is not a proof that the goal will inevitably be reached.