Understanding specific code segment in CBS-TA

[aakash0641]

Hi, I request for your help in understanding the purpose (logic) behind the below code segment. The code segment is from the class CBSTA. The reason that I could not get the logic behind the concerned code segment is that it is absent in the CBS-TA algorithm mentioned in the CBS-TA paper "Conflict-Based Search with Optimal Task Assignment". For convenience, I am providing the screenshot of the code segment so that we can refer using line numbers.

Q1: What is being done in the for loop from line 100 to 118 ? I mean what is the logic ?

Q2: In line 96, what is the purpose of calling nextTaskAssignment function ? Actually, the call to nextTaskAssignment function, which is shown in algorithm in the CBS-TA paper, is actually present in line 147 (see 2nd screenshot). So, I could not understand the logic behind calling nextTaskAssignment in line 96. I request for your help in clarifying my doubts. Thank you.

In other words:-

In CBS-TA paper, there is only one call to nextTaskAssignment function (in line 15 of algorithm in paper).
But in code, there are two calls to nextTaskAssignment function, in lines 96 and 147 respectively.
I feel the call in line 147 is corresponding to the call in the line 15 of algorithm in the paper.
So, what is the purpose of additional call to nextTaskAssignment function in line 96 ?

[whoenig]

1. This is a very simple test if the problem is even feasible (i.e., each robot needs to be able to find a path to the goal, when ignoring the other robots). This is not exhaustive and there are still cases where CBS-(TA) runs forever if no solution exists.
2. This is simply computing the initial assignment for the first root node.

[aakash0641]

1. This is a very simple test if the problem is even feasible (i.e., each robot needs to be able to find a path to the goal, when ignoring the other robots). This is not exhaustive and there are still cases where CBS-(TA) runs forever if no solution exists.
2. This is simply computing the initial assignment for the first root node.

1. Ok, I understood the 1st part of reply to Q1. If there are 10 robots and 10 goals, it checks for each robot, whether it can traverse to its assigned goal. This means there would be 10 calls to A*. (1 A* per robot). But regarding your second sentence in the 1st reply, could you please elaborate it a bit more. CBS-TA is complete and optimal according to the paper. So, in case no solution exists because some goal may be trapped by obstacles all around, in that case A* would return a result conveying that no path was able to be found. So, the cost of path would be say "infinity". If we go by this, won't CBS-TA stop saying no solution exists instead of running forever ?

2. Isn't the initial assignment for the the first root node computed in solve() function of NextBestAssignment class (attached a screenshot) ? The nextTaskAssignment function calls nextSolution function (in line 62) and it computes the next-best-assignment from the current assignment under processing. The reason for this doubt is that there is already this function solve() which is called to compute 1st optimal assignment.
   

[whoenig]

1. Completeness only implies that a solution is found if one exists, not that it detects the non-existance of a solution. Unfortunately, CBS (and variants) cannot detect the non-existance of a solution.
2. Solve doesn't return anything. The first call to nextSolution returns the first assignment.