We present POMP (Pareto Optimal Motion Planner), an anytime algorithm for geometric path planning on roadmaps. For robots with several degrees of freedom, collision checks are computationally expensive and often dominate planning time. Our goal is to minimize the number of collision checks for obtaining the first feasible path and successively shorter feasible paths. We assume that the roadmaps we search over are embedded in a continuous ambient space, where nearby points tend to share the same collision state. This enables us to formulate a probabilistic model that computes the probability of unevaluated configurations being collision-free. We update the model over time as more checks are performed. This model lets us define a weighting function for roadmap edges that is related to the probability of the edge being in collision. Our approach is to trade off between these two weights, gradually prioritizing edge length over collision likelihood. We also show that this tradeoff is approximately equivalent to minimizing the expected path length, with a penalty of being in collision. Our experiments demonstrate that POMP performs comparably with RRTConnect and LazyPRM for the first feasible path, and BIT* for anytime performance, both in terms of collision checks and total planning time.

We formulate and study the comprehensive multi-root (CMR) planning problem, in which feasible paths are desired between multiple regions. We propose two primary contributions which allow us to extend state-of-the-art sampling-based planners. First, we propose the notion of vertex coloring as a compact representation of the CMR objective on graphs. Second, we propose a method for deferring edge evaluations which do not advance our objective, by way of a simple criterion over these vertex colorings. The resulting approach can be applied to any CMR-agnostic graph-based planner which evaluates a sequence of edges. We prove that the theoretical performance of the colored algorithm is always strictly better than (or equal to) that of the corresponding uncolored version. We then apply the approach to the Probabalistic RoadMap (PRM) algorithm; the resulting Colored Probabalistic RoadMap (cPRM) is illustrated on 2D and 7D CMR problems.

A person practicing parkour is an incredible display of intelligent planning; he must reason carefully about his velocity and contact placement far into the future in order to locomote quickly through an environment. We seek to develop planners that will enable robotic systems to replicate this performance. An ideal planner can learn from examples and formulate feasible full-body plans to traverse a new environment. The proposed approach uses momentum equivalence to reduce the full-body system into a simplified one. Low-dimensional trajectory primitives are then composed by a sampling planner called Sampled Composition A* to produce candidate solutions that are adjusted by a trajectory optimizer and mapped to a full-body robot. Using primitives collected from a variety of sources, this technique is able to produce solutions to an assortment of simulated locomotion problems.