Generate incomplete but non colliding solutions

[ghost]

Hi, I just saw the youtube video and it looks very interesting. Few queries:

1) When there is no solution for a robot, does the planner generate a plan to the next best goal? Or is this out of scope -- in which case, the next best goal is fed from outside?

2) From the video, its seems like motion for all robots cannot proceed if one or more robots have no solution. Is this the case? Can some robots with solution can proceed with motion while attempting for a solution for the failed ones?

3) Assuming that there is a module that generates non conflicting end points for each robot, what would be the best way to use this algorithm? Note that robots could be in motion when attempting to replan

[ghost]

4) In a real life scenario, its not necessary that the robots will follow the plan exactly i.e. one maybe too fast and another too slow. Does this algorithm address this?

[mcapino]

Hi, 1) 2) what you mean by "no solution for a robot"? In this paper we deal with execution of multi-robot plans in the face of disturbance. We assume that coordinated trajectories are given.

Can you elaborate?

[ghost]

Sorry this was not clear. I tried creating a problem set for 55 robots in empty hall and the problem sets were created successfully. However, when I run I get this error:

java -jar solver.jar -problemfile instances/empty-hall-r25/1.xml -method RMTRACK -maxtime 60000 -timestep 340 -showvis
01:58:07 [DEBUG] (TrajectoryCoordinationProblemXMLDeserializer.java:328) - The environment consist of boundary and 27 obstacles, with total 605 corners.
01:58:07 [DEBUG] (TrajectoryCoordinationProblemXMLDeserializer.java:209) - Graph (|V|=1047, |E|=8494) parsing took 42 ms
01:58:07 [INFO ] (Util.java:54) - Computing trajectory for robot 0 from (2563, 1257) to (2881, 674)
01:58:07 [DEBUG] (BestResponse.java:135) - Planning finshed in 62ms; 4398 iterations; 70935 it/sec  path-length:137
01:58:07 [INFO ] (Util.java:54) - Computing trajectory for robot 1 from (2828, 939) to (2139, 1257)
01:58:08 [DEBUG] (BestResponse.java:135) - Planning finshed in 202ms; 7530 iterations; 37277 it/sec  path-length:129
01:58:08 [INFO ] (Util.java:54) - Computing trajectory for robot 2 from (2828, 1204) to (2404, 303)
01:58:08 [DEBUG] (BestResponse.java:135) - Planning finshed in 150ms; 10527 iterations; 70180 it/sec  path-length:117
01:58:08 [INFO ] (Util.java:54) - Computing trajectory for robot 3 from (2298, 303) to (549, 886)
01:58:09 [DEBUG] (BestResponse.java:135) - Planning finshed in 948ms; 62727 iterations; 66167 it/sec  path-length:66
01:58:09 [INFO ] (Util.java:54) - Computing trajectory for robot 4 from (1556, 303) to (2616, 1257)
01:58:09 [DEBUG] (BestResponse.java:135) - Planning finshed in 611ms; 33313 iterations; 54522 it/sec  path-length:97
01:58:09 [INFO ] (Util.java:54) - Computing trajectory for robot 5 from (814, 1257) to (655, 303)
01:58:10 [DEBUG] (BestResponse.java:135) - Planning finshed in 270ms; 11081 iterations; 41040 it/sec  path-length:119
01:58:10 [INFO ] (Util.java:54) - Computing trajectory for robot 6 from (1927, 303) to (1821, 303)
01:58:10 [DEBUG] (BestResponse.java:135) - Planning finshed in 6ms; 255 iterations; 42500 it/sec  path-length:164
01:58:10 [INFO ] (Util.java:54) - Computing trajectory for robot 7 from (2828, 356) to (1291, 1257)
01:58:11 [DEBUG] (BestResponse.java:135) - Planning finshed in 995ms; 37850 iterations; 38040 it/sec  path-length:73
01:58:11 [INFO ] (Util.java:54) - Computing trajectory for robot 8 from (2828, 886) to (2828, 1098)
01:58:11 [DEBUG] (BestResponse.java:135) - Planning finshed in 10ms; 366 iterations; 36600 it/sec  path-length:162
01:58:11 [INFO ] (Util.java:54) - Computing trajectory for robot 9 from (1132, 303) to (1980, 1310)
01:58:12 [DEBUG] (BestResponse.java:135) - Planning finshed in 864ms; 23764 iterations; 27504 it/sec  path-length:103
01:58:12 [INFO ] (Util.java:54) - Computing trajectory for robot 10 from (708, 1257) to (708, 303)
01:58:12 [DEBUG] (BestResponse.java:135) - Planning finshed in 385ms; 11062 iterations; 28732 it/sec  path-length:122
01:58:12 [INFO ] (Util.java:54) - Computing trajectory for robot 11 from (1821, 1310) to (1397, 303)
01:58:13 [DEBUG] (BestResponse.java:135) - Planning finshed in 1009ms; 20213 iterations; 20032 it/sec  path-length:111
01:58:13 [INFO ] (Util.java:54) - Computing trajectory for robot 12 from (1450, 1310) to (761, 1257)
01:58:14 [DEBUG] (BestResponse.java:135) - Planning finshed in 362ms; 8391 iterations; 23179 it/sec  path-length:130
01:58:14 [INFO ] (Util.java:54) - Computing trajectory for robot 13 from (2404, 1204) to (1450, 303)
01:58:15 [DEBUG] (BestResponse.java:135) - Planning finshed in 1072ms; 22921 iterations; 21381 it/sec  path-length:105
01:58:15 [INFO ] (Util.java:54) - Computing trajectory for robot 14 from (2033, 1310) to (2881, 515)
01:58:16 [DEBUG] (BestResponse.java:135) - Planning finshed in 938ms; 18333 iterations; 19544 it/sec  path-length:111
01:58:16 [INFO ] (Util.java:54) - Computing trajectory for robot 15 from (1079, 303) to (549, 1098)
01:58:16 [DEBUG] (BestResponse.java:135) - Planning finshed in 692ms; 12640 iterations; 18265 it/sec  path-length:119
01:58:16 [INFO ] (Util.java:54) - Computing trajectory for robot 16 from (549, 674) to (549, 992)
01:58:16 [DEBUG] (BestResponse.java:135) - Planning finshed in 71ms; 1322 iterations; 18619 it/sec  path-length:150
01:58:16 [INFO ] (Util.java:54) - Computing trajectory for robot 17 from (549, 1045) to (549, 621)
01:58:16 [DEBUG] (BestResponse.java:135) - Planning finshed in 92ms; 1705 iterations; 18532 it/sec  path-length:146
01:58:16 [INFO ] (Util.java:54) - Computing trajectory for robot 18 from (2351, 303) to (1503, 303)
01:58:17 [DEBUG] (BestResponse.java:135) - Planning finshed in 755ms; 11754 iterations; 15568 it/sec  path-length:123
01:58:17 [INFO ] (Util.java:54) - Computing trajectory for robot 19 from (2828, 992) to (1768, 303)
01:58:19 [DEBUG] (BestResponse.java:135) - Planning finshed in 1361ms; 21106 iterations; 15507 it/sec  path-length:101
01:58:19 [INFO ] (Util.java:54) - Computing trajectory for robot 20 from (549, 1204) to (2192, 303)
01:58:22 [DEBUG] (BestResponse.java:135) - Planning finshed in 2902ms; 43322 iterations; 14928 it/sec  path-length:64
01:58:22 [INFO ] (Util.java:54) - Computing trajectory for robot 21 from (2828, 1045) to (2881, 780)
01:58:22 [DEBUG] (BestResponse.java:135) - Planning finshed in 48ms; 724 iterations; 15083 it/sec  path-length:161
01:58:22 [INFO ] (Util.java:54) - Computing trajectory for robot 22 from (549, 939) to (2775, 1257)
01:58:27 [DEBUG] (BestResponse.java:135) - Planning finshed in 5045ms; 72652 iterations; 14400 it/sec  path-length:NONE
01:58:27 [ERROR] (Util.java:66) - ===== PATH PLANNING FOR ROBOT 22FAILED =====
01:58:27 [INFO ] (Util.java:74) - Path planning finished...
Exception in thread "main" java.lang.NullPointerException
    at cz.agents.rmtrack.Util.findLowerBoundDuration(Util.java:97)
    at cz.agents.rmtrack.ScenarioCreator.solveTracking(ScenarioCreator.java:174)
    at cz.agents.rmtrack.ScenarioCreator.createFromArgs(ScenarioCreator.java:126)
    at cz.agents.rmtrack.ScenarioCreator.main(ScenarioCreator.java:47)

So I assumed that its expected to have so solution in some cases

[ghost]

Actually by increasing the maxtime, there is a solution. Ignore 1. and 2.

Please address queries 3. and 4. if they are reasonable.

[mcapino]

3) The issue of incremental assignment of tasks is addressed by the COBRA algorithm:

M. Čáp, J. Vokřínek, and A. Kleiner, “Complete decentralized method for on-line multi-robot trajectory planning in well-formed infrastructures,” in Proceedings of the twenty-fifth international conference on automated planning and scheduling, ICAPS 2015, jerusalem, israel, june 7-11, 2015., 2015, pp. 324-332.

4) The problem of achieving multi-robot coordination under disturbance is addressed by the RMTRACK algorithm described in

M. Čáp, J. Gregoire, and E. Frazzoli, “Provably safe and deadlock-free execution of multi-robot plans under delaying disturbances,” in Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2016), 2016.

This algorithm can handle any disturbance that affects the time component of the planned trajectories. I.e. the robot must be able to track the spatial component of the solution, but it it can be behind or ahead of the plan.

[ghost]

Thank you