Geometric Reasoning About Mechanical AssemblyGoals and uses of Assembly PlanningGeneralized Motion Planning approachHierarchical approachAssembly TreeCriticality based decompositionDirectional Blocking Graph of a Simple Assembly (translation only)Non Directional Blocking GraphThe NDGBWork backwards from assembled state when generating NDGBGenerating AlgorithmsCalculating DBG for Adjacent Regular RegionsVisualProblems with using only infinitesimal translationsInfinitesimal generalized motionsGeneralized motionAddressing AccessibilityFurther ExtensionsComputation timeResults from TestingAssess ComplexityComplexityNumber of FingersConclusionSlide 25Geometric Reasoning About Geometric Reasoning About Mechanical AssemblyMechanical AssemblyBy Randall H. Wilson and Jean-Claude LatombePresented by Salik Syed and Denise JonesGoals and uses of Assembly Goals and uses of Assembly PlanningPlanningUnderstand how objects are assembled, and their complexity.Can be used to guide designers and engineers to create more efficient products by allowing them to understand service and manufacturing costs at design time.Generalized Motion Planning Generalized Motion Planning approachapproachWe can look at this as a general Motion planning problem.Problems:● Complicated planning● Key issues such as grasping are not known● We don't know what the manipulator will be.●We can instead use a “Virtual Manipulation system”Hierarchical approachHierarchical approachInstead we can abstract the notion of manipulators into a “virtual manipulation system”. Solve a succession of simplified but increasingly more realistic planning problems.Different levels of abstraction Free flying objects then at lower levels abstractions of different grippers/machines introducedThe paper assumes the most simplified manipulation system (all objects are free flying)Assembly TreeAssembly TreeCriticality based decompositionThe space is divided based on criticalities of the translational freedoms of part pairsThis is done using the notion of a “Non-Directional Blocking Graph”Directional Blocking Graph of a Directional Blocking Graph of a Simple Assembly (translation only)Simple Assembly (translation only)A BC DBDAC DBDAC DNon Directional Blocking GraphNon Directional Blocking GraphRegions are determined by comparing the local freedoms of two parts.Every such region is regular : in the sense that the Directional Blocking graph remains constant when d varies over it.Denoted as G(R,A) Unit Circle S1 represents directionsBAC DEach region has a DBG associated with it.The NDGBThe NDGBWe can look at the complete NDGB of an assembly as an implicit representation of the set of all possible assembly algorithms.However, these algorithms may or may not be correct given accessibility constraintsWork backwards from assembled Work backwards from assembled state when generating NDGBstate when generating NDGB Goal state generally more constrained than initial configuration.... contacts in goal can be used to filter out impossible motionsGenerating AlgorithmsGenerating AlgorithmsNDGB is used to determine candidate algorithms and candidate portionsThe set of all candidate portions is computed in O(r^2u) time where r is the number of pairs of parts and u is the number of candidate partitioningGenerating a candidate algorithm takes O(r^2n) time where n is the number of parts in an assembly.Calculating DBG for Adjacent Calculating DBG for Adjacent Regular RegionsRegular Regions●Simple way to optimize calculating adjacent regions.●Start by computing G(R1)●To generate G(R2) Take each contact edge in G(R1) that is parallel to D (Ek ). (where D is the diameter of S1 that ends at R2)●If the inner product of any direction in R1 and the outgoing normal to Pi in Ek is strictly positive then retract 1 from the weight of the arc connecting Pi to PjVisualVisualABS1:R1R2Normal dot D is positive for all D in R1DGB(R1):DGB(R2):A BA BNote : If R1 is a singleton, then we ADD rather than Subtract weightsR1R2Problems with using only Problems with using only infinitesimal translations infinitesimal translations ●Doesn't guarantee accessibility●Doesn't allow rotational motionsThere may be times when a translation is not possible but a rotation is:Assembly cannot be decomposed into translations.The set of translational DBGs cannot be represented discretelyInfinitesimal generalized motionsInfinitesimal generalized motions●Extension from 2d to 3d:Partition S2 rather than S1 (translation in 3d)●To extend this to general motion we must use 6D vectors. Regions are now partitions of S5.S1S2S5 (ish?)Generalized motionGeneralized motion●dX = (dx,dy,dz,da,dβ,dץ(●Motion of Vertex V of Pi is JvdX Where Jv Is the Jacobian of transform that gives coordinates of V in the frame of Pj●NF JvdX ≥ 0 if the face does not intersect.●NF JvdX = 0 defines a 5D hyperplane in 6D space. These planes define the boundaries of our regions.NFJvdX A1 A2 A3 A4 A5 A6 B1 B2 B3 B4 B5 B6C1 C2 C3 C4 C5 C6dX JvdXIn this case NF JvdX<0Addressing Accessibility●A new variant of the NDGB : Analyzes interferences for a family of non-infinitesimal motions (infinite translation)●Two parts A,B (may or not be touching)... B blocks the “infinite translation” of A if the swept volume of A along d ●Important because the swept volume guarantees accessibility, while infinite translation does not.●Set of direction where A is blocked is where Minkowski difference of A,B blocks origin.B A A A A A A A A A A A A A A A A A A A A ABDFurther Extensions●Each NDGB is defined for a limited family of motions and describes only the class of assembly algorithms for these motions.●One can imagine other NDBGs (for instance moving K+1 assemblies together simultaneously)●This can be represented by the partitioning of S^3m-1 (3 directions for translation)Computation timeComputation time●A singleton occurs only when 5 hyperplanes intersect, this means the arrangement contains O(K^5) regions where K is number of vertices●Constructed in O(K^5) time using a mutli-dimensional topological sweep (?)●DBG build in O(K) time, Crossing rule can be used to make NDBG in O(RK^5) time. Where is R is O(N^2) (number of pairs of contacts)Results from TestingResults from TestingNot goodGoodAssess