In order to realize spacecraft autonomy activity duration and complex temporal relations must be taken into consideration. In the space mission planning system, the traditional planners are unable to describe this kno...In order to realize spacecraft autonomy activity duration and complex temporal relations must be taken into consideration. In the space mission planning system, the traditional planners are unable to describe this knowledge, so an object-oriented temporal knowledge representation method is proposed to model every activity as an object to describe the activity's duration, start-time, end-time and the temporal relations with other activities. The layered planning agent architecture is then designed for spacecraft autonomous operation, and the functions of every component are given. A planning algorithm based on the temporal constraint satisfaction is built in detail using this knowledge representation and system architecture. The prototype of Deep Space Mission Autonomous Planning System is implemented. The results show that with the object-oriented temporal knowledge description method, the space mission planning system can be used to describe simultaneous activities, resource and temporal constraints, and produce a complete plan for exploration mission quickly under complex constraints.展开更多
The past decade witnessed rapid development of constraint satisfaction technologies, where algorithms are now able to cope with larger and harder problems. However, owing to the fact that constraints are inherently de...The past decade witnessed rapid development of constraint satisfaction technologies, where algorithms are now able to cope with larger and harder problems. However, owing to the fact that constraints are inherently declarative, attention is quickly turning toward developing high-level programming languages within which such problems can be modeled and also solved. Along these lines, this paper presents DEPICT, the language. Its use is illustrated through modeling a number of benchmark examples. The paper continues with a description of a prototype system within which such models may be interpreted. The paper concludes with a description of a sample run of this interpreter showing how a problem modeled as such is typically solved.展开更多
The conflict detection and resolution in collaborative design is a key issue to maintain multi disciplinary design consistency. This paper proposes a new method for conflict detection and resolution based on constrain...The conflict detection and resolution in collaborative design is a key issue to maintain multi disciplinary design consistency. This paper proposes a new method for conflict detection and resolution based on constraint satisfaction technique. The representation of design constraint, the interval arithmetic of the constraint satisfaction problem CSP and the conflict resolution strategy based on constraint relaxation and adjustment are introduced. A constraint satisfaction based conflict detection and resolution tool CSCDR is then developed. It can help collaborative designers to detect and resolve the conflicts in time in the early stage of the design process so that the unnecessary design iteration and repeated negotiation are avoided and the design efficiency is then much improved. A design case illustrates the effectiveness of CSCDR.展开更多
To overcome inefficiency in traditional logic programming, a declarative programming language COPS is designed based on the notion of concurrent constraint programming (CCP). The improvement is achieved by the adoptio...To overcome inefficiency in traditional logic programming, a declarative programming language COPS is designed based on the notion of concurrent constraint programming (CCP). The improvement is achieved by the adoption of constraint-based heuristic strategy and the introduction of deterministic components in the framework of CCP. Syntax specification and an operational semantic description are presented.展开更多
In order to facilitate solution, a complex problem is normally decomposed into many small sub-problems during product development process. Teams are formed to resolve each sub-problem. The original problem is resolved...In order to facilitate solution, a complex problem is normally decomposed into many small sub-problems during product development process. Teams are formed to resolve each sub-problem. The original problem is resolved from solutions of sub-problems. Ideally, sub-problems are not only mutually independent but also inherent parameters of original problem. Solution of original problem can be directly derived from the collection of solutions from simplified sub-problems. In practice, the degree of interdependency is indeed reduced, sub-problems are neither totally independent nor all inherent parameters of original problem. This paper discusses team coordination under this condition and design solution from each team, which not only satisfies total requirements but also is an optimal one. The suggested optimized constraint decomposition method will insure workable Pareto solution.展开更多
This research attempts to devise a multistage and multiproduct short-term integrative production plan that can dynamically change based on the order priority and virtual occupancy for application in steel plants. Cons...This research attempts to devise a multistage and multiproduct short-term integrative production plan that can dynamically change based on the order priority and virtual occupancy for application in steel plants. Considering factors such as the delivery time, varietal compatibility between different products, production capacity of variety per hour, minimum or maximum batch size, and transfer time, we propose an available production capacity network with varietal compatibility and virtual occupancy for enhancing production plan implementation and quick adjustment in the case of dynamic production changes. Here available means the remaining production capacity after virtual occupancy.To quickly build an available production capacity network and increase the speed of algorithm solving, constraint selection and cutting methods with order priority were used for model solving. Finally, the genetic algorithm improved with local search was used to optimize the proposed production plan and significantly reduce the order delay rate. The validity of the proposed model and algorithm was numerically verified by simulating actual production practices. The simulation results demonstrate that the model and improved algorithm result in an effective production plan.展开更多
Message passing algorithms,whose iterative nature captures complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages,provide a powerf...Message passing algorithms,whose iterative nature captures complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages,provide a powerful toolkit in tackling hard computational tasks in optimization,inference,and learning problems.In the context of constraint satisfaction problems(CSPs),when a control parameter(such as constraint density)is tuned,multiple threshold phenomena emerge,signaling fundamental structural transitions in their solution space.Finding solutions around these transition points is exceedingly challenging for algorithm design,where message passing algorithms suffer from a large message fiuctuation far from convergence.Here we introduce a residual-based updating step into message passing algorithms,in which messages with large variation between consecutive steps are given high priority in the updating process.For the specific example of model RB(revised B),a typical prototype of random CSPs with growing domains,we show that our algorithm improves the convergence of message updating and increases the success probability in finding solutions around the satisfiability threshold with a low computational cost.Our approach to message passing algorithms should be of value for exploring their power in developing algorithms to find ground-state solutions and understand the detailed structure of solution space of hard optimization problems.展开更多
In order to realize the explorer autonomy, the software architecture of autonomous mission management system (AMMS) is given for the deep space explorer, and the autonomous mission planning system, the kernel part of ...In order to realize the explorer autonomy, the software architecture of autonomous mission management system (AMMS) is given for the deep space explorer, and the autonomous mission planning system, the kernel part of this architecture, is designed in detail. In order to describe the parallel activity, the state timeline is introduced to build the formal model of the planning system and based on this model, the temporal constraint satisfaction planning algorithm is proposed to produce the explorer’s activity sequence. With some key subsystems of the deep space explorer as examples, the autonomous mission planning simulation system is designed. The results show that this system can calculate the executable activity sequence with the given mission goals and initial state of the explorer.展开更多
Qualitative spatial reasoning on topological relations can extract hidden spatial knowledge from qualitatively described topological information,which is of significant importance for decisionmaking and query optimiza...Qualitative spatial reasoning on topological relations can extract hidden spatial knowledge from qualitatively described topological information,which is of significant importance for decisionmaking and query optimization in spatial analysis.Qualitative reasoning on spatial topological information based on semantic knowledge and reasoning rules is an efficient means of reducing both the known relations and the corresponding rules,which can result in enhanced reasoning performance.This paper proposes a qualitative reasoning method for spatial topological relations based on the semantic description of reasoning rules and constraint set.Combined with knowledge from the Semantic Web,the proposed method can easily extract potential spatial results consistent with both unique and non-unique rules.The Constraint-Satisfactionbased approach,describing constraint set with semantic expressions,is then used together with an improved path consistency algorithm to verify the consistency of the unique-rules-based and non-unique-rules-based reasoning results.The verification can eliminate certain reasoning results to ensure the reliability of the final results.Thus,the task of qualitative spatial reasoning on topological relations is completed.展开更多
In this paper, a computationally efficient method is proposed for automated design of the prefilters for multivariable systems. In quantitative feedback theory （QFT） method, proposed by Horowitz, the prefilter is de...In this paper, a computationally efficient method is proposed for automated design of the prefilters for multivariable systems. In quantitative feedback theory （QFT） method, proposed by Horowitz, the prefilter is designed to achieve the desired tracking specifications. In the proposed approach, we pose the prefilter design problem as an interval constraint satisfaction problem and solve it using the well-established interval constraint satisfaction techniques. The proposed method finds optimal values of the parameters of fixed structure prefilter within the initial search domain. An approach based on prefilter synthesis for single-input single-output is already developed. The purpose of this paper is to extend this approach to QFT prefilter design for general multivariable systems. To validate the above design approach, we applied the method to a laboratory setup of magnetic levitation system.展开更多
Model predictive controllers(MPC)with the two-loop scheme are successful approaches practically and can be classified into two main categories,tube-based MPC and MPCbased reference governors(RG).In this paper,an enhan...Model predictive controllers(MPC)with the two-loop scheme are successful approaches practically and can be classified into two main categories,tube-based MPC and MPCbased reference governors(RG).In this paper,an enhanced twoloop MPC design is proposed for a pre-stabilized system with the bounded uncertainty subject to the input and state constraints.The proposed method offers less conservatism than the tube-based MPC methods by enlarging the restricted input constraint.Contrary to the MPC-based RGs,the investigated method improves tracking performance of the pre-stabilized system while satisfying the constraints.Additionally,the robust global asymptotic stability of the closed-loop system is guaranteed in a novel procedure with terminal constraint relaxation.Simulation of the proposed method on a servo system shows its effectiveness in comparison to the others.展开更多
This paper presents a matrix permuting approach to the construction of Low-Density Parity-Check (LDPC) code. It investigates the structure of the sparse parity-check matrix defined by Gallager. It is discovered that t...This paper presents a matrix permuting approach to the construction of Low-Density Parity-Check (LDPC) code. It investigates the structure of the sparse parity-check matrix defined by Gallager. It is discovered that the problem of constructing the sparse parity-check matrix requires an algorithm that is efficient in search environments and also is able to work with constraint satisfaction problem. The definition of Q-matrix is given, and it is found that the queen algorithm enables to search the Q-matrix. With properly permuting Q-matrix as sub-matrix, the sparse parity-check matrix which satisfied constraint condition is created, and the good regular-LDPC code that is called the Q-matrix LDPC code is generated. The result of this paper is significant not only for designing low complexity encoder, improving performance and reducing complexity of iterative decoding arithmetic, but also for building practical system of encodable and decodable LDPC code.展开更多
Mature algorithms for the Constraint Satisfaction Problem (CSP) of binary constraint with discrete variables have already been obtained for the application. For the instance of multi value constraint with continuous v...Mature algorithms for the Constraint Satisfaction Problem (CSP) of binary constraint with discrete variables have already been obtained for the application. For the instance of multi value constraint with continuous variables, the approach will be quite different and the difficulty of settling will aggrandize a lot. This paper presents the algorithm for realizing global consistency of continuous variable. And this algorithm can be applied to multi value constraint.展开更多
Conflicts between two or more parties arise for various reasons andperspectives. Thus, resolution of con-flicts frequently relies on some form of negotiation. Thispaper presents a general problem-solving framework for...Conflicts between two or more parties arise for various reasons andperspectives. Thus, resolution of con-flicts frequently relies on some form of negotiation. Thispaper presents a general problem-solving framework for modeling multi-issue multilateral negotiationusing fuzzy constraints. Agent negotiation is formulated as a distributed fuzzy constraintsatisfaction problem (DFCSP). Fuzzy constrains are thus used to naturally represent each agent''sdesires involving imprecision and human conceptualization, particularly when lexical imprecision andsubjective matters are concerned. On the other hand, based on fuzzy constraint-basedproblem-solving, our approach enables an agent not only to systematically relax fuzzy constraints togenerate a proposal, but also to employ fuzzy similarity to select the alternative that is subjectto its acceptability by the opponents. This task of problem-solving is to reach an agreement thatbenefits all agents with a high satisfaction degree of fuzzy constraints, and move towards the dealmore quickly since their search focuses only on the feasible solution space. An application tomultilateral negotiation of a travel planning is provided to demonstrate the usefulness andeffectiveness of our framework.展开更多
This paper presents a new look on emergence from the aspect of locality andglobality of evaluation functions for solving traditional computer problems. We first translate theConstraint Satisfaction Problem (CSP) into ...This paper presents a new look on emergence from the aspect of locality andglobality of evaluation functions for solving traditional computer problems. We first translate theConstraint Satisfaction Problem (CSP) into the multi-agent system, and then show how a globalsolution emerges from the system in which every agent uses a local evaluation function to decide itsaction, while comparing to other traditional algorithms, such as Local search and SimulatedAnnealing which use global evaluation functions. We also give some computer experimental results onlarge-scale N-queen problems and κ-Coloring problems, and show that emergence only depends onproblem instance, not details of agent settings, i.e. in some CSPs, the system can self-organize toa global solution, but can not in some other CSPs no matter what settings of agents have.展开更多
The random K-satisfiability （K-SAT） problem is very diffcult when the clause density is close to the satisfiability threshold. In this paper we study this problem from the perspective of solution space coupling. We ...The random K-satisfiability （K-SAT） problem is very diffcult when the clause density is close to the satisfiability threshold. In this paper we study this problem from the perspective of solution space coupling. We divide a given difficult random K-SAT formula into two easy sub-formulas and let the two corresponding solution spaces to interact with each other through a coupling field x. We investigate the statistical mechanical property of this coupled system by mean field theory and computer simulations. The coupled system has an ergodicity-breaking （clustering） transition at certain critical value Xd of the coupling field. At this transition point, the mean overlap value between the solutions of the two solution spaces is very close to 1. The mean energy density of the coupled system at its clustering transition point is less than the mean energy density of the original K-SAT problem at the temperature-induced clustering transition point. The implications of this work for designing new heuristic K-SAT solvers are discussed.展开更多
Software testing is an important technique to assure the quality of software systems, especially high-confidence systems. To automate the process of software testing, many automatic test-data generation techniques hav...Software testing is an important technique to assure the quality of software systems, especially high-confidence systems. To automate the process of software testing, many automatic test-data generation techniques have been proposed. To generate effective test data, we propose a test-data generation technique guided by static defect detection in this paper. Using static defect detection analysis, our approach first identifies a set of suspicious statements which are likely to contain faults, then generates test data to cover these suspicious statements by converting the problem of test-data generation to the constraint satisfaction problem. We performed a case study to validate the effectiveness of our approach, and made a simple comparison with another test-data generation on-line tool, JUnit Factory. The results show that, compared with JUnit Factory, our approach generates fewer test data that are competitive on fault detection.展开更多
For the problem of propositional satisfiability a polynomial algorithm of limited propositional deduction is proposed which can be viewed as a sort of boolean constraint propagation mechanism. It can be embodied in a ...For the problem of propositional satisfiability a polynomial algorithm of limited propositional deduction is proposed which can be viewed as a sort of boolean constraint propagation mechanism. It can be embodied in a backtracking search program for propositional satisfiability problems to make search efficient. The efficiency is gained in two ways:One is to use the algorithm to derive literals so as to overcome the ambiguities in search. The other is to exploit the consequence sets of unbound atoms generated during limited deduction as a heuristic measure for possible choices. The experiments have shown remarkable improvement in reducing search space.展开更多
Path-oriented test case generation is in essence a constraint satisfaction problem （CSP） solved by search strategies, among which backtracking algorithms are widely used. In this article, the backtracking algorithm ...Path-oriented test case generation is in essence a constraint satisfaction problem （CSP） solved by search strategies, among which backtracking algorithms are widely used. In this article, the backtracking algorithm branch and bound （BB） is introduced to generate path-oriented test cases automatically. A model based on state space search is proposed to construct the search tree dynamically. The BB is optimized from two perspectives. Variable permutation with a heuristic rule to break ties is adopted for the branching operation, and interval computation with analysis on the monotony of branching conditions is utilized for the bounding operation. Empirical experiments show that the proposed method performs well with linear complexity, and reaches 100% coverage on some benchmark programs with an advantage over some static and dynamic algorithms.展开更多
Quantified constraint satisfaction problems （QCSPs） are an extension to constraint satisfaction problems （CSPs） with both universal quantifiers and existential quantifiers. In this paper we apply variable ordering...Quantified constraint satisfaction problems （QCSPs） are an extension to constraint satisfaction problems （CSPs） with both universal quantifiers and existential quantifiers. In this paper we apply variable ordering heuristics and integrate standard dependency schemes in QCSP solvers. The technique can help to decide the next variable to be assigned in QCSP solving. We also introduce a new factor into the variable ordering heuristics： a variable＇s dep is the number of variables depending on it. This factor represents the probability of getting more candidates for the next variable to be assigned. Experimental results show that variable ordering heuristics with standard dependency schemes and the new factor dep can improve the performance of QCSP solvers.展开更多
文摘In order to realize spacecraft autonomy activity duration and complex temporal relations must be taken into consideration. In the space mission planning system, the traditional planners are unable to describe this knowledge, so an object-oriented temporal knowledge representation method is proposed to model every activity as an object to describe the activity's duration, start-time, end-time and the temporal relations with other activities. The layered planning agent architecture is then designed for spacecraft autonomous operation, and the functions of every component are given. A planning algorithm based on the temporal constraint satisfaction is built in detail using this knowledge representation and system architecture. The prototype of Deep Space Mission Autonomous Planning System is implemented. The results show that with the object-oriented temporal knowledge description method, the space mission planning system can be used to describe simultaneous activities, resource and temporal constraints, and produce a complete plan for exploration mission quickly under complex constraints.
基金This work was supported by Lebanese National Council for Scientific Research.
文摘The past decade witnessed rapid development of constraint satisfaction technologies, where algorithms are now able to cope with larger and harder problems. However, owing to the fact that constraints are inherently declarative, attention is quickly turning toward developing high-level programming languages within which such problems can be modeled and also solved. Along these lines, this paper presents DEPICT, the language. Its use is illustrated through modeling a number of benchmark examples. The paper continues with a description of a prototype system within which such models may be interpreted. The paper concludes with a description of a sample run of this interpreter showing how a problem modeled as such is typically solved.
文摘The conflict detection and resolution in collaborative design is a key issue to maintain multi disciplinary design consistency. This paper proposes a new method for conflict detection and resolution based on constraint satisfaction technique. The representation of design constraint, the interval arithmetic of the constraint satisfaction problem CSP and the conflict resolution strategy based on constraint relaxation and adjustment are introduced. A constraint satisfaction based conflict detection and resolution tool CSCDR is then developed. It can help collaborative designers to detect and resolve the conflicts in time in the early stage of the design process so that the unnecessary design iteration and repeated negotiation are avoided and the design efficiency is then much improved. A design case illustrates the effectiveness of CSCDR.
文摘To overcome inefficiency in traditional logic programming, a declarative programming language COPS is designed based on the notion of concurrent constraint programming (CCP). The improvement is achieved by the adoption of constraint-based heuristic strategy and the introduction of deterministic components in the framework of CCP. Syntax specification and an operational semantic description are presented.
基金Supportedby 86 3/CIMS (No .2 0 0 1AA4 1114 0 )andtheNationalNaturalScienceFoundationofChina (No .6 0 10 4 0 0 8)
文摘In order to facilitate solution, a complex problem is normally decomposed into many small sub-problems during product development process. Teams are formed to resolve each sub-problem. The original problem is resolved from solutions of sub-problems. Ideally, sub-problems are not only mutually independent but also inherent parameters of original problem. Solution of original problem can be directly derived from the collection of solutions from simplified sub-problems. In practice, the degree of interdependency is indeed reduced, sub-problems are neither totally independent nor all inherent parameters of original problem. This paper discusses team coordination under this condition and design solution from each team, which not only satisfies total requirements but also is an optimal one. The suggested optimized constraint decomposition method will insure workable Pareto solution.
基金financially supported by the National Natural Science Foundation of China (No.51274043)。
文摘This research attempts to devise a multistage and multiproduct short-term integrative production plan that can dynamically change based on the order priority and virtual occupancy for application in steel plants. Considering factors such as the delivery time, varietal compatibility between different products, production capacity of variety per hour, minimum or maximum batch size, and transfer time, we propose an available production capacity network with varietal compatibility and virtual occupancy for enhancing production plan implementation and quick adjustment in the case of dynamic production changes. Here available means the remaining production capacity after virtual occupancy.To quickly build an available production capacity network and increase the speed of algorithm solving, constraint selection and cutting methods with order priority were used for model solving. Finally, the genetic algorithm improved with local search was used to optimize the proposed production plan and significantly reduce the order delay rate. The validity of the proposed model and algorithm was numerically verified by simulating actual production practices. The simulation results demonstrate that the model and improved algorithm result in an effective production plan.
基金supported by Guangdong Major Project of Basic and Applied Basic Research No.2020B0301030008Science and Technology Program of Guangzhou No.2019050001+2 种基金the Chinese Academy of Sciences Grant QYZDJ-SSWSYS018the National Natural Science Foundation of China(Grant No.12171479)supported by the National Natural Science Foundation of China(Grant Nos.11301339 and 11491240108)。
文摘Message passing algorithms,whose iterative nature captures complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages,provide a powerful toolkit in tackling hard computational tasks in optimization,inference,and learning problems.In the context of constraint satisfaction problems(CSPs),when a control parameter(such as constraint density)is tuned,multiple threshold phenomena emerge,signaling fundamental structural transitions in their solution space.Finding solutions around these transition points is exceedingly challenging for algorithm design,where message passing algorithms suffer from a large message fiuctuation far from convergence.Here we introduce a residual-based updating step into message passing algorithms,in which messages with large variation between consecutive steps are given high priority in the updating process.For the specific example of model RB(revised B),a typical prototype of random CSPs with growing domains,we show that our algorithm improves the convergence of message updating and increases the success probability in finding solutions around the satisfiability threshold with a low computational cost.Our approach to message passing algorithms should be of value for exploring their power in developing algorithms to find ground-state solutions and understand the detailed structure of solution space of hard optimization problems.
文摘In order to realize the explorer autonomy, the software architecture of autonomous mission management system (AMMS) is given for the deep space explorer, and the autonomous mission planning system, the kernel part of this architecture, is designed in detail. In order to describe the parallel activity, the state timeline is introduced to build the formal model of the planning system and based on this model, the temporal constraint satisfaction planning algorithm is proposed to produce the explorer’s activity sequence. With some key subsystems of the deep space explorer as examples, the autonomous mission planning simulation system is designed. The results show that this system can calculate the executable activity sequence with the given mission goals and initial state of the explorer.
基金This work is funded by the National Natural Science Foundation of China[grant number 41271399]the China Special Fund for Surveying,Mapping and Geo-information Research in the Public Interest[grant number 201512015]the National Key Research Program of China[grant number 2016YFB0501400].
文摘Qualitative spatial reasoning on topological relations can extract hidden spatial knowledge from qualitatively described topological information,which is of significant importance for decisionmaking and query optimization in spatial analysis.Qualitative reasoning on spatial topological information based on semantic knowledge and reasoning rules is an efficient means of reducing both the known relations and the corresponding rules,which can result in enhanced reasoning performance.This paper proposes a qualitative reasoning method for spatial topological relations based on the semantic description of reasoning rules and constraint set.Combined with knowledge from the Semantic Web,the proposed method can easily extract potential spatial results consistent with both unique and non-unique rules.The Constraint-Satisfactionbased approach,describing constraint set with semantic expressions,is then used together with an improved path consistency algorithm to verify the consistency of the unique-rules-based and non-unique-rules-based reasoning results.The verification can eliminate certain reasoning results to ensure the reliability of the final results.Thus,the task of qualitative spatial reasoning on topological relations is completed.
文摘In this paper, a computationally efficient method is proposed for automated design of the prefilters for multivariable systems. In quantitative feedback theory （QFT） method, proposed by Horowitz, the prefilter is designed to achieve the desired tracking specifications. In the proposed approach, we pose the prefilter design problem as an interval constraint satisfaction problem and solve it using the well-established interval constraint satisfaction techniques. The proposed method finds optimal values of the parameters of fixed structure prefilter within the initial search domain. An approach based on prefilter synthesis for single-input single-output is already developed. The purpose of this paper is to extend this approach to QFT prefilter design for general multivariable systems. To validate the above design approach, we applied the method to a laboratory setup of magnetic levitation system.
文摘Model predictive controllers(MPC)with the two-loop scheme are successful approaches practically and can be classified into two main categories,tube-based MPC and MPCbased reference governors(RG).In this paper,an enhanced twoloop MPC design is proposed for a pre-stabilized system with the bounded uncertainty subject to the input and state constraints.The proposed method offers less conservatism than the tube-based MPC methods by enlarging the restricted input constraint.Contrary to the MPC-based RGs,the investigated method improves tracking performance of the pre-stabilized system while satisfying the constraints.Additionally,the robust global asymptotic stability of the closed-loop system is guaranteed in a novel procedure with terminal constraint relaxation.Simulation of the proposed method on a servo system shows its effectiveness in comparison to the others.
基金Supported by the National Natural Science Foundation of China (No.60572050)by the National Science Foundation of Hubei Province (No.2004ABA049)
文摘This paper presents a matrix permuting approach to the construction of Low-Density Parity-Check (LDPC) code. It investigates the structure of the sparse parity-check matrix defined by Gallager. It is discovered that the problem of constructing the sparse parity-check matrix requires an algorithm that is efficient in search environments and also is able to work with constraint satisfaction problem. The definition of Q-matrix is given, and it is found that the queen algorithm enables to search the Q-matrix. With properly permuting Q-matrix as sub-matrix, the sparse parity-check matrix which satisfied constraint condition is created, and the good regular-LDPC code that is called the Q-matrix LDPC code is generated. The result of this paper is significant not only for designing low complexity encoder, improving performance and reducing complexity of iterative decoding arithmetic, but also for building practical system of encodable and decodable LDPC code.
文摘Mature algorithms for the Constraint Satisfaction Problem (CSP) of binary constraint with discrete variables have already been obtained for the application. For the instance of multi value constraint with continuous variables, the approach will be quite different and the difficulty of settling will aggrandize a lot. This paper presents the algorithm for realizing global consistency of continuous variable. And this algorithm can be applied to multi value constraint.
文摘Conflicts between two or more parties arise for various reasons andperspectives. Thus, resolution of con-flicts frequently relies on some form of negotiation. Thispaper presents a general problem-solving framework for modeling multi-issue multilateral negotiationusing fuzzy constraints. Agent negotiation is formulated as a distributed fuzzy constraintsatisfaction problem (DFCSP). Fuzzy constrains are thus used to naturally represent each agent''sdesires involving imprecision and human conceptualization, particularly when lexical imprecision andsubjective matters are concerned. On the other hand, based on fuzzy constraint-basedproblem-solving, our approach enables an agent not only to systematically relax fuzzy constraints togenerate a proposal, but also to employ fuzzy similarity to select the alternative that is subjectto its acceptability by the opponents. This task of problem-solving is to reach an agreement thatbenefits all agents with a high satisfaction degree of fuzzy constraints, and move towards the dealmore quickly since their search focuses only on the feasible solution space. An application tomultilateral negotiation of a travel planning is provided to demonstrate the usefulness andeffectiveness of our framework.
基金This paper is supported by the International Program of Santa Fe Institute and the grant of China National Science Foundation(No.70171052).
文摘This paper presents a new look on emergence from the aspect of locality andglobality of evaluation functions for solving traditional computer problems. We first translate theConstraint Satisfaction Problem (CSP) into the multi-agent system, and then show how a globalsolution emerges from the system in which every agent uses a local evaluation function to decide itsaction, while comparing to other traditional algorithms, such as Local search and SimulatedAnnealing which use global evaluation functions. We also give some computer experimental results onlarge-scale N-queen problems and κ-Coloring problems, and show that emergence only depends onproblem instance, not details of agent settings, i.e. in some CSPs, the system can self-organize toa global solution, but can not in some other CSPs no matter what settings of agents have.
基金Supported by the Knowledge Innovation Program of Chinese Academy of Sciences under Grant No.KJCX2-EW-J02the Natural National Science Foundation of China under Grant Nos.11121403 and 11225526
文摘The random K-satisfiability （K-SAT） problem is very diffcult when the clause density is close to the satisfiability threshold. In this paper we study this problem from the perspective of solution space coupling. We divide a given difficult random K-SAT formula into two easy sub-formulas and let the two corresponding solution spaces to interact with each other through a coupling field x. We investigate the statistical mechanical property of this coupled system by mean field theory and computer simulations. The coupled system has an ergodicity-breaking （clustering） transition at certain critical value Xd of the coupling field. At this transition point, the mean overlap value between the solutions of the two solution spaces is very close to 1. The mean energy density of the coupled system at its clustering transition point is less than the mean energy density of the original K-SAT problem at the temperature-induced clustering transition point. The implications of this work for designing new heuristic K-SAT solvers are discussed.
基金sponsored by the National High-Tech Research and Development 863 Program of China under Grant No.2007AA010301the National Natural Science Foundation of China under Grant Nos. 60803012 and 90718016China Postdoctoral Science Foundation funded project under Grant No. 20080440254
文摘Software testing is an important technique to assure the quality of software systems, especially high-confidence systems. To automate the process of software testing, many automatic test-data generation techniques have been proposed. To generate effective test data, we propose a test-data generation technique guided by static defect detection in this paper. Using static defect detection analysis, our approach first identifies a set of suspicious statements which are likely to contain faults, then generates test data to cover these suspicious statements by converting the problem of test-data generation to the constraint satisfaction problem. We performed a case study to validate the effectiveness of our approach, and made a simple comparison with another test-data generation on-line tool, JUnit Factory. The results show that, compared with JUnit Factory, our approach generates fewer test data that are competitive on fault detection.
基金Project supported by the "863" High-Tech Program of China.
文摘For the problem of propositional satisfiability a polynomial algorithm of limited propositional deduction is proposed which can be viewed as a sort of boolean constraint propagation mechanism. It can be embodied in a backtracking search program for propositional satisfiability problems to make search efficient. The efficiency is gained in two ways:One is to use the algorithm to derive literals so as to overcome the ambiguities in search. The other is to exploit the consequence sets of unbound atoms generated during limited deduction as a heuristic measure for possible choices. The experiments have shown remarkable improvement in reducing search space.
基金supported by the Hi-Tech Research and Development Program of China(2012AA011201)the National Natural Science Foundation of China(61202080)+1 种基金the Major Program of the National Natural Science Foundation of China(91318301)the Open Funding of State Key Laboratory of Computer Architecture(CARCH201201)
文摘Path-oriented test case generation is in essence a constraint satisfaction problem （CSP） solved by search strategies, among which backtracking algorithms are widely used. In this article, the backtracking algorithm branch and bound （BB） is introduced to generate path-oriented test cases automatically. A model based on state space search is proposed to construct the search tree dynamically. The BB is optimized from two perspectives. Variable permutation with a heuristic rule to break ties is adopted for the branching operation, and interval computation with analysis on the monotony of branching conditions is utilized for the bounding operation. Empirical experiments show that the proposed method performs well with linear complexity, and reaches 100% coverage on some benchmark programs with an advantage over some static and dynamic algorithms.
基金supported in part by the National Natural Science Foundation of China under Grant No. 61070039
文摘Quantified constraint satisfaction problems （QCSPs） are an extension to constraint satisfaction problems （CSPs） with both universal quantifiers and existential quantifiers. In this paper we apply variable ordering heuristics and integrate standard dependency schemes in QCSP solvers. The technique can help to decide the next variable to be assigned in QCSP solving. We also introduce a new factor into the variable ordering heuristics： a variable＇s dep is the number of variables depending on it. This factor represents the probability of getting more candidates for the next variable to be assigned. Experimental results show that variable ordering heuristics with standard dependency schemes and the new factor dep can improve the performance of QCSP solvers.
