Search

In this article, based on the rapidly-exploring random tree (RRT), we propose a novel and efficient motion planning algorithm using bidirectional RRT search. First, a RRT extend function is used to organize the sampled states under kinodynamic constraints. Meanwhile, the bidirectional search strategy is implemented to grow a forward tree and backward tree simultaneously in the tree extension process. When these two trees meet each other, the backward tree will act as a heuristic to guide the forward tree to continuously grow toward the goal state, where the algorithm switches to unidirectional search mode. Therefore, the two-point boundary value problem (BVP) in the connection process is avoided, and the extension process gets much accelerated. We also prove that probabilistic completeness is guaranteed. Numerical simulations are conducted to demonstrate that the proposed algorithm performs much better than the state-of-the-art algorithms in different environments. Note to Practitioners—The motivation of this work is to develop an efficient sampling-based motion planning algorithm for mobile robots. Conventional sampling-based algorithms are time-consuming to find a feasible solution under differential constraints. When applying bidirectional search strategy to improve them, the complex 2-point BVP is required to solve. In this article, the backward free is regarded as a heuristic to guide the tree growth. On the one hand, the advantage of bidirectional search is retained. On the other hand, the 2-point BVP is avoided. Therefore, the bidirectional-unidirectional technique can achieve efficient robot motion planning. The proposed algorithm can be extended to other specified sampling-based algorithms to further improve their performance. Besides, it can be also applied to autonomous driving, service robot and medical robots to achieve efficient motion planning. [ABSTRACT FROM AUTHOR]

The rapidly exploring random tree and its variants (RRTs) have been widely adopted as the motion planning algorithms for mobile robots. However, the trap space problem, such as mazes and S-shaped corridors, hinders their planning efficiency. In this article, we present a generalized Voronoi diagram (GVD)-based heuristic path planning algorithm to generate a heuristic path, guide the sampling process of RRTs, and further improve the motion planning efficiency of RRTs. Different from other heuristic algorithms that only work in certain environments or depend on specified parameter setting, the proposed algorithm can automatically identify the environment feature and provide a reasonable heuristic path. First, the given environment is initialized with a lightweight feature extraction from the GVD, which guarantees that any state in the free space can be connected to the feature graph without any collision. Second, to remove the redundancy of feature nodes, a feature matrix is proposed to represent connections among feature nodes and a corresponding feature node fusion technique is utilized to delete the redundant nodes. Third, based on the GVD feature matrix, a heuristic path planning algorithm is presented. This heuristic path is then used to guide the sampling process of RRTs and achieve real-time motion planning. The proposed GVD feature matrix can be also utilized to improve the efficiency of the replanning. Through a series of simulation studies and real-world implementations, it is confirmed that the proposed algorithm achieves better performance in heuristic path planning, feature extraction of free space, and real-time motion planning. [ABSTRACT FROM AUTHOR]

In this article, a two-level planner is proposed to provide a solution to the autonomous luggage trolley collection problem at the airport. In the higher level planner, a decision-making problem is tackled where a sequence of luggage trolleys is determined with which the robot can collect them one by one. Based on the traditional traveling salesman problem (TSP), this decision-making problem is formulated as an open dynamic traveling salesman problem with fixed start (ODTSP-FS). Incorporating the modified transition rule, elitist global update rule, and additional local update rule, an efficient algorithm is proposed to handle this decision-making problem. The experimental results demonstrate that the proposed algorithm achieves fast convergence and smaller cost compared with the state-of-the-art algorithms. In the lower level planner, based on the pipeline of rapid-exploring random tree (RRT) scheme, a novel real-time path planning algorithm is introduced, which can adjust itself to moving obstacles and moving targets by retaining the whole tree and using two rewiring strategies. Finally, the proposed two-level planner is evaluated in a simulation environment similar to the airport to validate the effectiveness and efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In a human–robot coexisting environment, it is pivotal for a mobile service robot to arrive at the goal position safely and efficiently. In this article, an elastic band-based rapidly exploring random tree (EB-RRT) algorithm is proposed to achieve real-time optimal motion planning for the mobile robot in the dynamic environment, which can maintain a homotopy optimal trajectory based on current heuristic trajectory. Inspired by the EB method, we propose a hierarchical framework consisting of two planners. In the global planner, a time-based RRT algorithm is used to generate a feasible heuristic trajectory for a specific task in the dynamic environment. However, this heuristic trajectory is nonoptimal. In the dynamic replanner, the time-based nodes on the heuristic trajectory are updated due to the internal contraction force and the repulsive force from the obstacles. In this way, the heuristic trajectory is optimized continuously, and the final trajectory can be proved to be optimal in the homotopy class of the heuristic trajectory. Simulation experiments reveal that compared with two state-of-the-art algorithms, our proposed method can achieve better performance in dynamic environments. Note to Practitioners—The motivation of this work stems from the need to achieve real-time optimal motion planning for the mobile robot in the human–robot coexisting environment. Sampling-based algorithms are widely used in this area due to their good scalability and high efficiency. However, the generated trajectory is usually far from optimal. To obtain an optimized trajectory for the mobile robot in the dynamic environment with moving pedestrians, we propose the EB-RRT algorithm on the basis of the time-based RRT tree and the EB method. Depending on the time-based RRT tree, we quickly get a heuristic trajectory and guarantee the probabilistic completeness of our algorithm. Then, we optimize the heuristic trajectory similar to the EB method, which achieves the homotopy optimality of the final trajectory. We also take into account the nonholonomic constraints, and our proposed algorithm can be applied to most mobile robots to further improve their motion planning ability and the trajectory quality. [ABSTRACT FROM AUTHOR]

Rapidly random-exploring tree (RRT) and its variants are very popular due to their ability to quickly and efficiently explore the state space. However, they suffer sensitivity to the initial solution and slow convergence to the optimal solution, which means that they consume a lot of memory and time to find the optimal path. It is critical to quickly find a short path in many applications such as the autonomous vehicle with limited power/fuel. To overcome these limitations, we propose a novel optimal path planning algorithm based on the convolutional neural network (CNN), namely the neural RRT* (NRRT*). The NRRT* utilizes a nonuniform sampling distribution generated from a CNN model. The model is trained using quantities of successful path planning cases. In this article, we use the A* algorithm to generate the training data set consisting of the map information and the optimal path. For a given task, the proposed CNN model can predict the probability distribution of the optimal path on the map, which is used to guide the sampling process. The time cost and memory usage of the planned path are selected as the metric to demonstrate the effectiveness and efficiency of the NRRT*. The simulation results reveal that the NRRT* can achieve convincing performance compared with the state-of-the-art path planning algorithms. Note to Practitioners—The motivation of this article stems from the need to develop a fast and efficient path planning algorithm for practical applications such as autonomous driving, warehouse robot, and countless others. Sampling-based algorithms are widely used in these areas due to their good scalability and high efficiency. However, the quality of the initial path is not guaranteed and it takes much time to converge to the optimal path. To quickly obtain a high-quality initial path and accelerate the convergence speed, we propose the NRRT*. It utilizes a nonuniform sampling distribution and achieves better performance. The NRRT* can be also applied to other sampling-based algorithms for improved results in different applications. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]