基于二分搜索的牛耕式全覆盖规划算法研究

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (23): 51-53.

基于二分搜索的牛耕式全覆盖规划算法研究

赵慧南1，2，刘淑华1，吴富章1，程宇1

1.东北师范大学计算机学院，长春 130024
2.东北师范大学人文学院，长春 130117

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-08-11 发布日期:2011-08-11

Research on boustrophedon complete coverage path planning based on binary search

ZHAO Huinan1，2，LIU Shuhua1，WU Fuzhang1，CHENG Yu1

1.School of Computer Science，Northeast Normal University，Changchun 130024，China
2.College of Humanities，Northeast Normal University，Changchun 130117，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-08-11 Published:2011-08-11

摘要/Abstract

摘要： 针对栅格环境下存在任意形状的静态障碍物问题，提出了结合二分搜索法的牛耕式全覆盖路径规划算法，该算法可以加速寻找下一个未覆盖空间的初始位置，提高了覆盖的效率。对该算法在多种室内环境中进行仿真，仿真结果表明该算法切实可行。另外，通过与其他全覆盖算法进行对比，结果表明该方法能有效地降低重复覆盖率。

关键词: 全覆盖路径规划, 牛耕式, 二分法

Abstract: This paper proposes an improved boustrophedon complete coverage path planning combined with binary search.There are some static obstacles in the grid environment.The binary search algorithm enable robot search next uncovered area faster so as to increase coverage efficiency.The proposed algorithm is tested in many indoor environments.Simulation results show that the method is feasible and is not sensitive to robot’s initial position.In addition，compared with other algorithm，the proposed method is more effective.

Key words: complete coverage path planning, boustrophedon, binary search

赵慧南1，2，刘淑华1，吴富章1，程宇1. 基于二分搜索的牛耕式全覆盖规划算法研究[J]. 计算机工程与应用, 2011, 47(23): 51-53.

ZHAO Huinan1，2，LIU Shuhua1，WU Fuzhang1，CHENG Yu1. Research on boustrophedon complete coverage path planning based on binary search[J]. Computer Engineering and Applications, 2011, 47(23): 51-53.

[1]	许朝阳1，林耀海2，张萍1. 基于密度二分法的密度峰值聚类方法[J]. 计算机工程与应用, 2018, 54(12): 138-145.
[2]	智慧来. 采用二分法的信息系统属性约简研究[J]. 计算机工程与应用, 2014, 50(9): 21-24.
[3]	赵小龙1，2，赵杭生2，曹龙1，2，许金勇2. 基于改进型能量检测的加权协作频谱感知算法[J]. 计算机工程与应用, 2013, 49(24): 61-64.