The Fifth International Conference on Artificial Intelligence Planning and Scheduling
Anthony Barrett
In recent years, AI planning and scheduling has emerged as a technology critical to production management, space systems, the internet, and military applications. The Fifth International Conference on Artificial Intelligence Planning and Scheduling (AIPS2000) was held on 14-17 April 2000 at Breckenridge, Colorado;(1) it was colocated with the Seventh International Conference on Principles of Knowledge Representation and Reasoning (KR2000).
This conference brought together researchers working in all aspects of problems in planning, scheduling, planning and learning, and plan execution for dealing with complex problems. The format of the conference included paper presentations, invited speakers, panel discussions, workshops, and a planning competition. The conference was cochaired by Steve Chien of the Jet Propulsion Laboratory (JPL) at the California Institute of Technology, Subbarao Kambhampati of Arizona State University, and Craig Knoblock of the University of Southern California Information Sciences Institute, with the proceedings published by AAAI Press (Chien, Kambhampati, and Knoblock 2000). The three workshops were “Analyzing and Exploiting Domain Knowledge for Efficient Planning,” chaired by Maria Fox from University of Durham; “Decision-Theoretic Planning,” chaired by Richard Goodwin from IBM’s T. J. Watson Research Center and Sven Koenig from Georgia Institute of Technology; and “Model-Theoretic Approaches to Planning” by Paolo Traverso from IRST, Manuela Veloso from Carnegie Mellon University, and Fausto Giunchiglia from IRST.
Invited Speakers
The invited speakers at the conference presented some of their latest research and ideas on intelligent planning and execution: Drew McDermott from Yale University, gave the first talk, entitled “Bottom-Up Knowledge Representation,” and David Smith from NASA Ames Research Center gave the second talk, entitled “Coping with Time and Continuous Quantities.”
Bottom-Up Knowledge Representation
This talk was motivated by a rising interest in knowledge representation as the World Wide Web threatens to drown us in information. Many communities are discovering a need for information describing the content of documents or the behavior of programs. Because the described objects need to be processed by a wide variety of programs, designed by many different parties, finding a representation system to describe any content seems to be a daunting challenge. This challenge is similar to the well-known problems in trying to find a “formal theory of everything.” This talk described a more modest bottom-up approach that involves incrementally building small-specialized knowledge representation frameworks for immediate payoffs and facilitates greater payoffs as these small frameworks are linked together. This approach succeeds even if the process never converges to a general-purpose representation. Making it work involves carefully defining notions of when a framework is strictly more expressive than another and what it means to translate expressions within and between frameworks.
Coping with Time and Continuous Quantities
This talk was motivated by an underlying problem that arises when trying to manage one of a variety of spacecraft, from orbiting telescopes to planetary rovers. This problem involves maximizing science return while respecting various operating restrictions. This problem is hard because of a desire to satisfy many competing scientific objectives with limited time and resources. Solving the problem involves making action choices and timing decisions while reasoning about metric quantities, resources, and continuous time.
Is this problem one of planning or scheduling? Although AI problems that involve choosing actions are often regarded as planning problems, few AI planning systems can handle metric quantities, resources, continuous time, or optimization. In contrast, many scheduling problems have these characteristics, and many scheduling algorithms routinely deal with these issues. Although some job-shop scheduling systems can deal with choice over a finite set of alternative processes, none are designed to deal with unbounded action choice. To explain planners that bridge this gap between planning and scheduling, this talk defined constraint-based interval planning (Smith, Frank, and J6nsson 2000) and compared the common constraint-based interval planning algorithm with a partial-order causal-link planner such as SNLP.
Papers
The conference had 85 submitted papers, but only 30 were selected for presentation and 13 for a poster session. These papers can be grouped into four categories: (1) classical planning, extending to real-world problems; (2) uncertainty-probability; (3) scheduling; and (4) application systems. These papers were a mixture of basic research and developed ideas applied to real-world problems. Derek Long and Maria Fox from University of Durham won the outstanding research paper award for “Automatic Synthesis and Use of Generic Types in Planning.” This paper discussed getting domain-independent planners to use certain classes of domain-specific heuristics without requiring extra domain encoding effort. The second award was for outstanding applied research paper and went to Ari Jonsson, Paul Morris, Nicola Muscettola, and Kanna Rajan from NASA Ames Research Center and Ben Smith of JPL for “Planning in Interplanetary Space: Theory and Practice.” This paper discussed the planner used in the remote-agent experiment that controlled parts of the Deep Space 1 spacecraft for 2 days in May 1999. The outstanding student paper award went to Ioannis Tsamardinos and Martha Pollack from the University of Pittsburgh and John Horty from the University of Maryland for “Merging Plans with Quantitative Temporal Constraints, Temporally Extended Actions, and Conditional Branches.” This paper discussed using a constraint-satisfaction problem (CSP)–based approach to merging plans represented in a richly expressive language.
Classical Planning with STRIPS Actions
Over the last five years, GRAPHPLAN (Blum and Furst 1995) and SAT-based planning (Kautz and Selman 1992) have influenced the planning community with their surprising performance, and this year was no exception–seven papers focused on improvements to these planners. One paper discussed an improvement to GRAPHPLAN’S search phase with a set of distance-based variable-ordering heuristics, and another presented an alternative way to find a solution from a GRAPHPLAN planning graph that behaves like a SAT solver. A third paper presented another solution-extraction method based on compiling the planning graph into a CSP and using a CSP solver, and a fourth discussed a plan-adaptation system that uses planning graphs for adjusting existing plans to solve new problems. Although the previous four papers developed techniques for searching through a planning graph for a solution, the next three papers were devoted to altering the planning graph’s structure. One paper focused on the usefulness of MUTEX constraints when extracting a solution from a GRAPHPLAN graph using a SAT solver, and another described a domain-analysis system to infer persistent MUTEX constraints not currently found by GRAPHPLAN. The third paper involved altering the planning graph’s structure by relaxing the independence requirement between actions at a level.
Other papers on classical planning research focused on domain analysis, heuristic local search techniques, and alternative ways to encode a planning problem. For example, Long and Fox’s award-winning paper involved a domain-analysis system to infer promising domain-dependent heuristics. Another paper discussed building a domain-analysis system to infer (and remove) redundant operators from a planning problem, and a third was on an analysis system to find independent subproblems in large hierarchical task network (HTN) domains. To advance heuristic search, one paper presented a family of admissible heuristics for an IDA* search. Because many fast planners use inadmissible heuristics to sacrifice optimality for speed, another paper described a system that compares initial and optimal plans to learn rewrite rules for optimizing a plan by modifying pieces of it. Two final papers on techniques for speeding up the planning process involved alternative problem encoding. Although one paper combined HTN planning with a form of abstraction based on object-transition sequences, another described a system that solves planning problems encoded in linear time logic, facilitating a rich language for adding domain-dependent search control axioms to make problem more tractable.
Extending to Real-World Problems
Although classical planning research has advanced to ever-larger problems, planning in the real world requires more expressive models of activity and techniques to cope with incomplete knowledge and unexpected events. Seven papers focused on these issues: One paper described a sound and complete partial-order, contingent planner that uses sensory actions to solve problems in open worlds, and another developed adapting heuristic search to implement both conformant and contingent planners that solve incomplete information problems. A third paper also focused on contingent planning by developing a universal planning algorithm for nondeterministic domains, with multiple agents using techniques from symbolic model checking. The fourth paper discussed an alternative approach to coping with the real world by describing a heuristic iterative repair–based continual planner and testing it on an autonomous spacecraft control problem. The fifth paper also focused on iterative repair–based planning by describing a methodology for representing user preferences and continually optimizing a plan’s quality based on them. The sixth paper also focused on continually interleaved planning and execution by describing a technique for merging plans with temporal constraints, temporally extended actions, and conditional branches. Although the previous six papers assumed the existence of action models, the seventh paper used clustering and decision tree induction in a system that performs unsupervised learning of action models and demonstrated it on a PIONEER-1 mobile robot.
Uncertainty Probability
Another way to cope with the real world involves modeling unknowns using probability distributions and applying decision theory to maximize the utility of an agent’s expected behavior. Six papers focused on aspects of this approach. One paper presented a bucket-elimination algorithm that computes policies to maximize expected utility for an influence diagram, and another discussed work on the contingent-planning problem by developing a dynamic programming system that exploited a factored state representation of partially observable Markov decision problems. A third paper presented a policy representation for solving factored Markov decision problems (MDPs) using finite-state machine controllers. The fourth paper showed why decision theory problems remain intractable even with recent advances in classical planning by proving that transforming a structured MDP into a bounded-interval MDP is co-[NPP.sup.PP]-hard. Despite this theoretical result, a fifth paper discussed applying goal-directed Markov decision process models to decision-theoretic planning tasks for robot navigation, and the sixth paper focused on robotics by describing probabilistic models for predicting a concurrent precept-driven robot’s behavior.
Scheduling
In addition to the papers on planners with scheduling components, five papers were devoted explicitly to scheduling. The first paper reported on solving general job-shop scheduling problems with setup times and alternative resources using a two-phase heuristic algorithm that first optimizes the load balance across job-shop machines and then applies local improvements to minimize the sum of setup times. The second focused on the inventory management problem and described texture measurements to distill structural information from a constraint graph to drive heuristic methods for constraint-directed scheduling. The third paper also described a technique for exploiting structural information to rapidly determine legal times for inserting a cluster of activities into a schedule. Although the previous three papers focused on offline schedulers, the fourth paper was on building an online scheduling policy with heuristics based on an optimal offline scheduler, and the fifth described a system that incrementally executed a temporally constrained set of actions that use renewable resources.
Application Systems
On a more applied theme, six papers were devoted to applying planning techniques within industry as well as out of this world. The award-winning application paper explained the planner-scheduler used on the DS1 remote-agent experiment, and another paper described the testing methods for validating this planner before flying it on DS1. A third application paper reported on a mixed-initiative planning system that they implemented for managing day-to-day allocation and management of airlift and tanker resources at the United States Air Force Air Mobility Command. The fourth paper showed how to encode an advanced elevator control problem in PDDL and subsequently provided the domain to the planning competition, and the fifth was on applying MDP research to develop some global strategies for multimarket commodity trading. The sixth paper discussed a planning-based technique for generating test cases for graphic user interface software.
Presented Papers from KR2000
In addition to being colocated with KR2000, the first day of AIPS2000 included a shared session where several papers were presented to both the planning-scheduling and knowledge representation communities. In this session, five papers from KR2000 were presented. Two of these papers focused on SAT-based planning. One paper described a SAT-based conformant planner for domains with incomplete information and nondeterminism, and the second analyzed SAT-based planners to identify a common subsearch computation and develop a representational modification to exponentially accelerate this costly computation step. Instead of using SAT, the third paper focused on improving forward state-space planning and described a system that used concept languages to learn domain-dependent search control knowledge from small example problem solutions. In addition to focusing on planning, the fourth paper described a formalism to integrate reasoning about desires with planning. The fifth paper also focused on the larger picture by presenting a logical framework for planning with sensing, concurrency, and exogenous events; this framework was tested within the AZZURRA robot team from the RoboCup99 F-2000 competition.
Competition
In addition to presentations, AIPS2000 featured a planning competition designed to evaluate the current state of the art in planning-scheduling. The competition involved solving problems encoded in the PDDL description language and had two tracks: (1) fully automated planners and (2) hand-tailored planning systems. In the automated track, there were 12 competing planners; each planner solved sets of problems from several domains. In the hand-tailored track, developers were each given a fixed amount of time to look at a domain and configure their systems to automatically solve problems in the domain; four different teams competed in this track. The systems exhibited impressive performances by generating plans with hundreds of steps in less than a second; the winners were FF by Joerg Hoffman of Albert Ludwigs University in the automated track and TALPLANNER by Patrick Doherty, Jonas Kvarnstrom, and Patrik Haslum of Linkoping University in the hand-tailored track. A more complete description of this competition will appear in a future issue of AI Magazine.
Panel
On the final day of the conference, there was a panel entitled “Future Directions for Planning and Scheduling Research.” The panelists included Steve Chien of the Jet Propulsion Laboratory (JPL), California Institute of Technology; Jana Koehler of Schindler Lifts; David Wilkins of SRI International; Jimi Crawford of I2 Technologies; and Doug Dyer of the Defense Advanced Research Projects Agency. The panelists discussed open research areas from their various areas of expertise and opportunities for future research. Dyer described opportunities for spreadsheet-like decision-support aids using planning and scheduling technology. Crawford described numerous opportunities in supply-chain management and optimization, especially when enabled by electronic commerce and electronic exchanges. Wilkins described a number of practical problems, including user interaction, reasoning about continuous quantities, and complex goals (such as accumulation goals) from SRI problem domains. Koehler described a formulation of elevator control as a planning problem (involving optimization, resources, and other complexities). Chien described difficulties experienced in JPL deployment of planning systems, such as knowledge acquisition, validation, and knowledge base maintenance as well as ongoing opportunities in adaptive, learning planning systems and multiagent planning for rover swarms and spacecraft constellations. As this summary indicates, although there have been numerous successes with planning and scheduling technology, an exciting and diverse range of challenges still remain.
Conclusion
The range and depth of the papers presented at AIPS2000 illustrate that there is a strong international research and development community in AI planning and scheduling. The techniques and systems described in these papers are solving problems with ever-increasing complexity, and some are being embedded in practical applications. However, a diverse range of challenges still remain. Although the classical planners rapidly generate plans with hundreds of steps, they also make several simplifying assumptions (such as atomic actions and propositional state representations) that inhibit their applicability to real-world problems. Although several systems have found real-world application, their acceptance is slowed by problems in validating their correctness. In closing, many impressive results appeared at AIPS2000, and we look forward to continued progress.
Acknowledgments
As a testimony to the growing importance of planning and scheduling technology, several organizations provided financial and material support. These supporting organizations were the Defense Advanced Research Projects Agency, the National Aeronautics and Space Administration (NASA) Jet Propulsion Laboratory, Arizona State University, the University of Southern California Information Sciences Institute, 12 Corporation, Blue Pumpkin Software, IBM, the NASA Ames Research Center, Franz Inc., Schindler Lifts, SA, Lucent Technologies, and Celcorp. AIPS2000 was held in cooperation with the American Association for Artificial Intelligence.
Note
(1.) Further information on this and future AIPS conferences is available at www.isi. edu/aips/.
References
Blum, A., and Furst, M. 1995. Fast Planning through Planing Graph Analysis. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Menlo Park, Calif.: International Joint Conferences on Artificial Intelligence.
Chien, S.; Kambhampati, S.; and Knoblock, C., editors. 2000. Proceedings of the Fifth International Conference on Artificial Intelligence Planning and Scheduling. Menlo Park, Calif.: American Association for Artificial Intelligence.
Kautz, H., and Selman, B. 1992. Planning as Satisfiability. Paper presented at the Tenth European Conference on Artificial Intelligence, 3-7 August, Vienna, Austria.
Smith, D.; Frank, J.; and Jonsson, A. 2000. Bridging the Gap between Planning and Scheduling. Knowledge Engineering Review 15(1): 61-94.
Anthony Barrett is a member of the Artificial Intelligence Group at the Jet Propulsion Laboratory, California Institute of Technology, where his research and development activities involve planning and scheduling applied to controlling constellations of spacecraft. He holds a B.S. in computer science and applied mathematics from James Madison University and both an M.S. and a Ph.D. in computer science from the University of Washington. His research interests are in the areas of planning, scheduling, and multiagent systems. His e-mail address is anthony.barrett@ jpl.nasa.gov.
Steve Chien is technical group supervisor of the Artificial Intelligence Group at the Jet Propulsion Laboratory (JPL), California Institute of Technology, and autonomy technical community lead at JPL. He is also an adjunct associate professor in the Department of Computer Science at the University of Southern California. He holds a B.S., an M.S., and a Ph.D. in computer science from the University of Illinois. His research interests are in the areas of planning and scheduling, operations research, and machine learning.
COPYRIGHT 2000 American Association for Artificial Intelligence
COPYRIGHT 2001 Gale Group