CCQ: Efficient Local Planning using
Connection Collision Query


Min Tang 1        Young J. Kim1      Dinesh Manocha2

1-Ewha Womans University, Korea

 2-University of North Carolina at Chapel Hill, U.S.A.



1. To Appear in The Ninth International Workshop on the Algorithmic Foundations of Robotics (WAFR), Dec. 2010(pdf)


2. Ewha Technical Report CSE-TR-2010-01(pdf)



[Abstract]  We introduce a novel proximity query, called connection collision query (CCQ), and use it for efficient and exact local planning in sampling-based motion planners. Given two collision-free configurations, CCQ checks whether these configurations can be connected by a given continuous path that either lies completely in the free space or penetrates any obstacle by at most ε, a given threshold. Our approach is general, robust, and can handle different continuous path formulations. We have integrated the CCQ algorithm with sampling-based motion planners and can perform reliable local planning queries with little performance degradation, as compared to prior methods. Moreover, the CCQ-based exact local planner is about an order of magnitude faster than prior exact local planning algorithms.



Benchmarking Scenarios


The Performance of RRT using DCD and CCQ-based Local Planner. The x-axis represents different benchmarking scenes with different queries such as BL (Boolean query with a linear motion), BS (Boolean query with a screw motion), TL (ToV query with a linear motion), and TS (ToV query with a screw motion) for each benchmark. The y-axis denotes the planning time in seconds for the maze and pipe benchmark, in tens of seconds for the alpha puzzle, and in hundreds of seconds for the car seat. The blue, red and green bars denote the planning time using DCD, CCQs-based, and CCQp-based local planners, respectively.




Robot: CAD piece # of triangles - 2572

Obstacle: Maze # of triangles - 922




Alpha Puzzle

Robot: Alpha puzzle # of triangles - 1008

Obstacle: Alpha puzzle # of triangles - 1008



Car Seat

Robot: Seat # of triangles - 15197

Obstacle: Car body # of triangles - 30790



Robot: Pipe # of triangles - 10352

Obstacle: Machinery # of triangles - 38146


Related Links







Copyright 2010 Computer Graphics Laboratory
Dept of Computer Science & Engineering
Ewha Womans University, Seoul, Korea
Last update: May 15, 2010