Path Planning with Smooth Curve Using Electromagnetism-like Mechanism Algorithm

For all of the mainstream robots which have the movement capability, path planning will be a necessary and worthwhile problem to solve. The traditional path planning method is proposed by computer scientist Dijkstra [1], then A* algorithm [2] solves the problem of direction. The A* algorithm makes it work more efficiently, but these algorithms will encounter the map trade-off problem in the practical application. In a known environment, the map needs to be cut into many grids, and these grids are used to plan the path

The process of grids is a trade-off problem. If the map is cut into large grids, the relative generated path will be very rough. However, if the map is cut into small girds, it will cost a lot of computing costs. In real case, the obstacles on the map is irregular shape, such that path planning result is not the shortest path. As a result, many algorithms were proposed to compute shorter or more effective path for the trade-off problem.

To solve the problem mentioned above, we need to change the processing method for path planning by using a different map encoding method [3] and connect with the heuristic algorithm to solve the path planning problem. The electromagnetism-like (EM) algorithm [4] is innovative in the heuristic algorithm which is based on the characteristics of electromagnetic attraction and repulsion.

In this paper, instead of applying EM algorithm for optimization, we combine EM algorithm with different encoding method for path planning. It can avoid traditional trade-off problem by spreading points and connecting these points. The algorithm computes the path with path smoothing method. In this paper, cubic spline interpolation is chosen because it can smooth the path without increasing the algorithm’s parameters. To demonstrate the proposed method, we simulate the possible map configuration, and use map simulation to verify the feasibility of the algorithm.