Biconvex Optimization for Smooth Minimum-Time Trajectories around Convex Obstacles

We present a biconvex approach for minimum-time motion planning around convex obstacles that is guaranteed to converge, is anytime, and supports derivative constraints to arbitrary order. In experiments on drone navigation and dual-arm bin unloading, the method reliably produces high-quality trajectories, with computation times comparable to state-of-the-art decomposition-based motion planners, while being more general and more robust to bad initialization.

Method in a nutshell

Our biconvex minimum-time planner (BMTP) computes smooth, collision-free, minimum-time trajectories around convex obstacles. A change of variables makes the minimum-time objective and derivative constraints of any order (velocity, acceleration, jerk, snap, and so on) jointly convex. Collision avoidance is enforced with time-varying separating planes, which leaves a problem that is biconvex: convex in the trajectory for fixed planes, and convex in the planes for a fixed trajectory.

BMTP alternates between these two convex programs, computing maximum-margin separating planes for the current trajectory and then re-optimizing the trajectory against them. The cost never increases and the method is guaranteed to converge, so it can be stopped anytime. Since planes are only added for obstacles that the current iterate collides with, the trajectory can jump around obstacles and escape poor initializations. All it needs to start is a simple collision-free polygonal path.

Our biconvex procedure can jump around obstacles by selectively activating the collision-avoidance constraints. Constraints are added only for the obstacles that the current trajectory (red) collides with (shaded darker), so the best feasible trajectory (green) is free to switch sides and tighten as the alternation proceeds.

For a fixed trajectory, finding a time-varying separating plane is a convex program.

Experiments

Drone flying through a village

We plan a minimum-time quadrotor trajectory through a village of 521 box obstacles. The trajectory is four-times continuously differentiable and respects velocity, acceleration, jerk, and snap limits, which guarantees dynamic feasibility through differential flatness. Initialized with a naive 8-segment path that detours around the entire village, BMTP converges in 6 iterations to an 11.83-second trajectory that cuts diagonally through the village using 0.19 seconds of computation. This is over 50 times faster than a minimum-time variant of the decomposition-based baseline FPP at matching trajectory quality. Ignoring all obstacles yields a lower bound of 11.35 seconds on the trajectory duration, so avoiding every obstacle in the village costs only 0.48 seconds.

Quadrotor trajectory through the village: the black line shows the
initialization around the village, the magenta curve the optimized BMTP
trajectory, and the blue curve the FPP baseline.

Dual-arm bin unloading

Two Franka arms cooperatively move packages from a central bin to their offload bins. We plan in the six-dimensional task space of the two gripper positions, where the collision constraints between the axis-aligned boxes yield up to 123 convex obstacles. Across 50 randomized instances (300 trajectory optimizations), BMTP succeeds on every instance with every trajectory collision-free, computing 2.82-second trajectories in 188 milliseconds on average, on par with the state-of-the-art decomposition-based planner SCSPlanning paired with fast convex-set generation (EI+SCS), while requiring no precomputed convex decomposition of the free space. Warm-starting BMTP with a much longer, sequential initialization leaves the final trajectory quality essentially unchanged, whereas planners that optimize within a fixed corridor around the initialization are inherently limited by it.

Explore one planned unloading sequence in an interactive MeshCat viewer, or open it in a new tab.

Hardware validation

We validate the bin unloading results on two Franka Research 3 arms, each driven by a 1 kHz joint-impedance controller. The robots plan on the fly after every motion and autonomously stage and unload the bin. Across 50 executed motion plans, BMTP achieves 100% planning success and 100% collision-free execution with an average planning time of 145 milliseconds per stage, executing roughly four times faster than a waypoint baseline and head-to-head with EI+SCS.

Video

Acknowledgements

We are very grateful for the funding provided by the Office of Naval Research, Award Number N00014-23-1-2354. Research was also sponsored in part by the Department of the Air Force Artificial Intelligence Accelerator and was accomplished under Cooperative Agreement Number FA8750-19-2-1000. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Department of the Air Force or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.

We further thank Sam Creasey for help with the arm drivers, Russ Tedrake for guidance in the early stages of the project, and Nicholas Pfaff for help with the grippers. The rendered figures in this paper were produced using Drake Blender Tools.

BibTeX

@article{werner2026biconvex,
  author        = {Werner, Peter and Marcucci, Tobia and Rus, Daniela},
  title         = {Biconvex Optimization for Smooth Minimum-Time Trajectories around Convex Obstacles},
  journal       = {arXiv preprint arXiv:2608.02834},
  year          = {2026},
  eprint        = {2608.02834},
  archivePrefix = {arXiv},
  primaryClass  = {cs.RO},
}