Incremental Configuration Space Construction for Mechanism Analysis

Leo Joskowicz, Elisha SacksAAAI 1991

Abstract

This paper presents an incremental algorithm for constructing the configuration space (CS) of complex mechanical assemblies. By decomposing mechanisms into subassemblies and employing a reachability-based search, the method avoids the exponential complexity typically associated with high-dimensional kinematic analysis. The approach is validated on a variety of mechanisms, including a two-speed transmission, demonstrating significant efficiency gains by focusing on physically reachable states and utilizing piecewise linear approximations to maintain computational tractability.

Introduction

In mechanical engineering, understanding the interactions between parts—such as gears, linkages, and sliders—is essential for simulation and design. This kinematic analysis is often framed through the Configuration Space (CS), a high-dimensional map where every point represents a valid spatial arrangement of all components in a machine.

However, traditional CS construction suffers from the "curse of dimensionality." For a machine with many parts, calculating every potential interaction is computationally intractable. A simple 10-part machine could theoretically involve over 35 trillion potential interactions. While most are physically impossible (as parts cannot occupy the same space), standard algorithms often waste significant resources calculating these unreachable states.

Methodology

The proposed algorithm utilizes a three-step "divide and conquer" strategy to manage complexity:

  1. Decomposition: The mechanism is broken down into simpler subassemblies, such as a pair of gears or a single linkage.
  2. Local Analysis: The CS for these small pairs is constructed and partitioned into Uniform Motion Regions, where parts maintain consistent contact and move predictably.
  3. Incremental Composition: This core innovation starts at the machine's initial state and "searches" outward. The algorithm only calculates regions that are physically reachable from the current state, effectively filtering out the vast majority of the theoretical search space.

To ensure speed, the algorithm employs piecewise linear approximations for complex part geometries. By creating "inner" and "outer" boundaries for shapes, it can use efficient linear inequality solvers (such as BOUNDER) to determine configuration feasibility.

Key Insights: Reachability as a Filter

A primary insight of this work is that real-world machines are "tightly coupled," meaning most theoretical configurations are blocked by physical constraints. By focusing on reachability, the algorithm ignores the bulk of the search space.

The state transition graph for a two-speed transmission, showing reachable configurations (low, neutral, high) from a starting state.

Furthermore, the authors utilize relative coordinates for parts moving along the same axis (e.g., gears on a single shaft) to reduce mathematical complexity. They argue that a qualitatively correct "approximate" CS is often more valuable than an exact one, provided the linear approximations do not miss real behaviors.

Case Study and Results

The authors validated their method using a variety of case studies, most notably a complex two-speed transmission.

Schematic of the two-speed transmission used for validation, featuring gears G1-G4 and a shifter E.

In the transmission example, the incremental reachability filter allowed the algorithm to describe the machine's behavior by checking only 13 component sets. Without this filter, the system would have been forced to process 19,600 sets. On 1991-era hardware, this complex transmission was analyzed in just 5 minutes. Additionally, a survey of 2,500 mechanisms from the Artobolevsky encyclopedia confirmed that this approach could handle approximately two-thirds of all known mechanism types.

Limitations and Future Work

While efficient, the use of "outer" linear approximations can occasionally predict "spurious" regions—motions that appear possible in the model but are blocked in reality. The current version also struggles with highly non-linear components, such as logarithmic cam slots. Future work suggests a hybrid approach, where standard cases are handled by fast linear approximations and complex non-linearities are passed to more intensive algebraic solvers.

Summary updated

BibTeX
@inproceedings{joskowicz1991incremental,
  author = {Leo Joskowicz and Elisha Sacks},
  title = {{Incremental Configuration Space Construction for Mechanism Analysis}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure