知识卡片

普通读书笔记卡 · 3745.b

栅格把环境转换为连通空间

理解等级:中级

栅格分解法把机器人所处的环境切成大小相同的方格,用一个栅格数组表示:

  • 每个格子标为自由(可走)或被占据(障碍)。
  • 混合格子(一部分是空地、一部分是障碍)按两者所占比例,归为自由或占据。
  • 相邻格子互相连通,机器人只能在相连的自由格之间移动。

示例(补充演示):3×3 栅格中,0 表示自由、1 表示障碍,第一行到第三行依次为 (0, 0, 0)、(1, 1, 0)、(0, 0, 0)。从左上角到左下角,只能经右侧第三列绕过中间那排障碍。

这样,“找一条不碰撞的路线”就变成“找一串相连的自由格”,碰撞约束被转成离散的连通约束。代价是格子的分类误差会直接改变可走空间:障碍边缘被归为自由,路线就可能擦碰;归为占据过多,又可能堵死本可通行的缝隙。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 5 . 3 . 2 算 法 描 述 以 及 实 现 · 查看原书依据

      栅格分解法是研究路径规划问题时常用的建模方法,它能够对复杂环境进行单元分割,将环境空间划分成若干个相同大小的栅格,并用栅格数组表示环境。每个栅格点可能是自由或者被占据,对于混合栅格点(即一部分是自由空间另一部分是障碍物),依据其在自由空间或障碍物空间的比例,将其归属于自由或者被占据。

    参考来源

    - 位置:《智能算法导论》第054章《5 . 3 . 2 算 法 描 述 以 及 实 现》(源文件:_epub-src/EPUB/xhtml/chapter5_0006.xhtml) - 结论依据:原文说明栅格尺寸、占用状态、混合格比例归类和相邻连通关系,并由此推出路径可转为格点连接问题。离散模型会把占用分类作为搜索可行性的依据。3×3 栅格为补充教学示例,非书中数据。 - 原始内容:栅格分解法是研究路径规划问题时常用的建模方法,它能够对复杂环境进行单元分割,将环境空间划分成若干个相同大小的栅格,并用栅格数组表示环境。每个栅格点可能是自由或者被占据