Approach to high efficient hierarchical pathfinding of indoor mobile service robots based on grid map and Floyd-Warshall algorithm

摘要

A new high efficient hierarchical pathfinding algorithm named Floyd-A*(FA*) is presented based on grid map of indoor environment for a mobile service robot. In FA*, an algorithm for key points extraction and region partition is designed according to distinction of indoor environment so that the representation of abstract map about indoor environment is more effective for high speed pathfinding. In offline search phase, Floyd-Warshall algorithm is used to acquire some useful knowledge as priori ones so that a more efficient query operation can be conducted to replace the online search process on abstract maps. Moreover, a kind of matrix memory mechanism is employed to greatly reduce memory overheads and improve the capacity of saving abstract paths. A series of experiments and evaluation analysis on benchmarks show that FA* speeds up A* by one to two orders of magnitude and makes significant improvement on efficiency over some other excellent variants of A* on grid map so as to drastically enhance the performance of our proposed pathfinding approach for further practical applications.