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
    Adaptively Informed Trees (AIT*) and Effort Informed Trees (EIT*): Asymmetric bidirectional sampling-based path planning
    Publication
    Journal
    The International Journal of Robotics Research (IJRR)
    Volume
    41
    Number
    4
    Pages
    390–417
    Date
    Videos
    Video
    PDFs
    PDF
    Digital Object Identifier (DOI)
    doi: 10.1177/02783649211069572
    Google Scholar
    Google Scholar
  2. Author
    M. P. Strub
    Title
    Leveraging multiple sources of information to search continuous spaces
    Publication
    Type
    D.Phil. Thesis
    School
    University of Oxford
    Date
    PDFs
    PDF
    Google Scholar
    Google Scholar