Scalable Multi-Objective Planning for Metric Temporal Domains: Heuristics, Algorithms and Tradeoffs

Arizona State University, Scottsdale AZ

Investigators

Abstract

This project will develop effective algorithms for metric temporal domains. In many real world domains, planning involves handling actions with durations that produce and consume discrete as well as continuous resources, and goals with deadlines. The plans themselves may differ in multiple quality dimensions, including completion time, cost and execution flexibility. Previous approaches for synthesizing plans in such "metric temporal" domains have been plagued by poor scale-up potential, which inhibited the adaptation of the automated planning technology to such domains. In metric temporal domains, goals have deadlines, actions have temporal durations, and their preconditions and effects occur over arbitrary intervals during action durations, and actions can produce as well as consume discrete or continuous resources. Planning in many real-world situations, including logistics, supply chain as well as space autonomy, has these characteristics. Despite its potential applicability, adaptation of planning technology in these domains has been inhibited by the poor performance of the previous metric temporal planners. The overall aim of this proposed research is to build on the advances in our understanding of the classical plan synthesis to develop scalable approaches to metric temporal planning domains. The contributions of the project will include: (1) development of domain-independent heuristics based on planning graphs that are sensitive to multiple quality metrics of metric temporal plans (2) a suite of techniques based on constraint satisfaction problem encodings for improving the temporal quality of a given plan and (3) development of two planning algorithms with complementary tradeoffs, one searching in the space of position constrained plans, and the other searching in the space of order (precedence) constrained plans, and (4) a comprehensive investigation of the tradeoffs offered by position constrained and order constrained planners. The contributions of this research will be evaluated using the benchmark domains being developed in the planning community. The results of this work will improve the suitability of computerized planning systems for a number of practical application areas. They will also be incorporated into a textbook on foundations of automated planning and scheduling and into an undergraduate level course on automated planning and scheduling.