Revision 192:911d35bd4cdc

View differences:

.hgignore
2 2

  
3 3
log
4 4
target
5
*/.idea/*
5
.idea
6 6
.settings
7 7

  
8 8
*.log*
.idea/libraries/Maven__ags_utils_dataStructures_kdtreerednaxela_3_0_SNAPSHOT.xml
1
<component name="libraryTable">
2
  <library name="Maven: ags.utils.dataStructures:kdtreerednaxela:3.0-SNAPSHOT">
3
    <CLASSES>
4
      <root url="jar://$MAVEN_REPOSITORY$/ags/utils/dataStructures/kdtreerednaxela/3.0-SNAPSHOT/kdtreerednaxela-3.0-SNAPSHOT.jar!/" />
5
    </CLASSES>
6
    <JAVADOC>
7
      <root url="jar://$MAVEN_REPOSITORY$/ags/utils/dataStructures/kdtreerednaxela/3.0-SNAPSHOT/kdtreerednaxela-3.0-SNAPSHOT-javadoc.jar!/" />
8
    </JAVADOC>
9
    <SOURCES>
10
      <root url="jar://$MAVEN_REPOSITORY$/ags/utils/dataStructures/kdtreerednaxela/3.0-SNAPSHOT/kdtreerednaxela-3.0-SNAPSHOT-sources.jar!/" />
11
    </SOURCES>
12
  </library>
13
</component>
.idea/libraries/Maven__com_google_guava_guava_15_0.xml
1
<component name="libraryTable">
2
  <library name="Maven: com.google.guava:guava:15.0">
3
    <CLASSES>
4
      <root url="jar://$MAVEN_REPOSITORY$/com/google/guava/guava/15.0/guava-15.0.jar!/" />
5
    </CLASSES>
6
    <JAVADOC>
7
      <root url="jar://$MAVEN_REPOSITORY$/com/google/guava/guava/15.0/guava-15.0-javadoc.jar!/" />
8
    </JAVADOC>
9
    <SOURCES>
10
      <root url="jar://$MAVEN_REPOSITORY$/com/google/guava/guava/15.0/guava-15.0-sources.jar!/" />
11
    </SOURCES>
12
  </library>
13
</component>
.idea/libraries/Maven__com_vividsolutions_jts_1_12.xml
1
<component name="libraryTable">
2
  <library name="Maven: com.vividsolutions:jts:1.12">
3
    <CLASSES>
4
      <root url="jar://$MAVEN_REPOSITORY$/com/vividsolutions/jts/1.12/jts-1.12.jar!/" />
5
    </CLASSES>
6
    <JAVADOC>
7
      <root url="jar://$MAVEN_REPOSITORY$/com/vividsolutions/jts/1.12/jts-1.12-javadoc.jar!/" />
8
    </JAVADOC>
9
    <SOURCES>
10
      <root url="jar://$MAVEN_REPOSITORY$/com/vividsolutions/jts/1.12/jts-1.12-sources.jar!/" />
11
    </SOURCES>
12
  </library>
13
</component>
.idea/libraries/Maven__cz_agents_alite_alite_1_0_SNAPSHOT.xml
1
<component name="libraryTable">
2
  <library name="Maven: cz.agents.alite:alite:1.0-SNAPSHOT">
3
    <CLASSES>
4
      <root url="jar://$MAVEN_REPOSITORY$/cz/agents/alite/alite/1.0-SNAPSHOT/alite-1.0-20130913.125313-74.jar!/" />
5
    </CLASSES>
6
    <JAVADOC>
7
      <root url="jar://$MAVEN_REPOSITORY$/cz/agents/alite/alite/1.0-SNAPSHOT/alite-1.0-20130913.125313-74-javadoc.jar!/" />
8
    </JAVADOC>
9
    <SOURCES>
10
      <root url="jar://$MAVEN_REPOSITORY$/cz/agents/alite/alite/1.0-SNAPSHOT/alite-1.0-20130913.125313-74-sources.jar!/" />
11
    </SOURCES>
12
  </library>
13
</component>
.idea/libraries/Maven__cz_agents_alite_trajectorytools_2_0_SNAPSHOT.xml
1
<component name="libraryTable">
2
  <library name="Maven: cz.agents.alite:trajectorytools:2.0-SNAPSHOT">
3
    <CLASSES>
4
      <root url="jar://$MAVEN_REPOSITORY$/cz/agents/alite/trajectorytools/2.0-SNAPSHOT/trajectorytools-2.0-SNAPSHOT.jar!/" />
5
    </CLASSES>
6
    <JAVADOC>
7
      <root url="jar://$MAVEN_REPOSITORY$/cz/agents/alite/trajectorytools/2.0-SNAPSHOT/trajectorytools-2.0-SNAPSHOT-javadoc.jar!/" />
8
    </JAVADOC>
9
    <SOURCES>
10
      <root url="jar://$MAVEN_REPOSITORY$/cz/agents/alite/trajectorytools/2.0-SNAPSHOT/trajectorytools-2.0-SNAPSHOT-sources.jar!/" />
11
    </SOURCES>
12
  </library>
13
</component>
.idea/libraries/Maven__java3d_vecmath_1_5_2.xml
1
<component name="libraryTable">
2
  <library name="Maven: java3d:vecmath:1.5.2">
3
    <CLASSES>
4
      <root url="jar://$MAVEN_REPOSITORY$/java3d/vecmath/1.5.2/vecmath-1.5.2.jar!/" />
5
    </CLASSES>
6
    <JAVADOC>
7
      <root url="jar://$MAVEN_REPOSITORY$/java3d/vecmath/1.5.2/vecmath-1.5.2-javadoc.jar!/" />
8
    </JAVADOC>
9
    <SOURCES>
10
      <root url="jar://$MAVEN_REPOSITORY$/java3d/vecmath/1.5.2/vecmath-1.5.2-sources.jar!/" />
11
    </SOURCES>
12
  </library>
13
</component>
.idea/libraries/Maven__jgraph_jgraph_5_13_0_0.xml
1
<component name="libraryTable">
2
  <library name="Maven: jgraph:jgraph:5.13.0.0">
3
    <CLASSES>
4
      <root url="jar://$MAVEN_REPOSITORY$/jgraph/jgraph/5.13.0.0/jgraph-5.13.0.0.jar!/" />
5
    </CLASSES>
6
    <JAVADOC>
7
      <root url="jar://$MAVEN_REPOSITORY$/jgraph/jgraph/5.13.0.0/jgraph-5.13.0.0-javadoc.jar!/" />
8
    </JAVADOC>
9
    <SOURCES>
10
      <root url="jar://$MAVEN_REPOSITORY$/jgraph/jgraph/5.13.0.0/jgraph-5.13.0.0-sources.jar!/" />
11
    </SOURCES>
12
  </library>
13
</component>
.idea/libraries/Maven__jgrapht_jdk1_6_jgrapht_jdk1_6_0_8_2.xml
1
<component name="libraryTable">
2
  <library name="Maven: jgrapht-jdk1.6:jgrapht-jdk1.6:0.8.2">
3
    <CLASSES>
4
      <root url="jar://$MAVEN_REPOSITORY$/jgrapht-jdk1/6/jgrapht-jdk1.6/0.8.2/jgrapht-jdk1.6-0.8.2.jar!/" />
5
    </CLASSES>
6
    <JAVADOC>
7
      <root url="jar://$MAVEN_REPOSITORY$/jgrapht-jdk1/6/jgrapht-jdk1.6/0.8.2/jgrapht-jdk1.6-0.8.2-javadoc.jar!/" />
8
    </JAVADOC>
9
    <SOURCES>
10
      <root url="jar://$MAVEN_REPOSITORY$/jgrapht-jdk1/6/jgrapht-jdk1.6/0.8.2/jgrapht-jdk1.6-0.8.2-sources.jar!/" />
11
    </SOURCES>
12
  </library>
13
</component>
.idea/libraries/Maven__junit_junit_4_8_2.xml
1
<component name="libraryTable">
2
  <library name="Maven: junit:junit:4.8.2">
3
    <CLASSES>
4
      <root url="jar://$MAVEN_REPOSITORY$/junit/junit/4.8.2/junit-4.8.2.jar!/" />
5
    </CLASSES>
6
    <JAVADOC>
7
      <root url="jar://$MAVEN_REPOSITORY$/junit/junit/4.8.2/junit-4.8.2-javadoc.jar!/" />
8
    </JAVADOC>
9
    <SOURCES>
10
      <root url="jar://$MAVEN_REPOSITORY$/junit/junit/4.8.2/junit-4.8.2-sources.jar!/" />
11
    </SOURCES>
12
  </library>
13
</component>
.idea/libraries/Maven__log4j_log4j_1_2_16.xml
1
<component name="libraryTable">
2
  <library name="Maven: log4j:log4j:1.2.16">
3
    <CLASSES>
4
      <root url="jar://$MAVEN_REPOSITORY$/log4j/log4j/1.2.16/log4j-1.2.16.jar!/" />
5
    </CLASSES>
6
    <JAVADOC>
7
      <root url="jar://$MAVEN_REPOSITORY$/log4j/log4j/1.2.16/log4j-1.2.16-javadoc.jar!/" />
8
    </JAVADOC>
9
    <SOURCES>
10
      <root url="jar://$MAVEN_REPOSITORY$/log4j/log4j/1.2.16/log4j-1.2.16-sources.jar!/" />
11
    </SOURCES>
12
  </library>
13
</component>
.idea/libraries/Maven__math_javageom_javaGeom_0_11_1.xml
1
<component name="libraryTable">
2
  <library name="Maven: math.javageom:javaGeom:0.11.1">
3
    <CLASSES>
4
      <root url="jar://$MAVEN_REPOSITORY$/math/javageom/javaGeom/0.11.1/javaGeom-0.11.1.jar!/" />
5
    </CLASSES>
6
    <JAVADOC>
7
      <root url="jar://$MAVEN_REPOSITORY$/math/javageom/javaGeom/0.11.1/javaGeom-0.11.1-javadoc.jar!/" />
8
    </JAVADOC>
9
    <SOURCES>
10
      <root url="jar://$MAVEN_REPOSITORY$/math/javageom/javaGeom/0.11.1/javaGeom-0.11.1-sources.jar!/" />
11
    </SOURCES>
12
  </library>
13
</component>
.idea/libraries/Maven__org_apache_commons_commons_lang3_3_1.xml
1
<component name="libraryTable">
2
  <library name="Maven: org.apache.commons:commons-lang3:3.1">
3
    <CLASSES>
4
      <root url="jar://$MAVEN_REPOSITORY$/org/apache/commons/commons-lang3/3.1/commons-lang3-3.1.jar!/" />
5
    </CLASSES>
6
    <JAVADOC>
7
      <root url="jar://$MAVEN_REPOSITORY$/org/apache/commons/commons-lang3/3.1/commons-lang3-3.1-javadoc.jar!/" />
8
    </JAVADOC>
9
    <SOURCES>
10
      <root url="jar://$MAVEN_REPOSITORY$/org/apache/commons/commons-lang3/3.1/commons-lang3-3.1-sources.jar!/" />
11
    </SOURCES>
12
  </library>
13
</component>
.idea/libraries/Maven__org_jscience_jscience_4_3_1.xml
1
<component name="libraryTable">
2
  <library name="Maven: org.jscience:jscience:4.3.1">
3
    <CLASSES>
4
      <root url="jar://$MAVEN_REPOSITORY$/org/jscience/jscience/4.3.1/jscience-4.3.1.jar!/" />
5
    </CLASSES>
6
    <JAVADOC>
7
      <root url="jar://$MAVEN_REPOSITORY$/org/jscience/jscience/4.3.1/jscience-4.3.1-javadoc.jar!/" />
8
    </JAVADOC>
9
    <SOURCES>
10
      <root url="jar://$MAVEN_REPOSITORY$/org/jscience/jscience/4.3.1/jscience-4.3.1-sources.jar!/" />
11
    </SOURCES>
12
  </library>
13
</component>
.idea/libraries/Maven__org_teneighty_heaps_2_0_0.xml
1
<component name="libraryTable">
2
  <library name="Maven: org.teneighty:heaps:2.0.0">
3
    <CLASSES>
4
      <root url="jar://$MAVEN_REPOSITORY$/org/teneighty/heaps/2.0.0/heaps-2.0.0.jar!/" />
5
    </CLASSES>
6
    <JAVADOC>
7
      <root url="jar://$MAVEN_REPOSITORY$/org/teneighty/heaps/2.0.0/heaps-2.0.0-javadoc.jar!/" />
8
    </JAVADOC>
9
    <SOURCES>
10
      <root url="jar://$MAVEN_REPOSITORY$/org/teneighty/heaps/2.0.0/heaps-2.0.0-sources.jar!/" />
11
    </SOURCES>
12
  </library>
13
</component>
.idea/libraries/Maven__xerces_xercesImpl_2_11_0.xml
1
<component name="libraryTable">
2
  <library name="Maven: xerces:xercesImpl:2.11.0">
3
    <CLASSES>
4
      <root url="jar://$MAVEN_REPOSITORY$/xerces/xercesImpl/2.11.0/xercesImpl-2.11.0.jar!/" />
5
    </CLASSES>
6
    <JAVADOC>
7
      <root url="jar://$MAVEN_REPOSITORY$/xerces/xercesImpl/2.11.0/xercesImpl-2.11.0-javadoc.jar!/" />
8
    </JAVADOC>
9
    <SOURCES>
10
      <root url="jar://$MAVEN_REPOSITORY$/xerces/xercesImpl/2.11.0/xercesImpl-2.11.0-sources.jar!/" />
11
    </SOURCES>
12
  </library>
13
</component>
.idea/libraries/Maven__xml_apis_xml_apis_1_4_01.xml
1
<component name="libraryTable">
2
  <library name="Maven: xml-apis:xml-apis:1.4.01">
3
    <CLASSES>
4
      <root url="jar://$MAVEN_REPOSITORY$/xml-apis/xml-apis/1.4.01/xml-apis-1.4.01.jar!/" />
5
    </CLASSES>
6
    <JAVADOC>
7
      <root url="jar://$MAVEN_REPOSITORY$/xml-apis/xml-apis/1.4.01/xml-apis-1.4.01-javadoc.jar!/" />
8
    </JAVADOC>
9
    <SOURCES>
10
      <root url="jar://$MAVEN_REPOSITORY$/xml-apis/xml-apis/1.4.01/xml-apis-1.4.01-sources.jar!/" />
11
    </SOURCES>
12
  </library>
13
</component>
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/environments/csail.xml -nagents 10 -radius 24 -gridpattern 8  -gridstep 50 -seed 1000"/>
11
<stringAttribute key="org.eclipse.jdt.launching.PROGRAM_ARGUMENTS" value="-env src/main/resources/d-environments/101.xml -nagents 15 -radius 10 -seed 1011 -outfile src/main/resources/problems/101.xml -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/Solver (experiment tuning).launch
1
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
2
<launchConfiguration type="org.eclipse.jdt.launching.localJavaApplication">
3
<listAttribute key="org.eclipse.debug.core.MAPPED_RESOURCE_PATHS">
4
<listEntry value="/deconflictiontools"/>
5
</listAttribute>
6
<listAttribute key="org.eclipse.debug.core.MAPPED_RESOURCE_TYPES">
7
<listEntry value="4"/>
8
</listAttribute>
9
<stringAttribute key="org.eclipse.jdt.launching.CLASSPATH_PROVIDER" value="org.eclipse.m2e.launchconfig.classpathProvider"/>
10
<stringAttribute key="org.eclipse.jdt.launching.MAIN_TYPE" value="tt.euclidtime3i.Solver"/>
11
<stringAttribute key="org.eclipse.jdt.launching.PROGRAM_ARGUMENTS" value="-method PP -problemfile /home/capino/projects/deconfliction/repo/experiments/iterative/instances/empty/88.xml cross_conflict.xml -timeout 5000 -maxtime 2500 -gridstep 100 -showvis -summary -grid 4"/>
12
<stringAttribute key="org.eclipse.jdt.launching.PROJECT_ATTR" value="deconflictiontools"/>
13
<stringAttribute key="org.eclipse.jdt.launching.SOURCE_PATH_PROVIDER" value="org.eclipse.m2e.launchconfig.sourcepathProvider"/>
14
</launchConfiguration>
misc/eclipse/Solver (experiments).launch
1
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
2
<launchConfiguration type="org.eclipse.jdt.launching.localJavaApplication">
3
<listAttribute key="org.eclipse.debug.core.MAPPED_RESOURCE_PATHS">
4
<listEntry value="/deconflictiontools"/>
5
</listAttribute>
6
<listAttribute key="org.eclipse.debug.core.MAPPED_RESOURCE_TYPES">
7
<listEntry value="4"/>
8
</listAttribute>
9
<stringAttribute key="org.eclipse.jdt.launching.CLASSPATH_PROVIDER" value="org.eclipse.m2e.launchconfig.classpathProvider"/>
10
<stringAttribute key="org.eclipse.jdt.launching.MAIN_TYPE" value="tt.euclidtime3i.Solver"/>
11
<stringAttribute key="org.eclipse.jdt.launching.PROGRAM_ARGUMENTS" value="-method KDPMD -k  10 -problemfile ~/projects/deconfliction/repo/experiments/ksfo/instances/urbanC-bounded-r48-gs50/ -maxtime 2500 -gridstep 40 -grid 16 -summary -showvis"/>
12
<stringAttribute key="org.eclipse.jdt.launching.PROJECT_ATTR" value="deconflictiontools"/>
13
<stringAttribute key="org.eclipse.jdt.launching.SOURCE_PATH_PROVIDER" value="org.eclipse.m2e.launchconfig.sourcepathProvider"/>
14
</launchConfiguration>
misc/eclipse/Solver (kDPM-C).launch
1 1
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
2 2
<launchConfiguration type="org.eclipse.jdt.launching.localJavaApplication">
3 3
<listAttribute key="org.eclipse.debug.core.MAPPED_RESOURCE_PATHS">
4
<listEntry value="/deconflictiontools/src/main/java/tt/jointeuclid2ni/Solver.java"/>
4
<listEntry value="/deconflictiontools"/>
5 5
</listAttribute>
6 6
<listAttribute key="org.eclipse.debug.core.MAPPED_RESOURCE_TYPES">
7
<listEntry value="1"/>
7
<listEntry value="4"/>
8 8
</listAttribute>
9 9
<stringAttribute key="org.eclipse.jdt.launching.CLASSPATH_PROVIDER" value="org.eclipse.m2e.launchconfig.classpathProvider"/>
10
<stringAttribute key="org.eclipse.jdt.launching.MAIN_TYPE" value="tt.jointeuclid2ni.Solver"/>
10
<stringAttribute key="org.eclipse.jdt.launching.MAIN_TYPE" value="tt.euclidtime3i.Solver"/>
11 11
<stringAttribute key="org.eclipse.jdt.launching.PROGRAM_ARGUMENTS" value="-method KDPMC -k 10 -problemfile  src/main/resources/problems/99.xml  -maxtime 2500 -gridstep 50 -summary -showvis -verbose -objective TRAJECTORY"/>
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"/>
misc/eclipse/Solver (kDPM-D).launch
1 1
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
2 2
<launchConfiguration type="org.eclipse.jdt.launching.localJavaApplication">
3 3
<listAttribute key="org.eclipse.debug.core.MAPPED_RESOURCE_PATHS">
4
<listEntry value="/deconflictiontools/src/main/java/tt/jointeuclid2ni/Solver.java"/>
4
<listEntry value="/deconflictiontools"/>
5 5
</listAttribute>
6 6
<listAttribute key="org.eclipse.debug.core.MAPPED_RESOURCE_TYPES">
7
<listEntry value="1"/>
7
<listEntry value="4"/>
8 8
</listAttribute>
9 9
<stringAttribute key="org.eclipse.jdt.launching.CLASSPATH_PROVIDER" value="org.eclipse.m2e.launchconfig.classpathProvider"/>
10
<stringAttribute key="org.eclipse.jdt.launching.MAIN_TYPE" value="tt.jointeuclid2ni.Solver"/>
10
<stringAttribute key="org.eclipse.jdt.launching.MAIN_TYPE" value="tt.euclidtime3i.Solver"/>
11 11
<stringAttribute key="org.eclipse.jdt.launching.PROGRAM_ARGUMENTS" value="-method KDPMD -k 4 -problemfile  src/main/resources/problems/csail_r24_n5.xml  -maxtime 10000 -gridstep 50 -grid 8 -summary -showvis -heuristic PERFECT -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"/>
misc/eclipse/Solver (test).launch
1 1
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
2 2
<launchConfiguration type="org.eclipse.jdt.launching.localJavaApplication">
3 3
<listAttribute key="org.eclipse.debug.core.MAPPED_RESOURCE_PATHS">
4
<listEntry value="/deconflictiontools/src/main/java/tt/jointeuclid2ni/Solver.java"/>
4
<listEntry value="/deconflictiontools"/>
5 5
</listAttribute>
6 6
<listAttribute key="org.eclipse.debug.core.MAPPED_RESOURCE_TYPES">
7
<listEntry value="1"/>
7
<listEntry value="4"/>
8 8
</listAttribute>
9 9
<stringAttribute key="org.eclipse.jdt.launching.CLASSPATH_PROVIDER" value="org.eclipse.m2e.launchconfig.classpathProvider"/>
10
<stringAttribute key="org.eclipse.jdt.launching.MAIN_TYPE" value="tt.jointeuclid2ni.Solver"/>
11
<stringAttribute key="org.eclipse.jdt.launching.PROGRAM_ARGUMENTS" value="-method KDPMD -k  10 -problemfile src/main/resources/problems/superconflict4.xml -maxtime 2500 -gridstep 40 -grid 16 -summary -showvis"/>
10
<stringAttribute key="org.eclipse.jdt.launching.MAIN_TYPE" value="tt.euclidtime3i.Solver"/>
11
<stringAttribute key="org.eclipse.jdt.launching.PROGRAM_ARGUMENTS" value="-method ORCA -problemfile src/main/resources/problems/78_obstacles.xml -maxtime 3500 -summary -showvis -heuristic L2"/>
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/Solver.launch
1 1
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
2 2
<launchConfiguration type="org.eclipse.jdt.launching.localJavaApplication">
3 3
<listAttribute key="org.eclipse.debug.core.MAPPED_RESOURCE_PATHS">
4
<listEntry value="/deconflictiontools/src/main/java/tt/jointeuclid2ni/Solver.java"/>
4
<listEntry value="/deconflictiontools"/>
5 5
</listAttribute>
6 6
<listAttribute key="org.eclipse.debug.core.MAPPED_RESOURCE_TYPES">
7
<listEntry value="1"/>
7
<listEntry value="4"/>
8 8
</listAttribute>
9 9
<stringAttribute key="org.eclipse.jdt.launching.CLASSPATH_PROVIDER" value="org.eclipse.m2e.launchconfig.classpathProvider"/>
10
<stringAttribute key="org.eclipse.jdt.launching.MAIN_TYPE" value="tt.jointeuclid2ni.Solver"/>
10
<stringAttribute key="org.eclipse.jdt.launching.MAIN_TYPE" value="tt.euclidtime3i.Solver"/>
11 11
<stringAttribute key="org.eclipse.jdt.launching.PROGRAM_ARGUMENTS" value="-method PP -heuristic L1 -problemfile src/main/resources/problems/empty-unbounded-g4/190.xml -maxtime 3500 -timeout 20000 -grid 4 -gridstep 50 -summary -summaryprefix empty-unbounded;190;2;50;1037;4;50;3500;PP;NA;"/>
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"/>
misc/eclipse/TriangulationGenerator (alex).launch
1
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
2
<launchConfiguration type="org.eclipse.jdt.launching.localJavaApplication">
3
<listAttribute key="org.eclipse.debug.core.MAPPED_RESOURCE_PATHS">
4
<listEntry value="/deconflictiontools/src/main/java/tt/jointeuclid2ni/probleminstance/generator/TriangulationGenerator.java"/>
5
</listAttribute>
6
<listAttribute key="org.eclipse.debug.core.MAPPED_RESOURCE_TYPES">
7
<listEntry value="1"/>
8
</listAttribute>
9
<stringAttribute key="org.eclipse.jdt.launching.CLASSPATH_PROVIDER" value="org.eclipse.m2e.launchconfig.classpathProvider"/>
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 45 -bodyradius 10  -outfile src/main/resources/d-environments/101.xml -showvis"/>
12
<stringAttribute key="org.eclipse.jdt.launching.PROJECT_ATTR" value="deconflictiontools"/>
13
<stringAttribute key="org.eclipse.jdt.launching.SOURCE_PATH_PROVIDER" value="org.eclipse.m2e.launchconfig.sourcepathProvider"/>
14
</launchConfiguration>
misc/eclipse/TriangulationGenerator (test).launch
1
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
2
<launchConfiguration type="org.eclipse.jdt.launching.localJavaApplication">
3
<listAttribute key="org.eclipse.debug.core.MAPPED_RESOURCE_PATHS">
4
<listEntry value="/deconflictiontools/src/main/java/tt/jointeuclid2ni/probleminstance/generator/TriangulationGenerator.java"/>
5
</listAttribute>
6
<listAttribute key="org.eclipse.debug.core.MAPPED_RESOURCE_TYPES">
7
<listEntry value="1"/>
8
</listAttribute>
9
<stringAttribute key="org.eclipse.jdt.launching.CLASSPATH_PROVIDER" value="org.eclipse.m2e.launchconfig.classpathProvider"/>
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 src/main/resources/environments/empty-bounded.xml -dispersion 50 -connectionradius 45 -bodyradius 10  -outfile src/main/resources/d-environments/78_obstacles.xml -showvis"/>
12
<stringAttribute key="org.eclipse.jdt.launching.PROJECT_ATTR" value="deconflictiontools"/>
13
<stringAttribute key="org.eclipse.jdt.launching.SOURCE_PATH_PROVIDER" value="org.eclipse.m2e.launchconfig.sourcepathProvider"/>
14
</launchConfiguration>
pom.xml
109 109
            <version>15.0</version>
110 110
        </dependency>
111 111
        <dependency>
112
			<groupId>org.apache.commons</groupId>
113
			<artifactId>commons-math3</artifactId>
114
			<version>3.2</version>
115
		</dependency>
116

  
112
            <groupId>org.apache.commons</groupId>
113
            <artifactId>commons-math3</artifactId>
114
            <version>3.2</version>
115
        </dependency>
116
        <dependency>
117
            <groupId>ags.utils.dataStructures</groupId>
118
            <artifactId>kdtreerednaxela</artifactId>
119
            <version>3.0-SNAPSHOT</version>
120
        </dependency>
117 121
    </dependencies>
118 122

  
119
    <description>Implementations of different centralized cooperative pathfinding algorithms and other deconfliction-related tools.</description>
123
    <description>Implementations of different centralized cooperative pathfinding algorithms and other
124
        deconfliction-related tools.
125
    </description>
120 126

  
121 127
    <profiles>
122
    <profile>
123
      <id>release-profile</id>
128
        <profile>
129
            <id>release-profile</id>
124 130

  
125
      <activation>
126
        <property>
127
          <name>performRelease</name>
128
        </property>
129
      </activation>
131
            <activation>
132
                <property>
133
                    <name>performRelease</name>
134
                </property>
135
            </activation>
130 136

  
131 137

  
132

  
133
    </profile>
134
  </profiles>
138
        </profile>
139
    </profiles>
135 140
</project>
src/main/java/tt/euclidtime3i/SIPPDebug.java
1
package tt.euclidtime3i;
2

  
3

  
4
import java.util.Arrays;
5
import java.util.Collection;
6
import java.util.Collections;
7

  
8
import tt.euclid2i.Point;
9
import tt.euclid2i.Region;
10
import tt.euclid2i.discretization.LazyGrid;
11
import tt.euclid2i.probleminstance.Environment;
12
import tt.euclid2i.region.Rectangle;
13
import tt.jointeuclid2ni.LocalSolver;
14
import tt.jointeuclid2ni.probleminstance.EarliestArrivalProblem;
15
import tt.jointeuclid2ni.probleminstance.generator.ConflictGenerator;
16
import tt.jointeuclid2ni.probleminstance.generator.exception.ProblemNotCreatedException;
17
import tt.jointeuclid2ni.solver.Algorithms;
18
import tt.jointeuclid2ni.solver.HeuristicType;
19
import tt.jointeuclid2ni.solver.ObjectiveType;
20
import tt.jointeuclid2ni.solver.Parameters;
21

  
22
public class SIPPDebug {
23
    public static void main(String[] args) throws ProblemNotCreatedException {
24

  
25

  
26
        int[] radiuses = bodyRadiuses(4, 50);
27
        final Rectangle rectangle = new Rectangle(new Point(0, 0), new Point(1000, 1000));
28

  
29
        Environment environment = new Environment() {
30
            @Override
31
            public Collection<Region> getObstacles() {
32
                return Collections.emptyList();
33
            }
34

  
35
            @Override
36
            public Region getBoundary() {
37
                return rectangle;
38
            }
39
        };
40

  
41
        EarliestArrivalProblem problem = ConflictGenerator.generateSingleInstance(environment, null, radiuses, LazyGrid.PATTERN_8_WAY_WAIT, 50, 1, rectangle);
42
        Parameters parameters = parameters(LazyGrid.PATTERN_8_WAY_WAIT, Algorithms.PP);
43

  
44
        LocalSolver solver = new LocalSolver(problem, parameters);
45
        solver.solve(args);
46
    }
47

  
48
    public static Parameters parameters(int[][] PATTERN_4_WAY, Algorithms algorithm) {
49
        Parameters parameters = new Parameters();
50

  
51
        parameters.showVis = true;
52
        parameters.printSummary = true;
53
        parameters.summaryPrefix = "";
54
        parameters.verbose = false;
55
        parameters.maxTime = 5000;
56
        parameters.gridStep = 50;
57
        parameters.maxSpeed = 1;
58
        parameters.startedAtMs = 0;
59
        parameters.runtimeDeadlineMs = Long.MAX_VALUE;
60
        parameters.waitMoveDuration = 50;
61
        parameters.gridPattern = PATTERN_4_WAY;
62
        parameters.heuristic = HeuristicType.L2;
63
        parameters.objective = ObjectiveType.ARRIVAL;
64
        parameters.selectedAlgorithm = algorithm;
65

  
66
        return parameters;
67
    }
68

  
69
    private static int[] bodyRadiuses(int N, int r) {
70
        int[] ints = new int[N];
71
        Arrays.fill(ints, r);
72
        return ints;
73
    }
74

  
75
}
src/main/java/tt/euclidtime3i/demo/GSIPPDemo.java
1
package tt.euclidtime3i.demo;
2

  
3
import java.awt.Color;
4
import java.util.Arrays;
5
import java.util.Collection;
6
import java.util.HashMap;
7
import java.util.HashSet;
8
import java.util.LinkedList;
9
import java.util.Map;
10
import java.util.Set;
11

  
12
import javax.vecmath.Point2d;
13

  
14
import org.jgrapht.DirectedGraph;
15
import org.jgrapht.Graph;
16
import org.jgrapht.GraphPath;
17
import org.jgrapht.alg.AStarShortestPathSimple;
18
import org.jgrapht.alg.AStarShortestPathSimple.StateDominance;
19
import org.jgrapht.util.Goal;
20
import org.jgrapht.util.HeuristicToGoal;
21

  
22
import tt.discrete.vis.TrajectoryLayer;
23
import tt.discrete.vis.TrajectoryLayer.TrajectoryProvider;
24
import tt.euclid2i.SegmentedTrajectory;
25
import tt.euclid2i.discretization.LazyGrid;
26
import tt.euclid2i.trajectory.StraightSegmentTrajectory;
27
import tt.euclid2i.util.SeparationDetector;
28
import tt.euclidtime3i.Point;
29
import tt.euclidtime3i.discretization.ConstantSpeedTimeExtension;
30
import tt.euclidtime3i.discretization.Straight;
31
import tt.euclidtime3i.region.MovingCircle;
32
import tt.euclidtime3i.sipprrts.vis.SearchTreeLayer;
33
import tt.euclidtime3i.sipprrts.vis.SearchTreeLayer.SearchTreeProvider;
34
import tt.euclidtime3i.trajectory.LinearTrajectory;
35
import tt.euclidtime3i.vis.RegionsLayer;
36
import tt.euclidtime3i.vis.RegionsLayer.RegionsProvider;
37
import tt.euclidtime3i.vis.TimeParameter;
38
import tt.euclidtime3i.vis.TimeParameterProjectionTo2d;
39
import tt.vis.FastAgentsLayer;
40
import tt.vis.FastAgentsLayer.ColorProvider;
41
import tt.vis.FastAgentsLayer.TrajectoriesProvider;
42
import tt.vis.GraphLayer;
43
import tt.vis.GraphLayer.GraphProvider;
44
import tt.vis.ParameterControlLayer;
45
import cz.agents.alite.creator.Creator;
46
import cz.agents.alite.vis.VisManager;
47
import cz.agents.alite.vis.VisManager.SceneParams;
48
import cz.agents.alite.vis.layer.common.ColorLayer;
49
import cz.agents.alite.vis.layer.common.VisInfoLayer;
50

  
51

  
52
public class GSIPPDemo implements Creator {
53
    // create time parameter
54
    final static TimeParameter time = new TimeParameter();
55

  
56
    @Override
57
    public void init(String[] args) {}
58

  
59
    @Override
60
    public void create() {
61

  
62
        initVisualization();
63

  
64
        VisManager.registerLayer(ParameterControlLayer.create(time));
65

  
66
        final tt.euclid2i.Point START = new tt.euclid2i.Point(100,-100);
67
        final tt.euclid2i.Point END = new tt.euclid2i.Point(-100,100);
68

  
69
        // create discretization
70
        final DirectedGraph<tt.euclid2i.Point, tt.euclid2i.Line> spatialGraph
71
            = new LazyGrid(START,
72
                    new LinkedList<tt.euclid2i.Region>(),
73
                    new tt.euclid2i.region.Rectangle(new tt.euclid2i.Point(-200,-200),
74
                    new tt.euclid2i.Point(200,200)),
75
                    LazyGrid.PATTERN_8_WAY,
76
                    5).generateFullGraph();
77

  
78
        // graph
79
        VisManager.registerLayer(GraphLayer.create(new GraphProvider<tt.euclid2i.Point, tt.euclid2i.Line>() {
80

  
81
        	@Override
82
        	public Graph<tt.euclid2i.Point, tt.euclid2i.Line> getGraph() {
83
        		return spatialGraph;
84
        	}
85
        }, new tt.euclid2i.vis.ProjectionTo2d(), Color.GRAY, Color.GRAY, 1, 4));
86

  
87
        final int MAXTIME = 3000;
88
        final int BODY_RADIUS = 1;
89
        final int OBSTACLE_RADIUS = 45;
90

  
91
        final SegmentedTrajectory[] trajArr = new SegmentedTrajectory[] {
92
        	new tt.euclid2i.trajectory.LinearTrajectory(0, new tt.euclid2i.Point(-100,-100), new tt.euclid2i.Point(50, 50), 1, MAXTIME, MAXTIME),
93
        	new tt.euclid2i.trajectory.LinearTrajectory(0, new tt.euclid2i.Point(-100,0), new tt.euclid2i.Point(70,0), 1, MAXTIME, MAXTIME)
94
        };
95

  
96
        int[] radiuses = new int[trajArr.length];
97
        Arrays.fill(radiuses, OBSTACLE_RADIUS);
98

  
99

  
100
        VisManager.registerLayer(RegionsLayer.create(new RegionsProvider() {
101
        	@Override
102
        	public Collection<tt.euclidtime3i.Region> getRegions() {
103
        		Collection<tt.euclidtime3i.Region> regions = new LinkedList<tt.euclidtime3i.Region>();
104
        		for (SegmentedTrajectory traj : trajArr) {
105
        			regions.add(new MovingCircle(traj, OBSTACLE_RADIUS));
106
        		}
107
        		return regions;
108
        	}
109
        }, new TimeParameterProjectionTo2d(time), Color.RED, Color.GRAY));
110

  
111

  
112
        // **** Solve *****
113
        final SegmentedTrajectory trajectoryGSipp = solveGSIPP(START, END, spatialGraph, MAXTIME, BODY_RADIUS, trajArr, radiuses);
114
        final SegmentedTrajectory trajectoryFullSpaceTime = solveConventional(START, END, spatialGraph, MAXTIME, BODY_RADIUS, trajArr, radiuses);
115

  
116
        VisManager.registerLayer(TrajectoryLayer.create(new TrajectoryProvider<tt.euclid2i.Point>() {
117

  
118
            @Override
119
            public tt.discrete.Trajectory<tt.euclid2i.Point> getTrajectory() {
120
                return trajectoryGSipp;
121
            }
122
        }, new tt.euclid2i.vis.ProjectionTo2d(), Color.BLUE, 5, 1000, 's'));
123

  
124
        VisManager.registerLayer(TrajectoryLayer.create(new TrajectoryProvider<tt.euclid2i.Point>() {
125

  
126
            @Override
127
            public tt.discrete.Trajectory<tt.euclid2i.Point> getTrajectory() {
128
                return trajectoryFullSpaceTime;
129
            }
130
        }, new tt.euclid2i.vis.ProjectionTo2d(), Color.GREEN, 5, 1000, 's'));
131

  
132
        VisManager.registerLayer(FastAgentsLayer.create(new TrajectoriesProvider() {
133

  
134
			@Override
135
			public tt.euclid2i.Trajectory[] getTrajectories() {
136
				tt.euclid2i.Trajectory[] trajArr = new tt.euclid2i.Trajectory[] { (tt.euclid2i.Trajectory) trajectoryGSipp, (tt.euclid2i.Trajectory) trajectoryFullSpaceTime  };
137
				return trajArr ;
138
			}
139

  
140
			@Override
141
			public int[] getBodyRadiuses() {
142
				return new int [] {BODY_RADIUS, BODY_RADIUS};
143
			}
144
		}, new ColorProvider() {
145

  
146
			@Override
147
			public Color getColor(int i) {
148
				return i == 0 ? Color.BLUE : Color.GREEN;
149
			}
150
		}, time));
151

  
152
    }
153

  
154
	protected SegmentedTrajectory solveGSIPP(
155
			final tt.euclid2i.Point start,
156
			final tt.euclid2i.Point goal,
157
			final DirectedGraph<tt.euclid2i.Point, tt.euclid2i.Line> spatialGraph,
158
			final int maxtime, final int bodyRadius,
159
			final SegmentedTrajectory[] trajArr, final int[] radiuses) {
160

  
161
		System.out.println("\n\nSolving in full space-time using state dominance. ");
162

  
163
		final Collection<tt.euclidtime3i.Region> dynamicObstacles = new LinkedList<tt.euclidtime3i.Region>();
164

  
165
		final int[] inflatedRadiuses = new int[radiuses.length];
166
		for (int i=0; i < trajArr.length; i++) {
167
			inflatedRadiuses[i] = radiuses[i] + bodyRadius;
168
			dynamicObstacles.add(new MovingCircle(trajArr[i], inflatedRadiuses[i]));
169
		}
170

  
171
		ConstantSpeedTimeExtension spaceTimeGraph = new ConstantSpeedTimeExtension(spatialGraph, maxtime, new int [] {1}, dynamicObstacles , 1);
172

  
173
        System.out.println("\nStarting A* search...");
174

  
175
        StateDominance<tt.euclidtime3i.Point> stateDominance = new StateDominance<tt.euclidtime3i.Point>() {
176

  
177
        	HashMap<tt.euclid2i.Point,Set<tt.euclidtime3i.Point>> spatialStates = new HashMap<tt.euclid2i.Point,Set<tt.euclidtime3i.Point>>();
178
        	Map<tt.euclidtime3i.Point, Double> costs = new HashMap<Point, Double>();
179

  
180
			@Override
181
			public boolean isDominated(tt.euclidtime3i.Point state, double stateCost) {
182

  
183
				if (spatialStates.containsKey(state.getPosition())) {
184
					Collection<Point> statesInTheSameSpatialState = spatialStates.get(state.getPosition());
185
					for (tt.euclidtime3i.Point otherState : statesInTheSameSpatialState) {
186
						if (otherState.getTime() <= state.getTime()) {
187
							boolean waitHasConflict = SeparationDetector.hasAnyPairwiseConflictAnalytic(new LinearTrajectory(otherState, state, 0.0), trajArr, inflatedRadiuses);
188
							double waitCost = waitHasConflict ? Double.POSITIVE_INFINITY : (state.getTime() - otherState.getTime());
189
							boolean dominated =  costs.get(otherState) + waitCost <= stateCost;
190
							return dominated;
191
						}
192
					}
193
				}
194

  
195
				return false;
196
			}
197

  
198
			@Override
199
			public void addedState(tt.euclidtime3i.Point state, double cost) {
200
				if (!spatialStates.containsKey(state.getPosition())) {
201
					spatialStates.put(state.getPosition(), new HashSet<tt.euclidtime3i.Point>());
202
				}
203

  
204
				spatialStates.get(state.getPosition()).add(state);
205
				costs.put(state, cost);
206
			}
207

  
208

  
209
		};
210

  
211
		final AStarShortestPathSimple<tt.euclidtime3i.Point, Straight> astar = new AStarShortestPathSimple<tt.euclidtime3i.Point, Straight>(spaceTimeGraph, new HeuristicToGoal<tt.euclidtime3i.Point>() {
212

  
213
			@Override
214
			public double getCostToGoalEstimate(Point current) {
215
				return current.getPosition().distance(goal);
216
			}
217
		},
218
		stateDominance,
219
		new tt.euclidtime3i.Point(start, 0),
220
		new Goal<tt.euclidtime3i.Point>() {
221

  
222
			@Override
223
			public boolean isGoal(Point current) {
224
				return current.getPosition().equals(goal);
225
			}
226

  
227
		});
228

  
229
        VisManager.registerLayer(SearchTreeLayer.create(new SearchTreeProvider<tt.euclidtime3i.Point>() {
230

  
231
			@Override
232
			public Collection<tt.euclidtime3i.Point> getOpen() {
233
				return astar.getOpenedNodes();
234
			}
235

  
236
			@Override
237
			public Collection<tt.euclidtime3i.Point> getClosed() {
238
				return astar.getClosedNodes();
239
			}
240

  
241
			@Override
242
			public tt.euclidtime3i.Point getParent(tt.euclidtime3i.Point vertex) {
243
				return astar.getParent(vertex);
244
			}
245

  
246
			@Override
247
			public double getValue(tt.euclidtime3i.Point vertex) {
248
				return astar.getFValue(vertex) / 300;
249
			}
250

  
251
			@Override
252
			public tt.euclidtime3i.Point getCurrent() {
253
				return astar.getCurrentVertex();
254
			}
255
		},
256

  
257
		new tt.vis.ProjectionTo2d<tt.euclidtime3i.Point>() {
258

  
259
			@Override
260
			public Point2d project(tt.euclidtime3i.Point point) {
261
				if (point.getTime() == time.getTime()) {
262
					return new Point2d(point.x, point.y);
263
				} else {
264
					return null;
265
				}
266
			}
267

  
268
		}
269
		, 4));
270

  
271
        VisManager.registerLayer(SearchTreeLayer.create(new SearchTreeProvider<tt.euclidtime3i.Point>() {
272

  
273
			@Override
274
			public Collection<tt.euclidtime3i.Point> getOpen() {
275
				return astar.getOpenedNodes();
276
			}
277

  
278
			@Override
279
			public Collection<tt.euclidtime3i.Point> getClosed() {
280
				return astar.getClosedNodes();
281
			}
282

  
283
			@Override
284
			public tt.euclidtime3i.Point getParent(tt.euclidtime3i.Point vertex) {
285
				return astar.getParent(vertex);
286
			}
287

  
288
			@Override
289
			public double getValue(tt.euclidtime3i.Point vertex) {
290
				return astar.getFValue(vertex) / 300;
291
			}
292

  
293
			@Override
294
			public tt.euclidtime3i.Point getCurrent() {
295
				return astar.getCurrentVertex();
296
			}
297
		}, new tt.vis.ProjectionTo2d<tt.euclidtime3i.Point>() {
298
			@Override
299
			public Point2d project(tt.euclidtime3i.Point point) {
300
				return new Point2d(point.x, -200 -point.getTime());
301
			}
302

  
303
		}, 4));
304

  
305

  
306
        long startedAt = System.currentTimeMillis();
307

  
308
        GraphPath<Point, Straight> path = astar.findPath(Integer.MAX_VALUE);
309
        final SegmentedTrajectory trajectory = new StraightSegmentTrajectory(path, maxtime);
310

  
311
        System.out.println("...Done. Iterations: " + astar.getIterationCount()  + ". Took " + (System.currentTimeMillis() - startedAt) + " ms");
312
        System.out.println("Finished planning: " + trajectory);
313
		return trajectory;
314
	}
315

  
316

  
317
	protected SegmentedTrajectory solveConventional(
318
			final tt.euclid2i.Point start,
319
			final tt.euclid2i.Point goal,
320
			final DirectedGraph<tt.euclid2i.Point, tt.euclid2i.Line> spatialGraph,
321
			final int maxtime, final int bodyRadius,
322
			final SegmentedTrajectory[] trajArr, int[] radiuses) {
323

  
324
		System.out.println("\n\nSolving in full space-time...");
325

  
326
		Collection<tt.euclidtime3i.Region> dynamicObstacles = new LinkedList<tt.euclidtime3i.Region>();
327

  
328

  
329
		for (int i=0; i < trajArr.length; i++) {
330
			dynamicObstacles.add(new MovingCircle(trajArr[i], radiuses[i] + bodyRadius));
331
		}
332

  
333
		ConstantSpeedTimeExtension spaceTimeGraph = new ConstantSpeedTimeExtension(spatialGraph, maxtime, new int [] {1}, dynamicObstacles , 1);
334

  
335
        System.out.println("\nStarting A* search...");
336

  
337
        final AStarShortestPathSimple<tt.euclidtime3i.Point, Straight> astar = new AStarShortestPathSimple<tt.euclidtime3i.Point, Straight>(spaceTimeGraph, new HeuristicToGoal<tt.euclidtime3i.Point>() {
338

  
339
			@Override
340
			public double getCostToGoalEstimate(Point current) {
341
				return current.getPosition().distance(goal);
342
			}
343
		}, new tt.euclidtime3i.Point(start, 0), new Goal<tt.euclidtime3i.Point>() {
344

  
345
			@Override
346
			public boolean isGoal(Point current) {
347
				return current.getPosition().equals(goal);
348
			}
349

  
350
		});
351

  
352
        VisManager.registerLayer(SearchTreeLayer.create(new SearchTreeProvider<tt.euclidtime3i.Point>() {
353

  
354
			@Override
355
			public Collection<tt.euclidtime3i.Point> getOpen() {
356
				return astar.getOpenedNodes();
357
			}
358

  
359
			@Override
360
			public Collection<tt.euclidtime3i.Point> getClosed() {
361
				return astar.getClosedNodes();
362
			}
363

  
364
			@Override
365
			public tt.euclidtime3i.Point getParent(tt.euclidtime3i.Point vertex) {
366
				return astar.getParent(vertex);
367
			}
368

  
369
			@Override
370
			public double getValue(tt.euclidtime3i.Point vertex) {
371
				return astar.getFValue(vertex) / 300;
372
			}
373

  
374
			@Override
375
			public tt.euclidtime3i.Point getCurrent() {
376
				return astar.getCurrentVertex();
377
			}
378
		},
379

  
380
		new tt.vis.ProjectionTo2d<tt.euclidtime3i.Point>() {
381

  
382
			@Override
383
			public Point2d project(tt.euclidtime3i.Point point) {
384
				if (point.getTime() == time.getTime()) {
385
					return new Point2d(point.x, point.y);
386
				} else {
387
					return null;
388
				}
389
			}
390

  
391
		}
392
		, 4));
393

  
394
        VisManager.registerLayer(SearchTreeLayer.create(new SearchTreeProvider<tt.euclidtime3i.Point>() {
395

  
396
			@Override
397
			public Collection<tt.euclidtime3i.Point> getOpen() {
398
				return astar.getOpenedNodes();
399
			}
400

  
401
			@Override
402
			public Collection<tt.euclidtime3i.Point> getClosed() {
403
				return astar.getClosedNodes();
404
			}
405

  
406
			@Override
407
			public tt.euclidtime3i.Point getParent(tt.euclidtime3i.Point vertex) {
408
				return astar.getParent(vertex);
409
			}
410

  
411
			@Override
412
			public double getValue(tt.euclidtime3i.Point vertex) {
413
				return astar.getFValue(vertex) / 300;
414
			}
415

  
416
			@Override
417
			public tt.euclidtime3i.Point getCurrent() {
418
				return astar.getCurrentVertex();
419
			}
420
		}, new tt.vis.ProjectionTo2d<tt.euclidtime3i.Point>() {
421

  
422
			@Override
423
			public Point2d project(tt.euclidtime3i.Point point) {
424
				return new Point2d(point.x + 400, -200 -point.getTime());
425
			}
426

  
427
		}, 4));
428

  
429

  
430
        long startedAt = System.currentTimeMillis();
431

  
432
        GraphPath<Point, Straight> path = astar.findPath(Integer.MAX_VALUE);
433
        final SegmentedTrajectory trajectory = new StraightSegmentTrajectory(path, maxtime);
434

  
435
        System.out.println("...Done. Iterations: " + astar.getIterationCount()  + ". Took " + (System.currentTimeMillis() - startedAt) + " ms");
436
        System.out.println("Finished planning: " + trajectory);
437
		return trajectory;
438
	}
439

  
440
    private void initVisualization() {
441
        VisManager.setInitParam("Trajectory Tools Vis", 1024, 768, 200, 200);
442
        VisManager.setSceneParam(new SceneParams(){
443

  
444
            @Override
445
            public Point2d getDefaultLookAt() {
446
                return new Point2d(0,0);
447
            }
448

  
449
            @Override
450
            public double getDefaultZoomFactor() {
451
                return 5;
452
            } } );
453

  
454
        VisManager.init();
455

  
456
        // background
457
        VisManager.registerLayer(ColorLayer.create(Color.WHITE));
458

  
459
        // Overlay
460
        VisManager.registerLayer(VisInfoLayer.create());
461
    }
462

  
463

  
464
    public static void main(String[] args) {
465
        new GSIPPDemo().create();
466
    }
467

  
468
}
src/main/java/tt/euclidtime3i/demo/SIPPDemo.java
1
package tt.euclidtime3i.demo;
2

  
3
import java.awt.Color;
4
import java.util.Arrays;
5
import java.util.Collection;
6
import java.util.LinkedList;
7

  
8
import javax.vecmath.Point2d;
9

  
10
import org.jgrapht.DirectedGraph;
11
import org.jgrapht.Graph;
12
import org.jgrapht.GraphPath;
13
import org.jgrapht.alg.AStarShortestPathSimple;
14
import org.jgrapht.util.Goal;
15
import org.jgrapht.util.HeuristicToGoal;
16

  
17
import tt.discrete.vis.TrajectoryLayer;
18
import tt.discrete.vis.TrajectoryLayer.TrajectoryProvider;
19
import tt.euclid2i.SegmentedTrajectory;
20
import tt.euclid2i.discretization.L2Heuristic;
21
import tt.euclid2i.discretization.LazyGrid;
22
import tt.euclid2i.trajectory.LinearTrajectory;
23
import tt.euclid2i.trajectory.StraightSegmentTrajectory;
24
import tt.euclid2i.vis.ProjectionTo2d;
25
import tt.euclidtime3i.Point;
26
import tt.euclidtime3i.discretization.ConstantSpeedTimeExtension;
27
import tt.euclidtime3i.discretization.Straight;
28
import tt.euclidtime3i.region.MovingCircle;
29
import tt.euclidtime3i.sipp.SippEdge;
30
import tt.euclidtime3i.sipp.SippGoal;
31
import tt.euclidtime3i.sipp.SippHeuristic;
32
import tt.euclidtime3i.sipp.SippNode;
33
import tt.euclidtime3i.sipp.SippUtils;
34
import tt.euclidtime3i.sipp.SippWrapper;
35
import tt.euclidtime3i.sipp.intervals.Interval;
36
import tt.euclidtime3i.sipprrts.DynamicObstaclesImpl;
37
import tt.euclidtime3i.sipprrts.vis.SearchTreeLayer;
38
import tt.euclidtime3i.sipprrts.vis.SearchTreeLayer.SearchTreeProvider;
39
import tt.euclidtime3i.vis.RegionsLayer;
40
import tt.euclidtime3i.vis.RegionsLayer.RegionsProvider;
41
import tt.euclidtime3i.vis.TimeParameter;
42
import tt.euclidtime3i.vis.TimeParameterProjectionTo2d;
43
import tt.vis.FastAgentsLayer;
44
import tt.vis.FastAgentsLayer.ColorProvider;
45
import tt.vis.FastAgentsLayer.TrajectoriesProvider;
46
import tt.vis.GraphLayer;
47
import tt.vis.GraphLayer.GraphProvider;
48
import tt.vis.LabeledPointLayer;
49
import tt.vis.LabeledPointLayer.LabeledPoint;
50
import tt.vis.LabeledPointLayer.LabeledPointsProvider;
51
import tt.vis.ParameterControlLayer;
52
import cz.agents.alite.creator.Creator;
53
import cz.agents.alite.vis.VisManager;
54
import cz.agents.alite.vis.VisManager.SceneParams;
55
import cz.agents.alite.vis.layer.common.ColorLayer;
56
import cz.agents.alite.vis.layer.common.VisInfoLayer;
57
import cz.agents.alite.vis.layer.terminal.PointLayer;
58

  
59

  
60
public class SIPPDemo implements Creator {
61
    // create time parameter
62
    final static TimeParameter time = new TimeParameter();
63

  
64
    @Override
65
    public void init(String[] args) {}
66

  
67
    @Override
68
    public void create() {
69

  
70
        initVisualization();
71

  
72
        VisManager.registerLayer(ParameterControlLayer.create(time));
73

  
74
        final tt.euclid2i.Point START = new tt.euclid2i.Point(100,-100);
75
        final tt.euclid2i.Point END = new tt.euclid2i.Point(-100,100);
76

  
77
        // create discretization
78
        final DirectedGraph<tt.euclid2i.Point, tt.euclid2i.Line> spatialGraph
79
            = new LazyGrid(START,
80
                    new LinkedList<tt.euclid2i.Region>(),
81
                    new tt.euclid2i.region.Rectangle(new tt.euclid2i.Point(-200,-200),
82
                    new tt.euclid2i.Point(200,200)),
83
                    LazyGrid.PATTERN_8_WAY,
84
                    10).generateFullGraph();
85

  
86
        // graph
87
        VisManager.registerLayer(GraphLayer.create(new GraphProvider<tt.euclid2i.Point, tt.euclid2i.Line>() {
88

  
89
        	@Override
90
        	public Graph<tt.euclid2i.Point, tt.euclid2i.Line> getGraph() {
91
        		return spatialGraph;
92
        	}
93
        }, new tt.euclid2i.vis.ProjectionTo2d(), Color.GRAY, Color.GRAY, 1, 4));
94

  
95
        final int MAXTIME = 3000;
96
        final int BODY_RADIUS = 1;
97
        final int OBSTACLE_RADIUS = 45;
98

  
99
        final SegmentedTrajectory[] trajArr = new SegmentedTrajectory[] {
100
        	new LinearTrajectory(0, new tt.euclid2i.Point(-100,-100), new tt.euclid2i.Point(50, 50), 1, MAXTIME, MAXTIME),
101
        	new LinearTrajectory(0, new tt.euclid2i.Point(-100,0), new tt.euclid2i.Point(70,0), 1, MAXTIME, MAXTIME)
102
        };
103

  
104
        int[] radiuses = new int[trajArr.length];
105
        Arrays.fill(radiuses, OBSTACLE_RADIUS);
106

  
107
        VisManager.registerLayer(RegionsLayer.create(new RegionsProvider() {
108
        	@Override
109
        	public Collection<tt.euclidtime3i.Region> getRegions() {
110
        		Collection<tt.euclidtime3i.Region> regions = new LinkedList<tt.euclidtime3i.Region>();
111
        		for (SegmentedTrajectory traj : trajArr) {
112
        			regions.add(new MovingCircle(traj, OBSTACLE_RADIUS));
113
        		}
114
        		return regions;
115
        	}
116
        }, new TimeParameterProjectionTo2d(time), Color.RED, Color.GRAY));
117

  
118

  
119
        // **** Solve *****
120
        final SegmentedTrajectory trajectorySipp = solveSIPP(START, END, spatialGraph, MAXTIME, BODY_RADIUS, trajArr, radiuses);
121
        final SegmentedTrajectory trajectoryFullSpaceTime = solveConventional(START, END, spatialGraph, MAXTIME, BODY_RADIUS, trajArr, radiuses);
122

  
123
        VisManager.registerLayer(TrajectoryLayer.create(new TrajectoryProvider<tt.euclid2i.Point>() {
124

  
125
            @Override
126
            public tt.discrete.Trajectory<tt.euclid2i.Point> getTrajectory() {
127
                return trajectorySipp;
128
            }
129
        }, new tt.euclid2i.vis.ProjectionTo2d(), Color.BLUE, 5, 1000, 's'));
130

  
131
        VisManager.registerLayer(TrajectoryLayer.create(new TrajectoryProvider<tt.euclid2i.Point>() {
132

  
133
            @Override
134
            public tt.discrete.Trajectory<tt.euclid2i.Point> getTrajectory() {
135
                return trajectoryFullSpaceTime;
136
            }
137
        }, new tt.euclid2i.vis.ProjectionTo2d(), Color.GREEN, 5, 1000, 's'));
138

  
139
        VisManager.registerLayer(FastAgentsLayer.create(new TrajectoriesProvider() {
140

  
141
			@Override
142
			public tt.euclid2i.Trajectory[] getTrajectories() {
143
				tt.euclid2i.Trajectory[] trajArr = new tt.euclid2i.Trajectory[] { (tt.euclid2i.Trajectory) trajectorySipp, (tt.euclid2i.Trajectory) trajectoryFullSpaceTime  };
144
				return trajArr ;
145
			}
146

  
147
			@Override
148
			public int[] getBodyRadiuses() {
149
				return new int [] {BODY_RADIUS, BODY_RADIUS};
150
			}
151
		}, new ColorProvider() {
152

  
153
			@Override
154
			public Color getColor(int i) {
155
				return i == 0 ? Color.BLUE : Color.GREEN;
156
			}
157
		}, time));
158

  
159
    }
160

  
161
	protected SegmentedTrajectory solveSIPP(
162
			final tt.euclid2i.Point start,
163
			final tt.euclid2i.Point goal,
164
			final DirectedGraph<tt.euclid2i.Point, tt.euclid2i.Line> spatialGraph,
165
			final int maxtime, final int bodyRadius,
166
			final SegmentedTrajectory[] trajArr, int[] radiuses) {
167

  
168
		System.out.println("Creating SIPP Wrapper...");
169
        DynamicObstaclesImpl dynObstacles = new DynamicObstaclesImpl(trajArr, radiuses, maxtime);
170
        final SippWrapper wrapper = new SippWrapper(spatialGraph, dynObstacles, bodyRadius, 1, 2, maxtime);
171
        SippNode sippStartNode = new SippNode(start, Interval.toInfinity(0), 0);
172
        SippHeuristic heuristic = new SippHeuristic(new L2Heuristic(goal), 1);
173
        SippGoal sippGoalNode = new SippGoal(goal, maxtime);
174

  
175

  
176
        // Show SIPP nodes
177

  
178
        VisManager.registerLayer(LabeledPointLayer.create(new LabeledPointsProvider<tt.euclid2i.Point>() {
179
        	@Override
180
        	public Collection<LabeledPoint<tt.euclid2i.Point>> getLabeledPoints() {
181
        		LinkedList<LabeledPoint<tt.euclid2i.Point>> lpoints = new LinkedList<LabeledPoint<tt.euclid2i.Point>>();
182
        		for (tt.euclid2i.Point vertex : spatialGraph.vertexSet()) {
183
        			lpoints.add(new LabeledPoint<tt.euclid2i.Point>(vertex, ""+wrapper.getNoOfSafeIntervals(vertex)));
184
        		}
185
        		return lpoints;
186
        	}
187
        }, new ProjectionTo2d(), Color.BLACK));
188

  
189
        System.out.println("..Done \nStarting A* search...");
190

  
191
        final AStarShortestPathSimple<SippNode, SippEdge> astar = new AStarShortestPathSimple<SippNode, SippEdge>(wrapper, heuristic, sippStartNode, sippGoalNode);
192

  
193
        // Show search tree
194

  
195
        VisManager.registerLayer(SearchTreeLayer.create(new SearchTreeProvider<SippNode>() {
196

  
197
			@Override
198
			public Collection<SippNode> getOpen() {
199
				return astar.getOpenedNodes();
200
			}
201

  
202
			@Override
203
			public Collection<SippNode> getClosed() {
204
				return astar.getClosedNodes();
205
			}
206

  
207
			@Override
208
			public SippNode getParent(SippNode vertex) {
209
				return astar.getParent(vertex);
210
			}
211

  
212
			@Override
213
			public double getValue(SippNode vertex) {
214
				return astar.getFValue(vertex) / 300;
215
			}
216

  
217
			@Override
218
			public SippNode getCurrent() {
219
				return astar.getCurrentVertex();
220
			}
221
		},
222

  
223
		new tt.vis.ProjectionTo2d<SippNode>() {
224

  
225
			@Override
226
			public Point2d project(SippNode point) {
227
				if (point.getTime() == time.getTime()) {
228
					return new Point2d(point.getPoint().x, point.getPoint().y);
229
				} else {
230
					return null;
231
				}
232
			}
233

  
234
		}
235

  
236
		, 4));
237

  
238
        VisManager.registerLayer(SearchTreeLayer.create(new SearchTreeProvider<SippNode>() {
239

  
240
			@Override
241
			public Collection<SippNode> getOpen() {
242
				return astar.getOpenedNodes();
243
			}
244

  
245
			@Override
246
			public Collection<SippNode> getClosed() {
247
				return astar.getClosedNodes();
248
			}
249

  
250
			@Override
251
			public SippNode getParent(SippNode vertex) {
252
				return astar.getParent(vertex);
253
			}
254

  
255
			@Override
256
			public double getValue(SippNode vertex) {
257
				return astar.getFValue(vertex) / 300;
258
			}
259

  
260
			@Override
261
			public SippNode getCurrent() {
262
				return astar.getCurrentVertex();
263
			}
264
		}, new tt.vis.ProjectionTo2d<SippNode>() {
265

  
266
			@Override
267
			public Point2d project(SippNode point) {
268
				return new Point2d(point.getPoint().x, -200  - point.getTime());
269
			}
270

  
271
		}, 4));
272

  
273
        long startedAt = System.currentTimeMillis();
274
        GraphPath<SippNode, SippEdge> path = astar.findPath(Integer.MAX_VALUE);
275
        final SegmentedTrajectory trajectory = SippUtils.parseTrajectory(path, maxtime);
276
        System.out.println("...Done. Iterations: " + astar.getIterationCount()  + ". Took " + (System.currentTimeMillis() - startedAt) + " ms");
277
        System.out.println("Finished planning: " + trajectory);
278

  
279
		return trajectory;
280
	}
281

  
282
	protected SegmentedTrajectory solveConventional(
283
			final tt.euclid2i.Point start,
284
			final tt.euclid2i.Point goal,
285
			final DirectedGraph<tt.euclid2i.Point, tt.euclid2i.Line> spatialGraph,
286
			final int maxtime, final int bodyRadius,
287
			final SegmentedTrajectory[] trajArr, int[] radiuses) {
288

  
289
		System.out.println("\n\nSolving in full space-time...");
290

  
291
		Collection<tt.euclidtime3i.Region> dynamicObstacles = new LinkedList<tt.euclidtime3i.Region>();
292

  
293

  
294
		for (int i=0; i < trajArr.length; i++) {
295
			dynamicObstacles.add(new MovingCircle(trajArr[i], radiuses[i] + bodyRadius));
296
		}
297

  
298
		ConstantSpeedTimeExtension spaceTimeGraph = new ConstantSpeedTimeExtension(spatialGraph, maxtime, new int [] {1}, dynamicObstacles , 1);
299

  
300
        System.out.println("\nStarting A* search...");
301

  
302
        final AStarShortestPathSimple<tt.euclidtime3i.Point, Straight> astar = new AStarShortestPathSimple<tt.euclidtime3i.Point, Straight>(spaceTimeGraph, new HeuristicToGoal<tt.euclidtime3i.Point>() {
303

  
304
			@Override
305
			public double getCostToGoalEstimate(Point current) {
306
				return current.getPosition().distance(goal);
307
			}
308
		}, new tt.euclidtime3i.Point(start, 0), new Goal<tt.euclidtime3i.Point>() {
309

  
310
			@Override
311
			public boolean isGoal(Point current) {
312
				return current.getPosition().equals(goal);
313
			}
314

  
315
		});
316

  
317
        VisManager.registerLayer(SearchTreeLayer.create(new SearchTreeProvider<tt.euclidtime3i.Point>() {
318

  
319
			@Override
320
			public Collection<tt.euclidtime3i.Point> getOpen() {
321
				return astar.getOpenedNodes();
322
			}
323

  
324
			@Override
325
			public Collection<tt.euclidtime3i.Point> getClosed() {
326
				return astar.getClosedNodes();
327
			}
328

  
329
			@Override
330
			public tt.euclidtime3i.Point getParent(tt.euclidtime3i.Point vertex) {
331
				return astar.getParent(vertex);
332
			}
333

  
334
			@Override
335
			public double getValue(tt.euclidtime3i.Point vertex) {
336
				return astar.getFValue(vertex) / 300;
337
			}
338

  
339
			@Override
340
			public tt.euclidtime3i.Point getCurrent() {
341
				return astar.getCurrentVertex();
342
			}
343
		},
344

  
345
		new tt.vis.ProjectionTo2d<tt.euclidtime3i.Point>() {
346

  
347
			@Override
348
			public Point2d project(tt.euclidtime3i.Point point) {
349
				if (point.getTime() == time.getTime()) {
350
					return new Point2d(point.x + 400, point.y);
351
				} else {
352
					return null;
353
				}
354
			}
355

  
356
		}
357
		, 4));
358

  
359
        VisManager.registerLayer(SearchTreeLayer.create(new SearchTreeProvider<tt.euclidtime3i.Point>() {
360

  
361
			@Override
362
			public Collection<tt.euclidtime3i.Point> getOpen() {
363
				return astar.getOpenedNodes();
364
			}
365

  
366
			@Override
367
			public Collection<tt.euclidtime3i.Point> getClosed() {
368
				return astar.getClosedNodes();
369
			}
370

  
371
			@Override
372
			public tt.euclidtime3i.Point getParent(tt.euclidtime3i.Point vertex) {
373
				return astar.getParent(vertex);
374
			}
375

  
376
			@Override
377
			public double getValue(tt.euclidtime3i.Point vertex) {
378
				return astar.getFValue(vertex) / 300;
379
			}
380

  
381
			@Override
382
			public tt.euclidtime3i.Point getCurrent() {
383
				return astar.getCurrentVertex();
384
			}
385
		}, new tt.vis.ProjectionTo2d<tt.euclidtime3i.Point>() {
386

  
387
			@Override
388
			public Point2d project(tt.euclidtime3i.Point point) {
389
				return new Point2d(point.x + 400, -200 -point.getTime());
390
			}
391

  
392
		}, 4));
393

  
394

  
395
        long startedAt = System.currentTimeMillis();
396

  
397
        GraphPath<Point, Straight> path = astar.findPath(Integer.MAX_VALUE);
398
        final SegmentedTrajectory trajectory = new StraightSegmentTrajectory(path, maxtime);
399

  
400
        System.out.println("...Done. Iterations: " + astar.getIterationCount()  + ". Took " + (System.currentTimeMillis() - startedAt) + " ms");
401
        System.out.println("Finished planning: " + trajectory);
402
		return trajectory;
403
	}
404

  
405
    private void initVisualization() {
406
        VisManager.setInitParam("Trajectory Tools Vis", 1024, 768, 200, 200);
407
        VisManager.setSceneParam(new SceneParams(){
408

  
409
            @Override
410
            public Point2d getDefaultLookAt() {
411
                return new Point2d(0,0);
412
            }
413

  
414
            @Override
415
            public double getDefaultZoomFactor() {
416
                return 5;
417
            } } );
418

  
419
        VisManager.init();
420

  
421
        // background
422
        VisManager.registerLayer(ColorLayer.create(Color.WHITE));
423

  
424
        // Overlay
425
        VisManager.registerLayer(VisInfoLayer.create());
426
    }
427

  
428

  
... This diff was truncated because it exceeds the maximum size that can be displayed.

Also available in: Unified diff