Research On The Key Techniques Of Geometric Constraint Solving

Geometric constraint solving can be regarded as automated geometry entity design such as enterprise product model, molecular structure modeling and engineering design drawing and so on. As the core of modern parametric and variational design system, it is broadly applied to many fields such as product modeling, assembly design, virtual reality, kinematics analysis, chemical molecular modeling, robot dynamics, teaching geometry and is one of magnificent signs of modern computer aided design(CAD) and computer aided manufacture(CAM).Through more than three decade of unremitting efforts of domestic and foreign scholars, geometric constraint solving has achieved breakthrough of more problems having pertinence and can effectively solve quite a number of problems faced during designing. However, gaps still exist to a generalized method for solving all geometric constraint systems. This paper aims at researching the core of parametric and variational design system-geometric constraint solving and proposes systematic geometric constraint solving methods, which mainly includes:( I) Define the planning graph and propose the completeness increment decomposition technique of geometric constraint system. It is proved that the minimum influence domain based on minimum operation granularity is:(1) The geometric primitive itself if the operand is an assembly geometric primitive.(2) The independent-solvable fundamental constraint domain and the assembly geometric constraint contained in the sub-domain.(3) The residual set splitting full vertices in the generalized constraint closed-cycle generated when assembling a geometric constraint between full vertices.(4) The primitives an assembly geometric constraint associates if no constraint closed-cycles generated.(5) The residual sub-domain of a fundamental constraint domain set and its dependence domains when dismantling a geometric constraint from the set.(6) The residual sub-domain excluding a geometric primitive and the geometric constraints associating it of a fundamental constraint domain set and its dependence domains when dismantling the geometric primitive from the set. Therefore, the minimum influence domain is confirmed based on the operation with minimum granularities and the maximized decomposition of geometric constraint system including under-constrained systems can be realized based on the complete-incremental construction of the planning graph by the incremental Latham-Middleditch algorithm(ILMA), the search method of global generalized constraint closed-cycle, the method of augmentation search and the traverse method of partial bounded neighbourhood, so that the realtime response demand of geometry entity design can be satisfied.( I I) In consideration of the strong robustness, the high parallel performance and balancing the performance between the global search and the partial rapid convergence of evolution calculating technology based on swarm intelligence, equations of geometric constraint system are translated into optimization problems awaiting solved and the Hierarchy and Adaptive Size Particle Swarm Optimization Algorithm(HASPSO) for geometric constraint solving is proposed on the basis of the basic Particle Swarm Optimization(PSO) algorithm.The HASPSO mainly follows(1) Hierarchy: rank population and makes higher-hierarchy individuals can obtain higher-quality solutions, furtherly accelerate the convergence.(2) Adaptation size: maintaining the diversity characteristics of population is one of important factor of making algorithm converge, in terms of the complexity of geometric constraint system, based on the harmony and stability principle of the Fibonacci sequence and by simulating the behaviors of biological growth and reproduction, the HASPSO gradually expands population size from the hierarchy where a single individual is to subsequent hierarchies. Therefore, the diversity characteristics of population are maintained steadily, the local optimum is avoided and the global search feature is increased. Theoretical analysis and experiment show that compared with the traditional PSO algorithm and some related improved algorithm, HASPSO can greatly solving efficiency and solving stability and is an effective method for geometric constraint solving.( III) Propose Artificial Bee Colony(ABC) Algorithm Combining Immune and Graph Knowledge Transfer Mechanism(IA&GKT-ABC) for Geometric Constraint Solving. The ABC is a new type of evolution calculating technology based on swarm intelligence proposed in recent ten years, in comparison with the PSO, the ABC has faster convergence rate and higher convergence accuracy.The immune mechanism(AI) has the antibody diversity characteristic of immune system and the function of self-adjustment, generating the food source antibody based on the AI can form stable maintainance strategy of diversity characteristics of population and avoid the slow later convergence rate its reduction. Simultaneously, the AI increases and enhances the space size of parameter set of algorithm and the coupling between parameters. How to confirm the optimal combination of parameter making the search performance of algorithm is vital. Using the Graph Knowledge Transfer(GKT) mechanism to optimize the parameter set of immune ABC can effectively avoid local optimum or slow convergence resulted by blindly selecting the parameter set of algorithm. The GKT selectively transfers the parameter set of algorithm of solved geometric constraint system based on the model transfer graph therefore obtains the optimal running parameters of awaiting solved geometric constraint system. Analysis and experiments show that the IA&GKT-ABC is superior to similar algorithms, it still can satisfy established accuracy and fastly converge for complicated constraint systems.( IV) The prototype-based locus intersection method is proposed(PLIMd). For solving fundamental constraint domain, define the prototype of geometric constraint system based on the planning. The PLIMd confirms:(1) Dismantle constraint closed-cycles and eliminate complete couplings for ensuring the dynamic adjustability of the driving geometric primitive group, the set of geometric constraint Cr dismantled is regarded as satisfied complete coupling constraints when change minimum geometric primitive group.(2) Reconstruct the planning graph of system by dismantling geometric constraints and separate out the no-coupling sharing sole constraint chain for effectively judging whether the current chain satisfies the constraint set Cr.(3) By satisfying the dismantled constraints again based on recursion, uniformly adjust shapes of the geometric entities to ensure that the single constraint chains are solvable.(4) Dynamically adjust the sharing sole constraint chains by specific step size until Cr is satisfied so that the optimal solution matching the prototype is obtained. In comparison with traditional numerical calculation, the PLIMd reserves geometric property of constraint system and simultaneously, it considers both well- and under-constrained, the two types of constraint systems, so enhances the solving range of geometric constraint system and better meet the demand of entity design.