================================================================ reLOC 0.09-vegas : Multirobot Solution solver (C) Copyright 2011-2013 Pavel Surynek ---------------------------------------------------------------- Reading graph... 1,0 4,0 2,1 5,1 3,2 6,2 5,4 8,4 6,5 9,5 7,6 10,6 9,8 12,8 10,9 13,9 11,10 14,10 7,3 11,7 15,11 13,12 14,13 15,14 Reading initial arrangement... Reading goal arrangement... Undirected graph: (|V|=16 |E|=24) [ Vertex: (id = 0) {1 4 } Vertex: (id = 1) {0 2 5 } Vertex: (id = 2) {1 3 6 } Vertex: (id = 3) {2 7 } Vertex: (id = 4) {0 5 8 } Vertex: (id = 5) {1 4 6 9 } Vertex: (id = 6) {2 5 7 10 } Vertex: (id = 7) {6 3 11 } Vertex: (id = 8) {4 9 12 } Vertex: (id = 9) {5 8 10 13 } Vertex: (id = 10) {6 9 11 14 } Vertex: (id = 11) {10 7 15 } Vertex: (id = 12) {8 13 } Vertex: (id = 13) {9 12 14 } Vertex: (id = 14) {10 13 15 } Vertex: (id = 15) {11 14 } Edge 0: 1 <-> 0 Edge 1: 4 <-> 0 Edge 2: 2 <-> 1 Edge 3: 5 <-> 1 Edge 4: 3 <-> 2 Edge 5: 6 <-> 2 Edge 6: 5 <-> 4 Edge 7: 8 <-> 4 Edge 8: 6 <-> 5 Edge 9: 9 <-> 5 Edge 10: 7 <-> 6 Edge 11: 10 <-> 6 Edge 12: 9 <-> 8 Edge 13: 12 <-> 8 Edge 14: 10 <-> 9 Edge 15: 13 <-> 9 Edge 16: 11 <-> 10 Edge 17: 14 <-> 10 Edge 18: 7 <-> 3 Edge 19: 11 <-> 7 Edge 20: 15 <-> 11 Edge 21: 13 <-> 12 Edge 22: 14 <-> 13 Edge 23: 15 <-> 14 ] Robot arrangement: (|R| = 5, |V| = 16) [ robot locations: {1#14 2#4 3#1 4#3 5#2 } vertex occupancy: {0#0 3#1 5#2 4#3 2#4 0#5 0#6 0#7 0#8 0#9 0#10 0#11 0#12 0#13 1#14 0#15 } ] Robot arrangement: (|R| = -1, |V| = 0) [ robot locations: {} vertex occupancy: {} ] Robot goal: (|R| = 5, |V| = 16) [ robot goals: { 1#{3} 2#{5} 3#{6} 4#{11} 5#{4} } vertex compatibilities: { 0@{} 1@{} 2@{} 3@{1} 4@{5} 5@{2} 6@{3} 7@{} 8@{} 9@{} 10@{} 11@{4} 12@{} 13@{} 14@{} 15@{} } ] Open/close/exp size (steps): 4/1/4 (2) Open/close/exp size (steps): 14/4/14 (5) Open/close/exp size (steps): 1/0/1 (9) Open/close/exp size (steps): 4/1/4 (14) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 Groups 0 and 2 collide. Solution of group 0 Mulirobot solution: (|moves| = 4, paralellism = 1.000) [ Step 0: 1#14->10 Step 1: 1#10->6 Step 2: 1#6->2 Step 3: 1#2->3 ] Solution of group 2 Mulirobot solution: (|moves| = 2, paralellism = 1.000) [ Step 0: 1#1->2 Step 1: 1#2->6 ] Occupation table complementary for group 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 ** Open/close/exp size (steps): 4/1/4 (2) ** Open/close/exp size (steps): 6/4/6 (5) ** Open/close/exp size (steps): 10/8/10 (9) ** Open/close/exp size (steps): 5/13/5 (14) ** Open/close/exp size (steps): 5/19/5 (20) Occupation table complementary for group 2 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 Unable to resolve collision between groups 0 and 2. Merging groups 0 and 2. Searching solution for merged group 0+2. Open/close/exp size (steps): 10/3/10 (20) Open/close/exp size (steps): 36/11/36 (28) Open/close/exp size (steps): 60/21/60 (38) Open/close/exp size (steps): 80/33/80 (50) Open/close/exp size (steps): 112/48/112 (65) Open/close/exp size (steps): 136/66/136 (83) Open/close/exp size (steps): 175/88/175 (105) Open/close/exp size (steps): 241/115/241 (132) Open/close/exp size (steps): 241/148/241 (165) 0 2 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 2 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 2 0 0 0 0 0 0 0 0 0 Groups 0 and 2 collide. Solution of group 0 Mulirobot solution: (|moves| = 6, paralellism = 1.500) [ Step 0: 1#14->10 2#1->2 Step 1: 1#10->11 2#2->6 Step 2: 1#11->7 Step 3: 1#7->3 ] Solution of group 2 Mulirobot solution: (|moves| = 3, paralellism = 1.000) [ Step 0: 1#2->1 Step 1: 1#1->0 Step 2: 1#0->4 ] Occupation table complementary for group 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 Occupation table complementary for group 2 0 2 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 2 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 2 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 2 0 0 0 0 1 0 0 0 0 Unable to resolve collision between groups 0 and 2. Merging groups 0 and 2. Searching solution for merged group 0+2. Open/close/exp size (steps): 72/27/72 (205) Open/close/exp size (steps): 166/75/166 (253) Open/close/exp size (steps): 252/133/252 (311) Open/close/exp size (steps): 335/203/335 (381) Open/close/exp size (steps): 595/287/595 (465) Open/close/exp size (steps): 848/388/848 (566) Open/close/exp size (steps): 1009/510/1009 (688) Open/close/exp size (steps): 983/657/983 (835) Open/close/exp size (steps): 876/834/876 (1012) Open/close/exp size (steps): 956/1047/956 (1225) Open/close/exp size (steps): 1410/1303/1410 (1481) Open/close/exp size (steps): 1795/1611/1795 (1789) Open/close/exp size (steps): 2076/1981/2076 (2159) Open/close/exp size (steps): 2767/2425/2767 (2603) Open/close/exp size (steps): 2751/2958/2751 (3136) Open/close/exp size (steps): 2863/3598/2863 (3776) Open/close/exp size (steps): 2842/4366/2842 (4544) 0 2 3 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 3 0 0 2 0 0 0 0 1 0 0 0 0 0 0 3 0 0 0 0 2 0 0 0 0 1 0 0 0 0 3 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 1 3 0 2 0 0 0 0 0 0 0 0 0 Groups 0 and 1 collide. Solution of group 0 Mulirobot solution: (|moves| = 9, paralellism = 2.250) [ Step 0: 1#14->10 2#1->5 Step 1: 1#10->11 2#5->6 3#2->1 Step 2: 1#11->7 3#1->0 Step 3: 1#7->3 3#0->4 ] Solution of group 1 Mulirobot solution: (|moves| = 1, paralellism = 1.000) [ Step 0: 1#4->5 ] Occupation table complementary for group 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 ** Open/close/exp size (steps): 6/3/6 (28) ** Open/close/exp size (steps): 19/13/19 (38) ** Open/close/exp size (steps): 40/25/40 (50) ** Open/close/exp size (steps): 66/40/66 (65) ** Open/close/exp size (steps): 83/58/83 (83) ** Open/close/exp size (steps): 99/80/99 (105) ** Open/close/exp size (steps): 149/107/149 (132) ** Open/close/exp size (steps): 209/140/209 (165) ** Open/close/exp size (steps): 262/180/262 (205) ** Open/close/exp size (steps): 325/228/325 (253) ** Open/close/exp size (steps): 426/286/426 (311) ** Open/close/exp size (steps): 534/356/534 (381) ** Open/close/exp size (steps): 576/440/576 (465) ** Open/close/exp size (steps): 575/541/575 (566) ** Open/close/exp size (steps): 614/663/614 (688) ** Open/close/exp size (steps): 523/810/523 (835) ** Open/close/exp size (steps): 578/987/578 (1012) ** Open/close/exp size (steps): 565/1200/565 (1225) ** Open/close/exp size (steps): 747/1456/747 (1481) ** Open/close/exp size (steps): 1054/1764/1054 (1789) ** Open/close/exp size (steps): 1319/2134/1319 (2159) ** Open/close/exp size (steps): 1230/2578/1230 (2603) ** Open/close/exp size (steps): 1693/3111/1693 (3136) ** Open/close/exp size (steps): 1757/3751/1757 (3776) ** Open/close/exp size (steps): 1213/4519/1213 (4544) ** Open/close/exp size (steps): 1039/5441/1039 (5466) ** Open/close/exp size (steps): 1495/6548/1495 (6573) ** Open/close/exp size (steps): 1631/7877/1631 (7902) ** Open/close/exp size (steps): 1790/9472/1790 (9497) ** Open/close/exp size (steps): 619/11386/619 (11411) Occupation table complementary for group 1 0 2 3 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 3 0 0 2 0 1 0 0 1 0 0 0 0 0 0 3 0 0 0 0 2 0 0 0 0 1 0 0 0 0 3 0 0 0 0 0 2 1 0 0 0 1 0 0 0 0 0 0 0 1 3 0 2 0 0 0 0 1 0 0 0 0 Alternative solution of group 1 Mulirobot solution: (|moves| = 3, paralellism = 1.000) [ Step 0: 1#4->0 Step 1: 1#0->4 Step 2: 1#4->5 ] 0 2 3 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 3 0 0 2 0 0 0 0 1 0 0 0 0 0 0 3 0 0 0 0 2 0 0 0 0 1 0 0 0 0 3 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 1 3 0 2 0 0 0 0 0 0 0 0 0 Collision between groups 0 and 1 resolved. 0 2 3 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 3 0 0 2 0 0 0 0 1 0 0 0 0 0 0 3 0 0 0 0 2 0 0 0 0 1 0 0 0 0 3 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 1 3 0 2 0 0 0 0 0 0 0 0 0 Groups 0 and 2 collide. Solution of group 0 Mulirobot solution: (|moves| = 9, paralellism = 2.250) [ Step 0: 1#14->10 2#1->5 Step 1: 1#10->11 2#5->6 3#2->1 Step 2: 1#11->7 3#1->0 Step 3: 1#7->3 3#0->4 ] Solution of group 2 Mulirobot solution: (|moves| = 2, paralellism = 1.000) [ Step 0: 1#3->7 Step 1: 1#7->11 ] Occupation table complementary for group 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 ** Open/close/exp size (steps): 386/222/386 (13708) Alternative solution of group 0 Mulirobot solution: (|moves| = 11, paralellism = 2.750) [ Step 0: 1#14->10 2#1->5 Step 1: 1#10->6 2#5->9 3#2->1 Step 2: 1#6->2 2#9->10 3#1->0 Step 3: 1#2->3 2#10->6 3#0->4 ] 0 2 3 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 3 0 0 2 0 0 0 0 1 0 0 0 0 0 0 3 0 0 0 0 1 0 0 2 0 0 0 0 0 0 3 0 1 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 1 3 0 2 0 0 0 0 0 0 0 0 0 Collision between groups 0 and 2 resolved. 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 Computed optimal makespan:4 Makespan optimal solution: Mulirobot solution: (|moves| = 16, paralellism = 4.000) [ Step 0: 1#14->10 3#1->5 2#4->0 4#3->7 Step 1: 1#10->6 3#5->9 5#2->1 2#0->4 4#7->11 Step 2: 1#6->2 3#9->10 5#1->0 2#4->5 Step 3: 1#2->3 3#10->6 5#0->4 ] Multirobot solution analysis: ( total makespan = 4 total distance = 9 total trajectory = 16 average parallelism = 4.000 average distance = 1.800 average trajectory = 3.200 parallelism distribution = [ 0 0 1 2 1 ] distance distribution = [ 1 2 0 1 ] trajectory distribution = [ 0 1 2 2 ] ) Phase statistics (current phase = 'root_phase') [ Phase (name = 'root_phase') [ Total SAT solver calls = 0 Satisfiable SAT solver calls = 0 Unsatisfiable SAT solver calls = 0 Indeterminate SAT solver calls = 0 Move executions = 16 Produced CNF variables = 0 Produced CNF clauses = 0 Search steps = 0 Wall clock TIME (seconds) = 0.003 CPU/machine TIME (seconds) = 0.000 ] Sub-phases { Phase (name = 'independent_solving') [ Total SAT solver calls = 0 Satisfiable SAT solver calls = 0 Unsatisfiable SAT solver calls = 0 Indeterminate SAT solver calls = 0 Move executions = 33166 Produced CNF variables = 0 Produced CNF clauses = 0 Search steps = 0 Wall clock TIME (seconds) = 0.203 CPU/machine TIME (seconds) = 0.200 ] } ] ----------------------------------------------------------------