Planning with Complex Constraints and Preferences by Nonlinear Programming and Constraint Partitioning

提案0713109“基于非线性规划和约束划分的复杂约束和偏好规划”PI：陈宜欣华盛顿大学摘要本项目旨在开发有效的算法来解决制造，航空航天工程，应急计划和工作流调度等许多应用中的复杂规划问题。本研究的两个主要目标是提高规划模型的表达能力和降低计算成本。该项目的关键创新是为具有轨迹约束和偏好的复杂规划提供统一、高效和可扩展的框架。大多数现有的规划技术由于其公式和搜索方法的限制，难以支持更具表现力的模型。本项目将发展一种新的非线性规划模型。它将提供一种形式来适应复杂的特征，如轨迹约束和数值目标。为了降低搜索成本，该项目正在开发一种约束划分方法，将规划问题的约束分解为更简单的子问题。以前在SGPlan规划器中使用过，这种方法已被证明是有效的。然而，随着新的复杂特征的出现，原有的分区策略变得不够充分。该项目将开发新的非线性规划公式和划分方法，以利用复杂规划问题的结构。约束划分可以实现数量级的加速，极大地缓解了搜索空间的指数爆炸。这项研究有几个更广泛的影响。有许多潜在的应用，从生产管理到航空航天工程。该项目将其成果应用于移动计算，以支持移动设备（如蜂窝电话和pda）的快速发展。将公开开发的规划器，为不同学科的用户提供最先进的人工智能工具。

Proposal 0713109"Planning with Complex Constraints and Preferences by Nonlinear Programming and Constraint Partitioning"PI: Yixin ChenWashington UniversityABSTRACTThis project aims to develop efficient algorithms for solving complex planning problems that arise from many applications such as manufacturing, aerospace engineering, emergency planning, and workflow scheduling. Two main goals of this research are to improve the expressiveness of planning models and to reduce the computational costs. The key innovation of this project is a unified, efficient, and extendible framework for complex planning with trajectory constraints and preferences.Most existing planning techniques have difficulty in supporting more expressive models due to limitations in their formulations and search methods. This project will develop a new nonlinear programming model for planning. It will provide a formalism to accomodate complex features such as trajectory constraints and numerical objectives. To reduce the search cost, this project is developing a constraint partitioning approach that decomposes the constraints of a planning problem into much simpler subproblems. Previously used in the SGPlan planner, this approach has been proved effective. However, with the new complex features, the original partitioning strategies become inadequate. The project will develop new non-linear planning formulations and partitioning methods in order to exploit the structure of complex planning problems. Constraint partitioning may achieve orders of magnitudes speedup and greatly alleviate the exponential explosion of the search space.This research has several broader impacts. There are many potential applications, ranging from production management to aerospace engineering. This project will apply its results to mobile computing to support the rapid development of mobile devices such as cellular phones and PDAs. The planners to be developed will be made publicly available to provide state-of-the-art AI tools for users from various disciplines.