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

Estimation, Search, and Planning (ESP) Research Group

Effort Informed Roadmaps (EIRM*)

Jonathan has been working with Valentin Hartmann to extend Marlin's work on effort-informed planning to multiquery problems. Their Effort Informed Roadmaps (EIRM*) can solve individual problems an order-of-magnitude faster and has been submitted to ISRR 2022. If you'd like to know more you can watch the trailer video on YouTube, read the paper on arXiv, and checkout the code. Valentin is a Ph.D. student in Marc Toussaint's Learning and Intelligent Systems (LIS) lab at TUBerlin.

Authors
  1. V. N. Hartmann
  2. M. P. Strub
  3. M. Toussaint
  4. J. D. Gammell
Title
Effort informed roadmaps (EIRM*): Efficient asymptotically optimal multiquery planning by actively reusing validation effort
Publication
Conference
Proceedings of the International Symposium on Robotics Research (ISRR)
Date
Notes
Submitted, Manuscript #3
Code
Code
Videos
Video
PDFs
PDF
Google Scholar
Google Scholar

Abstract

Multiquery planning algorithms find paths between various different starts and goals in a single search space. They are designed to do so efficiently by reusing information across planning queries. This information may be computed before or during the search and often includes knowledge of valid paths.

Using known valid paths to solve an individual planning query takes less computational effort than finding a completely new solution. This allows multiquery algorithms, such as PRM*, to outperform single-query algorithms, such as RRT*, on many problems but their relative performance depends on how much information is reused. Despite this, few multiquery planners explicitly seek to maximize path reuse and, as a result, many do not consistently outperform single-query alternatives.

This paper presents Effort Informed Roadmaps (EIRM*), an almost-surely asymptotically optimal multiquery planning algorithm that explicitly prioritizes reusing computational effort. EIRM* uses an asymmetric bidirectional search to identify existing paths that may help solve an individual planning query and then uses this information to order its search and reduce computational effort. This allows it to find initial solutions up to an order-of-magnitude faster than state-of-the-art planning algorithms on the tested abstract and robotic multiquery planning problems.