  This paper presents a novel algorithm, called MRRT, which uses multiple
rapidly-exploring random trees for fast online replanning of autonomous
vehicles in dynamic environments with moving obstacles. The proposed algorithm
is built upon the RRT algorithm with a multi-tree structure. At the beginning,
the RRT algorithm is applied to find the initial solution based on partial
knowledge of the environment. Then, the robot starts to execute this path. At
each iteration, the new obstacle configurations are collected by the robot's
sensor and used to replan the path. This new information can come from unknown
static obstacles (e.g., seafloor layout) as well as moving obstacles. Then, to
accommodate the environmental changes, two procedures are adopted: 1) edge
pruning, and 2) tree regrowing. Specifically, the edge pruning procedure checks
the collision status through the tree and only removes the invalid edges while
maintaining the tree structure of already-explored regions. Due to removal of
invalid edges, the tree could be broken into multiple disjoint trees. As such,
the RRT algorithm is applied to regrow the trees. Specifically, a sample is
created randomly and joined to all the disjoint trees in its local neighborhood
by connecting to the nearest nodes. Finally, a new solution is found for the
robot. The advantages of the proposed MRRT algorithm are as follows: i) retains
the maximal tree structure by only pruning the edges which collide with the
obstacles, ii) guarantees probabilistic completeness, and iii) is computational
efficient for fast replanning since all disjoint trees are maintained for
future connections and expanded simultaneously.
