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

摘要

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