  Informed sampling-based planning algorithms exploit problem knowledge for
better search performance. This knowledge is often expressed as heuristic
estimates of solution cost and used to order the search. The practical
improvement of this informed search depends on the accuracy of the heuristic.
  Selecting an appropriate heuristic is difficult. Heuristics applicable to an
entire problem domain are often simple to define and inexpensive to evaluate
but may not be beneficial for a specific problem instance. Heuristics specific
to a problem instance are often difficult to define or expensive to evaluate
but can make the search itself trivial.
  This paper presents Adaptively Informed Trees (AIT*), an almost-surely
asymptotically optimal sampling-based planner based on BIT*. AIT* adapts its
search to each problem instance by using an asymmetric bidirectional search to
simultaneously estimate and exploit a problem-specific heuristic. This allows
it to quickly find initial solutions and converge towards the optimum. AIT*
solves the tested problems as fast as RRT-Connect while also converging towards
the optimum.
