search

hungpham2511 / toppra

robotic motion planning library
https://hungpham2511.github.io/toppra/index.html
MIT License
612 stars 169 forks source link

[CPP] Invented a parallel algorithm based on seidel implementation. #163

Open JS00000 opened 3 years ago

JS00000 commented 3 years ago

Fixes # PathParametrizationAlgorithm::computeFeasibleSets() now can pass the test.

Changes in this PRs:

Checklists:

hungpham2511 commented 3 years ago

Cool. Thanks for contributing @JS00000. I will try to get around to review the code quickly.

hungpham2511 commented 3 years ago

Do you have any numbers/graphs demonstrating the new algorithm?

JS00000 commented 3 years ago

Do you have any numbers/graphs demonstrating the new algorithm?

Not yet. The idea of this parallel optimization is very simple, that is, separate the parts that have no dependencies in the serial calculation of the controllable set, and then process them in parallel.

JS00000 commented 3 years ago

Thanks for raising this point. I need a bit more information to understand your changes.

  1. Duplicating the API to achieve parallelization is a bit excessive. The current API does not support parallelization. I would be in favor of updating the API to have only one API that supports parallelization, rather than changing it opportunistically.
  2. I may be overlooking, but Seidel and SeidelParallel seems to have a lot of code in common. Is this code duplication necessary ? This is bad because:
  • it makes code review hard because differences are hidden,
  • it makes maintenance harder. From what I understand, you want to store the result as an attribute of the class. I guess you also removed the reordering of the LP constraints. Am I missing something ?

I also made a few minor comments.

I will try to optimize the code structure, which will take a while.

jmirabel commented 3 years ago

The API modification can be discussed before you actually do them. I will let @hungpham2511 give his opinion on this.

hungpham2511 commented 3 years ago

Do you have any numbers/graphs demonstrating the new algorithm?

Not yet. The idea of this parallel optimization is very simple, that is, separate the parts that have no dependencies in the serial calculation of the controllable set, and then process them in parallel.

To be honest, I believe there is not so much gain we can get from parallelizing the algorithm. At best solving LP(s) is two times faster. Including the time taken for other parts, i.e., calculating the coefficients, the total speedup is probably less than that.

JS00000 commented 3 years ago

Do you have any numbers/graphs demonstrating the new algorithm?

Not yet. The idea of this parallel optimization is very simple, that is, separate the parts that have no dependencies in the serial calculation of the controllable set, and then process them in parallel.

To be honest, I believe there is not so much gain we can get from parallelizing the algorithm. At best solving LP(s) is two times faster. Including the time taken for other parts, i.e., calculating the coefficients, the total speedup is probably less than that.

Yes. In my tests, the total speed is atmost 2 times faster than origin Seidel solver, but still slower than qpOASES solver.