迷宫搜索算法的比较研究

Comparative study of algorithms for search in mazes

研究面向搜救的应用,将事故环境抽象为一个迷宫,通过仿真实验比较研究了深度优先搜索算法和三种不同启发式函数的A*算法在Perfect迷宫中的应用,并分别将深度优先搜索算法和A*算法用于实际迷宫中进行实现与比较。在实验中,迷宫环境对机器人是未知的,而由于迷宫环境的特殊性———未知的迷宫环境中很少有不会碰撞的路径,从而增加了机器人搜索的难度。通过仿真实验对比了不同启发式函数的A*算法与深度优先搜索算法的性能,最后得出在迷宫搜索中A*算法要优于深度优先搜索算法;同时,在实际迷宫中实现了深度优先搜索算法与A*算法的搜救应用。

This paper mainly concentrated on studying the application of robotic searching. In this case, the accident environment was abstracted as a maze ,and this paper compared the depth-first search algorithm and three A-star algorithms in application of Perfect maze by simulation experiment. Furthermore, it also implemented the depth-first search algorithm and the 3 heuristic functions of A-star algorithms in real maze application and compared the results. In the experiment, the environment of maze was unknown by the robot. Because an unknown maze had few collision-free path to a destination,it increased the difficulty to search the right path. By comparing the performances of different types of A-star algorithms and the depth-first search algorithm in simulation, experiments validate the usefulness of heuristic function with the results that the A-star algorithms out- perform the depth-first search algorithm in most cases, meanwhile, has implemented the use of the depth-first search algorithm and A-star algorithmin real maze Searching.