基于二分思想的迷宫机器人智能搜索算法

摘要

为解决迷宫机器人在复杂迷宫进行无效区域搜索导致的低效率问题，提出在智能迷宫搜索算法基础上加入二分查找方法对迷宫进行高效解算。利用迷宫单元顺序排列特征构建一个有序的迷宫坐标二维数组，设定初始边界元素集合并将机器人的搜索路径更新到边界集合；当边界将迷宫划分为2个部分时，对2个区域进行目标点查找，并据此划分有效和无效区域；机器人后续搜索将无效区域剔除，仅对有效区域进行智能搜索，迭代此过程实现迷宫目标的快速到达。将二分查找法与智能算法A和Flood-central算法结合，生成100幅迷宫地图，利用机器人开发研究平台（ROS）对机器人和迷宫进行建模，搭建交互环境进行两组算法应用测试。结果表明：在迷宫搜索路程分别超过100格、200格、300格的情况下，相较于单独使用A算法和Flood central算法，结合二分查找法后搜索效率平均提升了26%、28%与41%，证实了二分查找法与智能搜索算法相结合的策略可有效提升机器人在复杂迷宫中的搜索效率。

关键词

迷宫机器人 / 二分查找法 / 智能搜索算法 / 迷宫搜索效率 / 机器人开发研究平台(ROS)