| This thesis considers the problem of reasoning and planning in open worlds, where the agent does not have complete information about the world and must act to acquire knowledge and to change the world.;We designed a language PSIPLAN to represent and reason about the agent's knowledge. PSIPLAN uses a class of universally quantified propositions, which we call y -forms, that are used to represent partially closed worlds, such as 'There's nothing in the bag, except for a pen and maybe a paycheck' or 'The agent knows the format of all files in the directory except for the file a.img'. We developed a calculus for a y -reform based language and showed that the y -reform reasoning is sound, complete and has polynomial complexity. Thus, extending STRIPS-style planning to planning with y -reforms adds only polynomial time complexity.;We implemented a partial order planning algorithm PSIPOP-S based on PSIPLAN for open world planning with sensing and knowledge goals. Compared to existing implemented systems PSIPOP-S has several advantages: it can express partially closed worlds, it can represent precisely the agent's knowledge or lack of knowledge, it handles domains with a large or infinite number of objects, and it is sound and complete when it does no sensing. Moreover, PSIPOP-S has roughly the same complexity bounds as traditional closed-world partial-order planners. |
