Multi-objective path planning in discrete space

Finding a path for a robot which is near to natural looking paths is a challenging problem in motion planning. This paper suggests two single and multi-objective optimization models focusing on length and clearance of the path in discrete space. Considering the complexity of the models and potency of evolutionary algorithms we apply a genetic algorithm with NSGA-II framework for solving the problems addressed in the models. The proposed algorithm uses an innovative family of path refiner operators, in addition to the standard genetic operators. The new operators intensify explorative power of the algorithm in finding Pareto-optimal fronts in the complicated path planning problems such as narrow passages and clutter spaces. Finally, we compare efficiency of the refiner operators and the algorithm with PSO and A* algorithms in several path planning problems.

In this paper we investigate path planning problem in term of natural looking path in discrete space. We focus on the length and clearance objectives in the problem and suggest two single and multi-objective optimization models. Then, we use an evolutionary algorithm equipped to an innovative family of geometric operators. We show that the new operators intensify explorative power of the algorithm for searching Pareto-optimal fronts in the complicated path planning problems such as clutter spaces and narrow passages. Finally, we compare efficiency of the refiner operators and the algorithm with other algorithms in various path planning test problems.Figure optionsDownload as PowerPoint slideHighlights
► We introduce two single and multi-objective path planning models focusing on the length and clearance of the path.
► We develop a multi-objective evolutionary algorithm with NSGA-II framework for solving the problems addressed in the models.
► We proposed a new family of path refiner operators for efficient searching in the proposed algorithm.
► We compare the proposed algorithm and the refiner operators with PSO and A* algorithms in several test problems.