Overcoming Local Minima in Nonconvex Trajectory Optimization

318 concepts269 papers2 proposals

When an autonomous vehicle navigates a busy intersection, or a robotic arm reaches into a cluttered shelf, it must find a trajectory that is both physically feasible and collision-free. Mathematically, this is framed as a trajectory optimization problem: find a path that minimizes a cost (like time or energy) while satisfying constraints (like avoiding walls or respecting actuator limits).

If the world were convex, this would be easy. A local step toward a lower cost would guaranteed-ly lead to the globally best path. But the real world is aggressively non-convex. Obstacles, complex kinematics, and strict safety boundaries create optimization landscapes riddled with local minima—mathematical traps where a trajectory planner gets stuck, unable to find a valid path even if one clearly exists.

To understand why trajectory optimization fails in these environments, and how modern robotics overcomes it, we must look at the geometry of the optimization landscape itself.

The Geometry of Failure

Why do standard numerical solvers get trapped? Consider a robot facing a U-shaped obstacle or a dead end. A local trajectory optimizer looks at the immediate mathematical derivatives (the gradients) around its current guess. If the goal is directly behind the wall, the gradient points straight ahead—right into the obstacle.

As an anonymous paper (Safe Exploration and Escape Local Minima with Model Predictive Control under Partially Unknown Constraints) explains, local optimization fails here because the controller lacks the motivation to temporarily move away from the target to find a way around it. Moving backward or sideways initially increases the cost, which a local gradient-descent solver is designed to avoid.

This problem is fundamental to spatial environments. Klemens Esterle et al. (Spatiotemporal Motion Planning with Combinatorial Reasoning for Autonomous Driving) note that real-world driving environments feature non-convex obstacle spaces that force discrete, combinatorial choices—such as whether to pass an obstacle on the left or the right. Similarly, Johannes Gaber et al. (Adaptive Nonlinear Model Predictive Control for a Real-World Labyrinth Game) highlight how discrete physical boundaries like holes and walls create rugged optimization landscapes where standard controllers fail to converge to a valid path.

Standard Gradient Descent:
[Start] ----> [Local Minimum / Wall]   X   [Goal]

Desired Behavior:
[Start] ----> (Move Away) ----> (Bypass) ----> [Goal]

Non-convexity does not only stem from physical walls; it also emerges from the physics of motion and sensing. For instance, an anonymous work on maritime navigation (Autonomous docking using direct optimal control) demonstrates that incorporating trigonometric functions for vessel rotation and thruster orientation inherently introduces multiple local optima into the landscape.

When perception constraints are added to the mix, the landscape degrades further. Varun Murali et al. (Perception-aware trajectory generation for aggressive quadrotor flight using differential flatness) show that jointly optimizing for a vehicle's dynamics and its camera visibility requirements creates a highly non-convex space. In such cases, standard numerical solvers easily get trapped, failing to find trajectories that balance speed with visibility.

To escape these traps, researchers have developed three core strategies: generative warm-starting, maximum entropy exploration, and structural reformulation.

Strategy 1: Generative Warm-Starting

Local optimizers are exceptional at fine-tuning trajectories but terrible at global exploration. Conversely, global search methods can find the right general region but struggle with precise physical constraints. A powerful solution is to use a global mechanism to provide a high-quality "initial guess" (or warm-start) to seed the local numerical solver.

Recently, generative AI has emerged as an ideal tool for this. Anjian Li et al. (DiffuSolve: Diffusion-based Solver for Non-convex Trajectory Optimization) introduced a framework that uses generative diffusion models to sample diverse, physically plausible trajectories. By using these AI-generated samples as initial guesses for traditional numerical solvers, the system bypasses local optima entirely, discovering globally feasible paths while accelerating computational efficiency.

[Diffusion Model] ---> Generates Diverse Initial Guesses ---> [Local Solver] ---> Smooth, Optimal Path

This concept also applies to high-dimensional systems, such as multi-degree-of-freedom robotic arms. Roberto Lampariello et al. (Trajectory planning for optimal robot catching in real-time) utilize machine learning to instantly predict high-quality initial trajectories for a robot arm attempting to catch fast-moving objects. This initialization prevents the underlying nonlinear optimizer from getting trapped in the kinematic redundancies of the arm, enabling real-time convergence.

Strategy 2: Smooth Exploration via Maximum Entropy

Instead of changing where the optimizer starts, another approach changes how it moves through the landscape. Standard trajectory optimization frameworks, like Differential Dynamic Programming (DDP), rely on local derivatives and quickly collapse into a single local valley.

To prevent this premature collapse, Oswin So et al. (Maximum Entropy Differential Dynamic Programming) injected maximum entropy principles into the optimization objective. By optimizing for a mixture of Gaussian policies rather than a single deterministic path, the algorithm is forced to explore multiple potential solutions simultaneously, allowing it to navigate around complex obstacle configurations.

Evangelos Theodorou et al. (Generalized Maximum Entropy Differential Dynamic Programming) extended this intuition by replacing standard Shannon entropy with Tsallis entropy. This mathematical shift yields heavy-tailed $q$-Gaussian exploration policies.

When the robot encounters a high-cost region (like a barrier), the policy automatically inflates its exploratory noise. This allows the optimizer to mathematically "jump" over high-cost ridges that would otherwise trap a standard gradient-based method, discovering globally optimal paths hidden behind obstacles.

Strategy 3: Reformulating the Landscape

A third paradigm alters the mathematical formulation of the problem itself, smoothing out the wrinkles in the landscape before the optimizer even encounters them.

A frequent source of non-convexity is how safety constraints are handled. Typically, planners use penalty functions that punish the robot as it gets closer to an obstacle. However, these penalties introduce sharp, non-convex boundaries.

Hassan Almubarak et al. (Safety Embedded Differential Dynamic Programming Using Discrete Barrier States) solved this by embedding safety barriers directly into the system's dynamics rather than its cost function. By making safety a fundamental property of how the robot moves rather than a penalty it tries to avoid, they eliminated local non-convexities, drastically improving the solver's success rate in tight spaces.

Alternatively, complex tasks can be broken down into structurally simpler pieces. Svetlana Levit et al. (Solving Sequential Manipulation Puzzles by Finding Easier Subproblems) demonstrated that instead of optimizing a long, highly non-convex manipulation sequence all at once, the problem can be decomposed into a sequence of simpler subproblems. By solving these intermediate subgoals, local optimization solvers can successfully navigate narrow passages and complex object interactions where a flat, global optimization attempt would inevitably fail.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 240 papers
  2. Version 1 · 2026-10-04 · 327 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_non_convex_trajectory_optimization_eb22200e,
  title = {non-convex trajectory optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-convex-trajectory-optimization/rdr_eb22200e9c1c419bacd85de269be7c4a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_non_convex_trajectory_optimization_eb22200e_v2,
  title = {non-convex trajectory optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-convex-trajectory-optimization/rdr_eb22200e9c1c419bacd85de269be7c4a/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake