whoenig / libMultiRobotPlanning

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

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

Open lvyv opened 1 year ago

lvyv commented 1 year ago

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 obstacles; // for (const auto& node : config["map"]["obstacles"]) { //obstacles.insert(Location(node[0].as(), node[1].as())); // } std::unordered_set 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 commented 1 year ago