An Improved A^* Algorithm for Searching Infinite Neighbourhoods

The paths obtained by conventional A^* algorithm in grid map are usually not the optimal solutions, which have many turning nodes. To solve these problems, an improved A^* algorithm is presented. In this method, the number of searchable neighbourhood is extended to infinite (basic A^* algorithm has 8 discrete searchable neighbourhoods), and the search direction can be arbitrary. As a result, the path produced by the improved A^* is much shorter and the number of turning nodes is greatly reduced. The proposed method is implemented on our self-developed unmanned vehicle, Intelligent Pioneer. The vehicle experiments and its good performance in the Intelligent Vehicle Future Challenge of China show that the resulting path of our method is more optimal, which observably improves the driving efficiency and stationarity of the unmanned vehicles.