Planning from First Principles for Geometric Constraint Satisfaction

Sanjay Bhansali, Glenn A. KramerAAAI 1994

Abstract

Geometric constraint satisfaction is a fundamental challenge in computer-aided design (CAD) and robotics. While degrees of freedom (DOF) analysis offers a computationally efficient alternative to traditional algebraic solvers, it historically relied on manually authored "plan fragments." This paper introduces a two-phase AI planning framework that automatically generates these fragments from first principles of geometry and topology. By utilizing loci to discretize the search space and a secondary elaboration phase to handle geometric degeneracies, the system produces robust, polynomial-time solutions for complex geometric configurations.

Introduction

In fields like CAD and robotic assembly, the ability to position components according to specific constraints—such as tangency or fixed distances—is essential. Traditionally, these problems are addressed using large-scale algebraic equation solvers. However, these solvers are often computationally expensive and provide little insight into the geometric reasoning behind a solution.

A typical geometric constraint problem involving lines and circles.

Degrees of freedom (DOF) analysis offers a more symbolic approach, reasoning about how a part can move. This method relies on "plan fragments"—pre-defined sequences of transformations. Prior to this work, these fragments were hand-coded by experts. The authors propose a system to automate this process, allowing a planner to derive geometric solutions autonomously.

The Two-Phase Planning Framework

The core of the proposed system is a two-phase architecture designed to generate optimized plan fragments.

Architectural overview of the two-phase plan fragment generator.

Phase I: Skeletal Planning

The first phase employs a breadth-first search to identify a sequence of basic geometric operators (translation, rotation, and scaling) that satisfy the target constraints. To manage the potentially infinite search space of real-valued coordinates, the system utilizes Loci. A locus represents the set of all points satisfying a specific constraint (e.g., a circle representing all points at a fixed distance from a center). By intersecting these loci, the planner transforms a continuous geometric problem into a discrete topological search.

Phase II: Elaboration

The skeletal plan is refined in Phase II to account for degeneracies—edge cases where standard geometric assumptions fail. For instance, if a plan requires finding the intersection of two lines, Phase II adds conditional logic to handle scenarios where the lines are parallel or coincident. This "pre-compilation" of exception handling ensures that the resulting fragments are both fast and robust during real-time execution.

Key Innovations

The system introduces several critical concepts for geometric reasoning:

  • Reification of Actions: By associating specific geometric invariants with actions, the authors simplify the "Frame Problem," making the system easier to extend with new geometric primitives.
  • Least Motion Principle: The planner prioritizes transformations that result in the minimal displacement of existing components, ensuring stability in the model.
  • Geometric Unification: Unlike standard syntactic unification in AI, the system uses rules that understand geometric equivalence (e.g., recognizing different descriptions of the same rotation).

Conclusion

The automated generation of plan fragments represents a significant advancement in geometric constraint satisfaction. By moving from manual derivation to a first-principles planning approach, the authors achieved polynomial-time efficiency and high robustness. While initially demonstrated in 2D environments, the framework provides a scalable foundation for more complex 3D geometric reasoning in future CAD and robotic systems.

Summary updated

BibTeX
@inproceedings{bhansali1994planning,
  author = {Sanjay Bhansali and Glenn A. Kramer},
  title = {{Planning from First Principles for Geometric Constraint Satisfaction}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}

Loading related content...

Figure