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

本计画将针对度量时间域发展有效的演算法。 在许多真实的领域中，计划涉及处理具有持续时间的行动，这些行动产生和消耗离散的以及连续的资源，以及具有截止日期的目标。这些计划本身可能在多个质量方面有所不同，包括完成时间、成本和执行灵活性。以前的方法合成计划在这样的“度量时间”域一直困扰着穷人的规模扩大的潜力，这抑制了适应自动规划技术，这样的域。 在度量时域中，目标有截止期限，动作有持续时间，它们的前提条件和效果在动作持续时间内的任意时间间隔内发生，动作可以产生和消耗离散或连续的资源。在许多现实世界的情况下，包括物流，供应链以及空间自主规划，具有这些特点。 尽管其潜在的适用性，适应规划技术在这些领域已被抑制的性能不佳，以前的度量时间planners.The总体目标提出的研究是建立在我们的理解的经典计划合成的进步，发展可扩展的方法度量时间规划域。 该项目的贡献将包括：（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.