Efficient Open World Reasoning for Planning

摘要

We consider the problem of reasoning and planning with incomplete knowledgeand deterministic actions. We introduce a knowledge representation schemecalled PSIPLAN that can effectively represent incompleteness of an agent'sknowledge while allowing for sound, complete and tractable entailment indomains where the set of all objects is either unknown or infinite. We presenta procedure for state update resulting from taking an action in PSIPLAN that iscorrect, complete and has only polynomial complexity. State update is performedwithout considering the set of all possible worlds corresponding to theknowledge state. As a result, planning with PSIPLAN is done without directmanipulation of possible worlds. PSIPLAN representation underlies the PSIPOPplanning algorithm that handles quantified goals with or without exceptionsthat no other domain independent planner has been shown to achieve. PSIPLAN hasbeen implemented in Common Lisp and used in an application on planning in acollaborative interface.