Confusion in search algorithms used in CBS-TA code

[aakash0641]

Hi,

After reading the paper for CBS-TA, I had the understanding that CBS-TA uses A* search for low-level search (while resolving conflicts) (i.e. during execution of CBS part). But on going through the code, it seems that CBS-TA uses Dijkstra's algorithm for both the 1st assignment, and all subsequent assignments. Please let me know if I am missing something.

[whoenig]

Dijkstra is A* with a heuristic h(x)=0.
The low-level search uses A* with a "perfect" single-robot heuristic.
The high-level search grows the forest using an iterative-best-assignment method, which is more closely related to the Hungarian method than to Dijkstra.

[aakash0641]

@whoenig I agree to your reply but I am looking for a different doubt. I will try to present my doubt in another form.
On trying to run CBS-TA, I see that "perfect" heuristic distances are computed for each pair of workspace graph nodes using Floyd Warshall's all-pairs algorithm (see 1st and 2nd snapshots). Now, when you try to find the first optimal task assignment with minimal cost, the Dijkstra's algorithm is used (see 3rd and 4th snapshots from debug). My question is that when you already computed all-pairs shortest distances using Floyd-Warshall, why do you need to use Dijkstra's? Please let me know if I am missing something. Thank you so much. [
It was a pleasure reading your paper] [All the snapshots are from debug view, and the lines under discussion are hit during execution]

[whoenig]

For the Hungarian method, I use the min-cost max-flow formulation, which is more efficient in practice (but has the same complexity in the worst case). I simply call https://www.boost.org/doc/libs/1_78_0/libs/graph/doc/successive_shortest_path_nonnegative_weights.html, which internally seems to use dijkstra, according to your last screenshot. I am not familiar with the exact implementation details of boost, so I can't comment on why they use it that way. However, it is important that this Dijkstra call here is just an implementation detail.

[aakash0641]

Min-cost max-flow formulation finds minimum-cost maximum-matching in the given graph (here, bipartite graph having agents on one side and the goals on the other side). So, somewhere the cost needs to be computed and fed as input to min-cost max-flow formulation. What I understood finally is that, you handle the cost computation by using Floyd-Warshall's all-pair shortest path algorithm. The call to Dijkstra's algorithm is redundant and you have not used it explicitly in your implementation. I also saw that the A* (in low-level search) uses the heuristic distances computed initially by Floyd-Warshall's algorithm.

To summarize, the cost (i.e. the distance cost) computation is done using Floyd-Warshall's algorithm (and it is reused in A*).
Please correct me if I am wrong anywhere.