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.

Yochan at ICAPS

Yochanites formed a strong contingent at the recently concluded International Conference on Automated Planning and Scheduling (ICAPS) held in Providence, RI.

From L to R, top row first: Menkes, Will, Terry, J., Sungwook, Dan, Minh, Rao, Kartik

Bhaumik Chokshi's Defense

Bhaumik Chokshi will conduct his thesis defense on Tuesday, 11th Sept in BYENG 455. Details are available below:

Comparing Offline and Online Statistics Estimation for Text Retrieval from Overlapped Collections
Student Defense
Date: September 11, 2007
Time: 10:30 AM - 12:00 PM

Contact Person: Bhaumik Chokshi
Contact Email: bhaumik.chokshi@asu.edu
Location: BYENG 455
Defense Type: Master's Thesis Defense

Committee Members
Dr. Subbarao Kambhampati
Dr. Yi Chen
Dr. Hasan Davulcu

In an environment of distributed text collections, the first step in the information retrieval process is to identify which of all available collections are more relevant to a given query and should thus be accessed to answer the query. Collection selection is difficult due to the varying relevance of sources as well as the overlap between these sources. Some of the previous collection selection methods have considered relevance of the collections but have ignored overlap among collections. They thus make the unrealistic assumption that the collections are all effectively disjoint. Overlap estimation can be done in two ways - offline or online. In this thesis, the main objective is to compare these two approaches for estimating statistics. One of the existing approaches(e.g., COSCO) uses offline approach to store the statistics for frequent item sets. It uses these statistics to estimate statistics for the user query. In this thesis, ROSCO is presented, which uses sample based online approach to estimate the overlap among collections for a given query. In addition to that, COSCO and ROSCO are compared with ReDDE(which does not consider overlap) under a variety of scenarios. The experiments show that ROSCO is able to outperform existing methods by 8-10% in presence of overlap among collections.