Mixed Discrete-Continuous Planning with Convex Optimization

Enrique Fernández-González, Erez Karpas, Brian Charles WilliamsAAAI 2017 · DOI

Introduction

Autonomous robotic systems operate in environments requiring a sophisticated blend of discrete decision-making and continuous control. For instance, an underwater vehicle must decide which scientific sites to visit (discrete) while managing its velocity and battery life (continuous). Traditional planners often struggle with this "hybrid" nature, either oversimplifying constraints to maintain speed or becoming computationally intractable when modeling realistic physics. This paper introduces cqScotty, a robotic planner designed to bridge this gap by leveraging Second Order Cone Programming (SOCP).

The Challenge of Hybrid Planning

Existing planners face a significant trade-off between expressiveness and efficiency. Linear planners are fast but limited to "box" constraints—for example, treating a circular velocity limit as a square. This leads to unrealistic trajectories. Conversely, planners that handle non-linear constraints often rely on discretizing time or state, which causes a "state-space explosion" as mission duration increases.

The core difficulty lies in modeling constraints like the $L_2$-norm of a velocity vector ($v_x^2 + v_y^2 \leq v_{max}^2$) or speed-dependent fuel consumption in continuous time. These are non-linear but often convex, presenting an opportunity for more efficient optimization techniques.

The cqScotty Approach

The researchers developed cqScotty to handle convex quadratic constraints efficiently. The planner uses a heuristic forward search (Enforced Hill Climbing) and integrates an SOCP solver to verify plan consistency during the search process.

SOCP Encoding and the "Encoding Trick"

Unlike standard Linear Programming (LP), SOCP can model cones, which naturally represent quadratic constraints. However, a fundamental hurdle in continuous-time planning is the relationship $\Delta x = v \cdot \Delta t$. Since both velocity ($v$) and duration ($\Delta t$) are decision variables, their product is non-convex.

The authors circumvent this using a clever reformulation: they define a new variable representing the product of velocity and time. This allows the motion equations to remain linear while the SOCP solver enforces quadratic constraints on the original velocity components. This "Encoding Trick" enables the planner to maintain the speed of convex optimization while handling complex physical limits.

Experimental Evaluation

The performance of cqScotty was evaluated across three realistic mission domains designed to test the limits of hybrid planning:

  1. AUV Domain: An Autonomous Underwater Vehicle must navigate between regions while respecting a total velocity magnitude limit.
  2. ROV Domain: A Remotely Operated Vehicle is tethered to a moving ship and must remain within a specific radius (tether range) while sampling target regions.
  3. Air Refueling Domain: A UAV must coordinate with a tanker for mid-air refueling, where fuel consumption is a non-linear function of flight speed.
Illustration of the AUV and ROV mission domains involving region navigation and tether constraints.

Results and Discussion

The experimental results demonstrate that cqScotty significantly expands the range of solvable problems compared to previous state-of-the-art planners like Scotty or POPCORN.

Performance metrics for cqScotty across the AUV, ROV, and Air Refueling domains.

Efficiency and Scalability

As shown in the performance data, cqScotty maintains remarkable efficiency. The mean optimization time per problem instance was typically under 10ms for small problems and remained below 50ms even for larger, more complex scenarios. This speed is attributed to the tight integration of modern SOCP solvers (such as Gurobi) directly into the search process, allowing the planner to prune infeasible paths early.

Modeling Realism

By moving beyond independent linear bounds, cqScotty allows for joint constraints on velocity components. This is essential for minimizing actual distance traveled and modeling real-world hardware limits accurately. In the Air Refueling domain, the planner successfully managed non-linear resource consumption ($f = -k_1v - k_2v^2$) that previous linear-based planners could not model.

Conclusion and Future Work

The cqScotty planner represents a significant step forward in mixed discrete-continuous planning. By identifying that many robotic constraints are convex and can be mapped to SOCPs, the authors have created a tool that is both expressive and computationally efficient.

Future research directions include extending the framework to handle non-convex constraints, such as static obstacles, and incorporating more complex dynamics like acceleration and turning radius limits. While the current search is greedy, the ability to solve the continuous sub-problems optimally provides a strong foundation for more advanced global search strategies.

Summary updated

BibTeX
@inproceedings{fernandezgonzalez2017mixed,
  author = {Enrique Fernández-González and Erez Karpas and Brian Charles Williams},
  title = {{Mixed Discrete-Continuous Planning with Convex Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.11185},
}
Figure