Doctoral Dissertation Defense
Integer Programming Approaches for Automated Planning
Menkes van den Briel
Committee:
Co-Chairs: Drs. Subbarao Kambhampati and John Fowler
Drs. Ahmet Keha, Goran Konjevod, and Thomas Vossen
Defense Date/Location: Thursday, July 31, 2008 at 10:00 AM, GWC 510
Abstract
Automated planning is concerned with developing automated methods for generating and reasoning about sequences of actions to perform certain tasks or achieve certain goals. Since reasoning about a course of actions to achieve desired outcomes is an important hallmark of intelligent behavior, automated planning has been one of the longstanding sub-areas of artificial intelligence.
The use of integer programming approaches for automated planning has received only little attention, and is generally not thought to be competitive with the more traditional approaches for automated planning. This research, however, shows that the use of integer programming can provide effective approaches for solving automated planning problems, and has the potential to address quality and optimization criteria that arise in real world planning problems.
In particular, this research makes the following contributions. (1) It introduces novel integer programming approaches where causal considerations are separated from sequencing considerations, and where more general interpretations of action parallelism are introduced. The combination of these ideas leads to very effective integer programming formulations that are solved using a branch-and-cut algorithm. (2) It shows how to exploit these novel integer programming formulations in solving partial satisfaction problems, which are planning problems that typically require an increased emphasis on the modeling and handling of plan quality. (3) It develops a novel framework based on linear programming that gives rise to finding provably optimal plans. Moreover, this framework can also be used in heuristic search approaches for automated planning.
No comments:
Post a Comment