Active Structures Support Problem-driven Learning for Constraint Satisfaction

提案0739122“主动结构支持问题驱动的约束满足学习”，PI: Susan L. epstein，美国纽约大学亨特学院[j] .摘要许多重要的大规模、现实世界的问题可以很容易地表示、解决和理解为约束满足问题（csp）。然而，不同类型的csp对不同的解决方法组合有不同的响应。因此，在约束满足问题解决中存在一个持续的瓶颈：需要具有难以提取的领域知识和关于CSP方法的专业知识的人类专家来选择、组合和调整可用的技术，以适合手头问题的CSP求解器。此外，这样的求解器通常不会被重用来解决类似的问题或将看似无法解决的问题重新表述为可解决的问题。长期目标是了解如何构建先进的CSP工具，将“基于类的学习”（针对类似问题的类定制解决方法）和“问题驱动的学习”（针对单个问题定制解决方法）结合起来。问题驱动学习包括检测“活动”结构，即在搜索和约束满足问题解决过程中检测到的信息量最大且经常充满冲突的子问题，特别是在困难或独一无二的问题中，并使用这些结构生成一类类似的问题，从中可以学习该类的方法和启发式，然后将其应用于手头的问题。这个项目的具体重点是在问题驱动的学习中发现和利用主动结构。该项目涉及PI、爱尔兰科克约束计算中心和一位视觉表示专家之间的合作。该项目的结果将在一个公众可访问的网站上公布。由此产生的活性结构知识库将有助于支持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.