search

RobotLocomotion / drake

Model-based design and verification for robotics.
https://drake.mit.edu
Other
3.17k stars 1.24k forks source link

Speed up affine hull computation. #21525

Closed cohnt closed 4 weeks ago

cohnt commented 4 weeks ago

I've rewritten the code used to compute affine hulls of convex sets. It is now much quicker, and the number of LPs solved is equal to the ambient dimension. (Previously, it could be as many as the square of the ambient dimension.)

Thew new methodology is to incrementally construct a basis of the affine hull and its orthogonal complement. At each iteration, we take a vector which is orthogonal to both the affine hull basis and the orthogonal complement basis, and try to maximize the displacement of a line segment contained in the convex set along that direction. If we can exceed a user-designated tolerance, we treat that as a feasible direction, and add it to the basis. Otherwise, we add it to the orthogonal complement basis.

If you have time, +@alexandreamice for feature review.

cc @rhjiang @shaoyuancc

This change is Reviewable

jwnimmer-tri commented 4 weeks ago

The libomp thing looks like known flake #20344. I'm not sure why it's turning up here.

jwnimmer-tri commented 4 weeks ago

@drake-jenkins-bot linux-jammy-clang-bazel-experimental-everything-release please