Maybe a bug in CBS?

[zijinoier]

When I reading overlap function in Constraints struct from cbs.cpp, I encounter this:

std::unordered_set<VertexConstraint> vertexConstraints;
std::unordered_set<EdgeConstraint> edgeConstraints; 
bool overlap(const Constraints& other) {
    std::vector<VertexConstraint> vertexIntersection;
    std::vector<EdgeConstraint> edgeIntersection;
    std::set_intersection(vertexConstraints.begin(), vertexConstraints.end(),
                          other.vertexConstraints.begin(),
                          other.vertexConstraints.end(),
                          std::back_inserter(vertexIntersection));
    std::set_intersection(edgeConstraints.begin(), edgeConstraints.end(),
                          other.edgeConstraints.begin(),
                          other.edgeConstraints.end(),
                          std::back_inserter(edgeIntersection));
    return !vertexIntersection.empty() || !edgeIntersection.empty();
  }

As I know, std::set_intersection can only work on ordered set like std::set. The function may not work properly on std::unordered_set. https://stackoverflow.com/questions/48158811/c-library-method-for-intersection-of-two-unordered-set

Hope for your reply:)

[whoenig]

Thanks for pointing that out, this is certainly a bug (see also notes 1 and 3 in https://en.cppreference.com/w/cpp/algorithm/set_intersection). I think there are two potential solutions: 1) switch to a regular std::set, 2) use a foreach loop and https://en.cppreference.com/w/cpp/container/unordered_set/count for the check. Option 2) would eliminate the need to create the intersections explicitly, so might be actually better for this function.

[zijinoier]

Yeah. I agree with that option (2) is certainly a better solution. I am glad to fix this problem and submit a pull request😊

[whoenig]

I just pushed a fix - sorry a PR would have been great too, but I saw this message too late. As noted in the commit https://github.com/whoenig/libMultiRobotPlanning/commit/2a757de816e2574d0ba108a2ad905732fe66d91f, this bug luckily did not affect correctness, because the overlap function is only used in DEBUG builds as assertion.

[whoenig]

That would be great - PRs are always welcome!