ICAPS-05 Tutorial: Domain Modeling for Planning

6 June 2006

For a planning application, how the domain is modeled can mean the difference between success and failure. In this tutorial, we will present examples of modeling challenges drawn from a broad range of practical applications, including manufacturing, UAV control, and space operations, as well as some of the domains used in the most recent International Planning Competition. For each of these applications, we will discuss and illustrate the pros and cons of various modeling approaches, including PDDL, various HTN schema representations (e.g., SHOP2, ACT, O-Plan) logical formalisms (TAL), and constraint-based representations such as NASA's DDL and LAAS' IxTeT input language.

Despite an explicit attempt in many of these representations to follow McDermott's dictum regarding representing physics rather than advice, how planning problems are modeled interacts strongly with how they are solved. Some of the ways this manifests may be surprising, for example the presence of preconditions in an operator purely for the purpose of binding a variable, or the ordering of preconditions in a conjunct so as to minimize the number of ground operators or variable bindings considered.

Domain modeling for planning is very similar to domain modeling in conventional software engineering. Few if any current languages provide effective engineering support for the modeling process. In addition, for many applications the most significant factors in generating a solution are not easily represented or manipulated in the available formalisms. For example, it is cumbersome at best to model planning domains dominated by resource management in PDDL and other STRIPS derived languages, which have no explicit resource model. Many planning languages make it difficult to encode operators with complex context-dependent effects, such as sending an email message with attachments. Few current planning languages make any attempt to model asynchronous, overlapping continuous change, such as simultaneous charging and drawing from a battery in a space probe, or simultaneous drawing from and filling of a tank in an oil refinery.

In this tutorial, we will present and discuss these and other modeling issues and their effects, as well as possible work-arounds. We will accomplish this through a process of comparative modeling, providing worked examples in multiple formalisms for each of several, qualitatively different application domains. We will characterize both requirements and a proposed solution for the problem of support for constructing and maintaining domain models for planning. With regard to representation languages, our intent is not to identify or propose a specific language for all applications, but to illuminate the strengths and weaknesses of the current approaches, for specific types of applications.

Intended audience: Theorists and practitioners. Theorists interested in what happens when these formalisms must support a broad variety of representational requirements encountered in real domains. Practitioners interested in tradeoffs when choosing (or building) a representational framework. Any researchers or practitioners who wish to understand the relative strengths and weaknesses of a range of representational choices.

Draft viewgraphs

Acrobat Reader Format

The presenters:

Mark Boddy is currently employed at Adventium Labs a small nonprofit research lab in Minneapolis, working on a wide variety of applications of planning and scheduling in manufacturing, cyber-security, and autonomous and multi-agent systems. He was previously a Research Fellow at Honeywell Labs, where he led development teams working on planning and scheduling for a wide variety of manufacturing applications, as well as conducting research on planning under uncertainty, integrations of constraint programming and math programming, and distributed planning and scheduling.

Robert P. Goldman (rpgoldman @ sift dot info) is currently a Senior Scientist at SIFT, LLC , a small research company in Minneapolis that develops intelligent control systems. He is currently working on two planner-based systems for Uninhabited Aerial Vehicle (UAV) operations. Dr. Goldman's primary research focus is applications of planning systems for controlling autonomous systems, and interfaces between planning and control. Prior to joining SIFT, he was a Senior Principal Research Scientist at Honeywell Labs, where he worked on planning under uncertainty, manufacturing scheduling, and real-time controller synthesis, in applications including UAV control, manufacturing, and military logistics.