A hybrid sampling-based path planning algorithm for mobile robot navigation in unknown environments

The motion planning problem poses the question of how a robot can move from an initial to a final position. Sampling-based motion planning is a class of randomized path planning algorithms with proven completeness. These algorithms generate paths using random numbers and perform efficiently in guiding the robot in known environments. There are a variety of algorithms in this class with different objectives, advantages and drawbacks. The existing drawbacks of current samplingbased planners can be categorized into five categories including non-optimality of the resulted paths, instability of the results in different runs of the planner, high running time requirements in some problems, failure in difficult environments such as narrow passages and Bug traps, and inability to plan in unknown environments. Although several extensions of the sampling-based algorithms have been proposed for solving each drawback, but the lack of a randomized planner that overcomes abovementioned inefficiencies in a single package is evident and makes the sampling-based path planning less effective for certain purposes. In this research, a sampling-based path planning algorithm was proposed which employs several heuristic and intelligent techniques to improve the performance of the planner in terms of quality of the resulted paths, runtimes of the planner, stability of the results in different executions, ability to solve difficult problems effectively and capability of planning in unknown environment. First, a sensor-based path planner was designed which incorporates the heuristic rules of tabu search technique to handle uncertainty and lack of information about the environment and to prevent trapping in local minima which is quite common in online planning. This planner considers the points on the vision range of the robot’s sensory system as the sampling area and uses the tabu search rules to evaluate the generated samples and select the most promising ones. Secondly, a fuzzy logic controller (FLC) was constructed for evaluating the generated samples in order to make the planner behavior close to the human manner and solve the planning queries in difficult environments. Afterward, a genetic algorithm-based optimization framework was designed to improve the interpretability and accuracy of the proposed fuzzy-tabu controller by optimizing the parameters of the FLC and also some of the planner’s parameters in order to improve the quality of the generated paths and runtimes of the planner and also to decrease the variation of the results in different runs of the planner. The genetic optimizer also evaluates the fuzzy rules and selects those rules that directly affect the performance of the planner and ignores irrelevant and erroneous fuzzy rules. Finally, an adaptive neuro-fuzzy inference system (ANFIS) was designed which constructs and optimizes a fuzzy logic controller using a given dataset of input/output variables in order to increase the optimality and stability rates of the proposed path planning algorithm. The simulation and comparison results indicate the superiority of the proposed algorithm. The proposed Tabu-based path planner successfully guides the robot in unknown environments without trapping in encountered local minima. The designed fuzzy-Tabu controller effectively solves the path planning queries in difficult environments like mazes, narrow passages and Bug traps without any failure. After optimizing the proposed fuzzy model by means ofgenetic algorithm, the resulted planner produces shorter paths in shorter runtimes with limited variations in results of different runs of the planner. Finally, the proposed ANFIS-generated FLC successfully improves the optimality and stability of the proposed planner. The average runtime was less than 4 seconds while the optimality of the generated paths was more than 95% with less than 0.1 standard deviations for path length and runtime.

Preview PDF FK 2013 13R.pdf Download (1MB) | Preview

Actions (login required)

View Item