Menkes van den Briel's Doctoral Dissertation Defense

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.

Aravind Kalavagattu's Defense

Mining Approximate Functional Dependencies as Condensed Representations of Association Rules
Student Defense
Date: July 30, 2008
Time: 10:00 AM - 12:00 PM

Contact Person: Aravind Krishna Kalavagattu
Contact Email: aravindk@asu.edu
Location: BYENG 420
Defense Type: Master's Thesis Defense
Committee Members: Prof. Subbarao Kambhampati

Approximate Functional Dependencies (AFD) mined from database relations represent potentially interesting patterns and have proven to be useful for various tasks like feature selection for classification, query optimization and query rewriting. Though the discovery of Functional Dependencies (FDs) from a relational database is a well studied problem, the discovery of AFDs still remains under explored, posing a special set of challenges. Such challenges include defining right interestingness measures for AFDs, employing effective pruning strategies and performing an efficient traversal in the search space of the attribute lattice. This thesis presents a novel perspective for AFDs as condensed representations of association rules; for example, an AFD (Model=>Make) is a condensation of various association rules like, (Model:Accord=>Make:Honda), (Model:Camry=>Make:Toyota). In this regard, this thesis describes two metrics, namely Confidence and InfoSupport analogous to the standard metrics confidence and support used in association rules respectively. This thesis presents an algorithm called AFDMiner for efficiently mining high quality AFDs by employing effective pruning strategies. AFDMiner performs a bottom-up search in the attribute lattice to find all AFDs and FDs that fall within the given Confidence and InfoSupport thresholds. Experiments on real data sets show the effectiveness of the approach both in terms of performance as well as the quality of AFDs generated.