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

【Abstract】 In order to solve the low-efficiency problem caused by maze robot searching invalid area in complex maze, a binary search method is proposed to solve the maze efficiently based on intelligent maze search algorithm. An ordered two-dimensional array of maze coordinates is constructed by using the sequential arrangement characteristics of maze units, and the initial set of boundary elements is set and the search path of the robot is updated to the boundary set. When the boundary divides the maze into two parts, the target points of the two regions are searched, and the effective and invalid regions are divided accordingly. The robot will eliminate the invalid area in the subsequent search, and only carry out intelligent search for the effective area. This process is iterated to achieve the rapid arrival of the maze target. The binary search method is combined with intelligent algorithm A and Flood-central algorithm to generate 100 maze maps. The robot and maze are modeled using the robot development and research platform(ROS), and the interactive environment is built to test the application of two groups of algorithms. The test results show that: when the maze search distance is more than 100 grids, 200 grids,and 300 grids respectively, compared with the use of A algorithm and Flood-central algorithm alone, the search efficiency combined with binary search method is improved by 26%, 28%, and 41% on average, which proves that the strategy of combining binary search method with intelligent search algorithm can effectively improve the search efficiency of robot in complex maze.更多还原