Goto

Collaborating Authors

Extending Classical Planning with State Constraints: Heuristics and Search for Optimal Planning

Journal of Artificial Intelligence Research

We present a principled way of extending a classical AI planning formalism with systems of state constraints, which relate - sometimes determine - the values of variables in each state traversed by the plan. This extension occupies an attractive middle ground between expressivity and complexity. It enables modelling a new range of problems, as well as formulating more efficient models of classical planning problems. An example of the former is planning-based control of networked physical systems - power networks, for example - in which a local, discrete control action can have global effects on continuous quantities, such as altering flows across the entire network. At the same time, our extension remains decidable as long as the satisfiability of sets of state constraints is decidable, including in the presence of numeric state variables, and we demonstrate that effective techniques for cost-optimal planning known in the classical setting - in particular, relaxation-based admissible heuristics - can be adapted to the extended formalism. In this paper, we apply our approach to constraints in the form of linear or non-linear equations over numeric state variables, but the approach is independent of the type of state constraints, as long as there exists a procedure that decides their consistency.


The 2008 Scheduling and Planning Applications Workshop (SPARK'08)

AI Magazine

SPARK'08 was the first edition of a workshop series designed to provide a stable, longterm forum where researchers could discuss the applications of planning and scheduling techniques to real problems. Animated discussion characterized the workshop, which was collocated with the 18th International Conference on Automated Planning and Scheduling (ICAPS-08) held in Sydney, Australia, in September 2008. What keeps the fine advances in this field made over recent years hidden? The international Scheduling and Planning Applications Workshop (SPARK) was established to help address this issue. Building on precursory events, SPARK'08 was the first workshop designed to provide a stable, long-term forum where researchers could discuss the applications of planning and scheduling (P&S) techniques to real problems.


Logic and Decision-Theoretic Methods for Planning under Uncertainty

AI Magazine

Decision theory and nonmonotonic logics are formalisms that can be employed to represent and solve problems of planning under uncertainty. We analyze the usefulness of these two approaches by establishing a simple correspondence between the two formalisms. The analysis indicates that planning using nonmonotonic logic comprises two decision-theoretic concepts: probabilities (degrees of belief in planning hypotheses) and utilities (degrees of preference for planning outcomes). We present and discuss examples of the following lessons from this decision-theoretic view of nonmonotonic reasoning: (1) decision theory and nonmonotonic logics are intended to solve different components of the planning problem; (2) when considered in the context of planning under uncertainty, nonmonotonic logics do not retain the domain-independent characteristics of classical (monotonic) logic; and (3) because certain nonmonotonic programming paradigms (for example, frame-based inheritance, nonmonotonic logics) are inherently problem specific, they might be inappropriate for use in solving certain types of planning problems.


Planning Hierarchies and their Connections to Language

AAAI Conferences

Robots working with humans in real environments need to plan in a large state--action space given a natural language command. Such a problem poses multiple challenges with respect to the size of the state--action space to plan over, the different modalities that natural language can provide to specify the goal condition, and the difficulty of learning a model of such an environment to plan over. In this thesis we would look at using hierarchical methods to learn and plan in these large state--action spaces. Further, we would look the using natural language to guide the construction and learning of hierarchies and reward functions.


The 2008 Scheduling and Planning Applications Workshop (SPARK'08)

AI Magazine

SPARK'08 was the first edition of a workshop series designed to provide a stable, long-term forum where researchers could discuss the applications of planning and scheduling techniques to real problems. Animated discussion characterized the workshop, which was collocated with Eighteenth International Conference on Automated Planning and Scheduling (ICAPS-08) held in Sydney, Australia in September 2008.