admin 管理员组

文章数量: 1086019

基于BINN算法的CCPP全路径覆盖算法

1.CCPP整体算法文档

1.1 ccpp基础介绍

全路径覆盖算法(CCPP: Complete Coverage Path Planning)作为扫地机器人较为关键的组成部分,其问题的本质是:在栅格地图中,全覆盖路径规划问题就演变为寻找机器人的下一个移动位置,只有准确找出了该位置,才能使机器人自主规划出一条切实可行的无碰撞且重复率低的移动路径。

CCPP需解决的关键问题

  • 遍历工作区域内除障碍物以外的全部区域
  • 在遍历过程中有效避开所有障碍物
  • 在遍历过程中要尽量避免路径重复,缩短移动距离

CCPP技术指标

  • 区域覆盖率
  • 路径重复率
  • 总行程

路径规划方法分类(根据实现方法)

  • 传统经典算法
    • 基于图的方法
    • 基于栅格的方法
    • 势场法
    • 数学编程法
  • 智能方法
    • 横糊方法
    • 神经网络方法
    • 遗传算法

路径搜索要求

  • 路径表达:以环境模型中的结点序列组成或由直线段序列组成
  • 路径平滑:根据机器人运动学或动力学约束,形成机器人可跟踪执行的运动轨迹
    • 运动学约束:路径轨迹的一阶导数应连续
    • 动力学约束:路径轨迹的二阶导数应连续

1.2 ccpp输入输出

ccpp

包名文件名输入输出功能
ccppmain.cpp//创建rosnode,并调用ccpp_ros
ccpp_ros.cpp/路径点集获取地图信息以及机器人当前位置,通过调用binn,将返回的结果发布
binn.cpp地图信息&起始点信息路径点集通过binn算法+A*算法获取全路径规划中关键点集,并将返回的结果保存为vector数组
AStar.cpp运动起点&终点路径点集通过实际地图信息、当前机器人所在位置以及目标位置判断出一条可行路径

1.3 ccpp所用代码库

目前ccpp环境搭建是基于ros环境的,同时基于Opencv去进行分析

环境功能版本
ROS负责机器人信息交互的通讯平台ROS melodic
Opencv负责处理pgm图像信息Opencv 3.5

1.3ccpp处理流程

1.4 ccpp代码思路

​ 该部分主要是对上文中的binn.cpp以及AStar.cpp的代码思路解析

  1. 获取以pgm格式保存的场景地图

  2. 根据机器人当前的位置获取自身所在地图的位置信息

  3. 将地图信息已数组的形式进行保存

  4. 更新当前栅格的浓度信息,并从八个方向进行浓度探测

  5. 判断当前位姿是否为可记录回溯点,如果是,则保存并等待回溯。

  6. 选择最优方向前进,并重复第四、五步

  7. 如果八个方向均走过,则进入回溯,并寻找下一个需要清扫的区域

  8. A*算法求得最优的路径点集

  9. 继续执行上述4-8步,直到回溯点集全部清空

ccpp使用教程

目前ccpp仍处于调试阶段,并未生成动态链接库嵌入到整体行为树中。所以目前在system_tests中开辟一个ccpp_test.launch来方便调试。只需要运行:

roslaunch system_tests ccpp_test.launch

ccpp处理结果

全路径覆盖结果图

全路径覆盖关键路径图

纯路径规划示意图

2. 核心代码

…详情请参照古月居

本文标签: 基于BINN算法的CCPP全路径覆盖算法