Robot Path Planning Based On Narrow Passage Recognition

Robot path planning is an important research topic in mobile robot. After decades ofeffort by researchers, effective algorithms emerges, e.g. roadmap, A*based on grid,visibility-based path planning method etc. But the performance of these algorithms greatlydrops as the dimension in configuration space increases with the addition of robot DoFs, andeven leads to curse of dimensionality. Random sampling method was proposed twenty yearsago to plan path for robot with multiple DoFs. It acquires the connection of configurationspace through randomly rapid sampling. In recent years, random method has widely beenused in path planning for the working space with obstacles, e.g. random roadmap andrapid-exploring tree. They are especially effective for cases with plenty of DoFs in theconfiguration space of moving object. However, when the working space has obstacles orexists with narrow passages, the above algorithms will cost long computation time and someeven inability to find suitable answers. In view of the above-stated limitations, this thesisfocuses on path planning base on recognition of narrow passages in the working space. Themain contents are listed as follows.This thesis proposes Randomized Star Builder to improve the recognition of narrowpassages and to avoid sampling milestones locating in the corners of obstacles. The validity ofthis method is tested in simulations and we also compare the narrow passage recognitionperformance among the Uniform sampler, Gaussian sampler, Randomized Bridge Builder andthe proposed Randomized Star Builder.This thesis presents a triple-RRTs algorithm based on Randomized Star Builder to planpath for robots with multiple DoFs in a space with narrow passages. It uses the configurationpoint sampled by Randomized Star Builder to heuristically lead tree expansion to facilitatemore in the narrow passages. As a result, the RRT covers a wide free configuration space and offers good connections among trees. Simulation results show that this algorithm is simple,general, and possesses better performance compared with the RRT-CONNECT.In order to facilitate roadmap sampling in narrow passages, a hybrid roadmap plannerbase on the narrow passage identification is designed. This new planner, which relies onRandomized Star Builder, increases the roadmap density in narrow passages resulting inimprovement of the exploring speed of the roadmap connection tree. Randomized StarBuilder can be considered as a tool to filter narrow passages. It picks out narrow passages inglobal area, uses Uniform sampler to locally sample milestones in the identification area toincrease local roadmap density and samples milestones globally and locally in an alternatemanner. As a result, it gets an ideal roadmap distribution, reduces the total number ofmilestones and accelerates exploring speed of connection trees.We also propose a multiple-method planning algorithm which is based on map learning.It uses Gaussian sampler to recognize obstacles with a third of the milestones, employsRandomized Star Builder to identify narrow passages in configuration space with anotherone-third of the milestones and acquires the remaining milestones in the full space usingUniform sampler. With this hybrid sampling method learned the environment, an improvedexpansive random tree algorithm is developed to explore wide free space. This hybridsampling method also effectively identifies narrow passages in the configuration space andachieves multiple robot tasks in this frame. Simulations of rigid robot with multiple DoFs in2-D and3-D validate the effectiveness of the proposed method.