Wiki

Deconfliction Tools is a toolkit that can be used for multi-agent path and trajectory planning.
Algorithms supported:
  • OD (Standley et al. 2010)
  • Prioritized Planning
  • Iterative Incremental Homotopy Planner (Bhattacharya et al. 2011)
Packages:
  • tt.jointeuclid2ni represents space W^n, where W=R^2. It can be used to find coordinated paths for multiple agents with static obstacles
  • tt.jointeuclidtime3i represents space W^n, where W=R^3 and points in W represent point in 2D space + time. It can be used to find coordinated paths for multiple agents in environment with dynamic obstacles.
  • tt.jointeuclidtime3i represents space of trajectories T^n.

Some of the implemented algorithms can be executed using the command-line launcher class tt.jointeuclid2ni.Solver. For more information on the inputs and outputs see the Solver specification page.

Repositories

Public Mercurial repo (read-only):

hg clone http://jones.felk.cvut.cz/repo/alite-deconflictiontools

Mercurial repo (allow contributing):

ssh://smith.felk.cvut.cz//data/hg/alite/deconflictiontools

Building

The dependencies are manages through maven, to build the toolkit and package it in to a self-contained jar archive run:

mvn package

The resulting jar package is target/deconflictiontools-1.1-SNAPSHOT-jar-with-dependencies.jar.

Creating your Own Problem Instance

Problem instances are specified in an xml file. To create your own problem instance you can use this workflow:

1. Build deconflictiontools either by running mvn package or download the latest build at http://jones.felk.cvut.cz/jenkins/job/AliteDeconflictionTools/lastBuild/cz.agents.alite$deconflictiontools/.

2. Create a polygonal map of the environment using the Problem Instance Designer tool:

java -cp target/deconflictiontools-1.1-SNAPSHOT-jar-with-dependencies.jar tt.jointeuclid2ni.ProblemInstanceDesigner -outfile env.xml

Press F1 for help on the controls. Make sure that obstacles are drawn clockwise.

3. Generate roadmap for the environment:

java -cp target/deconflictiontools-1.1-SNAPSHOT-jar-with-dependencies.jar tt.jointeuclid2ni.probleminstance.generator.TriangulationGenerator -problemfile env.xml -bodyradius 75 -dispersion 113 -connectionradius 180 -showvis -verbose -outfile denv.xml

The parameters are:

-problemfile -- input xml file that contains specification of polygonal obstacles
-bodyradius -- radius of the robot
-dispersion -- specifies density of the points (see http://planning.cs.uiuc.edu/node203.html), corresponds to sqrt(2)*gridstep
-connectionradius -- distance within which two vertices will be connected by an edge
-showvis -- toggles visualization
-outfile -- name of the output file

Press "g" to see the generated roadmap graph. The resulting xml file with environment specification will be in file denv.xml.