A path planner based on multivariant optimization algorithm with absorption

Intelligent optimization algorithms are simple, efficient and adaptive; as a result, they have been used to solve path planning problems. However, the traditional algorithms are easily trapped into local optima caused by sub-optimal paths. To overcome this problem, a path planner based on multivariant optimization algorithm with absorption strategy is proposed. A path planning problem is translated into an optimization problem through describing a path by a Bezier curve. Then, the proposed algorithm is employed to locate the optimal control points of a Bezier path. The global optimal solution is located through iteration of alternate global explorations and local refinements by intelligent searchers named as atoms in the multivariant optimization algorithm. The good performance of the proposed algorithm is ensured by the efficient communication and cooperation among atoms which have variant responsibilities. Atoms in the global group are responsible for exploring the whole solution space to locate potential areas. Then, groups of local atoms exploit these potential areas for local refinements. To improve the efficiency of multivariant optimization algorithm through reducing the redundant exploitation in the same area, the absorption strategy is introduced, i.e., local groups will merge if they move into the same search area. Experiments, which are based on benchmark maps from a commercial video game and literature, are carried out to compare the proposed algorithm with some state-of-the-art heuristic path planning algorithms. Results show that our proposed method is superior in optimality, stability and efficiency.