search

RobotLocomotion / drake

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

Parallelize the Preprocessing in GraphOfConvexSets #21705

Open cohnt opened 2 months ago

cohnt commented 2 months ago

The optional preprocessing stage of GraphOfConvexSets involves solving a small linear program for every edge in the graph. This seems like an obvious target for parallelization -- up to n programs could be solved in parallel (with n threads).

The speedup for this would be very significant in some of the problems I've dealt with. In these cases, the presolve takes a long time, but results in a relatively easy and quick-to-solve GCS problem. But skipping the presolve leaves a much harder GCS problem, leading to a host of problems.

I'll self-assign this for now, since I've been meaning to learn to use multithreading (and I need it to tackle #21351, which is also assigned to me). But someone else can feel free to jump in if they want it done sooner.

RussTedrake commented 3 weeks ago

I think we should land #21341 before we do this. It will potentially change the form of the computation pretty significantly.

cohnt commented 3 weeks ago

I'll hold off on working on this for now. But if #19119 happens, and the facial reduction LP is still a ways off, this should be a quick addition.