一种改进的网格多边形online探索算法

针对网格多边形机器人online探索问题,在分析现有成果的基础上,结合SmartDFS算法,并通过扩大机器人视觉范围,使其范围限定在给定的单位网格内。通过区分不同类型的网格,确定遍历的优先级别以设计出不同的探索策略,提出SmartDFS-OPT算法。该算法将网格多边形online探索问题求解算法的竞争比从5/4降低为7/6,达到了理论分析结果的下界,使机器人的online遍历路径长度达到最短,因而是求解该问题的一个最优算法。该算法将有助于那些基于机器人探索未知环境的智能设备的研发与应用。

AN IMPROVED ONLINE EXPLORATION ALGORITHM FOR EXPLORING GRID POLYGONS

To solve the problem of robot’s online exploration of grid polygon,based on the analysis of the existing results and the SmartDFS algorithm,we bounded the robot’s visual range within a given unit grid by expanding the view of the robot.By distinguishing different types of grids to determine the priority of traversal,thus providing different exploration strategies.This paper proposes an algorithm,SmartDFS-OPT.It reduced the competition ratio for online exploration of grid polygon from 5/4 to 7/6,and it reached the lower bound of the theoretical analysis result,which made the traversal path of the robot reach the shortest,making it an optimal algorithm to solve the problem.SmartDFS-OPT is helpful for the robots to explore the unknown environments,thus pushing forward the developments and applications of intelligent devices.