机器人/导航/地图

为了有效地找到路线，机器人必须了解其周围环境。地图在这种情况下非常有用。机器人可以自己拥有记忆和工具来绘制地图，也可以事先获取地图，或者获取部分地图（例如，只有墙壁），然后自己添加其他障碍物。

• 在静态环境中，事先获取地图效果很好。
• 部分地图是一种更有效的方法，因为它已经包含了世界的所有静态部分。
• 当机器人经常被放置在新的环境中时，从头开始工作是最好的方法。

绘制地图有两个主要问题

• 并非周围环境中的所有元素都是静止的。大多数传感器过于有限，无法直接测量障碍物是墙壁、椅子还是人。解决此问题的办法是对每个测量的障碍物使用一个“分数”。如果机器人经过同一位置时再次检测到物体，则将分数添加到该物体。
• 定位并不完美。小的累积误差可能会使确定机器人确切位置变得困难，因此可能难以确定检测到的障碍物在地图上的位置。解决此问题的办法之一是同时定位与地图构建（SLAM），它根据机器人位置估计误差来校正检测到的物体的位置。

第三个小问题是内存。在没有计算机的机器人上，内存是有限的，存储整个地图几乎是不可能的。如果您有内存，地图可以以不同的方式存储

• 二维数组：易于访问且速度快，但内存浪费很大。
• 链表：使用速度较慢，但内存效率更高。
• 四叉树：比链表更快，但实现难度更大，内存效率很高。

在 PC 上实现这些结构相对容易，但在微控制器等有限环境中构建它们则是一项艰巨的挑战。