Automated planning is a branch of AI that addresses the problem of generating a course of action to achieve a specified objective, given an initial state of the world. It is an area that is central to the development of intelligent agents and autonomous robots. In the last decade, automated planning has seen significant progress in terms of scalability, much of it achieved by the development of heuristic search approaches. Many of these advances, are only immediately applicable to so-called classical planning tasks. However, there are compelling applications of planning that are non-classical. An example is the problem of web service composition, in which the
objective is to automatically compose web artifacts to achieve the objective of a human user. In doing so, not only the hard
goals but also the \emph{preferences} of the user---which are usually not considered in the classical model---must be considered.
% Also, the automated composition
%should deal with abstract representations of the web %artifacts---which may also not adjust to the classical model.
In this thesis we show that many of the most successful advances in classical planning can be leveraged for solving compelling
non-classical problems. In particular, we focus on the following non-classical planning problems: planning with
temporally extended goals; planning with rich, temporally extended preferences; planning with procedural control, and
planning with procedural programs that can sense the environment. We show that to efficiently solve these problems we
can use a common approach: reformulation. For each of these planning tasks, we propose a reformulation algorithm that generates another, arguably simpler instance. Then, if necessary, we adapt existing techniques to make the reformulated instance solvable efficiently. In particular, we show that both the problems of planning with temporally extended goals and with procedural control can be mapped into classical planning.
Planning with rich user preferences, even after reformulation, cannot be mapped into classical planning and thus we develop
specialized heuristics, based on existing heuristics, together with a branch-and-bound algorithm. Finally, for the problem of
planning with programs that sense, we show that under certain conditions programs can be reduced to simple operators, enabling
the use of a variety of existing planners. In all cases, we show experimentally that the reformulated problems can be solved
effectively by either existing planners or by our adapted planners, outperforming previous approaches.
| Identifer | oai:union.ndltd.org:TORONTO/oai:tspace.library.utoronto.ca:1807/24336 |
| Date | 15 April 2010 |
| Creators | Baier, Jorge A. |
| Contributors | McIlraith, Sheila Ann |
| Source Sets | University of Toronto |
| Language | en_ca |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.002 seconds