Leo Joskowicz

ICRA Conference 2005 Conference Paper

Geometric computation for assembly planning with planar toleranced parts

• Yaron Ostrovsky-Berman
• Leo Joskowicz

The assembly planning problem has received significant attention due to its importance in autonomous manufacturing. Typical assembly planners assume that parts have nominal shapes, while in reality their geometry varies according to the tolerance specifications. To account for toleranced parts, an assembly plan must be feasible for all possible variations of its components. Despite its practical importance, very few works address this problem. This paper presents a general framework for mechanical assembly planning with toleranced planar parts and shows how to incorporate it into existing planners. Our framework uses a general tolerancing model for parts: vertices are standard elementary functions of the part dimensions, which are allowed to vary within tolerance intervals. The relative position of parts is uniquely determined by an assembly graph, which defines constraints between features of neighboring parts. The assembly graph supports placements of parts with rotational degrees of freedom, cyclic relations, and conditional constraints, which occur in non-nominal contacts between edges. Using this framework, we show how to augment existing algorithms for useful motion types, including single and multiple step translations, and infinitesimal rigid motions. We demonstrate the dramatic reduction in the number of valid assembly plans when tolerances are introduced.

ICRA Conference 1999 Conference Paper

Contact Analysis of Spatial Fixed-Axes Pairs Using Configuration Spaces

• Iddo Drori
• Leo Joskowicz
• Elisha Sacks

We present the first configuration space computation algorithm for pairs of rigid parts that move along fixed spatial axes. The motivation is contact analysis for mechanical design of spatial systems and of planar systems with axis misalignment. The part geometry is specified in a parametric boundary representation using planes, cylinders, and spheres. Our strategy is to exploit the specialized part geometry and the 2D structure of the configuration space to: 1) derive low-degree algebraic contact equations in the two part motion parameters, which can readily be solved to obtain contact curves, and 2) to use a practical planar configuration space construction algorithm. We demonstrate a preliminary implementation on three representative pairs, none of which is covered by other contact analysis algorithms. We show how the program is used in answering design questions.

AIJ Journal 1999 Journal Article

Understanding mechanical motion: From images to behaviors

• Tzachi Dar
• Leo Joskowicz
• Ehud Rivlin

We present an algorithm for producing behavior descriptions of planar fixed axes mechanical motions from image sequences using a formal behavior language. The language, which covers the most important class of mechanical motions, symbolically captures the qualitative aspects of objects that translate and rotate along axes that are fixed in space. The algorithm exploits the structure of these motions to robustly recover the objects behaviors. It starts by identifying the independently moving objects, their motion parameters, and their variation with respect to time using normal optical flow analysis, iterative motion segmentation, and motion parameter estimation. It then produces a formal description of their behavior by identifying individual uniform motion events and simultaneous motion changes, and parsing them with a motion grammar. We demonstrate the algorithm on three sets of image sequences: mechanisms, everyday situations, and a robot manipulation scenario.

IROS Conference 1998 Conference Paper

Efficiently testing for unboundedness and m-handed assembly

• Fabian Schwarzer
• Florian Bieberbach
• Achim Schweikard
• Leo Joskowicz

We address the problem of efficiently determining if the intersection of a given set of d-dimensional halfspaces is unbounded. It is shown that detecting unboundedness can be reduced to a single linear range computation followed by a single linear feasibility test. In contrast, detecting unboundedness is at least as hard as linear feasibility testing and maximization. Our analysis suggests that algorithms for establishing linear unboundedness can be used as a basis of simple and practical algorithms in motion planning, insertability analysis and assembly planning. We show that m-handed assembly planning can be reduced to testing for unboundedness. A valid motion sequence can be computed in polynomial time, if the parts are not already separated in their initial placement. No polynomial algorithms were previously known for this problem. We present experimental results obtained with an implementation of our algorithms.

ICRA Conference 1998 Conference Paper

Understanding Mechanism: From Images to Behaviors

• Tzachi Dar
• Leo Joskowicz
• Ehud Rivlin

Presents a method for recognizing mechanisms and describing their behaviours from image sequences showing their relations. It uses a simple and expressive language for describing the behaviour of fixed-axes mechanisms. The language symbolically captures the important aspects of the kinematics and the simple dynamics of the mechanism. We show how this language combined with a vision system can automatically identify mechanisms and their behaviours from a sequence of images.

ICRA Conference 1997 Conference Paper

Dynamical simulation of assemblies of planar, 1 DOF parts with changing contacts using configuration spaces

• Elisha Sacks
• Leo Joskowicz

We present an algorithm for dynamical simulation of rigid-body mechanical systems with changing contact topologies based on configuration spaces. The algorithm advances the state of the art in contact analysis, which is the main bottleneck in dynamical simulation. The task is to identify the touching parts and to compute the ensuing contact forces. Our algorithm computes the configuration spaces of all pairs of parts and uses them as contact models. It overcomes the limitations of mechanical systems simulators, which require precomputed contact models, and of general-body simulators, which perform contact analysis on the part models at every time step. Neither approach is practical for mechanisms with multiple contacts and complex contact geometry, such as clock escapements, chain gears, and part feeders. We describe a configuration space simulator for assemblies of planar parts with one degree of freedom apiece and demonstrate it on two mechanisms with many complex contacts.

AIJ Journal 1996 Journal Article

Efficient compositional modeling for generating causal explanations

• P.Pandurang Nayak
• Leo Joskowicz

Effective problem solving requires building adequate models that embody the simplifications, abstractions, and approximations that parsimoniously describe the relevant system phenomena for the task at hand. Compositional modeling is a framework for constructing adequate device models by composing model fragments selected from a model fragment library. While model selection using compositional modeling has been shown to be intractable, it is tractable when all model fragment approximations are causal approximations. This paper addresses the reasoning and knowledge representation issues that arise in building practical systems for constructing adequate device models that provide parsimonious causal explanations of how a device functions. We make four important contributions. First, we present a representation of class level descriptions of model fragments and their relationships. The representation yields a practical model fragment library organization that facilitates knowledge base construction and supports focused generation of device models. Second, we show how the structural, behavioral, and functional contexts of the device define model adequacy and provide the task focus and additional constraints to guide the search for adequate models. Third, we describe a novel model selection algorithm that incorporates device behavior with order of magnitude reasoning and focuses model selection with component interaction heuristics. Fourth, we present the results of our implementation that produces adequate models and causal explanations of a variety of electromechanical devices drawn from a library of 20 components and 150 model fragments.

ICRA Conference 1994 Conference Paper

Configuration Space Computation for Mechanism Desigu

• Leo Joskowicz
• Elisha Sacks

We describe the HIPAIR configuration space computation program for higher pairs and show how it automates reasoning about shape and motion for mechanism design. We describe an interactive parametric design module that combines configuration space computation with differential constraint satisfaction. HIPAIR handles pairs of 2. 5D parts with two degrees of freedom, including pairs with intermittent, simultaneous, and degenerate contacts. This class contains 90% of 2. 5D pairs and 80% of all higher pairs according to our survey of 2500 mechanisms. We have tested HIPAIR on over 100 pairs, including gears, cams, ratchets, and escapements. It analyzes pairs with thousands of contacts in under ten seconds. The configuration spaces encode the relations among part shapes, part motions, and overall behavior in a concise, complete, and explicit format. They help designers analyze part interactions, implement functions, identify failure modes, and modify designs. >

AAAI Conference 1994 Short Paper

HIPAIR: Interactive Mechanism Analysis and Design Using Configuration Spaces

• Leo Joskowicz

We present an interactive problem solving environment for reasoning about shape and motion in mechanism design. Reasoning about shape and motion plays a central role in mechanism design because mechanisms perform functions by transforming motions via part interactions. The input motion, the part shapes, and the part contacts determine the output motion. Designers must reason about the interplay between shape and motion at every step of the design cycle.

AAAI Conference 1994 Conference Paper

HIPAIR: Interactive Mechanism Analysis and Design Using Configuration Spaces

• Leo Joskowicz

We present an interactive problem solving environment for reasoning about shape and motion in mechanism design. Reasoning about shape and motion plays a central role in mechanism design because mechanisms perform functions by transforming motions via part interactions. The input motion, the part shapes, and the part contacts determine the output motion. Designers must reason about the interplay between shape and motion at every step of the design cycle.

AIJ Journal 1991 Journal Article

Computational kinematics

• Leo Joskowicz
• Elisha P. Sacks

We present a kinematic analysis algorithm for mechanisms built of rigid parts, such as door locks, gearboxes, and transmissions. The algorithm produces a concise and complete description of the kinematics of a mechanism. It optimizes the computation by decomposing complex mechanisms into subassemblies, deriving the kinematics of the subassemblies, and incrementally composing the results. We define a class of mechanisms for which kinematic analysis is feasible by restricting the shapes, motions, and interactions of parts. The feasible class contains linkages, mechanisms whose parts move along fixed spatial axes, and combinations of the two types. We show that the feasible class covers most mechanisms by surveying 2500 mechanisms from an engineering encyclopedia. We implement the kinematic analysis algorithm for fixed-axes mechanisms. The inputs are the shapes and initial configurations of the parts. The output is a region diagram, a partition of the mechanism configuration space into regions that characterize its operating modes. The program computes the region diagram by identifying motion axes and interacting pairs of parts, partitioning the pairwise configuration spaces, and composing them. Coupling the program with existing linkage analysis packages covers most feasible mechanisms. We identify classes of infeasible mechanisms and describe possible analysis strategies for them.

AAAI Conference 1991 Conference Paper

Incremental Configuration Space Construction for Mechanism Analysis

• Leo Joskowicz

We present an incremental configuration space (CS) construction algorithm for mechanisms described as collections of subassemblies of rigid parts. The inputs are the initial subassembly configurations and the subassembly CSs partitioned into uniform motion regions in which part contacts are constant and motions are monotonic. The output is a partition of the mechanism CS into uniform motion regions. The algorithm optimizes CS construction by incrementally enumerating and testing only the regions reachable from the initial configuration. We implement the algorithm for subassemblies whose uniform motion regions are polyhedral or are of dimension two or lower. The program constructs the exact CS when possible and an approximate CS otherwise. The approximate CS usually is qualitatively correct and in good quantitative agreement with the true CS. The program covers most mechanisms composed of linkages and fixed-axes kinematic pairs, two subassembly types for which CS construction programs are available.

IJCAI Conference 1989 Conference Paper

Simplification and Abstraction of Kinematic Behaviors

• Leo Joskowicz

AAAI Conference 1988 Conference Paper

From Kinematics to Shape: An Approach to Innovative Design

• Leo Joskowicz

We address the problem of designing the shape of solid objects to satisfy a given set of functional specifications. In particular, we show how to design elementary components of mechanical devices (kinematic pairs) from a description of their desired behavior and a set of constraints. This is done using a backtracking algorithm that modifies (or creates) object shapes by adding and deleting line and arc segments to the objects’ contours. These modifications are guided by the configuration space description of the desired behavior. The algorithm is extended to handle both qualitative and causal descriptions of desired behaviors. This work is based on the theory of shape and kinematics developed in [Joskowicz, 19881.

AAAI Conference 1987 Conference Paper

Shape and Function in Mechanical Devices

• Leo Joskowicz

This paper describes a two-step algorithm for the qualitative analysis of mechanical devices. The first step takes the geometrical description of the parts and their initial position and produces a description of the possible relative motions of pairs in contact by computing the configuration space of those pairs with respect to selected motions. Given the possible relative motions and an input motion, the second step computes the actual motion of each object for fixed axis mechanisms using a constraint propagation, label inferencing technique. The output is a state diagram describing the motion of each part in the mechanism.