The Research On The Technique Of Geometric Constraint Solving

In recent years, parameterization design technique has become an effective way of the product initial design, product model, revision and multi-scheme comparison and dynamical design in the design process with its powerful sketch design and revision on the graphs by size-driven. And it has got people's more and more attention. Some foreign advanced CAD systems have had the functions of parameterization to a certain degree. It has already become one of the important symbols in modern CAD system that has a strong parameterization design capacity. The fundamental difference between the parameterization design system and the general drawing system is tha it also expresses and deals with the relation between various kinds of constraints among the geometric elements besides geometric topological information. Two major advantages of the parameterization design system are: First, it can make the project designer needn't consider the details and draw up the product model as soon as possible. The accurate figure is produced automatically by the system; second, it can update the design by changing some constraint parameters instead of operating the whole course of product design. The foundation of parameterization design technique is the constraint technology. It is very meaningful for improving parameterization design technique to study the constraint theory and its application in the graph design. Geometry constraint solving is the most central technology in the parameter design methods on the basis of constraint satisfaction. It is the key of the quality of the parameterization design system to weigh to whether the geometric constraint technology is good and mature or not. It should be pointed out that some scholars have completed a series of research work about some important problems such as geometric constraint model and parameterization design method. The research in the problem started very early. It started from the beginning of the sixties to now and it has achieved a lot of effective results in theory and practice. The research has spread all over the fields. The current solving methods can be summarized into: whole solving approach, sparse matrix approach, connect analytic approach, stipulation construction approach, constraint propagation approach, symbol algebra approach and auxiliary line approach. In the characteristic technique, some foreign scholars such as Gossard, Part, Dixon, Shah and Woo, some scientific institutions such as institute of technology of Central China, Northwest polytechnical university, Xi'an Jiaotong University, Institute of Computing Technology CAD open laboratory of Chinese Academy of Sciences, mathematics and system research institute of Chinese Academy of Sciences, Tsing-Hua University, Beijing Aerospace University, Dalian polytechnical university and Zhejiang University have made contributions to the development of characteristic technology. The constraint problem hasn't been solved well and it has difficulties in a certain degree. The problem has been paid close attention of a lot of scholars all the time. We can see that people have already done a lot of research on this problem but there are a lot of problems to be solved even to say solving some problems is still very urgent from our analysis above. For example the numerical iteration method can only get one solutiona and can't compare many solutions in the solution space; the speed and global capability; The classical numerical iteration method is sensible to the initial value and an unsuitable initial value will lead to a solution that the user doesn't want; under-consraint and over-constraint problems. In this thesis we attempt to break through and innovate on these questions to some extent. In this paper we put forward a new geometric constraint solving approach so that the geometric modeling method can be used in the practical CAD systems to improve the application level of current CAD system. For some problems existing in the geometric constraint solving field, we will do some research on the geometric constraint problem from the following some respects and put forward some new geometric constraint solving ideas and methods so that we can make geometric constraint technology get further development. 1.We will adopt the genetic quantum algorithm to solve geometric constraint problem so that we can find the best solution effectively and fast. Because it can only get one solution to solve the geometric constraint problem by numeric iteration method and is unable to compare many solutions in the solution space, we introduced the optimization algorithm to solve geometric constraint problem. By analyzing the evolutionary algorithm, we can see that in the evolutionary process the evolutionary algorithm tries its best to keep the balance between the variety of individuals and the convergence of the colony, but it can't use the information of the immature subgroup in the evolutionary process, so the convergence speed is very slow. If we can introduce the mechanism of memory and direction study in order to improve the intelligentcapability, the algorithm efficiency will be improved greatly and the prematurity and the convergence speed can be solved. Based on the above consideration, the paper combines the evolutionary algorithm and quantum theory and introduces the quantum evolutionary theory and studying algorithm.The genetic quantum algorithm is the combination result of the genetic algorithm and the quantum algorithm. We adopt the expression form of the qubit chromosome. Because of this kind of expression of probability, a quantum chromosome is carrying the information of a lot of states. We can observe at random that quantum chromosome can produce new individuals and it can bring the abundant population. And then it can keep the variety of the colony and overcome the shortcoming of the early maturing. In addition GQA adopts one "intelligence"updating method to guide to evolve. It can accelerate algorithms convergent. Because the genetic quantum algorithm doesn't involve matrix inversion and equation local derivation, it hasn't the disadvantage of sensity to the initial value. When converting the equation group into optimization models in this paper we will get the optimization model by the simple summation of the equation absolute value, while other most optimization algorithms utilize the square summation of the constraint equation group from getting the model. Compared with these constraint models, the constraint model in this paper is simpler and can make the calculation amount reduce greatly. So the geometric constraint solving based on the genetic quantum algorithm has a robust capability. We often come into label dimension deficiency when we design the sketch in the project. Even some designed sketches have the conditions of label dimension deficiency because some dimensions are not very important. But whe we solve the constaint, it will often lead the solving to fail. Many solvers can only give a failure reason and can't solve the problem as possible as they can, but the genetic quantum algorithm can solve the under-constraint problem well. When transferring the constraint problem into the number value optimization problem, we doesn't have special demand on the number of equation and the number of variable in equation, so we can deal with under-constraint problems. 2 . When transferring the geometric constaint geqaution group inito the optimization model, we need a method to jump out of the local bseat solution so that we can find a global best solution. Considering the speed and global capability, we adopt group intelligent algorithm to solve geometric constraint problem, here including ant genetic algorithm, compound particle group optimization algorithm. The genetic algorithm has fast global convergence ability, but it is powerless when meeting the feedback information in the system. So it may do a large amount of redundancyiteration when solving the problem to a certain limit. So the capability of getting accurate solution is low. Ant algorithm is an aolgorithm simulating the true behaviors. Ant optimization algorithm is an iteration algorithm itself, but it isn't a simple iteration. The current iteration takes use of the previous iteration information. That is to say that it simulates the information positive feedback theory. Just because of the reciprocity of the positive and heuristic algorithms, the ant optimization algorithm has a strong global convergence. The ant algorithm is convergent in the best path by the accumulation and upgrading of information elements. It has the capability of distributed parallel global searching. But the information elements are deficient in initial stage and the solving process is slow. The ant genetic algorithm merges the ant algorithm and the genetic algorithm. The basic idea of the integration (genetic algorithm-ant algorithm, GAAA ) of the genetic algorithm and ant algorithm is that we adopt the genetic algorithm in the initial process of the algorithm and utilize the fast , randomness , global convergence property of the genetic algorithm fully. Its result is to produce the initial information distribution of the question. We adopt ant algorithm in the following process. In the situation that we have a certain initial information distribution, we fully utilize the capability of parallel, positive feedback, the high precision of ant algorithm. The algorithm in this paper uses the stochastic colony. It can quicken the speed of ant algorithm and can avoid getting into the lobal best solution in the course of solving. Because the genetic ant algorithm reduces the parameter adjusting, it can avoid large numbers of blindfold experiments. Particle swarm optimization algorithm is a kind of evolution computation technology based on group intelligence. It comes from the research on the bird flock movement behavior. In all the evolution computations heuristic function should be included to control its one's own characteristic. These parameters are usually correlated with the specific problem and are defined by the users. Suitable parameter choice needs user abundant experience and correct judgment on the information offered by the problem. More important thing is that these heuristic parameters will influence the convergence characteristic of the algorithm. Because of this even experienced users may choose the not appropriate parameter and then make the problem unable to get effective solution. It needs to carry on some research on these parameters more and more. Here we choose the control parameters as an optimization question in the particle swarm algorithm. Thus heuristic function in the PSO can be controlled by the ordinal genetic algorithm and we form the composite particle swarm optimization algorithm. The primary advantage of the algorithm is that it can't get into the local best solution. In fact the change of the controlling parameters is exactly a kind of positivefeedback; and the illuminative parameters needn't be considered by the users. Because group intelligent algorithm itself has a lot of advantages: The individuals cooperating in the colony are distributed so that they are more adapting to the current work state in the net condition; there isn't central controlling and data, so the system has a stronger robust. It can't affect the whole solving because certain or some individuals'trouble; the system can cooperate by the strimergt not the communications among the individuals, so it has a better scalability. The increased communication spending with the increased individuals in the system is very little; the individual capability in the system is simple, so every individual performing time is very short. And it can realize easily. It has the capability of simplicity.Just because very strong calculation robustness, implicit inherent parallel, the fast global and local search capability, it will improve the solving efficiency greatly to combine the group intelligence with the genetic algorithm. It will be natural to solve under-constraint and over-constraint problems. It will be able to solve some problems that are difficult by other methods. 3.We should adopt the Path Tracking Homotopy Iteration Method to solve the geometric constraint problems. We give a further improvement on the number value method and non-linear equation group method in the geometric constraint solving. It will simplify the solving of non-linear equation group. It will accelerate the solving speed in a certain meaning. The ordinary method is Newton iteration method for the numerical solving. Generally, the method can get the solution quickly, but it needs a nice initialization value and it is quite sensitive to the initialized value. Using the method, when the initialization value changed a little, it may lead to emanative or converge to the solution that the user doesn't want. Because of the random of the designer in the initial design stage, the initial condition is not very good so that the Newton-Raphson method can't be convergent. And it can bring the problems that we can't judge the reason of having no solutions situation is that the system itself can't satisfy the constraint condition or the solving algorithm itself has the disadvantage. For the users the best solution is to adjust the initial location of the system and to judge which reason has caused the solving process to fail. Almost all the CAD systems are belonged to the alternant systems, but we can't deny that it has brought huge inconvenience. The analysis span method is convergent in quite range, and we can judge if there is no solution in a given range, by the method we can also solve all the solutions in the range if there exist solutions, but there still exist problem choosing appropriate range of the initialization value. Homotopy can overcome this shortcoming in a certain degree.