基于分治思想的扫地机器人全覆盖路径规划算法研究

摘要

针对大多数扫地机器人在进行全覆盖路径规划时,普遍存在重复率偏高和覆盖率偏低问题,并且在遇到密集零散的障碍区域时,会产生线路规划凌乱甚至不能覆盖的问题,设计一种基于分治思想的全覆盖路径规划算法,通过在地图上构建若干线段序列,按照线段序列端点间曼哈顿距离最小原则对局部路径线段进行相连,形成若干弓形线路块;然后采用分治算法实现全局各弓形线路块间最近端点对的匹配,并进行衔接,最终生成路径均匀的全覆盖线路。通过与牛耕式单元分解结合生物激励神经网络覆盖算法进行场景实验对比,分析表明在密集零散的障碍区域中,本文算法仍能规划出整齐平滑的可通行路径,覆盖率仍能高达91.3%,重复率下降约39.3%,时间花销约降低28.1%。