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:
- AUV Domain: An Autonomous Underwater Vehicle must navigate between regions while respecting a total velocity magnitude limit.
- 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.
- 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.
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.
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