Fast Marching Trees (FMT*) For Dynamic Motion Planning

Abstract

In light of recent advances in autonomous mobile robots, the chance for the robot presence in human domains have increased. To avoid collisions and to compute the optimal path between two points, motion planning has come to the fore as an essential area of research. Sampling based motion planners offer an advantage with respect to computational cost as in contrast to conventional planners they avoid an explicit construction of cspace. However, two of the major problems of sampling based motion planners is the need to efficiently adapt in the presence of dynamic obstacles and the degradation of path quality with a reduced number of samples. Much work has been done in order to adapt existing sampling based motion planning algorithms, including Randomly exploring Random Trees (RRT,RRT*), Probabilistic Roadmap Methods (PRM,PRM*), for dynamic scenarios. In order to solve the above-mentioned problems, we introduce two different sampling algorithms in order to solve the above mentioned problems. Firstly, Dual Tree Fast Marching Tree (DT-FMT*) is an asymptotically optimal static motion planning algorithm that is used to improve the path quality with a limited number of initial samples. It does this by quickly computing an initial path and uses that information to draw a batch of new samples to generate an improved path. Secondly, we introduced Reduced samples Replanning Fast Marching Tree (RR-FMT*) in order to modify an initial path in presence of dynamic obstacles. This is done by, first, computing an initial path using DT-FMT*, then during the course of robot motion along the path, we monitor the presence of obstacle at a certain clearance. In case of obstruction along the path, we grow a new tree to connect the current position of the robot to a way-point along the path. To validate our planner performance we have rigorously tested our both DT-FMT* and RR-FMT* performance against standard version of FMT*, as well as Secure tunnel FMT* (ST-FMT*). Similarly, in a dynamic environment, we compared planner performance against a dynamic versionxiv of RRT* planner. The result show an overall improvement with respect to both path cost and time taken to compute the path.