E* Interpolated Graph Replanner Documentation


The E-Star library implements the interpolated graph replanner originally developed in [1] and subsequently improved in [2,3]. It also includes an implementation of the Probabilistic Navigation Function, originally developed in [4] before E* had seen the day, and modified for it in [5]. A good starting point for using E* is to read [3] and look at estar::Facade, estar::Algorithm, and their source code. All the core functionality is in the estar namespace, which also includes some utilities.

Have a look at the bin/ subdirectory for examples of using E* and PNF. Most of these are simple text-based tools (that produce files with data and gnuplot instructions). test_estar_gfx and test_pnf_gfx are more elaborate and produce graphical output using OpenGL. For example, you can reproduce some of the figures in [5] by running:

   $ cd estar-X.Y/build/bin
   $ ./test_pnf_gfx ../../misc/pnf-setup-star06-a.pnf paper
     (quit the program by pressing 'q')
   $ ./test_pnf_gfx ../../misc/pnf-setup-star06-b.pnf paper


E-star Interpolated Graph Replanner
Some files are:
 Copyright (C) 2004-2005 Swiss Federal Institute of Technology, Lausanne
Some others are:
 Copyright (C) 2005-2007 Roland Philippsen <roland dot philippsen at gmx net>
All files are:
 Released under the GNU General Public License, see LICENSE.GPL

HOMEPAGE http://estar.sourceforge.net/


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.

If you want to give E* a try in simulation, try the E* "development
kit" available for download and checkout from the project homepage.


 * Boost Graph Library and smart pointers.
 * If you build from SVN, you need GNU Automake, Autoconf, and
   Libtool. If you're building from a release tarball, you don't need
 * An OpenGL implementation (currently works for Linux and OS X).
   [This is sort of optional, the configure script tries to guess if
   you have OpenGL, but it has never been really tested on a system
   without it.]
 * Doxygen (optional, http://www.doxygen.org/).


From source tarball (the "-s" option is important if you do *not* have
GNU Automake, Autoconf, and Libtool):

 $ tar xfvz estar-X.Y.tar.gz
 $ cd estar-X.Y
 $ ./build-stage.sh -s

This will "install" it in the stage/ directory under your current
working directory by default. You can also do a manual "configure /
make / make install", or read the output of "/build-stage.sh -h".

More cutting edge: Use subversion to check out (or update) a working copy!

 $ svn co https://estar.svn.sourceforge.net/svnroot/estar/trunk/estar
 $ cd estar
 $ ./build-stage.sh

Note that in any case, "./build-stage" will create a build/ directory,
which you can then use for recompiling the project after modifications
to the code. The GNU tools provide dependency tracking, and in most
cases only a small portion of the code gets recompiled after a
change. Also, in case of a working copy based on SVN, you can pass
"-s" to subsequent calls to "./build-stage.sh" to avoid wasting time
on recreating files that haven't changed.

The build-stage script has some more tricks up its sleeve, check out
its "--help" output. For example, to install E* on your system, say in
/usr/local/estar, just do this:

 $ ./build-stage.sh -p /usr/local/estar


Point your favorite browser to file doc/html/index.html if it exists,
or build it using doxygen by typing (after a successful configuration,
see BUILDING above):

 $ cd build
 $ make doc


[1] Roland Philippsen. "Motion Planning and Obstacle Avoidance for Mobile Robots in Highly Cluttered Dynamic Environments". Ph.D. Dissertation, Ecole Polytechnique Federale de Lausanne, 2004. (Available online http://library.epfl.ch/theses/?nr=3146)

[2] Roland Philippsen and Roland Siegwart. "An Interpolated Dynamic Navigation Function". Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 2005. (Available online http://estar.sourceforge.net/papers/philippsen_siegwart_icra2005_paper.pdf)

[3] Roland Philippsen. "A Light Formulation of the E* Interpolated Path Replanner". Technical Report, Autonomous Systems Lab, Ecole Polytechnique Fédérale de Lausanne, 2006. (Available online http://estar.sourceforge.net/papers/philippsen--estar-TR06.pdf)

[4] Bjoern Jensen, Roland Philippsen, and Roland Siegwart. "Motion Detection and Path Planning in Dynamic Environments". Workshop Proceedings Reasoning with Uncertainty in Robotics, International Joint Conference on Artificial Intelligence (IJCAI), 2003.

[5] Roland Philippsen, Bjoern Jensen, and Roland Siegwart. Chapter "Towards Real-Time Sensor-Based Path Planning in Highly Dynamic Environments" in "Autonomous Navigation in Dynamic Environments", Springer Tracts on Advanced Robotics, editors Christian Laugier and Raja Chatila, 2006. (Available online http://estar.sourceforge.net/papers/philippsen-jensen-siegwart--star06.pdf.zip)

doxygen SourceForge.net Logo
E* Interpolated Graph Replanner Wed Dec 12 18:55:40 2007