Timeout of cbs_roadmap about libmultirobotplanning HOT 1 CLOSED

The issue here is that the low-level A* planner plans in space-time. Here, the low-level planner never terminates, because the wait actions allow it to explore new nodes indefinitely. There are a number of solutions:
a) Use an upper bound on the time a plan can take. This is known to be O(V^3), which I implemented in 5692fc5. The risk here is that the constant factor is not known, so simply V^3 might not be good enough.
b) Use SIPP as low-level planner. In my opinion, this is the better solution, since this also resolves other problems related to unsolvable problems (e.g., identical goal states). The major downside is that this might come with a performance penalty over using A*.
c) Check a MAPF instance for feasibility before solving. In principle, this can be done in linear time w.r.t. graph size (e.g.

Jingjin Yu, Daniela Rus:
Pebble Motion on Graphs with Rotations: Efficient Feasibility Tests and Planning Algorithms. WAFR 2014: 729-746

provides an algorithm). However, this approach is not implemented in this library, (yet?).

from libmultirobotplanning.