Research Of Robot Path Planning Algorithm

Robot motion planning is a very important problem of mobile robots, and the objective of motion planning is to computer a continuous path without collision when the robot is in known or unknown environments. In the research of early years, the motion planning only considered the geometry of the robots and the obstacles, that is, we can view the motion planning problem as a search problem in a configuration space, such as the A*algorithm and the colony algorithm. But in reality the motion planning considered not only the configure constraint but also the dynamics constraints or the nonholonomic constraints.The RRT method can incorporate nonholonomic constraints into motion planning by the use of a tree-based exploration of the state space. The RRT method is a probabilistically complete under very general conditions. Its’advantage is that the method is relatively simple and the expansion of an RRT is heavily biased toward unexplored portions of the state space. In order to improve the efficiency, all kinds modified algorithm were mentioned. The traditional goal-bias RRT is one of them but it has an inherent problem, when there are lesser vertexes, the search towards the goal is often invalid, however when there are more vertexes, the search towards other regions is often unnecessary.To solve the problem of the traditional RRT, we introduce a kind bidirectional variable probability RRT algorithm. In this part, we build two trees, and one tree expands towards to the other tree at a variable probability. This probability is in proportion to the coverage of the trees, that is, when there are lesser vertexes, the searches are mainly towards unexplored regions, and when there are more vertexes, we attach more importance to the connection of two trees. The results show the good performance and convergence speed of the proposed algorithm.But with the environment becoming complex, the tree exploration slows down significantly. In this paper, a novel two-stage motion planning is proposed. The first stage is discrete search based on the scent pervasion principle, and the second stage is the sampled-based motion planning under the direction of the scent information, The results show the good performance and convergence speed of the proposed algorithm.