摘要
针对网格多边形机器人online探索问题,在分析现有成果的基础上,结合SmartDFS算法,并通过扩大机器人视觉范围,使其范围限定在给定的单位网格内。通过区分不同类型的网格,确定遍历的优先级别以设计出不同的探索策略,提出SmartDFS-OPT算法。该算法将网格多边形online探索问题求解算法的竞争比从5/4降低为7/6,达到了理论分析结果的下界,使机器人的online遍历路径长度达到最短,因而是求解该问题的一个最优算法。该算法将有助于那些基于机器人探索未知环境的智能设备的研发与应用。
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.
作者
谢玉莹
包敏泽
胡秀婷
蒋波
Xie Yuying;Bao Minze;Hu Xiuting;Jiang Bo(School of Information Science and Technology,Dalian Maritime University,Dalian 116026,Liaoning,China)
出处
《计算机应用与软件》
北大核心
2022年第3期218-222,315,共6页
Computer Applications and Software
基金
国家自然科学基金青年基金项目(61702242)。
