知识卡片
栅格把环境转换为连通空间
栅格分解法把机器人所处的环境切成大小相同的方格,用一个栅格数组表示:
- 每个格子标为自由(可走)或被占据(障碍)。
- 混合格子(一部分是空地、一部分是障碍)按两者所占比例,归为自由或占据。
- 相邻格子互相连通,机器人只能在相连的自由格之间移动。
示例(补充演示):3×3 栅格中,0 表示自由、1 表示障碍,第一行到第三行依次为 (0, 0, 0)、(1, 1, 0)、(0, 0, 0)。从左上角到左下角,只能经右侧第三列绕过中间那排障碍。
这样,“找一条不碰撞的路线”就变成“找一串相连的自由格”,碰撞约束被转成离散的连通约束。代价是格子的分类误差会直接改变可走空间:障碍边缘被归为自由,路线就可能擦碰;归为占据过多,又可能堵死本可通行的缝隙。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 5 . 3 . 2 算 法 描 述 以 及 实 现 · 查看原书依据
栅格分解法是研究路径规划问题时常用的建模方法,它能够对复杂环境进行单元分割,将环境空间划分成若干个相同大小的栅格,并用栅格数组表示环境。每个栅格点可能是自由或者被占据,对于混合栅格点(即一部分是自由空间另一部分是障碍物),依据其在自由空间或障碍物空间的比例,将其归属于自由或者被占据。
参考来源
- 位置:《智能算法导论》第054章《5 . 3 . 2 算 法 描 述 以 及 实 现》(源文件:_epub-src/EPUB/xhtml/chapter5_0006.xhtml)
- 结论依据:原文说明栅格尺寸、占用状态、混合格比例归类和相邻连通关系,并由此推出路径可转为格点连接问题。离散模型会把占用分类作为搜索可行性的依据。3×3 栅格为补充教学示例,非书中数据。
- 原始内容:栅格分解法是研究路径规划问题时常用的建模方法,它能够对复杂环境进行单元分割,将环境空间划分成若干个相同大小的栅格,并用栅格数组表示环境。每个栅格点可能是自由或者被占据