Integrating Planning and Search Methods to Solve Constraint Problems

集成规划和搜索方法来解决约束问题

• 批准号: 0328743
• 负责人: Susan Epstein
• 金额: $ 36.85万
• 依托单位: CUNY Hunter College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-09-01 至 2007-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0328743&HistoricalAwards=false
• 关键词: Integrating; Planning; Search; Methods; Solve

This project speeds the uptake of an important technology: constraint satisfaction programming. Many large-scale, real-world problems in areas such as design and configuration, planning and scheduling, and diagnosis and testing are readily understood, represented, and solved as constraint satisfaction problems. Despite a wealth of good, general-purpose methods, each new, large-scale constraint satisfaction problem faces the same bottleneck: scarce human experts must select, combine, and refine the various techniques currently available. This project increases the ability of both people and machines to address new constraint satisfaction problems.The project develops a system that is both an experimental tool for researchers and a problem solver for real problems. It learns and plans to solve particular classes of constraint satisfaction problems. It combines and adapts a broad range of known constraint methods, and explores new ones, to reason about solving hard problems. Learning supports adaptive solvers that tailor themselves to a problem class. Planning supports stronger solvers, and embodies higher-level insights into the solution process.This project addresses, both in its design and its implementation, important questions in the discovery and application of knowledge to problem solving. Expected outcomes include a database of interactions and plans, a development environment that facilitates the integration and evaluation of new methods and plans, and a tool for learning new methods and developing new plans. Broader impacts include improved scheduling algorithms, upgrades to the computation infrastructure for constraint programming worldwide, and the training of students in a predominantly female and minority institution.

这个项目加速了一项重要技术的应用：约束满足编程。在设计和配置、计划和调度、诊断和测试等领域中，许多大规模的、现实世界的问题很容易被理解、表示和解决为约束满足问题。尽管有很多好的、通用的方法，但每个新的、大规模的约束满足问题都面临着同样的瓶颈：稀缺的人类专家必须选择、组合和改进当前可用的各种技术。这个项目增加了人和机器处理新的约束满足问题的能力。该项目开发的系统既是研究人员的实验工具，也是解决实际问题的工具。它学习并计划解决特定类别的约束满足问题。它结合并适应了广泛的已知约束方法，并探索了新的约束方法，以解决难题。学习支持自适应解决方案，使自己适应问题类别。计划支持更强的解决者，并包含对解决方案过程的更高层次的洞察。这个项目在设计和实施中都涉及到发现和应用知识来解决问题的重要问题。预期的结果包括交互和计划的数据库，促进新方法和计划的集成和评估的开发环境，以及用于学习新方法和开发新计划的工具。更广泛的影响包括改进调度算法，升级全球约束规划的计算基础设施，以及在以女性和少数民族为主的机构中培训学生。