Adaptive Dynamic Collision Checking for Single and Multiple Articulated Robots in Complex Environments Schwarzer, Saha, and LatombeStatic vs. Dynamic Collision CheckingSlide 3Fixed Resolution MethodsSlide 5Adaptive Dynamic Collision CheckingDefinitionsKey Lemma for Adaptive BisectionSlide 9Adaptive Bisection of Paths ExampleOptimizationsCalculating Terms in the InequalityLower Bound On Distance Betw. Objects: ij(q)Bounding Motions in Workspace i(qa,qb)Slide 15Slide 16Slide 17Summary – Adaptive Bisection Collision CheckerSummaryAdaptive Dynamic Collision Checking for Single and Multiple Articulated Robots in Complex EnvironmentsSchwarzer, Saha, and Latombe CS326A Winter 2004, Presented by Irena PashchenkoStatic vs. Dynamic Collision CheckingStatic checking tests a single configuration q for overlapsAj(q)Ai(q)Static vs. Dynamic Collision CheckingDynamic checking ensure that all configurations on a continuous path are collision-free. qaqbFixed Resolution MethodsFixed Resolution checking is a sequence of static BVH checks along path of motion, divided into  length segments. qaqbFixed Resolution Methods is user selected value. Compromise between efficiency and reliability.qaqbAdaptive Dynamic Collision CheckingAutomatic local adjustment of value  Collisions are never missedDoes not cost much more than classical collision checking.Requires calculation of distances between objects; typically more expensive than plain collision checking.But paper proposed new techniques and heuristics to speed this up.Applicable to straight path segments in c-spaceSuited for scenarios with manipulator arms and/or multiple robotsDefinitionsThe robot and obstacles are defined by: A1,…,An, whose placement in workspace is q=(q1,…,qn)Aj(q)Ai(q)i(qa,qb)ij(q)Ai(qa)Aj(qb)ij(q) ≡ distance(Ai, Aj) i(qa,qb) ≡ curveLength(Ai) on qa… qbKey Lemma for Adaptive BisectionAiqaqbi(qa,qb)qbqaj(qa,qb)AjLemma: If i (qa,qb) + j (qa,qb) < ηij (qa) + ηij (qb),then there exists no collisions between Ai(qa) and Aj(qb) ηij(qa)ηij(qb)Key Lemma for Adaptive BisectionInequality only determines non-collisions.AiqaqbqaAjηij(qb) = 0Collision is defined by zero distance between Ai and Aj, i.e. ηij= 0.Adaptive Bisection of Paths ExampleqaqbqmidRun Inequality TestsRun Inequality test on path segment.[PASS] = no collisions between qa and qb[FAIL] = check if robot makes collision at qmidIf qmid doesn’t have a collision, recursively test both sub-segments until collision is found, or both sub-segments pass inequality test Collisions are never missed!OptimizationsLet Q be the priority queue containing elements objects being checked.If the path segment is collision-free, then the ordering of Q has no impact on running time. But for a colliding path, the calculation can complete as soon as collision is found => ordering matters.Since longer path lengths have higher probability of collision, Q is presorted by decreasing path lengths to potentially find collisions earlier.Calculating Terms in the InequalityHow do we get ij(q) and i(qa,qb) ?i (qa,qb) + j (qa,qb) < ηij (qa) + ηij (qb)Aj(q)Ai(q)i(qa,qb)ij(q)Ai(qa)Aj(qb)Algorithm GREEDY-DIST(Bi,Bj)d = distance(Bi, Bj)If triangles or d > 0, then return d = GREEDY-DIST( Bi, Bj.childLeft )if( > 0 ) = GREEDY-DIST(Bi, Bj.childRight )if(  > 0 ) return min {, }return 0Object iHalf,i1Leaf,i1 Leaf,i2Half,i2Object jHalf,j1Leaf,j1 Leaf,j2Half,j2Lower Bound On Distance Betw. Objects: ij(q) Rectangle Swept Spheres (RSS)Bounding Motions in Workspace i(qa,qb)q4q2q1q3A1A2A3A44 d.o.f. robotJoints: 3 rotational and 1 prismaticD is the max distance traveled by q3L is the length of each rigid linkBounding Motions in Workspace i(qa,qb)q3A3q2A2q4A4q1A1Upper Bound Path LengthRigid BodyA11(qa,qb)L qa,1qb,12(qa,qb)2L qa,1qb,1L qa,2qb,23(qa,qb)(2LD) qa,1qb,1(LD)qa,2qb,2qa,3qb,34(qa,qb)(3LD) qa,1qb,1(2LD) qa,2qb,2qa,3qb,3L qa,4qb,4A2A3A4Summary – Adaptive Bisection Collision CheckerEfficient and robust way to determine collision-free paths.Advantages over fixed resolution checker:Never misses a collisionEliminates need for determining resolution factor: There is room for improvement. Derive tighter bounds on path lengths .Greedy Distance Computation algorithm, nearly as efficient as pure collision checkerFast technique for bounding lengths of paths traced out in workspaceHeuristics for ordering collisions testsSummaryLimitations:Not the best method if one wants to determine the first collision configuration moving from qa to qbBad-case scenario: two moving objects stay very close along a long section of a path segment. (The key inequality fails to do its job here, and does not sample the path segments at coarser