Exposing GCS randomized rounding to the user

[bernhardpg]

Is your feature request related to a problem? Please describe. I often find that I want to solve a GCS problem and utilize the information in the flow variables to retrieve multiple potential paths in the graph.

In my specific case, this is because my GCS instance corresponds to a convex relaxation of the nonconvex motion planning problem I care about, and I perform downstream rounding/post-processing on the obtained GCS solution. For these instances, I want to retrieve multiple candidate paths from GCS, perform downstream rounding on each of them, and then pick the optimal solution in the end.

With the current GCS interface, I currently have two options:

1. To call SolveShortestPath with max_rounded_paths = 0 to obtain a solution where the flow-variables are (potentially) non-binary, and then implement the "standard" randomized DFS GCS rounding (or some other rounding scheme) myself.
2. Call SolveShortestPath with max_rounded_paths > 0 and accept that this will only return one path through the graph, and only do post-processing/downstream rounding on this one path.

Neither option is satisfactory.

Describe the solution you'd like I think the whole functionality for randomized DFS rounding implemented here should be moved to a separate function that is exposed to the user (and also called by SolveShortestPath), called something like GetRandomizedSolutionPaths, which takes as input the source, target, and relaxed GCS result (with nonbinary flows), and which returns all of the obtained solutions paths as a vector of Egdes and their corresponding MathematicalProgramResults.

The API could look like:

  std::pair<std::vector<std::vector<const Edge*>>,
            std::vector<solvers::MathematicalProgramResult>>
  GetRandomizedSolutionPath(
      const Vertex& source, const Vertex& target,
      const solvers::MathematicalProgramResult& result,
      const GraphOfConvexSetsOptions& specified_options) const;

(or potentially return a vector of pairs, as opposed to a pair of vectors).

The returned list could be either sorted according to the optimal costs or have no guarantees on sorting.

Describe alternatives you've considered A hacky implementation of this can be found here. Note that this implementation has not changed SolveShortestPath to use GetRandomizedSolutionPaths.

[bernhardpg]

@wrangelvid FYI

[RussTedrake]

I believe this is resolved by #21402. @bernhardpg -- please reopen if I'm wrong.