Risk-DTRRT-Based Optimal Motion Planning Algorithm for Mobile Robots

In a human-robot coexisting environment, reaching the target place efficiently and safely is pivotal for a mobile service robot. In this paper, a Risk-based Dual-Tree Rapidly exploring Random Tree (Risk-DTRRT) algorithm is proposed for the robot motion planning in a dynamic environment, which provides a homotopy optimal trajectory on the basis of a heuristic trajectory. A dual-tree framework consisting of an RRT tree and a rewired tree is proposed for the trajectory searching. The RRT tree is a time-based tree, considering the future trajectory predictions of the pedestrians, and this tree is utilized to generate a heuristic trajectory. However, the heuristic trajectory is usually nonoptimal. Then, a line-of-sight (LoS) control checking algorithm is proposed to detect whether two time-based nodes can be rewired with the least cost. On the basis of the LoS control checking algorithm, a tree rewiring algorithm is proposed to optimize the heuristic trajectory. The tree generated in the tree rewiring process is called the rewired tree. The trajectory generated by the Risk-DTRRT algorithm proves to be optimal in the homotopy class of the heuristic trajectory. The navigation run time and the lengths of the planned trajectories are selected to demonstrate the effectiveness of the proposed algorithm. The experimental results in both simulation studies and real-world implementations reveal that our proposed method achieves convincing performance in both static and dynamic environments. Note to Practitioners-This paper is motivated by planning optimized trajectories for the mobile service robots in dynamic environments with pedestrians. In this area, the sampling-based motion planning algorithms have been widely used for their high efficiency and robustness. However, the real-time optimality of the motion planning cannot be guaranteed due to the challenges caused by the moving pedestrians. In this paper, we propose a dual-tree framework to solve this problem. First, a classic Rapidly exploring Random Tree (RRT) is constructed to generate a heuristic trajectory. Then, instead of reconnecting the nodes on the heuristic trajectory directly, a rewired tree is built to optimize the heuristic trajectory. This proposed dual-tree framework can fully exploit the information of the RRT tree and ensure the completeness of the motion planning. The proposed motion planning algorithm also considers the constraints of the nonholonomic mobile robots, and it can be applied in most mobile service robots to improve their motion planning quality.