Closed marip8 closed 3 years ago
@colin-lewis-19 @Levi-Armstrong here are some specific reasons for the design choices in #71 that became evident as a part of this PR:
boost
visitor is actually a type-eraser, and the requirements for visitors of different search algorithms (Dijkstra, BFS, DFS, A*) are different. A common visitor would have to implement all methods for all types of visitors, most of which would be no-op. This is not impossible, but relatively hackyboost
visitor type erasers are also templates based on the graph and visitor type, so we would have to add an additional template argument to our solver classes to support this. This isn't hard but it starts to make the code unreadableboost
search algorithm?
This PR creates an alternative BGL solver using the Dijkstra search algorithm that uses a custom visitor to terminate the search once the first node in the last "rung" of the graph is encountered. The BGL Dijkstra search with a default visitor terminates once the distance from the start vertex to every vertex in the graph has been calculated, which performs much more work than necessary for most Descartes use-cases
Results
The colors in the diagrams below correspond to the status of the vertices in the search:
BGLDijkstraSolverVE
BGLEfficientDijkstraSolverVE
The new Dijkstra solver implementation visits fewer vertices and thus requires less time to perform the search. The benchmarks will updated in a future PR to quantify how many fewer vertices are visited for planning problems with a variety of sizes.
The next step in the development would be to create a Dijkstra visitor with this same behavior that adds edges dynamically during search rather than upfront during
build
. This should reduce both the time and memory foot print required by the solver