Research On Constraint Satisfaction And Its Distributed Solving & Application

Constraint satisfaction can describe the combinatorial solving problems suitably and be widely applied in Artificial Intelligence and other areas in computer science. It is one of the most successful problem solving paradigms in Artificial Intelligence. With the rapid development of the computer networks and the distributed computing environment in many areas, a lot of real world combinatorial solving problems have a new characteristic-being distributed. In this trend, the traditional centralized constraint satisfaction algorithms can not cope with the solving of the distributed combinatorial problems; especially, it can not be applied in the multi-agent systems that need negotiatory solving between autonomous agents. Along with the in-depth research of multi-agent systems, distributed constraint satisfaction problem has been proposed formally, and then the theory issues about modeling, solving algorithms, privacy protection and solving efficiency of distributed constraint satisfaction problem have been concerned more and more.Based on the constraint satisfaction solving protocols, we propose a fast method of schema change detection for semi-structured data in network environment. In addition, we make in-depth studies and analyses on the distributed constraint satisfaction problem and its solving algorithms. For the privacy security which is the new requirement in the applications, we present a high efficiency and real distributed solving algorithm of secure distributed constraint satisfaction problem. Finally, based on the algorithm, we make a beneficial study on the solving of the secure multi-agent negotiation in virtual enterprise. The main contributions are:1. Propose a fast method of schema change detection for semi-structured data based on the solving strategy of constraint satisfaction problem.On the basis of the solving strategy of constraint satisfaction problem, for efficiently detecting the schema change of XML documents, we present a fast method of schema change detection for semi-structured data. Firstly, XML document is represented as a directional labeled unordered tree, the schema is a frequent sub-tree extracted from the tree which represents XML document. Then, we present an efficient method of transforming the problem of the schema change detection of XML data into constraint satisfaction problem and a fast CSP algorithm for the schema change detection of XML data. The method overcomes the restriction of other methods that the change detection should be done on the basis of ordered trees. 2. Propose an encrypted solving method for secure distributed constraint satisfaction problem based on weights.For the privacy security of distributed constraint satisfaction problem, we emphasize on solving efficiency to propose an encrypted solving method for secure distributed constraint satisfaction problem based on weights. The algorithm analyses the security of different constraint relationship in agent or between agents, and uses different approach to get higher efficiency in encrypted solving process. Because of the characteristics about computing and interaction of agents, the algorithm does not need to introduce the additional controller into the solving process. The real distributed security protocol is realized and the protocol further reduces the possibility of the information leakage. With ensuring privacy security, we can introduce the better heuristic search strategy for solving.3. Present a negotiatory partner selection model of multi-agent virtual enterprise based on the solving method of secure distributed constraint satisfaction problem.For privacy security of enterprise candidates in multi-agent virtual enterprise, we present a negotiatory partner selection model of multi-agent virtual enterprise, which uses the solving method of secure distributed constraint satisfaction problem. In this model, the market demands or services are formalized as agents, and the relationship between demands or services is formalized as constraints in agent or among agents. Agents achieve secure negotiation according to the solving method of secure distributed constraint satisfaction problem, and then complete the partner selection which meets the secure demand.The applications of distributed problem solving depend on efficient solving of the efficiency, privacy security and other key issues of distributed constraint satisfaction problem. Thus, the study of these issues is of important theoretical significance and great application value. The emphasis of our further research will be on proposing a better algorithm to adapt to the distribution so as to reduce communication costs and requirements, and balancing the tradeoff between privacy loss and efficiency, etc. The theoretical research of these issues will present the solid theoretical foundation for the practical applications.