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

点击翻译按钮获取中文摘要

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.