  This paper addresses the fast replanning problem in dynamic environments with
moving obstacles. Since for randomly moving obstacles the future states are
unpredictable, the proposed method, called SMARRT, reacts to obstacle motions
and revises the path in real-time based on the current interfering obstacle
state (i.e., position and velocity). SMARRT is fast and efficient and performs
collision checking only on the partial path segment close to the robot within a
feasibility checking horizon. If the path is infeasible, then tree parts
associated with the path inside the horizon are pruned while maintaining the
maximal tree structure of already-explored regions. Then, a multi-resolution
utility map is created to capture the environmental information used to compute
the replanning utility for each cell on the multi-scale tiling. A hierarchical
searching method is applied on the map to find the sampling cell efficiently.
Finally, uniform samples are drawn within the sampling cell for fast
replanning. The SMARRT method is validated via simulation runs, and the results
are evaluated in comparison to four existing methods. The SMARRT method yields
significant improvements in travel time, replanning time, and success rate
compared against the existing methods.
