Journal of Artificial Intelligence Rearch 4 (1996) 419-443Submitted 2/96; published 6/96
A Principled Approach Towards Symbolic
Geometric Constraint Satisfaction
华浦英语Sanjay Bhansali BHANSALI@EECS.WSU.EDU School of EECS, Washington State University
Pullman, WA 99164-2752
Glenn A. Kramer GAK@EIT Enterpri Integration Technologies, 800 El Camino Real
Menlo Park, CA 94025
Tim J. Hoar TIMHOAR@MICROSOFT Microsoft Corporation一帆顺风
One Microsoft Way, 2/2069
Redmond, WA 98052
难忘的你
Abstract
An important problem in geometric reasoning is to find the configuration of a collection of geometric bodies so as to satisfy a t of given constraints. Recently, it has been suggested that this problem can be solved efficiently by symbolically reasoning about geometry. This approach, called degrees of freedom analysis, employs a t of specialized routines called plan fragments that specify how to change the configuration of a t of bodies to satisfy a new constraint while prerving existing constraints. A potential drawback, which limits the scalability of this approach, is concerned with the difficulty of writing plan fragments. In this paper we address this limitation by showing how the plan fragments can be automatically synthesized using first principles about geometric bodies, actions, and topology.
1. Introduction
An important problem in geometric reasoning is the following: given a collection of geometric bodies, called geoms, and a t of constraints between them, find a configuration– i.e., position, orientation, and dimension – of the geoms that satisfies all the constraints. Solving this problem is an integral task for many applications like constraint-bad sketching and design, geometric modeling for computer-aided design, kinematics analysis of robots and other mechanisms (Hartenberg & Denavit, 1964), and describing mechanical asmblies.
General purpo constraint satisfaction techniques are not well suited for solving constraint problems involving complicated geometry. Such techniques reprent geoms and constraints as algebraic equations, who real solutions yield the numerical values describing the desired configuration of the geoms. Such equation ts are highly non-linear and highly coupled and in the general ca require iterative numerical solutions techniques. Iterative numerical techniques are not particularly efficient and can have problems with stability and robustness (Press, Flannery, Teukolsky & Vetterling, 1986). For many tasks (e.g., simulation and optimization of mechanical devices) the same equations are solved repeatedly which makes a compiled solution desirable. In theory, symbolic manipulation of equations can often yield a non-iterative, clod form solution. Once found, such a clod-form solution can be executed very efficiently.
B HANSALI, K RAMER &H OAR
However, the computational intractability of symbolic algebraic solution of the equations renders this approach impractical (Kramer, 1992; Liu & Popplestone, 1990).
In earlier work Kramer describes a system called GCE that us an alternative approach called degrees of freedom analysis (1992, 1993). This approach is bad on symbolic reasoning about geo
metry, rather than equations, and was shown to be more efficient than systems bad on algebraic equation solvers. The approach us two models. A symbolic geometric model is ud to reason symbolically about how to asmble the geoms so as to satisfy the constraints incrementally. The "asmbly plan" thus developed is ud to guide the solution of the complex nonlinear equations - derived from the cond, numerical model - in a highly decoupled, stylized manner.
The GCE system was ud to analyze problems in the domain of kinematics and was shown to perform kinematics simulation of complex mechanisms (including a Stirling engine, an elevator door mechanism, and a sofa-bed mechanism) much more efficiently than pure numerical solvers (Kramer, 1992). The GCE has subquently been integrated in a commercial system called Bravo TM by Applicon where it is ud to drive the 2D sketcher (Brown-Associates, 1993). Several academic systems are currently using the degrees of freedom analysis for other applications like asmbly modeling (Anantha, Kramer & Crawford, 1992), editing and animating planar linkages (Brunkhart, 1994), and feature-bad design (Salomons, 1994; Shah & Rogers, 1993).
GCE employs a t of specialized routines called plan fragments to create the asmbly plan.
A plan fragment specifies how to change the configuration of a geom using a fixed t of operators a
nd the available degrees of freedom, so that a new constraint is satisfied while prerving all prior constraints on the geom. The asmbly plan is completed when all constraints have been satisfied or the degrees of freedom is reduced to zero. This approach is canonical: the constraints may be satisfied in any order; the final status of the geom in terms of remaining degrees of freedom is the same (p. 80-81, Kramer, 1992). The algorithm for finding the asmbly procedure has a time complexity of O(cg) where c is the number of constraints and g is the number of geoms (p. 139, Kramer, 1992).英语过渡词
Since the crux of problem-solving is taken care of by the plan fragments, the success of the approach depends on one’s ability to construct a complete t of plan fragments meeting the canonical specification. The number of plan fragments needed grows geometrically as the number of geoms and constraints between them increa. Wor, the complexity of the plan fragments increas exponentially since the various constraints interact in subtle ways creating a large number of special cas that need to be individually handled. This is potentially a rious limitation in extending the degrees of freedom approach. In this paper we address this problem by showing how plan fragments can be automatically generated using first principles about geoms, actions, and topology.
Our approach is bad on planning. Plan fragment generation can be reduced to a planning problem by considering the various geoms and the invariants on them as describing a state. Operators are actions, such as rotate, that can change the configuration of geoms, thereby violating or achieving some constraint. An initial state is specified by the t of existing invariants on a geom and a final state by the additional constraints to be satisfied. A plan is a quence of actions that when applied to the initial state achieves the final state.
With this formulation, one could presumably u a classical planner, such as STRIPS (Fikes & Nilsson, 1971), to automatically generate a plan-fragment. However, the operators in this domain are parametric operators with a real-valued domain. Thus, the arch space consists of an infinite number of states. Even if the real-valued domain is discretized by considering real-valued intervals there is still a very large arch space and finding a plan that satisfies the
P RINCIPLED S YMBOLIC G EOMETRIC C ONSTRAINT S ATISFACTION
specified constraints would be an intractable problem. Our approach us loci information (reprenting a t of points that satisfy some constraints)to reason about the effects of various operators and thus reduces the arch problem to a problem in topology, involving reasoning about the interction of various loci.
An issue to be faced in using a conventional planner is the frame problem: how to determine what properties or relationships do not change as a result of an action. A typical solution is to u the assumption: an action does not modify any property or relationship unless explicitly stated as an effect of the action. Such an approach works well if one knows a priori all possible constraints or invariants that might be of interest and relatively few constraints get affected by each action - which is not true in our ca. We u a novel scheme for reprenting effects of actions. It is bad on reifying (i.e., treating as first class objects) actions in addition to geometric entities and invariant types. We associate, with each pair of geom and invariants, a t of actions that can be ud to achieve or prerve that invariant for that geom. Whenever a new geom or invariant type is introduced the corresponding rules for actions that can achieve/prerve the invariants have to be added. Since there are many more invariant types than actions in this domain, this scheme results in simpler rules. Borgida, Mylopoulos & Reiter (1993) propo a similar approach for reasoning with program specifications. A unique feature of our work is the u of geometric-specific matching rules to determine when two or more general actions that achieve/prerve different constraints can be reformulated to a less general action.
Another shortcoming of using a conventional planner is the difficulty of reprenting conditional effec
ts of operators. In GCE an operation’s effect depends on the type of geom as well as the particular geometry. For example, the action of translating a body to the interction of two lines on a plane would normally reduce the body’s translational degrees of freedom to zero; however, if the two lines happen to coincide then the body still retains one degree of translational freedom and if the two lines are parallel but do not coincide then the action fails. Such situations are called degeneracies. One approach to handling degeneracies is to u a reactive planner that dynamically revis its plan at run-time. However, this could result in unacceptable performance in many real-time applications. Our approach makes it possible to pre-compile all potential degeneracies in the plan. We achieve this by dividing the planning algorithm into two phas. In the first pha a skeletal plan is generated that works in the normal ca and in the cond pha, this skeletal plan is refined to take care of singularities and degeneracies. The approach is similar to the idea of refining skeletal plans in MOLGEN (Friedland, 1979) and the idea of critics in HACKER (Sussman, 1975) to fix known bugs in a plan. However, the skeletal plan refinement in MOLGEN esntially consisted of instantiating a partial plan to work for specific conditions, whereas in our method a complete plan which works for a normal ca is extended to handle special conditions like degeneracies and singularities. 1.1 A Plan Fragment Example.
We will u a simple example of a plan fragment specification to illustrate our approach. Domains such as mechanical CAD and computer-bad sketching rely heavily on complex combinations of relatively simple geometric elements, such as points, lines, and circles and a small collection of constraints such as coincidence, tangency, and parallelism. Figure 1 illustrates some fairly complex mechanisms (all implemented in GCE) using simple geoms and constraints.
B HANSALI, K RAMER &H OAR
Stirling Engine
Figure 1. Modeling complex mechanisms using simple geoms and constraints. All the constraints
needed to model the joints in the above mechanisms are solvable using the degrees of freedom approach.
Our example problem is illustrated in Figure 2 and is specified as follows:
Geom-type: circle
Name: $c
Invariants: (fixed-distance-line $c $L1 $dist1 BIAS_COUNTERCLOCKWISE)
驴肉的做法及配料To-be-achieved: (fixed-distance-line $c $L2 $dist2 BIAS_CLOCKWISE)
In this example, a variable-radius circle $c1 has a prior constraint specifying that the circle is at a fixed distance $dist1 to the left of a fixed line $L1 (or alternatively, that a line drawn parallel
to $L1 at a distance $dist1 from the center of $c is tangent in a counterclockwi direction to the circle). The new constraint to be satisfied is that the circle be at a fixed distance $dist2 to the
1We u the following conventions: symbols preceded by $ reprent constants, symbols preceded by ?
reprent variables, expressions of the form (>> parent subpart) denote the subpart of a compound term, parent.
P RINCIPLED S YMBOLIC G EOMETRIC C ONSTRAINT S ATISFACTION To solve this problem, three different plans can be ud: (a) translate the circle from its current position to a position such that it touches the two lines $L2’ and $L1’ shown in the figure (b) scale the circle while keeping its point of contact with $L1’ fixed, so that it touches $L2’ (c) scale and translate the circle so that it touc
hes both $L2’ and $L1’.
Each of the above action quences constitute one plan fragment that can be ud in the above situation and would be available to GCE from a plan-fragment library. Note that some of the plan fragments would not be applicable in certain situations. For example, if $L1 and $L2 are parallel, then a single translation can never achieve both the constraints, and plan-fragment (a) would not be applicable. In this paper we will show how each of the plan-fragments can be automatically synthesized by reasoning from more fundamental principles.
The rest of the paper is organized as follows: Section 2 gives an architectural overview of the system built to synthesize plan fragments automatically with a detailed description of the various components. Section 3 illustrates the plan fragment synthesis process using the example of Figure 2. Section 4 describes the results from the current implementation of the system. Section 5 relates our approach to other work in geometric constraint satisfaction. Section 6 summarizes the main results and suggests future extensions for this work.
2. Overview of System Architecture
Figure 3 gives an overview of the architecture of our system showing the various knowledge compon
ents and the plan generation process. The knowledge reprented in the system is broadly categorized into a Geom knowledge-ba that contains knowledge specific to particular geometric entities and a Geometry knowledge-ba that is independent of particular geoms and can be reud for generating plan fragments for any geom.铁山寺国家森林公园
学校教务管理系统
Figure 3. Architectural overview of the plan fragment generator
2.1 Geom Knowledge-ba
The geom specific knowledge-ba can be further decompod into ven knowledge components.
B HANSALI, K RAMER &H OAR
2.1.1A CTIONS
The describe operations that can be performed on geoms. In the GCE domain, three actions suffice to change the configuration of a body to an arbitrary configuration: (translate g v) which denotes a translation of geom g by vector v; (rotate g pt ax amt) which denotes a rotation of geom g, around point pt, about an axis ax, by an angle amt; and (scale g pt amt) where g is a geom, pt is a point on the geom, and amt is a scalar. The mantics of a scale operation depends on the type of the geom; for example, for a circle, a scale indicates a change in the radius of the circle and for a line-gment it denotes a change in the line-gment’s length. Pt is the point on the geom that is fixed (e.g., the center of a circle).
2.1.2 I NVARIANTS
The describe constraints to be solved for the geoms. The initial version of our system has been designed to generate plan fragments for a variable-radius circle and a variable length line-gment on a fixed workplane, with constraints on the distances between the geoms and points, lines, and other geoms on the same workplane. There are ven invariant types to reprent the constraints.
Examples of two such invariants are:
• (Invariant-point g pt glb-coords) which specifies that the point pt of geom g is coincident with the global coordinates glb-coords, and
• (Fixed-distance-point g pt dist bias) which specifies that the geom g lies at a fixed distance dist from point pt; bias can be either BIAS_INSIDE or BIAS_OUTSIDE depending on whether g lies inside or outside a circle of radius dist around point pt.
2.1.3 L OCI
The reprent ts of possible values for a geom parameter, such as the position of a point on a geom. The various kinds of loci can be grouped into either a 1d-locus (reprentable by a t of parametric equations in one parameter) or a 2d-locus (reprentable by a t of parametric equations in two variables). For, example a line is a 1d locus specified as (make-line-locus through-pt direc) and reprents an infinite line passing through through-pt and having a direction direc. Other loci reprented in the system include rays, circles, parabolas, hyperbolas, and ellips.
2.1.4 M EASUREMENTS
孕四月
The are ud to reprent the computation of some function, object, or relationship between objects. The terms are mapped into a t of rvice routines which get called by the plan fragments. An example of a measurement term is: (0d-interction 1d-locus1 1d-locus2). This reprents the interction of two 1d-loci. In the normal ca, the interction of two 1-dimensional loci is a point. However, there may be singular cas, for example, when the two loci happen to coincide; in such a ca their interction returns one of the locus instead of a point. There may also be degenerate cas, for example, when the two loci do not interct; in such a ca, the interction is undefined. The exceptional conditions are also reprented with each measurement type and are ud during the cond pha of the plan generation process to elaborate a skeletal plan (e Section 3.3).
