Constraint Solving and Matching: Parallel Algorithms and Applications

寻求一种灵活高效的知识表示机制是人工智能的关键研究问题之一。在许多智能系统中，复杂对象描述与大量预定义对象的瞬时匹配是一个关键的计算原语。基于记忆的推理的这种功能体现在不同的活动中，如计算机视觉中的模式识别任务、语言理解或一般问题解决。同时满足许多可能冲突的约束是智能系统中另一个非常重要的功能需求，它对于学习、规划和一般问题的解决是至关重要的。人们普遍认为，人类通过利用大脑中的大规模并行性有效地(即，在几乎不变的时间内)完成这类任务。这项研究的目的是得到并行在约束求解和匹配等基本人工智能问题中的效用的精确表征。这项研究的最终目标是为并行智能系统产生一个计算框架。具体的研究目标是为约束网络设计高效的并行算法，开发集成多个约束求解活动的方法，以及将广义匹配和约束求解应用于反应性规划、资源分配和科学数据分析。

The quest for a flexible and efficient knowledge representation mechanism is one of the key research problems in Artificial Intelligence (AI). Instantaneous matching of a complex object description to a large set of predefined objects is a key computational primitive in many intelligent systems. This function of memory based reasoning manifests itself in different activities such as pattern recognition tasks in computer vision, language understanding or general problem solving. Simultaneous satisfaction of many possibly conflicting constraints is another very important functional requirement in intelligent systems, which is critical for learning, planning and general problem solving. It is generally believed that humans perform such tasks efficiently (i.e., in almost constant time) by exploiting massive parallelism in the brain. This research is aimed at deriving a precise characterization of the utility of parallelism in fundamental AI problems such as constraint solving and matching. The ultimate goal of the research is to produce a computational framework for parallel intelligent systems. Specific research objectives are design of efficient parallel algorithms for constraint networks, development of methods to integrate multiple constraint solving activities, and applications of generalized matching and constraint solving to reactive planning, resource allocation and analysis of scientific data.//