An Efficient Conflict Detection and Resolution Scheme for Geometric Constraints Using a Pruning and Backtracking Strategy

Abstract

Identifying and eliminating conflicts and redundancies between geometric constraints is crucial for effective constraint resolving in engineering design. This research proposes a graph-based conflict detection and resolution scheme for geometric constraint systems with both equality and inequality constraints based on numerical methods using a pruning and backtracking strategy. Initially, the minimum subset of conflicting constraints is detected by traversing all connected subgraphs of the original constraint graph in a pruning manner. The traversal process is encoded in a directed acyclic graph (DAG). The solvability of each constraint subgraph is determined by solving its equivalent algebraic system using variants of the Levenberg–Marquardt (LM) algorithm (Ma, 2008, “A Globally Convergent Levenberg–Marquardt Method for the Least l2-Norm Solution of Nonlinear Inequalities,” Appl. Math. Comput., 206(1), pp. 133–140; Amini et al., 2018, “An Efficient Levenberg–Marquardt Method With a New LM Parameter for Systems of Nonlinear Equations,” Optimization, 67(5), pp. 637–650) and verifying the solution. Inconsistencies between conflicting constraints are eliminated by modifying or discarding constraints recommended by a set of criteria. Finally, the resolution is validated by backtracking ancestor subgraphs along the paths of the DAG. Experimental results demonstrate the effectiveness of the proposed framework in handling inconsistent overconstrainedness between geometric constraints in various parametric forms, including those arising from violations of geometric rules or theorems.