We relax the non-convex SO(3) constraint on rotation matrix R to mixed-integer linear constraints.
The formulation of these constraints are described in Global Inverse Kinematics via Mixed-integer Convex Optimization by Hongkai Dai, Gregory Izatt and Russ Tedrake, ISRR, 2017
The SO(3) constraint on a rotation matrix R = [r₁, r₂, r₃], rᵢ∈ℝ³ is
rᵢᵀrᵢ = 1 (1)
rᵢᵀrⱼ = 0 (2)
r₁ x r₂ = r₃ (3)
To relax SO(3) constraint on rotation matrix R, we divide the range [-1, 1] (the range of each entry in R) into smaller intervals [φ(i), φ(i+1)], and then relax the SO(3) constraint within each interval. We provide 3 approaches for relaxation
- By replacing each bilinear product in constraint (1), (2) and (3) with a new variable, in the McCormick envelope of the bilinear product w = x * y.
- By considering the intersection region between axis-aligned boxes, and the surface of a unit sphere in 3D.
- By combining the two approaches above. This will result in a tighter relaxation.
These three approaches give different relaxation of SO(3) constraint (the feasible sets for each relaxation are different), and different computation speed. The users can switch between the approaches to find the best fit for their problem.
- Note
- If you have several rotation matrices that all need to be relaxed through mixed-integer constraint, then you can create a single MixedIntegerRotationConstraintGenerator object, and add the mixed-integer constraint to each rotation matrix, by calling AddToProgram() function repeatedly.