Data-driven acceleration of mixed-integer bilinear programs: a comparative study for robot motion planning

This paper presents a comparative study of data-driven acceleration techniques for mixed-integer bilinear programs (MIBLPs) applied to robot motion planning. MIBLPs combine discrete decision variables and nonlinear constraints, making them computationally challenging for real-time robotics applications. We investigate two reformulation strategies: (1) converting binary variables into continuous variables with complementarity constraints (MPCC), and (2) converting bilinear constraints into mixed-integer linear constraints using McCormick envelopes (MICP). Using offline computed solutions as datasets, we apply K-nearest neighbor methods to warm-start both reformulations. We experimented with the proposed data-driven MIBLP formulation for motion planning on a linear inverted pendulum with contacts, and planning motion using a single rigid body model with mode transitions and contacts. Our results demonstrate that when sufficient data is available, MICP achieves consistently fast solving speeds that are suitable for real-time computation, while MPCC achieves higher success rates with limited amount of data. Our approach is capable of planning motions for the SCALER robot platform to transition between bipedal and quadrupedal configurations to navigate around obstacles without pre-specified gaits. Code for reproducing our results is available at https://github.com/XuanLin/MIBLP_benchmark.