Using focusing search algorithms and a strong heuristic to solve the findpath problem in robotics

摘要

Two problems are associated with the seeking of good solutions to the find path problem (Find Path) in robotics. First, the use of artificial intelligence searching techniques is limited to the A* algorithm. Secondly, simple and poor heuristics are employed in this best-first search. To speed up the search, two approaches are taken in this paper: i) using two A*-based focusing search algorithms, A+ and Aδ, for FindPath; ii) constructing a problem-tailored strong heuristic, h2, under the configuration space representation chosen (2-D with rotation). These approaches are compared with the use of A* and a standard heuristic. Experimental evidence indicates that each of the new approaches improves speed considerably and solution quality in each case is very close to the optimal. When combined, the new approaches speed up the search by more than 40%. We conclude that Aδ is, among the three search algorithms studied, the fastest and most suitable one for high branching-factor problems such as FindPath, especially when a strong heuristic (such as h2) is employed.