基于约束满足问题的配置解释算法研究
摘要
配置问题是人工智能研究的热点,配置解释是配置研究问题的重要内容。本文首先描述了解释的研究现状,然后通过分析约束满足问题与配置之间的对应关系,结合配置中遇到的问题引入解释的形式化描述,并着重描述了两大主流的求解解释的方法:TMS(侵入式)方法和近些年来研究的非侵入式的Junker的QuickXplain方法。重点分析了Junker的QuickXplain方法。本文通过分析交互配置的特点,然后在分析原有配置的求解解释的方法存在的问题的基础上,给出一种基于用户决策时约束满足问题表示配置的形式化描述,在此框架下,给出一种求解解释的算法,并与其他求解方法作比较,然后对新的算法进行设计实现,采用Junker中的案例对其进行了测试。与原配置器中算法相比在处理线性约束方面有其独特的优势。最后我们结合原有配置器中的相关资源给出算法在配置器中的应用分析,并改进了相应的配置求解算法。
In recent years, the configuration problems is a hot issue in study ,is an important branch of the research in the field of artificial intelligence. By the concern of many researchers .With the development of society, more and more problems were representation as configuration problems .People on the solve of configuration for the demand put forward higher, require- ments .Configuration tasks are completed mainly divided into two areas, On the one hand is the issue of how to describe configuration tasks ,We call it the know- ledge representation, On the other hand what is described in this field of knowledge to solve problems .We call configuration solution. At present ,there are many method of knowledge representation for the respect of knowledge representation .More popular method of represent the area of configuration knowledge with logic and CSP(Constraint Satisfaction Problems).
Constraint Satisfaction Problems is an important and fundament problem .It is a method to represent the configuration task. Manifested as a kind of mapping, Corresponding the relevant elements of Constraint Satisfaction Problems with the relevant elements of configuration. Configuration was represent as Dynamic Constraint Satisfaction problems with the interactive relationship between users and configuration .It clearly the elements of part of decision-making in configuration task Thus we transformation the configuration task into a Constraint Satisfaction Problem .How to proceed from a collection of variables ,and seek to meet various constraints relations between the variable values is the fundamental problem of Constraint Satisfaction Problems .There are many research results for Constraint Satisfaction problem .and some good research results can be applied on the Constraint Satisfaction Problem in the area of configuration.
This paper mainly on the research the method for the explain of the configuration problems .this is on the basis of the representation of configuration with Constraint Satisfaction Problem .with the idea to find a better method to answer to the problem in configuration task and good guide users to configure .In order to a better research .first this paper describes the concepts of configuration and Constraint Satisfaction Problem .Also we describes the relationship between the mapping of them .On the basis of this paper mainly research and analysis the algorithms for explain on the frameworks of this .At present ,algorithm of explain mainly divided into two types. Intrusive(have the ability to judge and record explanations in constraint propagation)and non-intrusive(solving explanation independent of the constraint propagation process).The intrusive method increased the system complexity of solution space for record explanations in constraint propagation process .It will increase the storage configuration information for the burden .In support of multi-user configuration solver , It would need to store a large amount of information relating to explanation if too many users use solver .It is a thorny issue about how to sore the information .This paper describes TMS methods such as representatives of the algorithm .To address this issue the non-intrusive methods without recorded information in the constraint propagation is very important .This paper describes two typical of such approaches AOP and QuickXplain.The AOP use AOP method the expansion of OOP implementation separation between interpretation of the solution and constraint solving .This method has many limitations not apply in many configuration solving ,This paper with basis of QuickXplain In the interactive configuration the current decision-making impact the explain of configuration .Give a method of solving explanation based on the current constraint satisfaction problem .Over-constrained problems(the problem has not been a viable solution)expected the conflict is exponential. And also the corresponding explanation is exponential .How to look for a better explanation in such a large of explanations is a issue need to solve. A solution is: first allow users to determine the priority of parameters. In interactive configuration it is that users preferences there favorite parts .So we defines the parameters of the order with the priority order.
So if the current decision-making is conflict ,then the decision made recently by the user is a part of the conflict .At this point the problem is a over-constraint problem .For this problem the recently decision-making as a constraint in the constraints in the knowledge .We abstract the current issue into a conflict for the optimal based on the principle of QuickXplain.We get the optimal solution through the issue divided into two sub-problems with the same way .In the view of the current decision-making involved in the conflict may not be a constraint issues .This paper come through: the optimal number of constraints conflict sets each constraint is the solving set of the conflict and set. And with the other methods of solving algorithm that in configuration the solution has its advantages, in some areas. This paper give a simple example of the testing of experimental data shows that the algorithm running time (consistency of performance for the number of detections) and the number of conflicts and the number of parameters is closely linked to verify when given a control, Time is running the algorithm can be expected (in a certain range).In this case the algorithm is an effective method to solve.
This paper analyzes the explained method in the original configuration. The explained method in the original configuration is through consistency constraints set for conflict .This task provided with the original allocation algorithm integration possible .This paper give the map for the relationship between the various objects of our algorithm is involved with the function of the main targets of the relationship. Another explanation is part of the solution solve explanation is a tools explained the failure and guide users, It service the configuration. This paper analysis the solving thinking on the original configuration and the relationship between configuration solve and explanation .This paper also give a map of configuration solve .That is using java object-oriented method.
In short, based on the current decision-making constraint satisfaction problems configuration can direct and effective give users the explanation for the failure of the optimal. The algorithm can show good prospects in dealing with multiple constraints and consider users preferences.
In recent years, the configuration problems is a hot issue in study ,is an important branch of the research in the field of artificial intelligence. By the concern of many researchers .With the development of society, more and more problems were representation as configuration problems .People on the solve of configuration for the demand put forward higher, require- ments .Configuration tasks are completed mainly divided into two areas, On the one hand is the issue of how to describe configuration tasks ,We call it the know- ledge representation, On the other hand what is described in this field of knowledge to solve problems .We call configuration solution. At present ,there are many method of knowledge representation for the respect of knowledge representation .More popular method of represent the area of configuration knowledge with logic and CSP(Constraint Satisfaction Problems).
Constraint Satisfaction Problems is an important and fundament problem .It is a method to represent the configuration task. Manifested as a kind of mapping, Corresponding the relevant elements of Constraint Satisfaction Problems with the relevant elements of configuration. Configuration was represent as Dynamic Constraint Satisfaction problems with the interactive relationship between users and configuration .It clearly the elements of part of decision-making in configuration task Thus we transformation the configuration task into a Constraint Satisfaction Problem .How to proceed from a collection of variables ,and seek to meet various constraints relations between the variable values is the fundamental problem of Constraint Satisfaction Problems .There are many research results for Constraint Satisfaction problem .and some good research results can be applied on the Constraint Satisfaction Problem in the area of configuration.
This paper mainly on the research the method for the explain of the configuration problems .this is on the basis of the representation of configuration with Constraint Satisfaction Problem .with the idea to find a better method to answer to the problem in configuration task and good guide users to configure .In order to a better research .first this paper describes the concepts of configuration and Constraint Satisfaction Problem .Also we describes the relationship between the mapping of them .On the basis of this paper mainly research and analysis the algorithms for explain on the frameworks of this .At present ,algorithm of explain mainly divided into two types. Intrusive(have the ability to judge and record explanations in constraint propagation)and non-intrusive(solving explanation independent of the constraint propagation process).The intrusive method increased the system complexity of solution space for record explanations in constraint propagation process .It will increase the storage configuration information for the burden .In support of multi-user configuration solver , It would need to store a large amount of information relating to explanation if too many users use solver .It is a thorny issue about how to sore the information .This paper describes TMS methods such as representatives of the algorithm .To address this issue the non-intrusive methods without recorded information in the constraint propagation is very important .This paper describes two typical of such approaches AOP and QuickXplain.The AOP use AOP method the expansion of OOP implementation separation between interpretation of the solution and constraint solving .This method has many limitations not apply in many configuration solving ,This paper with basis of QuickXplain In the interactive configuration the current decision-making impact the explain of configuration .Give a method of solving explanation based on the current constraint satisfaction problem .Over-constrained problems(the problem has not been a viable solution)expected the conflict is exponential. And also the corresponding explanation is exponential .How to look for a better explanation in such a large of explanations is a issue need to solve. A solution is: first allow users to determine the priority of parameters. In interactive configuration it is that users preferences there favorite parts .So we defines the parameters of the order with the priority order.
So if the current decision-making is conflict ,then the decision made recently by the user is a part of the conflict .At this point the problem is a over-constraint problem .For this problem the recently decision-making as a constraint in the constraints in the knowledge .We abstract the current issue into a conflict for the optimal based on the principle of QuickXplain.We get the optimal solution through the issue divided into two sub-problems with the same way .In the view of the current decision-making involved in the conflict may not be a constraint issues .This paper come through: the optimal number of constraints conflict sets each constraint is the solving set of the conflict and set. And with the other methods of solving algorithm that in configuration the solution has its advantages, in some areas. This paper give a simple example of the testing of experimental data shows that the algorithm running time (consistency of performance for the number of detections) and the number of conflicts and the number of parameters is closely linked to verify when given a control, Time is running the algorithm can be expected (in a certain range).In this case the algorithm is an effective method to solve.
This paper analyzes the explained method in the original configuration. The explained method in the original configuration is through consistency constraints set for conflict .This task provided with the original allocation algorithm integration possible .This paper give the map for the relationship between the various objects of our algorithm is involved with the function of the main targets of the relationship. Another explanation is part of the solution solve explanation is a tools explained the failure and guide users, It service the configuration. This paper analysis the solving thinking on the original configuration and the relationship between configuration solve and explanation .This paper also give a map of configuration solve .That is using java object-oriented method.
In short, based on the current decision-making constraint satisfaction problems configuration can direct and effective give users the explanation for the failure of the optimal. The algorithm can show good prospects in dealing with multiple constraints and consider users preferences.
引文
[1] McDermott J, R1: A rule-based configurer of computer systems, ArtificialIntel- ligence, 1982, 19(1):39-88.
[2] Mittal S, and Frayman F. Towards a generic model ofconfigurationtasks. SridharanN S.edited Proc. of the 10th international joint conference on artificial intelligence,San Mateo Morgan Kaufmann publishers, 1989, 1395-1401.
[3] Wache H and Kamp G., Using description logic for configuration problems, 1996, www.informatik.uni-bremen.de/~wache/publications.html.
[4] McGuinness D L and Wright R., An industrial-strength description logic-based configuratior platform, IEEE Intelligent Systems & Their Applicatins, 1998,13(4) 69-77.
[5] Sabin D and Freuder E C., Configuration as composite constraint satisfaction, In Configuration-Papers from the 1996 Fall Symposium.1996. http://citeseer.ist.psu.edu/cache/papers/cs/1548/ftp:zSzzSzftp.cs.unh.eduzSzpubzSzcspzSzPaperszSzaiman96-ds1.pdf/sabin96configuration.pdf.
[6] Soininen T and Gelle E., Dynamic constraint satisfaction in configuration,1999, http://www.cs.hut.fi/-pdmg/papers/TSoininen99.pdf.
[7] Soininen T ,Gelle E and Niemela I., A fixpoint definition of dynamic constraint satisfaction, 1999, http://www.cs.hut.fi/~pdmg/papers/sgn-cp99.pdf.
[8] J′er?ome Amilhastre, H′el`ene Fargier, and Pierre Marquis, ‘Consistency restoration and explanations in dynamic CSPs application to configura- 5 See http://www.activebuyersguide.com. tion.’, Artificial Intelligence, 135(1-2), 199–234, (2002).
[9] Bowen.Using Dendency records to generate design coordination advice in a constraint-based approach to concurrent engineering.Computers in Industry,pages 191-199,1997.
[10]Freuder E C, Likitvatanavong C,Moretti M, ect, Computing explanations and implications in preference-based configurators, O’Sullivan B edited Constraint solving and CLP,LNAI 2627,2003,76-9
[11]Jakob Mauss and Mugur M. Tatar, ‘Computing minimal conflicts for rich constraint languages.’, in ECAI, pp. 151–155, (2002).
[12]Barry O’Callaghan, Barry O’Sullivan, and Eugene C. Freuder, ‘Generating corrective explanations for interactive constraint satisfaction’, in Proceedings of CP, pp. 445–459, (2005).
[13]Jon Doyle, ‘A truth maintenance system’, Artificial Intelligence, 12, 231–272, (1979).
[14]Johan de Kleer, ‘An assumption–based truth maintenance system’,ArtificialIntelligence, 28, 127–162, (1986).
[15]Ulrich Junker, ‘QuickXplain: preferred explanations and relaxations for over-constrained problems’, in Proceedings of AAAI, pp. 167–172, (2004).
[16]R′emi Douence and Narendra Jussien. Non-intrusive constraint solver enhancements. Research Report 02-2-INFO, ′Ecole des Mines de Nantes, Nantes, France, 2002.
[17]Stumptner M., An overview of knowledge-based configuration, AI Communications,1997,10(2):1-16
[18]Gerhard Friedrich, ‘Elimination of spurious explanations’, in Sixteenth European Conference on Artificial Intelligence, pp. 813–817, (2004).
[19]Sabin D,Weigel R., Product configuration frameworks-A survey,IEEE Intelligent Systems,1998,14(3):42-49
[20] Friedrich G and Stumptner M., Consistency-based configuration.1999, http://www.ifi.uni.klu.ac.at/IWAS/staff/Gerhard.Friedrich
[21] Eugene C. Freuder, Chavalit Likitvivatanavong, Manuela Moretti, Francesca Rossi, and Richard J.Wallace, ‘Computing explanations andimplications in preference-based configurators’, in Recent Advances in Constraints, LNAI 2627, pp. 76–92, (2003).
[22]Albert Haag, Ulrich Junker and Barry O’Sullivan A Survey on Principal Explanation Techniques for Configurators in 17th European Conference on Artificial Intelligence (2006)
[23]Mittal S, and Frayman F. Towards a generic model of configuration tasks.Sridharan N S.edited Proc. of the 10th international joint conference on artificial intelligence, San Mateo Morgan Kaufmann publishers,1989, 1395-1401
[24]Rina Dechter, Daniel Frost. Backjump-based backtracking for constraint satisfaction problems. Artificial Intelligence, 2002.
[25]李占山,王涛,孙吉贵,张朝辉. 产品配置器的工作机理研究. 计算机应用研究,2004.
[2] Mittal S, and Frayman F. Towards a generic model ofconfigurationtasks. SridharanN S.edited Proc. of the 10th international joint conference on artificial intelligence,San Mateo Morgan Kaufmann publishers, 1989, 1395-1401.
[3] Wache H and Kamp G., Using description logic for configuration problems, 1996, www.informatik.uni-bremen.de/~wache/publications.html.
[4] McGuinness D L and Wright R., An industrial-strength description logic-based configuratior platform, IEEE Intelligent Systems & Their Applicatins, 1998,13(4) 69-77.
[5] Sabin D and Freuder E C., Configuration as composite constraint satisfaction, In Configuration-Papers from the 1996 Fall Symposium.1996. http://citeseer.ist.psu.edu/cache/papers/cs/1548/ftp:zSzzSzftp.cs.unh.eduzSzpubzSzcspzSzPaperszSzaiman96-ds1.pdf/sabin96configuration.pdf.
[6] Soininen T and Gelle E., Dynamic constraint satisfaction in configuration,1999, http://www.cs.hut.fi/-pdmg/papers/TSoininen99.pdf.
[7] Soininen T ,Gelle E and Niemela I., A fixpoint definition of dynamic constraint satisfaction, 1999, http://www.cs.hut.fi/~pdmg/papers/sgn-cp99.pdf.
[8] J′er?ome Amilhastre, H′el`ene Fargier, and Pierre Marquis, ‘Consistency restoration and explanations in dynamic CSPs application to configura- 5 See http://www.activebuyersguide.com. tion.’, Artificial Intelligence, 135(1-2), 199–234, (2002).
[9] Bowen.Using Dendency records to generate design coordination advice in a constraint-based approach to concurrent engineering.Computers in Industry,pages 191-199,1997.
[10]Freuder E C, Likitvatanavong C,Moretti M, ect, Computing explanations and implications in preference-based configurators, O’Sullivan B edited Constraint solving and CLP,LNAI 2627,2003,76-9
[11]Jakob Mauss and Mugur M. Tatar, ‘Computing minimal conflicts for rich constraint languages.’, in ECAI, pp. 151–155, (2002).
[12]Barry O’Callaghan, Barry O’Sullivan, and Eugene C. Freuder, ‘Generating corrective explanations for interactive constraint satisfaction’, in Proceedings of CP, pp. 445–459, (2005).
[13]Jon Doyle, ‘A truth maintenance system’, Artificial Intelligence, 12, 231–272, (1979).
[14]Johan de Kleer, ‘An assumption–based truth maintenance system’,ArtificialIntelligence, 28, 127–162, (1986).
[15]Ulrich Junker, ‘QuickXplain: preferred explanations and relaxations for over-constrained problems’, in Proceedings of AAAI, pp. 167–172, (2004).
[16]R′emi Douence and Narendra Jussien. Non-intrusive constraint solver enhancements. Research Report 02-2-INFO, ′Ecole des Mines de Nantes, Nantes, France, 2002.
[17]Stumptner M., An overview of knowledge-based configuration, AI Communications,1997,10(2):1-16
[18]Gerhard Friedrich, ‘Elimination of spurious explanations’, in Sixteenth European Conference on Artificial Intelligence, pp. 813–817, (2004).
[19]Sabin D,Weigel R., Product configuration frameworks-A survey,IEEE Intelligent Systems,1998,14(3):42-49
[20] Friedrich G and Stumptner M., Consistency-based configuration.1999, http://www.ifi.uni.klu.ac.at/IWAS/staff/Gerhard.Friedrich
[21] Eugene C. Freuder, Chavalit Likitvivatanavong, Manuela Moretti, Francesca Rossi, and Richard J.Wallace, ‘Computing explanations andimplications in preference-based configurators’, in Recent Advances in Constraints, LNAI 2627, pp. 76–92, (2003).
[22]Albert Haag, Ulrich Junker and Barry O’Sullivan A Survey on Principal Explanation Techniques for Configurators in 17th European Conference on Artificial Intelligence (2006)
[23]Mittal S, and Frayman F. Towards a generic model of configuration tasks.Sridharan N S.edited Proc. of the 10th international joint conference on artificial intelligence, San Mateo Morgan Kaufmann publishers,1989, 1395-1401
[24]Rina Dechter, Daniel Frost. Backjump-based backtracking for constraint satisfaction problems. Artificial Intelligence, 2002.
[25]李占山,王涛,孙吉贵,张朝辉. 产品配置器的工作机理研究. 计算机应用研究,2004.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |