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

Abstract

This paper summarizes recent work reported at ICAPS on applying artificial intelligence techniques to the control of production printing equipment. Like many other real-world applications, such as mobile robotics, this complex domain requires real-time autonomous decision-making and robust continual operation. To our knowledge, this work represents the first successful industrial application of embedded domain-independent temporal planning. At the heart of our system is an on-line algorithm that combines techniques from state-space planning and partial-order scheduling. For example, our planning-graph-based planning heuristic takes resource contention into account when estimating makespan remaining. We suggest that this general architecture may prove useful as more intelligent systems operate in continual, online settings. Our system has enabled a new product architecture for our industrial partner and has been used to drive several commercial prototypes. When compared with stateof-the-art off-line planners, our system is hundreds of times faster and often finds better plans.