Analyzing External Conditions to Improve the Efficiency of HTN Planning

AAAI Conferences

One difficulty with existing theoretical work on HTN planning is that it does not address some of the planning constructs that are commonly used in HTN planners for practical applications. Although such constructs can make it difficult to ensure the soundness and completeness of HTN planning, they are important because they can greatly improve the efficiency of planning in practice. In this paper, we describe a way to achieve some of the advantages of such constructs while preserving soundness and completeness, through the use of what we will call external conditions. We describe how to detect some kinds of external conditions automatically by preprocessing the planner's knowledge base, and how to use this knowledge to improve the efficiency of the planner's refinement strategy. We present experimental results showing that by making use of external conditions as described here, an HTN planner can be significantly more efficient and scale better to large problems.


Planning As Mixed-Initiative Goal Manipulation

AAAI Conferences

The idea to present planning as a goal manipulation process rather than a search process has much appeal, at least intuitively. Goals have long been recognized as important to a full understanding of both human and machine problemsolving abilities (Newell and Simon 1963; 1972; Schank 1982; Schank and Abelson 1977).


Decision-Theoretic Subgoaling for Planning with External Events

AAAI Conferences

One of the central assumptions of classical planning is that the state resulting at some time after performing an action can be predicted completely and with certainty. This assumption permits a style of planning in which a goal, represented by a sentence in first-order logic, is achieved exactly by a plan, represented as a partially ordered set of actions. The plan need include no sensing or branching because of the assumption. More realistic planners allow for uncertainty in the results of actions. Specifically, uncertainty in the domain is typically represented in one or more of 3 ways: 1. non-deterministic effects of operators, possibly with probability distributions, 2. uncertainty in the initial conditions of the domain, and 3. uncertainty about future states due to unpredictable external events in the domain.


On-line Planning and Scheduling: An Application to Controlling Modular Printers

Journal of Artificial Intelligence Research

We present a case study of artificial intelligence techniques applied to the control of production printing equipment. Like many other real-world applications, this complex domain requires high-speed autonomous decision-making and robust continual operation. To our knowledge, this work represents the first successful industrial application of embedded domain-independent temporal planning. Our system handles execution failures and multi-objective preferences. At its heart is an on-line algorithm that combines techniques from state-space planning and partial-order scheduling. We suggest that this general architecture may prove useful in other applications as more intelligent systems operate in continual, on-line settings. Our system has been used to drive several commercial prototypes and has enabled a new product architecture for our industrial partner. When compared with state-of-the-art off-line planners, our system is hundreds of times faster and often finds better plans. Our experience demonstrates that domain-independent AI planning based on heuristic search can flexibly handle time, resources, replanning, and multiple objectives in a high-speed practical application without requiring hand-coded control knowledge.


Online Planning and Scheduling: An Application to Controlling Modular Printers

AAAI Conferences

We present a case study of artificial intelligence techniques applied to the control of production printing equipment. Like many other real-world applications, this complex domain requires high-speed autonomous decision-making and robust continual operation. To our knowledge, this work represents the first successful industrial application of embedded domain-independent temporal planning. Our system handles execution failures and multi-objective preferences. At its heart is an online algorithm that combines techniques from state-space planning and partial-order scheduling. We suggest that this general architecture may prove useful in other applications as more intelligent systems operate in continual, online settings. Our system has been used to drive several commercial prototypes and has enabled a new product architecture for our industrial partner. When compared with state-of-the-art off-line planners, our system is hundreds of times faster and often finds better plans. Our experience demonstrates that domain-independent AI planning based on heuristic search can flexibly handle time, resources, replanning, and multiple objectives in a high-speed practical application without requiring hand-coded control knowledge.