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.//