Linear programming infeasible problems

Question

A part of ORCA local avoidance collision is calculating a linear program with an incremental approach - adding the constraints one by one. If the problem is determined to be infeasible, the constraints $g_i(x) \leq 0$ are relaxed, and we could instead solve the problem of

$\min_{x,d} d$

$g_i(x) -d \leq 0, \forall i$

However, I don't really understand the approach to how this is done here (which corresponds to the above mentioned problem when $x$ is two dimensional), in the function linearProgram3, line 518:

https://github.com/snape/RVO2/blob/main/src/Agent.cpp

The method there seems to directly convert the 3d problem to a 2d one, using the lines where $d$ is the same for both lines. A quick summary of my understanding of what happens:

Suppose we have three oriented lines that form a triangle and assume the "normals" (suppose they are pointing in the direction of feasibility, not outside of it) point outside and so the problem is infeasible. The algorithm would see that once it adds the constraint of $l_3$, the problem is infeasible, and use a different approach. It does the following: For $l_1$ and $l_2$ we create lines $\tilde{l_1}, \tilde{l_2}$ where $\tilde{l_1}$ passes through the intersection point of $l_1$ and $l_3$, and it bisects the angle between $l_1$ and $l_3$. Similarly for $l_2$. Then,

$\min_{x,d} d$, where $\tilde{g(l_1)}(x) \leq 0$, $\tilde{g(l_2)}(x) \leq 0$

is solved. In the inequality above, $\tilde{g(l_1)}(x)$ corresponds to the constraint of $x$ being on the "correct" side of $\tilde{l_1}$.

I can intuitively see that this approach will work, but I'm not able to justify it formally. Would someone please explain why it will work, or perhaps refer me to a text that would explain this technique?

Answer 1

Disclaimer: I think I've just figured this out a couple of minutes ago, so some details may be fuzzy.

The formal theory is in Computational Geometry: Algorithms and Applications (2008 de Berg et al.), in the Linear Programming chapter.

Just as in 2D linear programming where we know the optimal incremental solution must lie somewhere on the newly-added line segment, in 3D linear programming, we know the optimal incremental solution must lie on the newly-added plane.

RVO2 defines the constraint plane of a given ORCA line to extend into the Z-axis with a slight tilt, and the infeasible problem we're looking at is just at some slice on an XY-plane.

Now, consider the intersection of two ORCA planes, slightly tilted on the Z-axis -- their intersection is a slightly skewed line, which can be projected onto the XY-plane. This is the bisecting line that RVO2 defines.(1)

Remember that the lines of intersection are parametric; geometrically, we can view these t-parameters as the Z-axis component, i.e. where we should decide to take a new "slice" of the original system of constraints.

When we solve for LP1 in LP3, we are finding the [tl, tr] interval of these bisecting lines -- that is, we are finding the "bounding planes" in the Z-axis between which the optimal solution should be found.

Note that RVO2.LP3 calls LP2 with an optimal velocity pointing into the feasible region of the iterative constraint -- we know the current system is infeasible, so we want to move as directly as possible into a feasible state.

Also note that in LP1, we drop the calculation to find a point closest to the (bisecting) constraint when dirOpt = True -- this is because the linear problem has changed when we project the 3D problem into 2D space. We are no longer looking for minimal perturbation in 2D space, but looking for a shared feasible point among all projected constraints. We have left the minimal perturbation requirement to LP3.

I'm attempting to re-implement ORCA at the moment, at https://github.com/downflux/go-orca. Hopefully I will have more comments to the effect of this post soon.

1. N.B.: The XY-slice that LP3 feeds into LP2 is not technically aligned with the constraint plane itself, but is a 2D planar projection into 2D ambient space -- this nicely avoids attempting to deal with 3D lines and makes reasoning a bit easier.