Automated planning in computer science consists of finding a sequence of actions leading from an initial state to a goal state. People who have expert knowledge of the specific problem domain work with experts in automated planning to define the domain states and actions. This knowledge engineering required to create complete and correct domain descriptions for planning problems is often very costly and difficult. Our goal with incomplete planning is to allow people to program domains without the need for planning experts. Throughout the process of instruction of intelligent systems, teachers can often leave out whole procedures and aspects of action descriptions. In such cases, the alternative to making domains complete is to plan around the incompleteness. That is, given knowledge of the possible action descriptions, we seek out plans that will succeed despite any incompleteness in the domain formulation. A state in a domain consists of a set of propositions that can be either true or false. Actions in a domain require specific propositions to be true for the action to occur. Actions then add and remove propositions from the state to create a subsequent state. A valid plan consists of a sequence of actions that, starting with the initial state, change to match the goal state. An incomplete domain contains the same qualities as a complete domain, with the additional abilities of actions to possibly require a proposition to be true to initiate the action, as well as possibly adding and possibly removing propositions in the subsequent state. Actions that have possible preconditions and effects are referred to as incomplete actions. Because no prior work exists for the purpose of empirical comparisons, we compare our incomplete action planner, which we call DeFAULT, with a traditional planner that assumes all good possibilities and no bad possibilities will occur. DeFAULT finds much better quality plans than the traditional planner while maintaining similar speed.
| Identifer | oai:union.ndltd.org:UTAHS/oai:digitalcommons.usu.edu:etd-2434 |
| Date | 01 May 2012 |
| Creators | Robertson, Jared William |
| Publisher | DigitalCommons@USU |
| Source Sets | Utah State University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | All Graduate Theses and Dissertations |
| Rights | Copyright for this work is held by the author. Transmission or reproduction of materials protected by copyright beyond that allowed by fair use requires the written permission of the copyright owners. Works not in the public domain cannot be commercially exploited without permission of the copyright owner. Responsibility for any use rests exclusively with the user. For more information contact Andrew Wesolek (andrew.wesolek@usu.edu). |
Page generated in 0.0019 seconds