US5617510A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Dependency graph solution for constraint systems
Assignee: Schlumberger Technology Corp
•
Filing: 1995-04-12
•
Granted: 1997-04-01
•
Expires: 2015-04-12
Abstract
Abstract A method, useful in computer-aided design, of identifying possible solutions to an over-constrained system having a collection of entities and constraints. The method represents the entities in terms of degrees of freedom and incrementally assembles the system by adding entities, satisfying constraints and reducing the degrees of freedom of the entities. For an over-constrained system, the method constructs a dependency graph of the system and identifies the set of constraints which over-constrains the system. The over-constraining set includes the constraint which initiated the over-constraint and those constraints back traced in the dependency graph from the initiating constraint. Removal of one or more constraints from the over-constraining set results in a solvable fully or under-constrained system. Intelligent selection of the removed constraint may increase computational efficiency or system stability. The method is useful in diverse constraint satisfaction problems, particularly geometric modeling problems such as describing mechanical assemblies, constraint-based sketching and design, geometric modeling for CAD, and kinematic analysis of robot and linkage mechanisms.
Inventors
- 👤 Walid T. Keyrouz
- 👤 Glenn A. Kramer
- 👤 Jahir A. Pabon
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 13:43
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/10; G06F30/17
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
156 words
In a digital computer programmed generally for computer-aided design, a method of generating a solution plan for a geometric constraint system comprising a collection of rigid body geometric entities satisfying a set of constraints, where the set of constraints over-constrain the system, comprising the steps of: representing the rigid body geometric entities in terms of degrees of freedom; incrementally satisfying constraints and systematically reducing the degrees of freedom of the system; adding a constraint to the geometric constraint system reducing the degrees of freedom and resulting in an over-constrained system; identifying the over-constraining set of constraints by (i) constructing a dependency graph describing the constrained relationships between entities; (ii) identifying the constraint which initiated system over-constraint, (iii) identifying the constraints coupled to the initiating constraint by back tracing through the dependency graph, the set of identified constraints comprising the over-constraining set; and generating a solution plan by altering one or more constraints from said over-constraining set.
Claim 2
Dependent Claim
156 words
In a digital computer programmed generally for computer-aided design, a method of generating a solution plan for a geometric constraint system comprising a collection of rigid body geometric entities satisfying a set of constraints, where the set of constraints over-constrain the system, comprising the steps of: representing the rigid body geometric entities in terms of degrees of freedom; incrementally satisfying constraints and systematically reducing the degrees of freedom of the system; adding a constraint to the geometric constraint system reducing the degrees of freedom and resulting in an over-constrained system; identifying the over-constraining set of constraints by (i) constructing a dependency graph describing the constrained relationships between entities; (ii) identifying the constraint which initiated system over-constraint, (iii) identifying the constraints coupled to the initiating constraint by back tracing through the dependency graph, the set of identified constraints comprising the over-constraining set; and generating a solution plan by altering one or more constraints from said over-constraining set.
Claim 3
Dependent Claim
30 words
The method of claim 1, where the geometric rigid bodies are parameterized by a set of configuration variables and the configuration variables describe translational, rotational, and dimensional degrees of freedom.
Claim 4
Dependent Claim
21 words
The method of claim 1, said solution plan comprising the solution steps taken to incrementally satisfy the constraints in the system.
Claim 5
Dependent Claim
30 words
The method of claim 3, including the steps of changing one or more numerical constraint parameters in reusing the solution plan to solve the constraint system by satisfying the constraints.
Claim 6
Dependent Claim
26 words
The method of claim 1, the generating step including identifying a constraint for removal from said over-constraining set by selecting from a set of default constraints.
Claim 7
Dependent Claim
30 words
The method of claim 1, the generating step including identifying a constraint for removal from said over-constraining set where removal of the identified constraint results in a fully constrained system.
Claim 8
Dependent Claim
25 words
The method of claim 1, the generating step including identifying a constraint for removal from said over-constraining set by removing one or more dimensional constraints.
Claim 9
Dependent Claim
26 words
The method of claim 1, the generating step including identifying a constraint for removal from said over-constraining set by selecting from a subset of inconsistent constraints.
Claim 10
Dependent Claim
24 words
The method of claim 1, including the step of identifying subgraphs in the dependency graph and solving the constraints in each subgraph in parallel.
Claim 11
Dependent Claim
41 words
The method of claim 1, including the steps of removing a constraint from the system, identifying portions of the dependency graph that are not affected by the removal of a constraint, and regenerating a solution plan for only the affected portions.
Claim 12
Dependent Claim
16 words
The method of claim 1, said altering step comprising removing said one constraint from the system.
Claim 13
Dependent Claim
17 words
The method of claim 1, said altering step comprising changing the parameter value of said one constraint.
Claim 14
Dependent Claim
27 words
The method of claim 1, including the step of analyzing the system comprising the substeps of replacing said one constraint and removing another constraint from said set.
Claim 15
Dependent Claim
150 words
In a digital computer, a method of determining a solution plan of a geometric constraint system comprising a collection of geometric entities satisfying a set of constraints where the geometric constraint system is over-constrained, comprising the steps of: a. representing the geometric entities with configuration variables describing translational, rotational, and dimensional degrees of freedom; b. constructing a dependency graph with constraints and entities represented as nodes; c. identifying the set of constraints which over-constrain the system by beginning with the over-determined entity node where system over-constraint was detected and identifying the coupled constraint nodes that over determine the beginning entity node by back tracing through the dependency graph; d. altering one of the constraints from the set of constraints reducing the system from over-constraint; and e. building a solution plan of the system as one traversal path of the nodes of the dependency graph after removal of said one constraint.
Claim 16
Dependent Claim
150 words
In a digital computer, a method of determining a solution plan of a geometric constraint system comprising a collection of geometric entities satisfying a set of constraints where the geometric constraint system is over-constrained, comprising the steps of: a. representing the geometric entities with configuration variables describing translational, rotational, and dimensional degrees of freedom; b. constructing a dependency graph with constraints and entities represented as nodes; c. identifying the set of constraints which over-constrain the system by beginning with the over-determined entity node where system over-constraint was detected and identifying the coupled constraint nodes that over determine the beginning entity node by back tracing through the dependency graph; d. altering one of the constraints from the set of constraints reducing the system from over-constraint; and e. building a solution plan of the system as one traversal path of the nodes of the dependency graph after removal of said one constraint.
Claim 17
Dependent Claim
16 words
The method of claim 14, said altering step comprising removing said one constraint from the system.
Claim 18
Dependent Claim
17 words
The method of claim 14, said altering step comprising changing the parameter value of said one constraint.
Claim 19
Dependent Claim
36 words
The method of claim 14, where said altering step comprises removing said one constraint, including the step of analyzing the system comprising the substeps of replacing said one constraint and removing another constraint from said set.
Claim 20
Dependent Claim
143 words
A digital computer programmed generally for computer-aided-design and specially programmed for determining a solution plan for a geometric constraint system where the geometric constraint system comprises a collection of geometric rigid body entities satisfying a set of constraints and the set of constraints over-constrains the geometric constraint system, comprising: means for representing the geometric rigid body entities with configuration variables which describe translational, rotational, and dimensional degrees of freedom; means for identifying the over-constraining constraints which includes means for constructing a dependency graph for describing the constrained relationships between entities; means for identifying the constraint which initiated the system over-constraint, means for identifying the constraints coupled to the initiating constraint by back tracing through the dependency graph the identified over-constraining constraint; and means for generating a solution plan by altering one or more constraints from said over-constraining set reducing the system from over-constraint.
Claim 21
Dependent Claim
143 words
A digital computer programmed generally for computer-aided-design and specially programmed for determining a solution plan for a geometric constraint system where the geometric constraint system comprises a collection of geometric rigid body entities satisfying a set of constraints and the set of constraints over-constrains the geometric constraint system, comprising: means for representing the geometric rigid body entities with configuration variables which describe translational, rotational, and dimensional degrees of freedom; means for identifying the over-constraining constraints which includes means for constructing a dependency graph for describing the constrained relationships between entities; means for identifying the constraint which initiated the system over-constraint, means for identifying the constraints coupled to the initiating constraint by back tracing through the dependency graph the identified over-constraining constraint; and means for generating a solution plan by altering one or more constraints from said over-constraining set reducing the system from over-constraint.
Claim 22
Dependent Claim
14 words
The digital computer of claim 18, including a display for displaying the solution plan.
References Cited (Backward Citations)
US5412762A
Cited
US5410496A
Cited
US5497452A
Cited
US5251290A
Cited
US5390294A
Cited
US5427531A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-03-31 | 2000-09-30 | 2001-04-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-03-31 | 2004-09-30 | 2005-04-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-03-31 | 2008-09-30 | 2009-04-01 | $7700.00 | Window Closed / Lapsed |