Jump to Content
  1. Oxford
  2. MPLS
  3. Eng. Sci.
  4. ORI

Estimation, Search, and Planning (ESP) Research Group

Effort Informed Trees (EIT*)

Source Code

A reference implementation of EIT* is available in pull request #844 for the Open Motion Planning Library (OMPL) and will hopefully be part of future binary releases. You can find details on how to download and install OMPL on their website.

Description

Effort Informed Trees (EIT*) is an almost-surely asymptotically optimal path planning algorithm. It simultaneously calculates and exploits multiple heuristics with an asymmetric bidirectional search in which both searches continuously inform each other. One of these heuristics guides EIT* towards fast-to-find solutions by considering information about the computational effort required to validate a path. EIT* outperforms other almost-surely asymptotically optimal algorithms (e.g., RRT* and AIT*) on problems with expensive edge evaluations by finding initial solutions as fast as RRT-Connect and converging to the optimum in an anytime manner.

Return to Top
  1. Authors
    1. M. P. Strub
    2. J. D. Gammell
    Title
    AIT* and EIT*: Asymmetric bidirectional sampling-based path planning
    Publication
    Journal
    The International Journal of Robotics Research (IJRR)
    Date
    Notes
    To appear, Manuscript #IJR-21-4179
    Videos
    Video
    PDFs
    PDF
    Google Scholar
    Google Scholar