WAFR 2016 Roundup

Mark Moll

A couple weeks ago the Workshop on the Algorithmic Foundations of Robotics (WAFR) took place in San Francisco, CA. As always, WAFR was excellent. It was good to see many friends and colleagues again. There were many excellent papers, but I will focus here on some of the papers that used OMPL one way or another.

  1. Collision detection or nearest-neighbor search? On the computational bottleneck in sampling-based motion planning
    Michal Kleinbort, Oren Salzman, and Dan Halperin
    Blavatnik School of Computer Science, Tel-Aviv University, Israel
    Kleinbart et al. show that the computational bottleneck in asymptotically optimal planning algorithms is, in the limit, created by nearest-neighbor calculations. They also show that computing all near-neighbors within a ball of a given radius can provide speedups compared to computing k nearest neighbors.

  2. Efficient Nearest-Neighbor Search for Dynamical Systems with Nonholonomic Constraints
    Valerio Varricchio, Brian Paden, Dmitry Yershov, and Emilio Frazzoli
    Massachusetts Institute of Technology
    Varricchio et al. also analyze nearest-neighbor search, but here the focus is on dynamical systems with nonholonomic constraints. The authors focus specifically on kd-trees and propose a new way to build and query such trees for nonholonomic systems. The proposed approach is evaluated using a Reeds-Shepp system and outperforms regular kd-trees, hierarchical clustering (as implemented in FLANN), and Geometric Near-neighbor Access Trees (as implemented in OMPL).

  3. Matrix Completion as a Post-Processing Technique for Probabilistic Roadmaps
    Joel M. Esposito and John N. Wright
    United States Naval Academy, Annapolis, MD and Columbia University, New York, NY
    Esposito and Wright observe that the existence of many edges in a probabilistic roadmap can be predicted using only a small subset of the edges in the roadmap. This is done using matrix completion techniques. If valid and invalid edges can be predicted accurately, then many collision checks can be avoided. How to best leverage this insight into accelerating motion planning algorithms is the topic of further research.

  4. Resolution-Exact Planner for Thick Non-Crossing 2-Link Robots
    Chee K. Yap, Zhongdi Luo, and Ching-Hsiang Hsu
    Department of Computer Science, Courant Institute, NYU
    Yap et al. present a new type of motion planning algorithm that is not based on sampling or heuristic search, but is based on subdivision instead. Initial results are presented for a 2-link robot in the plane. The algorithm is compared with a number of sampling-based planning algorithms in OMPL and performs really well in comparison. Generalizing the algorithm to higher-dimensional systems is non-trivial and is the subject of future work.

  5. Motion Planning for Reconfigurable Mobile Robots Using Hierarchical Fast Marching Trees
    William Reid, Robert Fitch, Ali Haydar Göktogan and Salah Sukkarieh
    Australian Centre for Field Robotics, The University of Sydney and the Centre for Autonomous Systems, University of Technology Sydney, Australia
    Reid et al. present a hierarchical variant of FMT*, an asymptotically optimal planning algorithm. They use a path in a subspace of a high-dimensional state space to guide the exploration in the full state space while preserving optimality and completeness guarantees. The algorithm was developed for a reconfigurable mobile robot, specifically, a four-legged rover with wheels as feet. The idea may extend to other asymptotically optimal algorithms. Using this hierarchical approach the authors show a significantly improved convergence to energy-optimal paths for their rover.