In a specific map scene, the cbs algorithm cannot find a solution and falls into an infinite loop

[lvyv]

I once made a map as attachment, '#' means obstacle, '.' means space, '1','2','3' is start position of three agent, and 'A', 'B', 'C' is the goal position one by one.

When I apply the cbs implemention, It falls into an infinite loop. To reproduce the problem, I slightly modifed the source code of cbs.cpp as following. ...... // std::unordered_set<Location> obstacles; // for (const auto& node : config["map"]["obstacles"]) { //obstacles.insert(Location(node[0].as(), node[1].as())); // } std::unordered_set<Location> obstacles; std::ifstream map(mapFile);

int y = 0; while (map.good()) { std::string line; std::getline(map, line); int x = 0; for (char c : line) { if (c == '#') { obstacles.insert(Location(x, y)); } ++x; } ++y; } ......

map.txt

[whoenig]

• CBS does not guarantee to terminate with an error if no solution exists. (From your map, it looks like a solution should exist, though)
• You can try with bounded suboptimal variants, such as ECBS, since CBS can be very slow on larger examples.