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

本项目将开发有效的度量时域算法。在许多现实世界的领域中，计划涉及到处理具有产生和消耗离散和连续资源的持续时间的行动，以及具有截止日期的目标。计划本身可能在多个质量维度上有所不同，包括完成时间、成本和执行灵活性。以前在这种“度量时间”领域中综合规划的方法一直受到规模扩大潜力差的困扰，这抑制了自动化规划技术对这些领域的适应。在度量时间域中，目标有最后期限，操作有时间持续时间，它们的前提条件和效果在操作持续时间内任意间隔发生，并且操作可以产生和消耗离散或连续的资源。许多现实情况下的规划，包括物流、供应链和空间自治，都具有这些特征。尽管规划技术具有潜在的适用性，但由于以前度量时态规划器的性能不佳，规划技术在这些领域的适应性受到了抑制。本研究的总体目标是建立在我们对经典规划综合的理解的基础上，开发可扩展的方法来度量时间规划领域。该项目的贡献将包括：(1)基于对度量时态规划的多个质量指标敏感的规划图的领域独立启发式开发；(2)基于约束满足问题编码的一套技术，用于提高给定规划的时间质量；(3)开发了两种具有互补权衡的规划算法，一种在位置约束规划空间中搜索，另一种在顺序（优先）约束规划空间中搜索。(4)对位置约束和顺序约束规划者的权衡进行了综合研究。这项研究的贡献将使用规划界正在开发的基准领域进行评估。这项工作的结果将提高计算机化规划系统在若干实际应用领域的适用性。它们还将被纳入自动化计划和调度基础的教科书以及自动化计划和调度的本科课程。

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.