Potential Bug in ECBS

[emregoynugur]

Hello,

First of all, thank you for this awesome repository! These implementations will help a lot of people.

I just cloned the repository and I ran my own trivial examples. However, I ran into some problems in two examples (see attached files). I use the below command to run the test files in the build directory.

./ecbs -i test1.yaml -o output.yaml -w 1.3

The program runs for a while and eventually terminates displaying the below error.

libc++abi.dylib: terminating with uncaught exception of type std::length_error: vector

The funny thing with the first test case (test1.txt) is that the program is able to find a solution, if I change the starting point of Agent1 from 4,2 to 8,2. When Agent1 starts on 4,2, it has to go back to make way for Agent0. Test2 is a bit more complicated scenario, but the error is the same.

test1.txt
test2.txt

Edit: Accidentally posted this a little earlier than I intended :)

Thank you for your time and great work!

Emre

[whoenig]

Hi Emre,

Thanks for the detailed bug report! I was able to reproduce the issue (although I did get a slightly different bad_alloc error). It looks like the bug is not in ECBS, but the underlying A*_epsilon, which does not build the focal list correctly incrementally. As workaround, you can add #define REBUILT_FOCAL_LIST in https://github.com/whoenig/libMultiRobotPlanning/blob/master/example/ecbs.cpp#L8 (i.e., before ecbs.hpp is included) and recompile. I'll keep this issue open, until I found a fix for the incremental focal list update. Of course, rebuilding the focal list does have a performance impact.

A few more notes:

• test1.txt works fine with CBS (test2 might as well, but I stopped it after 1GB of memory was consumed)
• Although your examples are small in the number of agents, they are not ideal candidates for (E)CBS, because they require a lot of collaboration between agents to be solved successfully. If you are interested in complicated settings with a few agents, you might get results faster if you plan in joint-space. Also, both tests do not really benefit from a suboptimal solver the way they are setup.

[emregoynugur]

Thanks for the detailed explanation!

Eventually, I am hoping to increase the number of agents (maybe 20+) in my problem. I am in the research phase, so I am currently trying potential approaches. For example, single player monte carlo methods seem to be promising in my case, but it is difficult to tune the parameters and the simulation right. I just wanted see if ECBS would save me from my problems :) because I am not very familiar with this domain.

Please let me know if you have some suggestions!

[whoenig]

If your case is a small area and very dense, reduction-based methods work very well (reduction to ILP or SAT). Another option might be to work on graphs instead of 4-connected grids - you seem to have many long corridors. Finally, I noticed that my examples use a pretty poor low-level heuristic - I added issue #2 to address that (however, I don't expect this will help you significantly).

[emregoynugur]

Sorry to bother you all the time :), but I will just post these two last examples in case you are interested. I didn't have time to debug these examples, but I will do it asap.

I know that agents have to collaborate again, but it is a relatively small search space. Is this suffering from a poor heuristic or the search algorithm? i.e. it has to choose a longer path, which contains a cycle.

graph.txt

map:
dimensions: [4, 2]
obstacles:
- [0, 1]
- [1, 1]
- [3, 1]
agents:

• name: agent0
  start: [0, 0]
  goal: [3, 1]

• name: agent1
  start: [3, 1]
  goal : [0, 0]

I listened to your advice and tested your library with a graph environment (see attached file). The scenario is similar as two agents have to switch places. It is working if I set the starting place of the second agent to 3 from 4. I really feel like this might be my bad :), but the above case is very similar. I get the below error:

Assertion failed: (!newNode.constraints[i].overlap(c.second)), function search, file /Users/emre/Documents/workspace/libMultiRobotPlanning/include/libMultiRobotPlanning/ecbs.hpp, line 258.

[ProVival]

@whoenig Hi, did you find a solution for the issue you mentioned

It looks like the bug is not in ECBS, but the underlying A*_epsilon, which does not build the focal list correctly incrementally. As workaround, you can add #define REBUILT_FOCAL_LIST

i am using the workaround but in large maps it takes way too long time even for just 2 agents

[whoenig]

I have not really investigated this in detail. I usually use small epsilons (e.g., 1.3), where rebuilding doesn't seem to be a major performance penalty.

[ProVival]

Maybe i can try with low epsilon values, i was trying with ep=1.5 but in large maps are like 300x300 maps openset is getting too big in size and causing rebuild to get expensive. Thanks again!