Revision 29:57230317ea4b

View differences:

src/main/java/tt/jointeuclid2ni/Solver.java
1 1
package tt.jointeuclid2ni;
2 2

  
3
import static tt.jointtraj.util.Util.getSumCost;
4

  
5
import java.io.File;
6
import java.io.FileInputStream;
7
import java.io.FileNotFoundException;
8
import java.io.PrintWriter;
9

  
3 10
import tt.euclid2i.EvaluatedTrajectory;
4 11
import tt.euclid2i.discretization.LazyGrid;
5 12
import tt.jointeuclid2ni.probleminstance.EarliestArrivalProblem;
......
8 15
import tt.jointeuclid2ni.solver.Algorithm;
9 16
import tt.jointeuclid2ni.solver.Algorithms;
10 17
import tt.jointeuclid2ni.solver.Parameters;
11
import tt.jointeuclid2ni.solver.impl.*;
18
import tt.jointeuclid2ni.solver.impl.AlgorithmIIHP;
19
import tt.jointeuclid2ni.solver.impl.AlgorithmKSFO;
20
import tt.jointeuclid2ni.solver.impl.AlgorithmODCN;
21
import tt.jointeuclid2ni.solver.impl.AlgorithmODPiN;
22
import tt.jointeuclid2ni.solver.impl.AlgorithmORCARRT;
23
import tt.jointeuclid2ni.solver.impl.AlgorithmPP;
12 24
import tt.jointtraj.solver.SearchResult;
13 25
import tt.util.Args;
14 26
import tt.util.Counters;
15 27

  
16
import java.io.File;
17
import java.io.FileInputStream;
18
import java.io.FileNotFoundException;
19
import java.io.PrintWriter;
20

  
21
import static tt.jointtraj.util.Util.getSumCost;
22

  
23 28

  
24 29
public class Solver {
25 30

  
......
34 39
    public static void main(String[] args) throws FileNotFoundException {
35 40
        Solver solver = new Solver();
36 41
        solver.parseArgs(args);
37
        solver.solve();
42
        solver.solve(args);
38 43
    }
39 44

  
40 45
    private void parseArgs(String[] args) throws FileNotFoundException {
......
149 154
        System.out.println("  time1 posX1 posY1; time2 posX2 posY2; time3 posX3 posY3; ...");
150 155
    }
151 156

  
152
    public void solve() {
157
    public void solve(String[] args) {
153 158
        Algorithm algorithm;
154 159

  
155 160
        switch (algorithms) {
......
158 163
                break;
159 164

  
160 165
            case KSFO:
161
                algorithm = new AlgorithmKSFO();
166
                algorithm = new AlgorithmKSFO(args);
162 167
                break;
163 168

  
164 169
            case IIHP:
src/main/java/tt/jointeuclid2ni/solver/Algorithm.java
4 4
import tt.jointtraj.solver.SearchResult;
5 5

  
6 6
public interface Algorithm {
7

  
8

  
9

  
10 7
    public SearchResult solve(final EarliestArrivalProblem problem, Parameters parameters);
11 8
}
src/main/java/tt/jointeuclid2ni/solver/impl/AbstractAlgorithm.java
1 1
package tt.jointeuclid2ni.solver.impl;
2 2

  
3 3
import static tt.jointtraj.util.Util.getSumCost;
4
import cz.agents.alite.vis.VisManager;
5
import cz.agents.alite.vis.layer.common.ColorLayer;
6
import cz.agents.alite.vis.layer.common.VisInfoLayer;
7
import cz.agents.alite.vis.layer.toggle.KeyToggleLayer;
4

  
5
import java.awt.Color;
6
import java.util.Collection;
7
import java.util.Collections;
8
import java.util.LinkedList;
9

  
10
import javax.vecmath.Point2d;
11

  
8 12
import org.jgrapht.DirectedGraph;
9 13
import org.jgrapht.Graph;
10 14

  
......
26 30
import tt.jointtraj.solver.SearchResult;
27 31
import tt.util.AgentColors;
28 32
import tt.util.Counters;
29
import tt.vis.*;
30

  
31
import javax.vecmath.Point2d;
32
import java.awt.*;
33
import java.util.Collection;
34
import java.util.Collections;
35
import java.util.LinkedList;
33
import tt.vis.FastAgentsLayer;
34
import tt.vis.FastTrajectoriesLayer;
35
import tt.vis.GraphLayer;
36
import tt.vis.LabeledCircleLayer;
37
import tt.vis.ParameterControlLayer;
38
import cz.agents.alite.vis.VisManager;
39
import cz.agents.alite.vis.layer.common.ColorLayer;
40
import cz.agents.alite.vis.layer.common.VisInfoLayer;
41
import cz.agents.alite.vis.layer.toggle.KeyToggleLayer;
36 42

  
37 43

  
38 44
public abstract class AbstractAlgorithm implements Algorithm {
......
41 47
    protected EarliestArrivalProblem problem;
42 48
    protected TimeParameter time;
43 49

  
44
    protected AbstractAlgorithm() {
45
    }
46

  
47 50
    protected abstract SearchResult solveProblem();
48 51

  
49 52
    @Override
......
85 88
                params.gridPattern,
86 89
                params.gridStep).generateFullGraph();
87 90

  
88
		//        // create discretization
89
		//        final DirectedGraph<tt.euclid2i.Point, tt.euclid2i.Line> spatialGraph
90
		//                = new ToGoalEdgeExtension(grid, target, gridStep*2).generateFullGraph(start); //it's important to generate the full graph
91
		//
91
        //        // create discretization
92
        //        final DirectedGraph<tt.euclid2i.Point, tt.euclid2i.Line> spatialGraph
93
        //                = new ToGoalEdgeExtension(grid, target, gridStep*2).generateFullGraph(start); //it's important to generate the full graph
94
        //
92 95
        // create discretization
93 96
        final DirectedGraph<tt.euclid2i.Point, Line> spatialGraph
94 97
                = new AdditionalPointsExtension(grid, Collections.singleton(problem.getTarget(i)), params.gridStep, true);
......
225 228
        }
226 229
    }
227 230

  
228
	protected void printSummary(EvaluatedTrajectory[] trajs) {
229
	    String costStr;
230
	    if (trajs != null) {
231
	        double cost = getSumCost(trajs);
232
	        costStr = String.format("%.2f", cost);
233
	    } else {
234
	        costStr = "inf";
235
	    }
231
    protected void printSummary(EvaluatedTrajectory[] trajs) {
232
        String costStr;
233
        if (trajs != null) {
234
            double cost = getSumCost(trajs);
235
            costStr = String.format("%.2f", cost);
236
        } else {
237
            costStr = "inf";
238
        }
236 239

  
237
	    long runtimeElapsed = System.currentTimeMillis() - params.startedAtMs;
240
        long runtimeElapsed = System.currentTimeMillis() - params.startedAtMs;
238 241

  
239
	    System.out.print(params.summaryPrefix);
240
	    System.out.print(costStr + ";");
241
	    System.out.print(runtimeElapsed + ";");
242
	    System.out.print(Counters.expandedStatesCounter + ";");
243
	    System.out.println();
244
	}
242
        System.out.print(params.summaryPrefix);
243
        System.out.print(costStr + ";");
244
        System.out.print(runtimeElapsed + ";");
245
        System.out.print(Counters.expandedStatesCounter + ";");
246
        System.out.println();
247
    }
245 248
}
src/main/java/tt/jointeuclid2ni/solver/impl/AbstractSFBasedAlgorithm.java
22 22
    private static final double IIHP_MAX_PENALTY = 10;
23 23

  
24 24
    public AbstractSFBasedAlgorithm() {
25
        this(new String[0]);
26
    }
27

  
28
    public AbstractSFBasedAlgorithm(String[] args) {
25 29
        super();
26 30
    }
27 31

  
......
31 35

  
32 36
        // create spatial graph for each agent
33 37
        @SuppressWarnings("unchecked")
34
		DirectedGraph<Point, Line> graph[] = new DirectedGraph[problem.nAgents()];
38
        DirectedGraph<Point, Line> graph[] = new DirectedGraph[problem.nAgents()];
35 39

  
36 40
        for (int i = 0; i < problem.nAgents(); i++) {
37 41
            graph[i] = createAndShowGridForIthAgent(i);
......
41 45
        HeuristicToGoal<tt.euclidtime3i.Point>[] heuristics = new HeuristicToGoal[problem.nAgents()];
42 46

  
43 47
        for (int i = 0; i < problem.nAgents(); i++) {
44
        	heuristics[i] = new PerfectBasedHeuristic(graph[i], problem.getTarget(i));
48
            heuristics[i] = new PerfectBasedHeuristic(graph[i], problem.getTarget(i));
45 49
        }
46 50

  
47 51
        // Create trajectory optimizers
48 52
        TrajectoryOptimizer[] trajectoryOptimizers = new TrajectoryOptimizer[problem.nAgents()];
49 53
        for (int i = 0; i < problem.nAgents(); i++) {
50
        	trajectoryOptimizers[i] = new AStarTrajectoryOptimizer(graph[i],
51
        								new tt.euclidtime3i.Point(problem.getStart(i),0),
52
        								new tt.euclidtime3i.Point(problem.getTarget(i),  params.maxTime),
53
        								problem.getMaxSpeeds()[i],
54
        								params.waitMoveDuration,
55
        								heuristics[i]);
56
		}
54
            trajectoryOptimizers[i] = new AStarTrajectoryOptimizer(graph[i],
55
                                        new tt.euclidtime3i.Point(problem.getStart(i),0),
56
                                        new tt.euclidtime3i.Point(problem.getTarget(i),  params.maxTime),
57
                                        problem.getMaxSpeeds()[i],
58
                                        params.waitMoveDuration,
59
                                        heuristics[i]);
60
        }
57 61

  
58 62
        // Create constraints
59 63
        PairwiseConstraint[][] constraints = new PairwiseConstraint[problem.nAgents()][problem.nAgents()];
60 64
        for (int i = 0; i < problem.nAgents(); i++) {
61
        	for (int j = 0; j < problem.nAgents(); j++) {
62
        		if (i != j) {
63
        			constraints[i][j] = new SeparationConstraint(new LinearSeparationPenaltyFunction(IIHP_MAX_PENALTY),
64
        					10, problem.getBodyRadius(i)+problem.getBodyRadius(j));
65
        		}
65
            for (int j = 0; j < problem.nAgents(); j++) {
66
                if (i != j) {
67
                    constraints[i][j] = new SeparationConstraint(new LinearSeparationPenaltyFunction(IIHP_MAX_PENALTY),
68
                            10, problem.getBodyRadius(i)+problem.getBodyRadius(j));
69
                }
66 70

  
67 71
            }
68 72
        }
69 73

  
70 74
        EvaluatedTrajectory[] trajs = solveCore(trajectoryOptimizers, constraints);
71 75

  
72
		return new SearchResult(trajs, true);
76
        return new SearchResult(trajs, true);
73 77

  
74 78
    }
75 79

  
76
	abstract protected EvaluatedTrajectory[] solveCore(
77
			TrajectoryOptimizer[] trajectoryOptimizers,
78
			PairwiseConstraint[][] constraints) ;
80
    abstract protected EvaluatedTrajectory[] solveCore(
81
            TrajectoryOptimizer[] trajectoryOptimizers,
82
            PairwiseConstraint[][] constraints) ;
79 83

  
80 84

  
81 85
}
src/main/java/tt/jointeuclid2ni/solver/impl/AlgorithmKSFO.java
5 5
import tt.euclidtime3i.discretization.softconstraints.PairwiseConstraint;
6 6
import tt.jointtraj.separableflow.SeparableFlowOptimizer;
7 7
import tt.jointtraj.separableflow.TrajectoryOptimizer;
8
import tt.util.Args;
8 9

  
9 10

  
10 11
public class AlgorithmKSFO extends AbstractSFBasedAlgorithm {
11 12

  
12
    private static final int K = 150;
13
    private int k = 150;
13 14

  
14 15
    public AlgorithmKSFO() {
15
        super();
16
        this(new String[0]);
16 17
    }
17 18

  
18
   	protected EvaluatedTrajectory[] solveCore(
19
			TrajectoryOptimizer[] trajectoryOptimizers,
20
			PairwiseConstraint[][] constraints) {
19
    public AlgorithmKSFO(String[] args) {
20
        k = Integer.parseInt(Args.getArgumentValue(args, "-k", true));
21
    }
21 22

  
22
		EvaluatedTrajectory[] trajs
23
			= SeparableFlowOptimizer.solve(trajectoryOptimizers, constraints, K, Double.POSITIVE_INFINITY, params.runtimeDeadlineMs);
23
    @Override
24
    protected EvaluatedTrajectory[] solveCore(
25
            TrajectoryOptimizer[] trajectoryOptimizers,
26
            PairwiseConstraint[][] constraints) {
24 27

  
25
		if (params.printSummary) {
28
        EvaluatedTrajectory[] trajs = SeparableFlowOptimizer.solve(
29
                trajectoryOptimizers, constraints, k, Double.POSITIVE_INFINITY,
30
                params.runtimeDeadlineMs);
31

  
32
        if (params.printSummary) {
26 33
            printSummary(trajs);
27 34
        }
28 35

  
29
		return trajs;
30
	}
36
        return trajs;
37
    }
31 38

  
32 39

  
33 40
}
src/main/resources/eclipse/Solver.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.Solver"/>
11
<stringAttribute key="org.eclipse.jdt.launching.PROGRAM_ARGUMENTS" value="-method KSFO -problemfile src/main/resources/problems/cross_conflict.xml -timeout 500000 -maxtime 1000 -gridstep 25 -showvis -summary -grid 4"/>
11
<stringAttribute key="org.eclipse.jdt.launching.PROGRAM_ARGUMENTS" value="-method KSFO -problemfile src/main/resources/problems/cross_conflict.xml -timeout 500000 -maxtime 1000 -gridstep 25 -showvis -summary -grid 8 -k 50"/>
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/resources/problems/59.xml
1
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
2
<multiagentproblem>
3
<environment>
4
<obstacles/>
5
<bounds>
6
<point>
7
<x>0</x>
8
<y>0</y>
9
</point>
10
<point>
11
<x>1000</x>
12
<y>1000</y>
13
</point>
14
</bounds>
15
</environment>
16
<agents>
17
<agent>
18
<start>
19
<point>
20
<x>750</x>
21
<y>850</y>
22
</point>
23
</start>
24
<target>
25
<point>
26
<x>100</x>
27
<y>150</y>
28
</point>
29
</target>
30
<radius>80</radius>
31
<maxspeed>1</maxspeed>
32
</agent>
33
<agent>
34
<start>
35
<point>
36
<x>250</x>
37
<y>500</y>
38
</point>
39
</start>
40
<target>
41
<point>
42
<x>750</x>
43
<y>700</y>
44
</point>
45
</target>
46
<radius>80</radius>
47
<maxspeed>1</maxspeed>
48
</agent>
49
<agent>
50
<start>
51
<point>
52
<x>750</x>
53
<y>600</y>
54
</point>
55
</start>
56
<target>
57
<point>
58
<x>450</x>
59
<y>100</y>
60
</point>
61
</target>
62
<radius>80</radius>
63
<maxspeed>1</maxspeed>
64
</agent>
65
<agent>
66
<start>
67
<point>
68
<x>700</x>
69
<y>200</y>
70
</point>
71
</start>
72
<target>
73
<point>
74
<x>500</x>
75
<y>800</y>
76
</point>
77
</target>
78
<radius>80</radius>
79
<maxspeed>1</maxspeed>
80
</agent>
81
</agents>
82
</multiagentproblem>
src/main/resources/problems/85.xml
1
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
2
<multiagentproblem>
3
<environment>
4
<obstacles/>
5
<bounds>
6
<point>
7
<x>0</x>
8
<y>0</y>
9
</point>
10
<point>
11
<x>1000</x>
12
<y>1000</y>
13
</point>
14
</bounds>
15
</environment>
16
<agents>
17
<agent>
18
<start>
19
<point>
20
<x>750</x>
21
<y>850</y>
22
</point>
23
</start>
24
<target>
25
<point>
26
<x>100</x>
27
<y>150</y>
28
</point>
29
</target>
30
<radius>80</radius>
31
<maxspeed>1</maxspeed>
32
</agent>
33
<agent>
34
<start>
35
<point>
36
<x>250</x>
37
<y>500</y>
38
</point>
39
</start>
40
<target>
41
<point>
42
<x>750</x>
43
<y>700</y>
44
</point>
45
</target>
46
<radius>80</radius>
47
<maxspeed>1</maxspeed>
48
</agent>
49
<agent>
50
<start>
51
<point>
52
<x>750</x>
53
<y>600</y>
54
</point>
55
</start>
56
<target>
57
<point>
58
<x>450</x>
59
<y>100</y>
60
</point>
61
</target>
62
<radius>80</radius>
63
<maxspeed>1</maxspeed>
64
</agent>
65
<agent>
66
<start>
67
<point>
68
<x>700</x>
69
<y>200</y>
70
</point>
71
</start>
72
<target>
73
<point>
74
<x>500</x>
75
<y>800</y>
76
</point>
77
</target>
78
<radius>80</radius>
79
<maxspeed>1</maxspeed>
80
</agent>
81
<agent>
82
<start>
83
<point>
84
<x>400</x>
85
<y>200</y>
86
</point>
87
</start>
88
<target>
89
<point>
90
<x>100</x>
91
<y>800</y>
92
</point>
93
</target>
94
<radius>80</radius>
95
<maxspeed>1</maxspeed>
96
</agent>
97
<agent>
98
<start>
99
<point>
100
<x>900</x>
101
<y>100</y>
102
</point>
103
</start>
104
<target>
105
<point>
106
<x>300</x>
107
<y>700</y>
108
</point>
109
</target>
110
<radius>80</radius>
111
<maxspeed>1</maxspeed>
112
</agent>
113
</agents>
114
</multiagentproblem>
src/main/resources/problems/cross_conflict.xml
27 27
<y>876</y>
28 28
</point>
29 29
</target>
30
<radius>60</radius>
30
<radius>80</radius>
31 31
<maxspeed>1</maxspeed>
32 32
</agent>
33 33
<agent>

Also available in: Unified diff