Active Structures Support Problem-driven Learning for Constraint Satisfaction

提案0739122“主动结构支持约束满足的问题驱动学习“PI：Susan L。许多重要的大规模的，现实世界中的问题可以很容易地表示，解决和理解为约束满足问题（CSP）。然而，不同类型的CSP响应于不同的解决方案组合。因此，在约束满足问题的解决中存在一个持续的瓶颈：需要一个拥有难以提取的领域知识和CSP方法的专家知识的人类专家来选择、联合收割机并将可用的技术调整到适合手头问题的CSP求解器中。此外，这样的求解器通常不会被重新用于解决类似的问题，或者将看似不可解决的问题重新表达为可解决的问题。长期目标是了解如何构建高级CSP工具，该工具结合了联合收割机“基于类的学习”和“问题驱动学习”，“基于类的学习”为类似问题的类定制解决方法，“问题驱动学习”为单个问题定制解决方法。问题驱动学习涉及检测“主动”结构，即在搜索和约束满足问题解决过程中检测到的信息量最大且经常冲突不断的子问题，特别是在困难或独一无二的问题中，以及使用这些结构来生成一类类似问题，从中可以学习该类的方法和算法，然后将其应用于手头的问题。该项目的具体重点是在问题驱动学习中检测和利用主动结构。该项目涉及PI，爱尔兰的Cork约束计算中心和视觉表示专家之间的合作。该项目的结果将在一个可公开访问的网站上公布。由此产生的主动结构的知识库将有助于支持CSP的其他研究项目。

Proposal 0739122"Active Structures Support Problem-driven Learning for Constraint Satisfaction"PI: Susan L. EpsteinCUNY Hunter CollegeABSTRACTMany important large-scale, real-world problems can be readily represented, solved and understood as constraint satisfaction problems (CSPs). However, different kinds of CSPs respond to different combinations of solution methods. As a result, there is a persistent bottleneck in constraint satisfaction problem solving: the need for a human expert armed with hard-to-extract domain knowledge and with expert knowledge about CSP methods to select, combine, and tune available techniques into an appropriate CSP solver for the problem at hand. Furthermore, such solvers are typically not re-used to solve similar problems or to reformulate seemingly unsolvable problem into solvable ones.The long-range goal is to understand how to build advanced CSP tools that combine "class-based learning" that tailors solution methods to classes of similar problems and "problem-driven learning" that tailors solution methods to an individual problem. Problem-driven learning involves detection of "active" structures, that is, the most informative and often conflict-ridden sub-problems detected during search and constraint-satisfaction problem solving, particularly in difficult or one-of-a-kind problems, and the use of these structures to generate a class of similar problems from which methods and heuristics for the class can be learned and then applied back to the problem at hand. The specific focus of this project is the detection and harnessing of active structures in problem-driven learning.The project involves collaboration among the PI, the Cork Constraint Computation Center in Ireland, and an expert on visual representation. Results of the project will be made available on a publicly accessible website. The resulting knowledgebase of active structures will help support other research projects on CSP.