search

whoenig / libMultiRobotPlanning

Library with search algorithms for task and path planning for multi robot/agent systems
MIT License
840 stars 220 forks source link

Target Assignment Part #45

Closed TachikakaMin closed 1 year ago

TachikakaMin commented 1 year ago

Hi,

In your code, you are using successive_shortest_path_nonnegative_weights to get the solution for Target Assignment part.

https://github.com/whoenig/libMultiRobotPlanning/blob/b01a527103d5a7c0eda529cf0e1ae9568b9b9391/include/libMultiRobotPlanning/assignment.hpp#L84

But Successive Shortest Path algorithm is Pseudo-polynomial time, why not just use hungarian algorithm which is O(n^3)?

whoenig commented 1 year ago

The complexity of successive_shortest_path_nonnegative_weights is documented here: https://www.boost.org/doc/libs/1_61_0/libs/graph/doc/successive_shortest_path_nonnegative_weights.html. Note that this is better than the hungarian method and also that max-flow algorithms tend to have better "real-world" performance.

TachikakaMin commented 1 year ago

“ if U is the value of the max flow, then the complexity is O(U (|E| + |V|log|V|))”

It is not true.

This method's time complexity will include U, so it is slower than hungarian method( O(n^3) ) when U becomes larger.

whoenig commented 1 year ago

But the relationship of U and N is not really known. Nevertheless, I personally have not benchmarked/compared different algorithms for task assignments and only looked at "small" cases (N<1000), where the computational runtime was negligible to path planning. Dlib has a C++ implementation of the Hungarian method, if you are interested in benchmarking.

TachikakaMin commented 1 year ago

Yes, you are right if we use a grid map. And the max-flow won't be very large.

But U is related to edge weights so it can be a very large number even if N is small. For example, you can generate an undirected graph with N<1000 but increase the edge weights to, maybe 1e8. It is pseudo-polynomial.