Planning Paths for Elastic Objects Under Manipulation ConstraintsOutlineIntroductionRelated WorkProblem DefinitionSlide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Path Planning AlgorithmSlide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Experimental ResultsSlide 24Slide 25Slide 26Slide 27Slide 28ConclusionsPlanning Paths for Elastic Objects Under Manipulation ConstraintsFlorent Lamiraux Lydia E. KavrakiRice UniversityPresented by: Michael AdamsOutline•Introduction•Related Work•Problem Definition•Path Planning Algorithm•Experimental Results•ConclusionsIntroduction•Goal: Plan paths for elastically deformable objects in a static environment•What is hard?–Representing the shape of an object with a possibly infinitely dimensional configuration space–Computing object shapes under actuator loading conditions–Collision checking for a shape-changing objectRelated Work•Paper draws from other fields including:–High dimensional robot planning – random path planning–Mechanics – energy modeling of deformation shapes–Geometric modeling – representation of infinitely dimensional configuration space–Graphics – physically based models of deformable objectsProblem Definition•What objects are we looking at?–Elastically deformable objects constrained by two actuators–Shape is determined by the lowest energy state for a given configuration of the actuators–Only the actuators are responsible for deformations (object cannot touch obstacles)Problem Definition•Configuration–Rest configuration q0–Rest volume V0 in R3–Configuration q corresponds to changing volume from V0 to Vq in R3VoVqConfiguration q0Configuration qProblem Definition•Local Deformation Field–Object deformation is defined by a field of local deformations over the volume of the object–Local deformation at a point x is defined as:•e(x) = ½(U|V – u|v)–Where u&v are two vectors at x before deformation and U&V are the two vectors after deformation and (M|N) is the inner product of M&NProblem Definition•Elasticity and Energy–Reversibility of deformation due to restoring force–Characterize elasticity by the density () of elastic energy at every point x–Eel(q) = V0((x,e(x))dx–This paper considers homogeneous isotropic linear elastic material – (e)Problem Definition•Manipulation Constraints–Actuators constrain a subset of points V0p in V0–Denote M as set of possible actuator positions and m is one these positions in M–For all x in V0p there is a mapping Xm from V0 to VqProblem Definition•Stable Equilibrium Configurations–Motion is slow enough to consider quasi-static paths – only stable equilibrium configurations–Stable equilibrium configurations are shapes at which the elastic energy is minimizedMinimum Energy Cannot form this with two actuatorsProblem Definition•Elastically Admissible Configurations–Elastic materials have a range of elastic deformation, large deformations may exceed this range and permanently deform–A range of elastic e(x) is defined–Admissible configurations are those in which e(x) is within the elastic range for all x in V0Problem Definition•In path planning, “collision-free paths” are not enough – other conditions must be met–Manipulability: every point along the path must meet the actuator constraints–Quasi-static equilibrium: every point along the path must be in stable equilibrium (a minimum energy shape)–Elastic admissibility: no points along the path exceed the elastic limits of the materialPath Planning Algorithm•Geometric Representation–Approximate infinite-dimensional space as some finite-dimensional space–A geometric representation of configuration space is a family, Gn, of finite-dimensional subspaces where:•Limn max dC(q,Gn) = 0 (dC is a distance function)–Most common are polynomial or finite difference representationsPath Planning Algorithm•Computation of Stable Equilibrium Configurations–Stable equilibrium configurations are found by minimizing elastic energy–Elastic energy is computed by integrating the energy density  over the volume (analytically or numerically depending on geometric representation)•Computation of Stable Equilibrium Configurations–Stable equilibrium configurations are found by minimizing elastic energy–Elastic energy is computed by integrating the energy density  over the volume (analytically or numerically depending on geometric representation)Path Planning Algorithm•Algorithm–PRM approach is used, similar to conventional planners•Initial/Final configurations are chosen •Random free stable equilibrium configurations are chosen as nodes in roadmap•Nodes are connected by a local planner to form edges•Decompose deformation and position of object to save computing time and minimize wear on materialPath Planning Algorithm•Node Generation–A random manipulator position is chosen and minimum energy shape calculated and admissibility is checked–Random rigid-body motions are evaluated for collision-free configurations–N collision-free configurations are found for the same deformationPath Planning Algorithm•Node Connection–Each newly generated node is tested for connection with its K closest neighbors–Distance function should account for rigid body transformation and deformation–Local planner checks for collisions and admissibilityPath Planning Algorithm•Enhancement–Under the assumption that unconnected nodes are in difficult parts of the configuration space, add more nodes in these difficult areas–Randomly walk away from unconnected nodes in the same configuration for a certain distance, reflecting off obstacles–A total of M enhancement nodes are addedPath Planning Algorithm•Local Planner–For efficiency, again decouple deformation and position–Each configuration is denoted q = (d,r)–d is deformation and r is position in space of a local reference framexryrzrxdzdydrdPath Planning Algorithm•Local Planner–First checks the path with rigid body motion of the local frame –Then checks the path considering deformation within the local frame–Saves time by avoiding energy minimizationsPath Planning Algorithm•Distance Metric–Distance d(p,q) = dd(p,q) + dr(p,q)–dd is deformation distance, defined as the maximum distance a point moves in the local frame during a deformation–dr is rigid body translation and rotation distance, defined as the Euclidean distance in