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

通过非线性规划和约束划分来规划复杂的约束和首选项

• 批准号: 0713109
• 负责人: Yixin Chen
• 金额: $ 38.91万
• 依托单位: Washington University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0713109&HistoricalAwards=false
• 关键词: Planning; Complex; Constraints; Preferences; Nonlinear

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.

提案0713109“利用非线性规划和约束划分进行复杂约束和偏好的规划“项目负责人：陈益新华盛顿大学摘要该项目旨在开发有效的算法，用于解决许多应用中出现的复杂规划问题，如制造业、航空航天工程、应急规划和工作流调度。本研究的两个主要目标是提高规划模型的表达能力和降低计算成本。该项目的主要创新之处在于为具有轨迹约束和偏好的复杂规划提供了一个统一、高效和可扩展的框架，而现有的规划技术由于其公式和搜索方法的限制，很难支持更具表达力的模型。本计画将发展一种新的非线性规划模式。它将提供一个形式主义，以适应复杂的功能，如轨迹约束和数值目标。为了减少搜索成本，这个项目正在开发一种约束划分方法，将规划问题的约束分解为更简单的子问题。该方法在SGPlan规划器中得到了应用，并取得了较好的效果。然而，随着新的复杂功能，原来的分区策略变得不够。该项目将开发新的非线性规划公式和划分方法，以利用复杂规划问题的结构。约束划分可以实现数量级的加速，并大大缓解搜索空间的指数爆炸。它有许多潜在的应用，从生产管理到航空航天工程。该项目将把其成果应用于移动的计算，以支持蜂窝电话和PDA等移动的设备的快速发展。即将开发的规划器将公开提供，为来自不同学科的用户提供最先进的人工智能工具。