This paper presents Exact Least-Restrictive Hyperplane (ELRH), a novel, solver-free method for robot collision avoidance that jointly optimizes the orientation of separating hyperplanes and control inputs. By leveraging the geometry of Minkowski difference polygons, the authors transform a complex, non-convex optimization problem into a simple algebraic check over a finite set of candidates, ensuring global optimality and safety with significantly lower computational overhead than traditional nonlinear solvers.
TL;DR
ELRH provides a "solver-free" way to find the mathematically best path for a robot to avoid obstacles while staying as close as possible to its original command. By replacing heavy numerical optimization with clever geometry, it achieves a 6.1× speedup in complex environments and significantly reduces the "intervention cost"—the amount the robot has to deviate from its intended path.
What Problem Does This Paper Address?
In autonomous navigation, robots often use Control Barrier Functions (CBFs) to ensure safety. When dealing with polygonal robots and obstacles, a common technique is to place a "separating hyperplane" (a line in 2D) between them. If the robot stays on its side of the line, it won't collide.
However, the angle of this line matters immensely. A poorly chosen angle might force the robot to take a sharp, unnecessary turn, even if a slight nudge would have sufficed. This deviation is called control intervention. Ideally, we want the "Least-Restrictive Hyperplane" (LRH)—the one that minimizes this intervention.
The catch? Finding this optimal angle jointly with the control input is a non-convex optimization problem. Existing solutions either use slow, unpredictable nonlinear solvers (like IPOPT) that can get stuck in local minima, or they use "grids" of angles that become computationally explosive as the number of obstacles increases.
Methods
The authors introduce ELRH, which avoids numerical solvers entirely. Their approach relies on several key technical pillars:
- Minkowski Difference Geometry: They represent the robot and obstacles as polygons. By calculating the Minkowski difference, they turn the "robot vs. obstacle" problem into a "point vs. polygon" problem.
- Finite Candidate Set: The core insight is that the global optimum for the control intervention must lie within a specific, polynomial-size set of candidates. These candidates are derived from:
- The origin (zero intervention).
- Projections onto obstacle constraints.
- Intersections between two obstacle constraints.
- Intersections between obstacle constraints and the robot's physical actuator limits.
- Algebraic Filtering: Instead of "searching," the algorithm simply evaluates this finite list of candidates using closed-form algebraic checks and picks the one with the smallest norm that satisfies all safety conditions.
- Sampled-Data Invariance: They derive a theoretical bound on the control time-step ($\delta t$) to guarantee that a safe command chosen at the start of a step remains safe until the next update, even with moving obstacles.
Datasets
The authors evaluated their method using 250 simulated navigation scenarios across five distinct "families" designed to test different geometric challenges:
- Doorway: Navigating a narrow gap between static posts.
- Offset: Static obstacles blocking the direct path.
- Crossing: Moving obstacles intercepting the path laterally.
- Closing: Head-on approaching obstacles.
- Cut-in: Slower obstacles merging ahead of the robot.
They compared ELRH against MDH (Minimum Distance Hyperplane, which picks angles based only on geometry) and C-LRH (Continuous LRH using the IPOPT solver).
Key Insights and Ideas
- Control-Awareness is Crucial: Geometry-only methods (like MDH) often fail in "closing" scenarios because they pick hyperplanes that block the robot's forward progress. ELRH "sees" the intended command and picks a hyperplane that accommodates it.
- Global Optimality via Discretization: The most surprising finding is that a continuous, non-convex problem can be solved exactly by looking at a small, discrete set of points. This is possible because the optimal solution in planar space is always constrained by at most two active boundaries.
- Scalability: Because the candidate set size grows polynomially ($O(N_{obs}^2)$), ELRH handles many obstacles much better than grid-based methods, which grow exponentially.
Key Results
- Lower Intervention: Compared to a local nonlinear solver, ELRH reduced cumulative intervention cost by 3.6% at the median and 27.3% at the 90th percentile.
- Faster Completion: Robots reached their goals faster, with a 5.6% improvement at the 90th percentile.
- Efficiency: In benchmarks with 16 simultaneous obstacles, ELRH achieved a 6.1× per-step speedup over the nonlinear solver (41.8 ms vs 253.0 ms).
- Reliability: While the nonlinear solver (C-LRH) only found the global minimum in 30% of test cases, ELRH is mathematically guaranteed to find it every time it is feasible.
Limitations and Future Work
- Planar Only: The current derivation is specific to 2D planar navigation. Extending this to 3D (e.g., for drones) would require handling more complex geometric intersections.
- No Rotation: The model assumes the robot and obstacles translate but do not rotate.
- Single-Step Horizon: ELRH optimizes for the immediate next step. The authors suggest that integrating this into a multi-step horizon (like Model Predictive Control) could further improve long-term path efficiency.
- Rigid Bodies: The method assumes rigid polygonal footprints; extending it to soft or deformable bodies remains an open challenge.
Summary updated