E* Interpolated Graph Replanner

The E* algorithm is a path planner for (mobile) robotics. Unlike A*, which constrains movements to graph edges, it produces smooth trajectories by interpolating between edges. Like D*, it supports dynamic replanning after local path cost changes. E* was originally developed for a PhD thesis (chapter 4) at the Autonomous Systems Lab of the Swiss Federal Institute of Technology in Zürich (formerly at its sister institution EPFL in Lausanne). It is written in C++ and provides a C wrapper for easier interfacing with other systems.

----------------------------------------------------------------------
Copyright (C) 2004, 2005 Swiss Federal Institute of Technology, Lausanne
Copyright (C) 2005, 2006,2007 Roland Philippsen <roland dot philippsen at gmx net>
Released under the GNU General Public License, version 2.
----------------------------------------------------------------------

Building and Running E*

NEW: Try the E* Development Kit!

Go to the estar-devkit page on the NEW Wiki and try that. Otherwise, keep reading...

0. Get all Required Dependencies

• Boost smart pointers and graph library (download at Sourceforge)
• Building from SVN requires GNU Automake, Autoconf, and Libtool. If you build a downloaded tarball, you do not need this.
• Optionally (for the test programs) an OpenGL implementation. The configure script should detect this automatically.
• Optionally Doxygen for generating the documentation.

1. Get the Source Code

You can get the cutting-edge version from the repository, in which case you need GNU Automake, Autoconf, and Libtool (see dependencies above). Or just grab a release tarball from the download page.

This project uses the Subversion revision control system. The repository can be browsed online on Sourceforge. Be sure to only take the trunk/estar part if you're only interested in the most recent sources, like this:

$ svn co https://estar.svn.sourceforge.net/svnroot/estar/trunk/estar

For more information on working with the Subversion repository, look at the online documentation available on Sourceforge.

2. Build

The easiest way build is with the build-stage.sh script. If you do not have GNU Automake + Autoconf + Libtool, you need to pass it the '-s' option to skip recreating build files. otherwise, just go ahead:

$ cd estar
$ ./build-stage.sh

Which will "install" everything underneath the stage/ directory. Otherwise, if you want to install into /path/to/somewhere you can use:

$ cd estar
$ ./build-stage.sh -p /path/to/somewhere

See the output of ./build-stage.sh -h for more options. If you want to, the documentation can be generated with Doxygen, but if you downloaded one of the estar-with-doc-* packages you won't need this.

$ cd estar/build
$ doxygen Doxyfile

Then simply point your favorite browser to html/index.html

3. Test

After building and installing, test programs will be either in estar/stage/bin/ (if you built using build-stage.sh) or in /path/to/somewhere/bin/ (if you configured and installed manually).

The graphical programs are controlled using the keyboard:

• SPACE: Compute one propagation step.
• c : Continuous propagation, plot each step.
• f : Flush - Propagate all cells, then plot.
• q : Quit (and optionally write to file)

Main E* Test: test_estar_gfx

This program is a graphical test of E*. It expects the name of a grid config file and runs the E* algorithm using the goal and robot positions (indices) defined therein. You can use the -t option to disable graphical output, in which case it makes sense to also define an output file using -o filename in order to capture the result (it simply writes resulting cell values in ASCII).

In the misc/ directory there are some grid config files that can be used for test_estar_gfx: