我应该采用什么算法来对房间清洁机器人进行编程？

Question

对于这个问题，假设以下事情是未知的：

• 房间的大小和形状
• 机器人的位置
• 是否存在任何障碍物

还假设以下条件不变：

• 房间的大小和形状
• 所有障碍物（如果有）的数量、形状和位置

并假设机器人具有以下属性：

• 它只能以绝对单位的增量向前移动并以度数转动。另外，移动的操作如果成功则返回 true，如果由于障碍物而无法移动则返回 false
• 相当无限的电源（假设它是一个太阳能机器人，放置在空间站上，始终面向太阳，没有天花板）
• 每次移动和旋转都以绝对精度进行（不用担心数据不可靠）

我被问到这个问题的一个更简单的版本（房间是一个矩形，没有障碍物，你将如何移动它以保证你可以在每个部分至少一次），并且在我开始想知道如果你无法保证障碍物的形状或存在。我已经开始用 Dijkstra 算法 来研究这个问题，但我很想听听其他人如何解决这个问题（或者是否有一个被广泛接受的答案？（Roomba 是如何做到的？）

Answer 1

查看 SLAM http://openslam.org/ 以及更多信息 Wiki

Answer 2

你应该进一步调查

Mark de Berg：计算几何算法与应用 第13章机器人运动规划