polygons – Integer Linear (ILP / MILP) Formulation for Collision Avoidance of Convex Polytopes / Polyhedra


I am looking for a possibility to avoid the collision of two convex polytopes using (mixed integer) linear programming. I know how I can detect a collision (Akgunduz, A., Banerjee, P., and Mehrotra, S. (March 14, 2005). “A Linear Programming Solution for Exact Collision Detection .” ASME. J. Comput. Inf. Sci. Eng. March 2005; 5(1): 48–55. https://doi.org/10.1115/1.1846053):

Vertices of polytopes are given: vj, wj

Weights are variables: αj ⩾ 0, βj ⩾ 0

∑vj αj − ∑wj βj = 0 (1)

∑αj = 1 (2)

∑βj = 1 (3)

Equation (1) applies to each of the x, y, and z coordinates of the vertices for P1 and P2. Here the presence of a feasible solution indicates a collision. If no solution is found, no collision exists. What I am now looking for is the opposite. I am looking for a feasible solution for no-collision and a not feasible solution if the polytopes collide. How can I change the equations to get this? It is also important for me, that the collision avoidance is not included in the objective function, since the objective parameters are others. The equations should just create a feasible solution space for non-collsion solutions.

Thanks in advance.