Backward and bidirectional versions

As usual, both backward and bidirectional versions of this approach can be made. If the $ {X_{G}}$ is large (or the goal tolerance is large) and the BVP is costly to solve, then the backward version seems less desirable if the BVP is hard. The forward direction is preferred because the BVP can be avoided altogether.

For a bidirectional algorithm, the same collection $ {\cal D}$ of cells can be used for both trees. The problem could be considered solved if the same cell is reached by both trees; however, one must be careful to still ensure that the remaining BVP can be solved. It must be possible to find an action trajectory segment that connects a vertex from the initial-based tree to a vertex of the goal-based tree. Alternatively, connections made to within a tolerance may be acceptable.



Steven M LaValle 2012-04-20