Revision 199:945c92506424

View differences:

misc/eclipse/GenerateInstance.launch
8 8
</listAttribute>
9 9
<stringAttribute key="org.eclipse.jdt.launching.CLASSPATH_PROVIDER" value="org.eclipse.m2e.launchconfig.classpathProvider"/>
10 10
<stringAttribute key="org.eclipse.jdt.launching.MAIN_TYPE" value="tt.jointeuclid2ni.probleminstance.generator.GenerateInstance"/>
11
<stringAttribute key="org.eclipse.jdt.launching.PROGRAM_ARGUMENTS" value="-env src/main/resources/d-environments/101.xml  -nagents 12 -radius 10 -seed 1005 -outfile src/main/resources/problems/101.xml -sgavoiding -onecluster -showvis -verbose"/>
11
<stringAttribute key="org.eclipse.jdt.launching.PROGRAM_ARGUMENTS" value="-env src/main/resources/d-environments/101.xml  -nagents 15 -radius 10 -seed 1005 -outfile src/main/resources/problems/101.xml -sgavoiding -showvis -verbose"/>
12 12
<stringAttribute key="org.eclipse.jdt.launching.PROJECT_ATTR" value="deconflictiontools"/>
13 13
<stringAttribute key="org.eclipse.jdt.launching.SOURCE_PATH_PROVIDER" value="org.eclipse.m2e.launchconfig.sourcepathProvider"/>
14 14
</launchConfiguration>
src/main/java/tt/jointeuclid2ni/probleminstance/generator/ConflictGenerator.java
7 7
import java.util.Random;
8 8
import java.util.Set;
9 9

  
10
import javax.print.attribute.standard.MediaSize.Other;
11

  
10 12
import org.jgrapht.DirectedGraph;
11 13
import org.jgrapht.GraphPath;
12 14
import org.jgrapht.alg.AStarShortestPathSimple;
......
24 26
import tt.euclid2i.trajectory.SegmentedTrajectoryFactory;
25 27
import tt.euclid2i.util.SeparationDetector;
26 28
import tt.euclid2i.util.Util;
29
import tt.euclidtime3i.region.MovingCircle;
27 30
import tt.jointeuclid2ni.probleminstance.AgentMission;
28 31
import tt.jointeuclid2ni.probleminstance.AgentMissionImpl;
29 32
import tt.jointeuclid2ni.probleminstance.EarliestArrivalProblem;
......
277 280
        int attempts = 0;
278 281
        do {
279 282
            try {
280
                AgentMission mission = generateMission(problem, bodyRadius, possibleEndpoints, false, rnd);
283
                AgentMission mission = generateMission(problem, bodyRadius, possibleEndpoints, false, problem.getAgentMissions(), otherTrajectoriesArray, rnd);
281 284

  
282 285
               	Trajectory trajectory = solveMission(planningGraph, mission, maxTime, problem.getAgentMissions(), requireStartGoalAvoiding);
283 286

  
284 287
               	if (otherTrajectories.isEmpty() || (requireConflict ? SeparationDetector.hasAnyPairwiseConflict(trajectory, otherTrajectoriesArray, separations, 5) : true)) {
285
                    problem.addAgent(mission);
288
               		
289
               		problem.addAgent(mission);
286 290
                    otherTrajectories.add(trajectory);
287 291
                    return;
288 292
                }
......
302 306
        return separations;
303 307
    }
304 308

  
305
    static private AgentMission generateMission(ExtensibleProblem problem, int bodyRadius, Collection<Point> possibleEndpoints, boolean startAndGoalsCanOverlap, Random rnd) throws MissionNotAddedException {
309
	static private AgentMission generateMission(ExtensibleProblem problem,
310
			int bodyRadius, Collection<Point> possibleEndpoints,
311
			boolean startAndGoalsCanOverlap, AgentMission[] otherMissions, Trajectory[] otherTrajectories,
312
			Random rnd) throws MissionNotAddedException {
306 313

  
307 314
        Point start = null;
308 315
        int startPointAttempts = 0;
......
312 319
            if (startPointAttempts++ > MAX_ATTEMPTS_START) {
313 320
                throw new MissionNotAddedException();
314 321
            }
315
        } while (collidesWithOtherStartPoint(start, bodyRadius, problem));
322
        } while (collidesWithOtherStartPoint(start, bodyRadius, problem) ||
323
        		!startAndGoalsCanOverlap ? startsGoalsOverlap(start, bodyRadius, problem): false || 
324
        		 collidesWithOtherTrajectory(start, bodyRadius, otherMissions, otherTrajectories));
316 325

  
317 326
        Point target = null;
318 327
        int targetPointAttempts = 0;
......
323 332
                throw new MissionNotAddedException();
324 333
            }
325 334
        } while (collidesWithOtherTargetPoint(target, bodyRadius, problem) || start == target ||
326
        		!startAndGoalsCanOverlap ? startsGoalsOverlap(start, target, bodyRadius, problem): false);
335
        		!startAndGoalsCanOverlap ? startsGoalsOverlap(target, bodyRadius, problem): false ||
336
        		collidesWithOtherTrajectory(target, bodyRadius, otherMissions, otherTrajectories));
327 337

  
328 338
        Verbose.printf(" -- -- -- -- new random mission S:%s G:%s%n", start, target);
329 339

  
330 340
        return new AgentMissionImpl(start, target, bodyRadius, MAX_SPEED);
331 341
    }
332 342

  
333
    private static Trajectory solveMission(DirectedGraph<Point, Line> graph, AgentMission mission, int maxTime, AgentMission[] otherMissions, boolean requireStartGoalAvoiding) throws PathNotFoundException {
334 343

  
344
	private static boolean collidesWithOtherTrajectory(Point point, int bodyRadius,
345
			AgentMission[] otherMissions, Trajectory[] otherTrajectories) {
346
		
347
		for (int i = 0; i < otherTrajectories.length; i++) {
348
			MovingCircle mc = new MovingCircle(otherTrajectories[i], otherMissions[i].getBodyRadius() + bodyRadius);
349
			if (mc.intersectsPoint(point)) {
350
				return true;
351
			}
352
		}
353
		
354
		return false;
355
	}
356

  
357
	private static Trajectory solveMission(DirectedGraph<Point, Line> graph, AgentMission mission, int maxTime, AgentMission[] otherMissions, boolean requireStartGoalAvoiding) throws PathNotFoundException {
358
    	
359
    	final int RADIUS_BUFFER = 1;
360
    	
335 361
        Point target = mission.getTarget();
336 362
        Point start = mission.getStart();
337 363
        
338 364
        if (requireStartGoalAvoiding) {
339
        	graph = removeStartsTargetsOfOtherAgents(graph, otherMissions, mission.getBodyRadius());
365
        	graph = removeStartsTargetsOfOtherAgents(graph, otherMissions, mission.getBodyRadius() + RADIUS_BUFFER);
340 366
        }
341 367

  
342 368
        GraphPath<Point, Line> path = AStarShortestPathSimple.findPathBetween(graph, new HeuristicToPoint(target), start, target);
......
374 400
        return false;
375 401
    }
376 402

  
377
    static private boolean startsGoalsOverlap(Point start, Point target, int bodyRadius, ExtensibleProblem currentProblem) {
403
    static private boolean startsGoalsOverlap(Point point, int bodyRadius, ExtensibleProblem currentProblem) {
378 404
    	AgentMission[] otherMissions = currentProblem.getAgentMissions();
379 405
    	for (AgentMission otherMission : otherMissions) {
380 406
            double sep = otherMission.getBodyRadius() + bodyRadius;
381 407

  
382 408
            // start-start
383
            if (sep / otherMission.getStart().distance(start) > 0.99)
409
            if (sep / otherMission.getStart().distance(point) > 0.99)
384 410
                return true;
385 411

  
386 412
            // start-target
387
            if (sep / otherMission.getStart().distance(target) > 0.99)
388
                return true;
389

  
390
            // target-target
391
            if (sep / otherMission.getTarget().distance(target) > 0.99)
392
                return true;
393

  
394
            // target-start
395
            if (sep / otherMission.getTarget().distance(start) > 0.99)
413
            if (sep / otherMission.getStart().distance(point) > 0.99)
396 414
                return true;
397 415
        }
398 416
        return false;
src/main/java/tt/jointeuclid2ni/probleminstance/generator/GenerateInstance.java
46 46
        	} else {
47 47
        		docks = problem.getPlanningGraph().vertexSet();
48 48
        	}
49
        	instance = ConflictGenerator.generateInstance(problem.getEnvironment(), problem.getPlanningGraph(), docks, bodyRadiuses, MAXTIME, oneCluster, sgAvoiding, new Random(seed));
49
			instance = ConflictGenerator.generateInstance(
50
					problem.getEnvironment(), problem.getPlanningGraph(),
51
					docks, bodyRadiuses, MAXTIME, oneCluster, sgAvoiding,
52
					new Random(seed));
50 53
        } else {
51
        	instance = ConflictGenerator.generateInstance(problem.getEnvironment(), bodyRadiuses, pattern, step, missionArea, MAXTIME, oneCluster, sgAvoiding, new Random(seed));
54
			instance = ConflictGenerator.generateInstance(
55
					problem.getEnvironment(), bodyRadiuses, pattern, step,
56
					missionArea, MAXTIME, oneCluster, sgAvoiding, 
57
					new Random(seed));
52 58
        }
53 59
        
54 60
        return instance;
src/main/resources/problems/101.xml
15 15
<agent>
16 16
<start>
17 17
<point>
18
<x>1051</x>
19
<y>169</y>
18
<x>438</x>
19
<y>322</y>
20
</point>
21
</start>
22
<target>
23
<point>
24
<x>634</x>
25
<y>391</y>
26
</point>
27
</target>
28
<radius>10</radius>
29
<maxspeed>1</maxspeed>
30
</agent>
31
<agent>
32
<start>
33
<point>
34
<x>559</x>
35
<y>342</y>
36
</point>
37
</start>
38
<target>
39
<point>
40
<x>116</x>
41
<y>341</y>
42
</point>
43
</target>
44
<radius>10</radius>
45
<maxspeed>1</maxspeed>
46
</agent>
47
<agent>
48
<start>
49
<point>
50
<x>460</x>
51
<y>220</y>
52
</point>
53
</start>
54
<target>
55
<point>
56
<x>94</x>
57
<y>334</y>
58
</point>
59
</target>
60
<radius>10</radius>
61
<maxspeed>1</maxspeed>
62
</agent>
63
<agent>
64
<start>
65
<point>
66
<x>833</x>
67
<y>154</y>
68
</point>
69
</start>
70
<target>
71
<point>
72
<x>457</x>
73
<y>337</y>
74
</point>
75
</target>
76
<radius>10</radius>
77
<maxspeed>1</maxspeed>
78
</agent>
79
<agent>
80
<start>
81
<point>
82
<x>686</x>
83
<y>377</y>
84
</point>
85
</start>
86
<target>
87
<point>
88
<x>396</x>
89
<y>226</y>
90
</point>
91
</target>
92
<radius>10</radius>
93
<maxspeed>1</maxspeed>
94
</agent>
95
<agent>
96
<start>
97
<point>
98
<x>963</x>
99
<y>356</y>
20 100
</point>
21 101
</start>
22 102
<target>
......
31 111
<agent>
32 112
<start>
33 113
<point>
34
<x>783</x>
35
<y>171</y>
114
<x>759</x>
115
<y>178</y>
36 116
</point>
37 117
</start>
38 118
<target>
39 119
<point>
40
<x>783</x>
41
<y>171</y>
120
<x>331</x>
121
<y>223</y>
42 122
</point>
43 123
</target>
44 124
<radius>10</radius>
......
47 127
<agent>
48 128
<start>
49 129
<point>
50
<x>833</x>
51
<y>154</y>
130
<x>751</x>
131
<y>323</y>
52 132
</point>
53 133
</start>
54 134
<target>
55 135
<point>
56
<x>546</x>
57
<y>204</y>
136
<x>773</x>
137
<y>326</y>
58 138
</point>
59 139
</target>
60 140
<radius>10</radius>
......
63 143
<agent>
64 144
<start>
65 145
<point>
66
<x>1035</x>
67
<y>154</y>
146
<x>1009</x>
147
<y>357</y>
68 148
</point>
69 149
</start>
70 150
<target>
71 151
<point>
72
<x>1009</x>
73
<y>357</y>
152
<x>687</x>
153
<y>184</y>
74 154
</point>
75 155
</target>
76 156
<radius>10</radius>
......
79 159
<agent>
80 160
<start>
81 161
<point>
82
<x>1065</x>
83
<y>203</y>
162
<x>344</x>
163
<y>334</y>
84 164
</point>
85 165
</start>
86 166
<target>
87 167
<point>
88
<x>311</x>
89
<y>235</y>
168
<x>1062</x>
169
<y>253</y>
90 170
</point>
91 171
</target>
92 172
<radius>10</radius>
......
95 175
<agent>
96 176
<start>
97 177
<point>
98
<x>711</x>
99
<y>182</y>
178
<x>430</x>
179
<y>224</y>
100 180
</point>
101 181
</start>
102 182
<target>
103 183
<point>
104
<x>1063</x>
105
<y>231</y>
184
<x>635</x>
185
<y>348</y>
106 186
</point>
107 187
</target>
108 188
<radius>10</radius>
......
111 191
<agent>
112 192
<start>
113 193
<point>
114
<x>733</x>
115
<y>179</y>
194
<x>241</x>
195
<y>385</y>
116 196
</point>
117 197
</start>
118 198
<target>
119 199
<point>
120
<x>617</x>
121
<y>194</y>
122
</point>
123
</target>
124
<radius>10</radius>
125
<maxspeed>1</maxspeed>
126
</agent>
127
<agent>
128
<start>
129
<point>
130
<x>374</x>
131
<y>228</y>
132
</point>
133
</start>
134
<target>
135
<point>
136
<x>759</x>
137
<y>178</y>
138
</point>
139
</target>
140
<radius>10</radius>
141
<maxspeed>1</maxspeed>
142
</agent>
143
<agent>
144
<start>
145
<point>
146
<x>687</x>
147
<y>184</y>
148
</point>
149
</start>
150
<target>
151
<point>
152
<x>344</x>
153
<y>334</y>
154
</point>
155
</target>
156
<radius>10</radius>
157
<maxspeed>1</maxspeed>
158
</agent>
159
<agent>
160
<start>
161
<point>
162
<x>600</x>
163
<y>210</y>
164
</point>
165
</start>
166
<target>
167
<point>
168
<x>963</x>
169
<y>356</y>
200
<x>1051</x>
201
<y>169</y>
170 202
</point>
171 203
</target>
172 204
<radius>10</radius>
......
181 213
</start>
182 214
<target>
183 215
<point>
184
<x>94</x>
185
<y>334</y>
216
<x>611</x>
217
<y>345</y>
186 218
</point>
187 219
</target>
188 220
<radius>10</radius>
......
191 223
<agent>
192 224
<start>
193 225
<point>
194
<x>773</x>
195
<y>326</y>
226
<x>240</x>
227
<y>243</y>
196 228
</point>
197 229
</start>
198 230
<target>
199 231
<point>
200
<x>524</x>
201
<y>208</y>
232
<x>1059</x>
233
<y>328</y>
234
</point>
235
</target>
236
<radius>10</radius>
237
<maxspeed>1</maxspeed>
238
</agent>
239
<agent>
240
<start>
241
<point>
242
<x>535</x>
243
<y>341</y>
244
</point>
245
</start>
246
<target>
247
<point>
248
<x>251</x>
249
<y>331</y>
202 250
</point>
203 251
</target>
204 252
<radius>10</radius>

Also available in: Unified diff