More Like this

1. Motion Planning around Obstacles with Convex Optimization

   Tobia Marcucci, Mark Petersen2 ( May 2022 , ArXivorg)

   Trajectory optimization o↵ers mature tools for motion planning in high-dimensional spaces under dynamic constraints. However, when facing complex configuration spaces, cluttered with obstacles, roboticists typically fall back to sampling-based planners that struggle in very high dimensions and with continuous di↵erential constraints. Indeed, obstacles are the source of many textbook examples of problematic nonconvexities in the trajectory-optimization prob- lem. Here we show that convex optimization can, in fact, be used to reliably plan trajectories around obstacles. Specifically, we consider planning problems with collision-avoidance constraints, as well as cost penalties and hard constraints on the shape, the duration, and the velocity of the trajectory. Combining the properties of B ́ezier curves with a recently-proposed framework for finding shortest paths in Graphs of Convex Sets (GCS), we formulate the planning problem as a compact mixed-integer optimization. In stark contrast with existing mixed-integer planners, the convex relaxation of our programs is very tight, and a cheap round- ing of its solution is typically sufficient to design globally-optimal trajectories. This reduces the mixed-integer program back to a simple convex optimization, and automatically provides optimality bounds for the planned trajectories. We name the proposed planner GCS, after its underlying optimization framework. We demonstrate GCS in simulation on a variety of robotic platforms, including a quadrotor flying through buildings and a dual-arm manipulator (with fourteen degrees of freedom) moving in a confined space. Using numerical experiments on a seven-degree-of-freedom manipulator, we show that GCS can outperform widely-used sampling-based planners by finding higher-quality trajectories in less time. 

   more » « less
2. A Sampling-based Motion Planning Framework for Complex Motor Actions

   Sobti, S. ; Shome, R. ; Chaudhuri, S. ; Kavraki, L.E. ( July 2021 , 2021 the IEEE/RSJ International Conference on Intelligent Robots and Systems)

   null (Ed.)

   We present a framework for planning complex motor actions such as pouring or scooping from arbitrary start states in cluttered real-world scenes. Traditional approaches to such tasks use dynamic motion primitives (DMPs) learned from human demonstrations. We enhance a recently proposed state of- the-art DMP technique capable of obstacle avoidance by including them within a novel hybrid framework. This complements DMPs with sampling-based motion planning algorithms, using the latter to explore the scene and reach promising regions from which a DMP can successfully complete the task. Experiments indicate that even obstacle-aware DMPs suffer in task success when used in scenarios which largely differ from the trained demonstration in terms of the start, goal, and obstacles. Our hybrid approach significantly outperforms obstacle-aware DMPs by successfully completing tasks in cluttered scenes for a pouring task in simulation. We further demonstrate our method on a real robot for pouring and scooping tasks. 

   more » « less
3. The blindfolded traveler’s problem: A search framework for motion planning with contact estimates

   https://doi.org/10.1177/02783649231170893  

   Saund, Brad ; Choudhury, Sanjiban ; Srinivasa, Siddhartha ; Berenson, Dmitry ( May 2023 , The International Journal of Robotics Research)

   We address the problem of robot motion planning under uncertainty where the only observations are through contact with the environment. Such problems are typically solved by planning optimistically assuming unknown space is free, moving along the planned path and re-planning if the robot collides. However this approach can be very inefficient, leading to many unnecessary collisions and unproductive motion. We propose a new formulation, the Blindfolded Traveler’s Problem (BTP), for planning on a graph containing edges with unknown validity, with true validity observed only through attempted traversal by the robot. The solution to a BTP is a policy indicating the next edge to attempt given previous observations and an initial belief. We prove that BTP is NP-complete and show that exact modeling of the belief is intractable, therefore we present several approximation-based policies and beliefs. For the policy we propose graph search with edge weights augmented by the probability of collision. For the belief representation we propose a weighted Mixture of Experts of Collision Hypothesis Sets and a Manifold Particle Filter. Empirical evaluation in simulation and on a real robot arm shows that our proposed approach vastly outperforms several baselines as well as a previous approach that does not employ the BTP framework.

    

   more » « less
4. Efficient Robot Motion Planning via Sampling and Optimization

   https://doi.org/10.23919/ACC50511.2021.9483146  

   Leu, Jessica ; Zhang, Ge ; Sun, Liting ; Tomizuka, Masayoshi ( May 2021 , 2021 American Control Conference (ACC))

   null (Ed.)

   Robot motion planning is one of the important elements in robotics. In environments full of obstacles, it is always challenging to find a collision-free and dynamically feasible path between the robot's initial configuration and goal configuration. While many motion planning algorithms have been proposed in the past, each of them has its pros and cons. This work presents a benchmark which implements and compares existing planning algorithms on a variety of problems with extensive simulation. Based on that, we also propose a hybrid planning algorithm, RRT*-CFS, that combines the merits of sampling-based planning methods and optimization-based planning methods. The first layer, RRT*, quickly samples a semi-optimal path. The second layer, CFS, performs sequential convex optimization given the reference path from RRT*. The proposed RRT*-CFS has feasibility and convergence guarantees. Simulation results show that RRT*-CFS benefits from the hybrid structure and performs robustly in various scenarios including the narrow passage problems. 

   more » « less
5. Spatio-temporal Motion Planning for Autonomous Vehicles with Trapezoidal Prism Corridors and Bézier Curves

   https://doi.org/10.23919/ACC55779.2023.10155930  

   Deolasee, S. ; Lin, Q. ; Li, J. ; Dolan, J.M. ( May 2023 , Proceedings of the American Control Conference)

   Safety-guaranteed motion planning is critical for self-driving cars to generate collision-free trajectories. A layered motion planning approach with decoupled path and speed planning is widely used for this purpose. This approach is prone to be suboptimal in the presence of dynamic obstacles. Spatial-temporal approaches deal with path planning and speed planning simultaneously; however, the existing methods only support simple-shaped corridors like cuboids, which restrict the search space for optimization in complex scenarios. We propose to use trapezoidal prism-shaped corridors for optimization, which significantly enlarges the solution space compared to the existing cuboidal corridors-based method. Finally, a piecewise Bezier curve optimization is conducted in our proposed ´ corridors. This formulation theoretically guarantees the safety of the continuous-time trajectory. We validate the efficiency and effectiveness of the proposed approach in numerical and CommonRoad simulations 

   more » « less