This domain models the operation of the multi-engine printer, for which one prototype is developed at the Palo Alto Research Center (PARC). This type of printer can handle multiple print jobs simultaneously. Multiple sheets, belonging to the same job or different jobs, can be printed simultaneously using multiple Image Marking Engines (IME). Each IME can either be color, which can print both color and black&white images, or mono, which can only print black&white image. Each sheet needs to go through multiple printer components such as feeder, transporter, IME, inverter, finisher and need to arrive at the finisher in order. Thus, sheet (n+1) needs to be stacked in the same finisher with sheet n of the same job, but needs to arrive at the finisher right after sheet n (no other sheet stacked in between those two consecutive sheets). Given that the IMEs are heterogeneous (mixture of color and mono) and can run at different speeds, optimizing the operation of this printer for a mixture of print jobs, each of them is an arbitrary mixture of color/b&w pages that are either simplex (one-sided print) or duplex (two-sided print) is a hard problem. The picture below shows the fully-operational prototype at PARC with 4 mono IMEs. For the detail description of this domain and the continual online planner controlling it, please refer to the references listed at the end of this page.
We decided to use this domain in two tracks: sequential and temporal. The temporal track is the most natural fit due to the default objective function for the printer of maximizing its productivity, which equals to finish printing all print job requests as quickly as possible. For the sequential track, we use a more seldom used objective function of minimizing printing cost. For example, using a more expensive color IME to print a black&white page costs more than using a mono IME. However, the cost tradeoff may not be clearcut if the feeder, where the blank sheets originally reside at is closer to the mono IME than to the color IME.
Even though the internal representation of the planner controlling these printers is not too far from the PDDL representation, the online continual nature of the domain and several constraints in this domain such as multiple resource usages by each action and sequential finishing order of sheets in the same job lead to the blowup in the domain/problem size when using pure PDDL. Therefore, we had to: 1) remove or approximate some certain constraints in the original domain; and 2) model less complex machines (compared to the one shown in the picture above)
Overall, we modelled three different printers, two with 2 IMEs (one color and one mono) and one with 4 IMEs (two colors and two monos). Two with rather symmetric design and a third one is asymmetric. We try to model the actions as close as possible to the hardware specifications. Even those the printers are hypothetical, the hardware that can be used to make those printers are real.
For the problem files, to reduce complexity, we only create print request of a single job with multiple sheets. The sheets are randomly set to be either simplex (one-sided print) or duplex (two-sided print) and each image is also randomly selected to be either mono or color. The number of sheets varies from 1 to 20. Given this print job request and a particular printer configuration, the competing planner needs to find a plan with lowest total printing cost in the sequential track (matching well between image requirement and IME capabilities) and smallest makespan in the temporal track (synchronize well different IMEs).
References:
On-line Planning and Scheduling for High-speed Manufacturing. Wheeler Ruml, Minh B. Do, & Markus Fromherz. In Proc. of the 15th International Conference on Automated Planning and Scheduling (ICAPS) 2005. (PDF)
Lessons Learned in Applying Domain-Independent Planning to High-Speed Manufacturing. Minh B. Do, & Wheeler Ruml. In Proc. of 16th International Conference on Automated Planning and Scheduling (ICAPS), 2006. (PDF)
On-line Planning and Scheduling: An Application to Controlling Modular Printers. Minh B. Do, Wheeler Ruml, and Rong Zhou. In the Proc. of 23rd AAAI Conference on Artificial Intelligence (AAAI), NECTAR Track.(PDF)
Planning for Modular Printers: Beyond Productivity. Minh B. Do, Wheeler Ruml, and Rong Zhou. To appear in the 18th International Conference on Automated Planning and Scheduling (ICAPS), (PDF)