high level of LB in ECBS do not used?

[xue19890510]

The paper ECBS said that the node that pushed into the FOCAL from OPEN should meet the condition LB<n.cost<=LB*W, but in your code

    bestCost = open.top().cost;

if (newNode.cost <= bestCost * m_w) { focal.push(handle); }

should it be bestCost = open.top().LB? can you explain it? Than you very much.

[whoenig]

the lower bound (LB) of OPEN (assuming an admissible heuristic) is open.top().cost, that is, all other entries in OPEN will have the same or a higher cost.

[tangmingkai]

But the open.top().cost is the cost of suboptimal solution of the single-agent pathfinding problem. I think use open.top().cost directly cannot obtain the solution satisfying the condition cost(solution) <= cost(best_solution) * m_w.

[TachikakaMin]

Hi @whoenig , I think @john123741 is correct.

It should use LB rather than cost in high-level search.

https://tzin.bgu.ac.il/~felner/2014/cbseShort.pdf

[whoenig]

Thanks for your concerns. Could you point to a concrete line in the code that you think should be changed? I agree with the paper, but I believe that this might be just an issue with how LB is defined. I still think that my comment is correct. Note that

open.top().cost is the cost of suboptimal solution of the single-agent pathfinding problem

is not true, since open always contains the lowest-bound solution at the top (but the algorithm expands from FOCAL, not from OPEN).

[TachikakaMin]

When you are doing Lowlevel search

LowLevelSearch_t lowLevel(llenv, m_w);
bool success = lowLevel.search(initialStates[i], newNode.solution[i]);

The newNode.solution[i] satisfy

newNode.solution[i].fmin <= newNode.solution[i] <= m_w*newNode.solution[i].fmin

So for each CT node, the cost is

newNode.LB <= newNode.cost <= m_w*newNode.LB

In Highlevel search

const auto& top = open.top();
Cost bestCost = top.cost;

we have:

top.LB <= top.cost == bestCost <= top.LB*m_w

In code:

if (val > oldBestCost * m_w && val <= bestCost * m_w) {
  const HighLevelNode& n = *iter;
  focal.push(n.handle);
}

which means all nodes in focal satisfy:

top.cost <= node.cost <= top.cost*m_w

So in focal queue, we have all node that:

top.LB <= top.cost <= node.cost <= top.cost*m_w <= top.LB*m_w*m_w
top.LB <= node.cost <= top.LB*m_w*m_w

And also top.LB is not the smallest LB in open, which will make the upper bound greater.