TechTalks from event: Technical session talks from ICRA 2012

Conference registration code to access these videos can be accessed by visiting this link: PaperPlaza. Step-by-step to access these videos are here: step-by-step process .
Why some of the videos are missing? If you had provided your consent form for your video to be published and still it is missing, please contact

Sampling-Based Motion Planning

  • A Scalable Method for Parallelizing Sampling-Based Motion Planning Algorithms Authors: Jacobs, Sam Ade; Burgos, Juan; Manavi, Kasra; Denny, Jory; Thomas, Shawna; Amato, Nancy
    This paper describes a scalable method for parallelizing sampling-based motion planning algorithms. It subdivides configuration space (C-space) into (possibly overlapping) regions and independently, in parallel, uses standard (sequential) sampling-based planners to construct roadmaps in each region. Next, in parallel, regional roadmaps in adjacent regions are connected to form a global roadmap. By subdividing the space and restricting the locality of connection attempts, we reduce the work and inter-processor communication associated with nearest neighbor calculation, a critical bottleneck for scalability in existing parallel motion planning methods. We show that our method is general enough to handle a variety of planning schemes, including the widely used Probabilistic Roadmap (PRM) and Rapidly-exploring Random Trees (RRT) algorithms.We compare our approach to two other existing parallel algorithms and demonstrate that our approach achieves better and more scalable performance. Our approach achieves almost linear scalability on a 2400 core LINUX cluster and on a 153,216 core Cray XE6 petascale machine.
  • LQR-RRT*: Optimal Sampling-Based Motion Planning with Automatically Derived Extension Heuristics Authors: Perez, Alejandro; Platt, Robert; Konidaris, George Dimitri; Kaelbling, Leslie; Lozano-Perez, Tomas
    The RRT* algorithm has recently been proposed as an optimal extension to the standard RRT algorithm [1]. However, like RRT, RRT* is difficult to apply in problems with complicated or underactuated dynamics because it requires the design of a two domain-specific extension heuristics: a distance metric and node extension method. We propose automatically deriving these two heuristics for RRT* by locally linearizing the domain dynamics and applying linear quadratic regulation (LQR). The resulting algorithm, LQR-RRT*, finds optimal plans in domains with complex or underactuated dynamics without requiring domain-specific design choices. We demonstrate its application in domains that are successively torquelimited, underactuated, and in belief space.
  • SR-RRT: Selective Retraction-Based RRT Planner Authors: Lee, Junghwan; Kwon, Osung; Zhang, Liangjun; Yoon, Sung-eui
    We present a novel retraction-based planner, selective retraction-based RRT, for efficiently handling a wide variety of environments that have different characteristics. We first present a bridge line-test that can identify regions around narrow passages, and then perform an optimizationbased retraction operation selectively only at those regions. We also propose a non-colliding line-test, a dual operator to the bridge line-test, as a culling method to avoid generating samples near wide-open free spaces and thus to generate more samples around narrow passages. These two tests are performed with a small computational overhead and are integrated with a retraction-based RRT. In order to demonstrate benefits of our method, we have tested our method with different benchmarks that have varying amounts of narrow passages. Our method achieves up to 21 times and 3.5 times performance improvements over a basic RRT and an optimizationbased retraction RRT, respectively. Furthermore, our method consistently improves the performances of other tested methods across all the tested benchmarks that have or do not have narrow passages.
  • Sampling-Based Motion Planning with Dynamic Intermediate State Objectives: Application to Throwing Authors: Zhang, Yajia; Luo, Jingru; Hauser, Kris
    Dynamic manipulations require attaining high velocities at specified configurations, all the while obeying geometric and dynamic constraints. This paper presents a motion planner that constructs a trajectory that passes at an intermediate state through a dynamic objective region, which is comprised of a certain lower dimensional submanifold in the configuration/velocity state space, and then returns to rest. Planning speed and reliability is greatly improved using optimizations based on the fact that ramp-up and ramp-down subproblems are coupled by the choice of intermediate state, and that very few (often less than 1%) intermediate states yield feasible solution trajectories. Simulation experiments demonstrate that our method quickly generates trajectories for a 6-DOF industrial manipulator throwing a small object.
  • Towards Small Asymptotically Near-Optimal Roadmaps Authors: Marble, James; Bekris, Kostas E.
    An exciting recent development is the definition of sampling-based motion planners which guarantee asymptotic optimality. Nevertheless, roadmaps with this property may grow too large and lead to longer query resolution times. If optimality requirements are relaxed, existing asymptotically near-optimal solutions produce sparser graphs by removing redundant edges. Even these alternatives, however, include all sampled configurations as nodes in the roadmap. This work proposes a method, which can reject redundant samples but does provide asymptotic coverage and connectivity guarantees, while keeping local path costs low. Not adding every sample can significantly reduce the size of the final roadmap. An additional advantage is that it is possible to define a reasonable stopping criterion for the approach inspired by previous methods. To achieve these objectives, the proposed method maintains a dense graph that is used for evaluating the performance of the roadmap with regards to local path costs. Experimental results show that the method indeed provides small roadmaps, allowing for shorter query resolution times. Furthermore, smoothing the final paths results in an even more advantageous comparison against alternatives with regards to path quality.
  • Proving Path Non-Existence Using Sampling and Alpha Shapes Authors: McCarthy, Zoe; Bretl, Timothy; Hutchinson, Seth
    In this paper, we address the problem determining the connectivity of a robot's free configuration space. Our method iteratively builds a constructive proof that two configurations lie in disjoint components of the free configuration space. Our algorithm first generates samples that correspond to configurations for which the robot is in collision with an obstacle. These samples are then weighted by their generalized penetration distance, and used to construct alpha shapes. The alpha shape defines a collection of simplices that are fully contained within the configuration space obstacle region. These simplices can be used to quickly solve connectivity queries, which in turn can be used to define termination conditions for sampling-based planners. Such planners, while typically either resolution complete or probabilistically complete, are not able to determine when a path does not exist, and therefore would otherwise rely on heuristics to determine when the search for a free path should be abandoned. An implementation of the algorithm is provided for the case of a 3D Euclidean configuration space, and a proof of correctness is provided.