Exploiting Belief State Structure in Graph Search

摘要: It is well-known that eliminating repeated states essential for efficient search of state-space AND-OR graphs. The same technique has been found useful searching beliefstate graphs, which arise in nondeterministic partially observable planning problems and games. Whereas physical are viewed by algorithms as atomic admit only equality tests, belief states, sets possible have additional structure: one state can subsume or be subsumed another. This paper presents new exploit this property to achieve substantial speedups. demonstrated on Kriegspiel checkmate a vacuum world domain.