SOUND AND EFFICIENT CLOSED-WORLD REASONING FOR PLANNING

Closed-world inference--an essential component of many planning algori thms--is the process of determining that a logical sentence is false b ased on its absence from a knowledge base, or the inability to derive it. We describe a novel method for closed-world inference and update o ver the first-order theories of action used by planning algorithms suc h as NONLIN, TWEAK, and UCPOP. We show the method to be sound and effi cient, but incomplete. In our experiments, closed-world inference cons istently averaged about 2 milliseconds while updates averaged approxim ately 1.2 milliseconds, Furthermore, we demonstrate that incompletenes s is nonproblematic in practice, since our mechanism makes over 99% of the desired inferences. We incorporated our method into the XII plann er, which supports our Internet Softbot (software robot), The techniqu e cut the number of actions executed by the Softbot by a factor of one hundred, and resulted in a corresponding speedup to XII.