A strategy to escape from local traps for sparse A* algorithm

摘要

In this paper the sparse A* algorithm (SAS) has been studied from the aspect of handling local traps. Firstly, SAS is briefly introduced and differences between the standard A* algorithm and SAS has been analyzed. The comparison shows that SAS is serious deficient in dealing with local traps, however it is very important for SAS to work in practical applications. Thirdly, a method to measure local traps is proposed. Based on this method, the efficiency of using different step lengths has been studied. Forth, a combined strategy to improve the performance of SAS is proposed, two simulation closed to real applications have proven the effectiveness of the proposed strategy.