Research

I'm interested in problem solving in planning/scheduling. I've done some work in plan representation, plan generation, scheduling by constraint satisfaction, and more recently, in optimal control theory.

Optimal Control Theory

I have recently developed an interest in applying optimal control theory to search. Optimal control theory applies mathematics to problems of optimal allocation of resources. In search, the problem is to allocate search effort where it is most likely to be successful. The work I've done for my dissertation involves applying mathematics (calculus of variations) in order to solve the problem of how to allocate search effort optimally. I've shown that this approach is valid in the case where nodes have cost functions associated with them and where the objective is to maximize probability of success given a time bound. My thesis will be available shortly.

Scheduling

There have been several successful approaches to scheduling in the literature. Most successful approaches use good heuristics and some kind of non-systematic search, i.e., search methods that may revisit nodes and which do not guarantee they will search the space completely. Most of these non-systematic methods are local-search-like methods, i.e., methods that start out with a candidate solution and make local changes, within a specified neighborhood, in search for a solution. I've been interested on a particular class of search algorithms that exploit the fact that good heuristics are usually accurate except for a few choices which they decide incorrectly. One such algorithm is Limited Discrepancy Search which explores the search space in order of increasing number of deviations from the heuristic path. It has been demonstrated that LDS is competitive with the state of the art in solving Resource Constrained Project Scheduling problems. LDS has a local search flavor in that the neighborhood is defined as all paths that lie at a fixed number of deviations from the heuristic path. Following the intuitions in LDS, I developed Weighted Discrepancy Search (WDS) which weighs discrepancies according to their signal strength in order to search more efficiently.

Plan Representation

I've done some work comparing different formalisms for reasoning about action and change. Adequate specifications for worlds that change according to action executions are usually too large, making reasoning in these domains highly inefficient. These domains typically include domain descriptions in terms of states and actions, where each action is specified with preconditions and effects (much like a STRIPS representation), plus domain constraints. Representing what is true and what is false at each state is also computationally expensive in many instances, for example, when actions are not fully specified or when the truth value of some condition depends only on the truth value of other conditions. The formalisms that have been proposed for representing knowledge in these domains are only able to deal with restricted cases. Efficient methods for representing knowledge in these domains is one of my interests.

Plan Generation

An adequate representation for reasoning about action and change would be useless without an adequate reasoning mechanism to obtain conclusions from the domain. The plan generation process is a mechanism to obtain conclusions where you are given a description of an initial state of the world and a description of a goal state and where the task is to generate a sequence of steps, or a plan, that "transforms" the initial state into the goal state. It is widely recognized that part of the plan generation process is a scheduling problem (where we may view the task related to the ordering of the steps as a scheduling problem). Understanding the role scheduling plays in the planning process and in more general terms, the role of constraint satisfaction in planning, is one of my main concerns. I believe this understanding will shed light on what makes planning computationally hard (undecidable) and it will indicate ways to recognize "easy" planning problems that can be solved efficiently.

Back to my Home Page