ITR: Efficient Algorithms for Temporal Planning Under Nonlinear Constraints

ITR：非线性约束下时间规划的高效算法

• 批准号: 0312084
• 负责人: Benjamin Wah
• 金额: $ 37.5万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-07-15 至 2007-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0312084&HistoricalAwards=false
• 关键词: ITR; Efficient; Algorithms; Temporal; Planning

This research will develop formal mathematical conditions for reducing the search space of planning problems, and will demonstrate performance improvements in search engines of planners and other discrete searches. Based on the observation that temporal planning problems can be arranged into stages by time, they can be formulated as dynamic optimization problems with dynamic variables that evolve over time. Due to the presence of general constraints that span across multiple stages, path dominance in dynamic programming cannot be applied to reduce the search complexity. This research will seek new node-dominance conditions in each stage by developing the necessary or necessary-and-sufficient conditions for local optimality and by partitioning the conditions into distributed necessary conditions, based on local constraints in each stage and constraints between adjacent stages. By partitioning the search into stages and by finding only dominating states in each stage using the necessary conditions, the search for feasible or optimal plans can be restricted to a much smaller subspace in each stage, leading to a smaller number of combinations of possible paths that need to be searched across multiple stages.Three research tasks will be completed in this work. Based on the discrete-space variational search implementing the stopping conditions, research will develop a new planning system that fully supports PDDL2.1 language features, using the constraint-based-interval representation. Temporal flexible scheduling will be extended by formulating a temporal constraint network with flexible time points into a constrained nonlinear optimization problem and by partitioning the search space. Research will study algorithms for partitioning satisfiability (SAT), mixed-integer optimization, and planning problems.The research is on a new approach that reduces the computational complexity by exploiting the locality of constraints in multi-stage optimization problems. By developing node dominance conditions that identify dominating nodes in each stage, it will lead to reduced search space in each stage and a significant reduction in base of the exponential number of possible paths to be searched across multiple stages. Although a similar approach has been studied in calculus of variations in continuous space, the extension to discrete problems requires the development of a completely new foundation in the theory of Lagrange multipliers in discrete space. The approach developed is general and can be used as stopping conditions in existing planners or integrated into new search algorithms. It can also benefit the solution of other discrete optimization problems, including SAT and mixed-integer optimization.In addition to training graduate and undergraduate students in their research, the project develops a fundamental approach that will be incorporated into courses on optimization. The results will also carry significant impact on autonomous vehicle planning and will be applied to planners currently developed at the National Aeronautics and Space Administration and Jet Propulsion Laboratory. Improved planners will allow higher dependability of space missions that will benefit society at large.

这项研究将开发正式的数学条件，减少规划问题的搜索空间，并将展示规划和其他离散搜索搜索引擎的性能改进。基于时间规划问题可以按时间划分为多个阶段的观察，它们可以被表述为具有随时间演化的动态变量的动态优化问题。由于存在跨越多个阶段的一般约束，动态规划中的路径优势不能用于降低搜索复杂度。本研究将寻求新的节点优势的条件，在每个阶段，通过开发必要或必要和充分的条件，局部最优性，并通过划分的条件到分布式的必要条件，在每个阶段的局部约束条件和相邻阶段之间的约束。通过将搜索划分为多个阶段，并利用必要条件在每个阶段中只找到主导状态，可以将可行或最优方案的搜索限制在每个阶段中的一个更小的子空间内，从而减少了需要在多个阶段中搜索的可能路径组合的数量。基于离散空间变分搜索实现停止条件，研究将开发一个新的规划系统，完全支持PDDL2.1语言功能，使用基于约束的区间表示。通过将具有灵活时间点的时间约束网络转化为约束非线性优化问题，并通过划分搜索空间，扩展了时间柔性调度。本研究将研究分割可满足性（SAT）、混合整数优化和规划问题的算法，研究利用多阶段优化问题中约束的局部性来降低计算复杂度的新方法。通过开发识别每个阶段中的支配节点的节点支配条件，这将导致每个阶段中的搜索空间减小，并且跨多个阶段搜索的可能路径的指数数量的基数显著减小。虽然一个类似的方法已经研究了连续空间的变分法，但扩展到离散问题需要在离散空间的拉格朗日乘子理论中建立一个全新的基础。开发的方法是通用的，可以用来作为停止条件，在现有的规划或集成到新的搜索算法。它也可以有利于其他离散优化问题的解决方案，包括SAT和混合整数优化。除了培养研究生和本科生在他们的研究，该项目开发了一个基本的方法，将被纳入优化课程。研究结果还将对自动驾驶汽车规划产生重大影响，并将应用于美国国家航空航天局和喷气推进实验室目前开发的规划器。改进的规划者将使空间任务具有更高的可靠性，这将使整个社会受益。