Revision 203:d2053d3b5a8f

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 15 -radius 10 -seed 1005 -outfile src/main/resources/problems/101.xml -sgavoiding -showvis -verbose"/>
11
<stringAttribute key="org.eclipse.jdt.launching.PROGRAM_ARGUMENTS" value="-env src/main/resources/d-environments/101_r10.xml  -nagents 15 -radius 10 -seed 1005 -outfile src/main/resources/problems/101_r10.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>
misc/eclipse/TriangulationGenerator (alex).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.TriangulationGenerator"/>
11
<stringAttribute key="org.eclipse.jdt.launching.PROGRAM_ARGUMENTS" value="-problemfile /home/capino/projects/deconfliction/3rdparty/mrs2dplan/maps/101.xml -dispersion 30 -connectionradius 25 -bodyradius 10  -outfile src/main/resources/d-environments/101.xml -showvis -docks"/>
11
<stringAttribute key="org.eclipse.jdt.launching.PROGRAM_ARGUMENTS" value="-problemfile /home/capino/projects/deconfliction/3rdparty/mrs2dplan/maps/101.xml -dispersion 30 -connectionradius 35 -bodyradius 10  -outfile src/main/resources/d-environments/101_r10.xml -showvis -docks"/>
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
46 46
    private static final int MAX_SPEED = 1;
47 47
    private static final int MAX_ATTEMPTS_PROBLEM = 500;
48 48
    private static final int MAX_ATTEMPTS_MISSION = 150;
49
    private static final int MAX_ATTEMPTS_START = 5000;
50
    private static final int MAX_ATTEMPTS_TARGET = 5000;
49
    private static final int MAX_ATTEMPTS_START = 500;
50
    private static final int MAX_ATTEMPTS_TARGET = 500;
51 51
    private static final int RADIUS_BUFFER_GRACE = 1; 
52 52

  
53 53
    private static DirectedGraph<Point, Line>[] toGraphArray(DirectedGraph<Point, Line> planningGraph, int nAgents) {
......
211 211

  
212 212
        int attempts = 0;
213 213
        do {
214
            try {
215
                AgentMission mission = generateMission(problem, bodyRadius, possibleEndpoints, false, requireStartGoalAvoiding, planningGraph, problem.getAgentMissions(), rnd);
216
               	Trajectory trajectory = solveMission(planningGraph, mission, maxTime, problem.getAgentMissions(), requireStartGoalAvoiding);
217

  
214
            
215
            AgentMission mission = generateMission(problem, bodyRadius, possibleEndpoints, false, requireStartGoalAvoiding, planningGraph, problem.getAgentMissions(), rnd);
216
           	Trajectory trajectory = solveMission(planningGraph, mission, maxTime, problem.getAgentMissions(), requireStartGoalAvoiding);
217
           	
218
           	if (trajectory != null) {
218 219
               	if (otherTrajectories.isEmpty() || (requireConflict ? SeparationDetector.hasAnyPairwiseConflict(trajectory, otherTrajectoriesArray, separations, 5) : true)) {
219 220
               		problem.addAgent(mission);
220 221
                    otherTrajectories.add(trajectory);
221 222
                    return;
222 223
                }
223

  
224
            } catch (PathNotFoundException e) {
225
            }
224
           	}
226 225
        } while (attempts++ < MAX_ATTEMPTS_MISSION);
227 226

  
228 227
        throw new MissionNotAddedException();
......
244 243

  
245 244
        Point start = null;
246 245
        int startPointAttempts = 0;
246
        
247
        boolean collidesWithOtherStart;
248
        boolean collidesWithOtherGoal;
249
        boolean connectivityLost; 
247 250
        do {
248 251
            start = randomVertex(possibleEndpoints, rnd);
252
            Verbose.printf(" -- -- -- -- -- trying start S:%s %n", start);
249 253

  
250 254
            if (startPointAttempts++ > MAX_ATTEMPTS_START) {
251 255
                throw new MissionNotAddedException();
252 256
            }
253
        } while (collidesWithOtherStartPoint(start, bodyRadius, problem) ||
254
        		(!startAndGoalsCanOverlap ? startsGoalsOverlap(start, bodyRadius, problem) : false) || 
255
        		(sgAvoiding ? !maintainsConnectivityIfRemoved(start, bodyRadius, planningGraph, otherMissions) : false));
257
            
258
            collidesWithOtherStart = collidesWithOtherStart(start, bodyRadius, problem);
259
            collidesWithOtherGoal = (!startAndGoalsCanOverlap ? collidesWithOtherTarget(start, bodyRadius, problem) : false);
260
            connectivityLost = (sgAvoiding ? !maintainsConnectivityIfRemoved(start, null, bodyRadius, planningGraph, otherMissions) : false);
261
            Verbose.printf(" -- -- -- -- -- -- start collision: %b goal collision: %b connectivityLost: %b %n", collidesWithOtherStart, collidesWithOtherGoal, connectivityLost);
262
            
263
        } while (collidesWithOtherStart || collidesWithOtherGoal || connectivityLost);
256 264

  
257 265
        Point target = null;
258 266
        int targetPointAttempts = 0;
259 267
        do {
260 268
            target = randomVertex(possibleEndpoints, rnd);
269
            Verbose.printf(" -- -- -- -- -- trying goal G:%s %n", target);
261 270

  
262 271
            if (targetPointAttempts++ > MAX_ATTEMPTS_TARGET) {
263 272
                throw new MissionNotAddedException();
264 273
            }
265
        } while (collidesWithOtherTargetPoint(target, bodyRadius, problem) || start == target ||
266
        		(!startAndGoalsCanOverlap ? startsGoalsOverlap(target, bodyRadius, problem): false) ||
267
        		(sgAvoiding ? !maintainsConnectivityIfRemoved(target, bodyRadius, planningGraph, otherMissions) : false));
274
            
275
            collidesWithOtherGoal = collidesWithOtherTarget(start, bodyRadius, problem);
276
            collidesWithOtherStart = (!startAndGoalsCanOverlap ? collidesWithOtherStart(start, bodyRadius, problem) : false);
277
            connectivityLost = (sgAvoiding ? !maintainsConnectivityIfRemoved(start, target, bodyRadius, planningGraph, otherMissions) : false);
278

  
279
            
280
        } while (start == target || collidesWithOtherGoal || collidesWithOtherStart || connectivityLost);
268 281

  
269 282
        Verbose.printf(" -- -- -- -- new random mission S:%s G:%s%n", start, target);
270 283

  
271 284
        return new AgentMissionImpl(start, target, bodyRadius, MAX_SPEED);
272 285
    }
273 286
	
274
	private static boolean maintainsConnectivityIfRemoved(Point point,
287
	private static boolean maintainsConnectivityIfRemoved(Point start, Point target, 
275 288
			int bodyRadius, DirectedGraph<Point, Line> planningGraph, 
276 289
			AgentMission[] otherMissions) {
277 290
		
......
290 303
				}
291 304
			}
292 305
			
293
			// Hack! We will assume put start = target = point to be able to reuse removeStartsTargetsOfOtherAgents
294
			otherAgentOtherMissions[j] = new AgentMissionImpl(point, point, bodyRadius, 1); 
306
			if (target == null) {
307
				// Hack! We will put start = target to be able to reuse removeStartsTargetsOfOtherAgents method
308
				otherAgentOtherMissions[j] = new AgentMissionImpl(start, start, bodyRadius, 1); 
309
			} else {
310
				otherAgentOtherMissions[j] = new AgentMissionImpl(start, target, bodyRadius, 1); 
311
			}
295 312
			
296 313
			DirectedGraph<Point, Line> augmentedGraph = removeStartsTargetsOfOtherAgents(planningGraph, otherAgentOtherMissions, otherAgentBodyRadius);
297 314
			
298 315
			if (!isReachable(otherAgentStart, otherAgentTarget, augmentedGraph)) {
316
				Verbose.printf(" -- -- -- -- -- -- reachablility lost between: %s and: %s %n", otherAgentStart, otherAgentTarget);
299 317
				return false;
300 318
			}
301 319
		}
......
303 321
		return true;
304 322
	}
305 323

  
306
	private static Trajectory solveMission(DirectedGraph<Point, Line> graph, AgentMission mission, int maxTime, AgentMission[] otherMissions, boolean requireStartGoalAvoiding) throws PathNotFoundException {
324
	private static Trajectory solveMission(DirectedGraph<Point, Line> graph,
325
			AgentMission mission, int maxTime, AgentMission[] otherMissions,
326
			boolean requireStartGoalAvoiding) {
307 327
    	
308 328
        Point target = mission.getTarget();
309 329
        Point start = mission.getStart();
330
        int bodyRadius = mission.getBodyRadius();
310 331
        
311 332
        if (requireStartGoalAvoiding) {
312
        	graph = removeStartsTargetsOfOtherAgents(graph, otherMissions, mission.getBodyRadius());
333
        	graph = removeStartsTargetsOfOtherAgents(graph, otherMissions, bodyRadius);
313 334
        }
314 335

  
315 336
        GraphPath<Point, Line> path = AStarShortestPathSimple.findPathBetween(graph, new HeuristicToPoint(target), start, target);
316 337

  
317 338
        if (path == null)
318
            throw new PathNotFoundException();
339
            return null;
319 340

  
341
        assert isReachable(start, target, graph);
342
        
320 343
        return SegmentedTrajectoryFactory.createConstantSpeedTrajectory(path, 0, mission.getMaxSpeed(),
321 344
                maxTime, path.getWeight() / MAX_SPEED);
322 345
    }
......
334 357
    	return new ObstacleWrapper<Point, Line>(directedGraph, startTargetRegions);
335 358
	}
336 359

  
337
	static private boolean collidesWithOtherStartPoint(Point start, int bodyRadius, ExtensibleProblem currentProblem) {
360
	static private boolean collidesWithOtherStart(Point start, int bodyRadius, ExtensibleProblem currentProblem) {
338 361
		AgentMission[] otherMissions = currentProblem.getAgentMissions();
339 362
        for (AgentMission mission : otherMissions) {
340 363
            double sep = mission.getBodyRadius() + bodyRadius;
......
347 370
        return false;
348 371
    }
349 372

  
350
    static private boolean startsGoalsOverlap(Point point, int bodyRadius, ExtensibleProblem currentProblem) {
351
    	AgentMission[] otherMissions = currentProblem.getAgentMissions();
352
    	for (AgentMission otherMission : otherMissions) {
353
            double sep = otherMission.getBodyRadius() + bodyRadius;
354

  
355
            // start-start
356
            if (sep / otherMission.getStart().distance(point) > 0.99)
357
                return true;
358

  
359
            // start-target
360
            if (sep / otherMission.getStart().distance(point) > 0.99)
361
                return true;
362
        }
363
        return false;
364
    }
365

  
366
	static private boolean collidesWithOtherTargetPoint(Point start, int bodyRadius, ExtensibleProblem currentProblem) {
373
	static private boolean collidesWithOtherTarget(Point start, int bodyRadius, ExtensibleProblem currentProblem) {
367 374
        AgentMission[] otherMissions = currentProblem.getAgentMissions();
368 375
        for (AgentMission mission : otherMissions) {
369 376
            double sep = mission.getBodyRadius() + bodyRadius;

Also available in: Unified diff