The Boustrophedon Cellular Decomposition
BCD(Boustrophedon Cellular Decomposition)是一种栅格地图的分解方法。完成该分解后，每个cell都可以通过一个牛耕式路径遍历。不同cell之间通过旅行商问题获得最优路径即可做到全地图的覆盖式清扫。
算法原理非常简单。地图中的每一列称为一个slice。遍历地图中的slice，并计算区块的连通性。每当连通性增加，则触发一个IN事件，封闭当前cell，并开启两个新的cell。若遇到连通性降低，则触发一个OUT事件，当前的两个cell封闭，并开启一个新的cell。
覆盖路径规划是确定机器人为了通过环境中的每个点而必须走的路径。应用包括吸尘、地板擦洗和检查。我们发展了boustrophedon细胞分解，这是一种精确的细胞分解方法，目的是覆盖。布斯特罗夫顿的每个细胞都被简单的来回运动所覆盖。一旦每个单元都被覆盖，那么整个环境就被覆盖了。因此，在boustrophedon分解中，覆盖率被简化为通过表示细胞邻接关系的图找到穷尽路径。该方法是完全可行的，在移动机器人上的实验验证了该方法的有效性。
另一种解释
牛耕分解法
一种方法是把Cfree分解成cells，然后像牛耕地一样运动。
它假设机器人是W=R2中的一个点，但是其有工具厚度E挂在机器人的两边，覆盖cfree以E/2,这种方法常用在打印机减少打印转弯
如果COBS是多边形，像6.2.2讨论的垂直分解，那个算法里有很多情况，在牛耕运动中只遇到第一种情况。
这使得分解出的cell数目少，即使是非凸的，也能很好的切成垂直的片，很适合于牛耕。
原始的垂直方法也可以使用，但是多余的cell边缘会导致机器人不必要的重新定位。
一个相似的方法是最优化机器人的转角
论文
简介