房间的大小和形状
机器人的位置
是否存在障碍物
/>
还假设以下情况是恒定的：
房间的大小和形状
所有房间的数量，形状和位置（如果有）障碍物
并假定机器人具有以下属性：
它只能以绝对单位递增并以度为单位旋转。同样，如果操作成功，则移动的操作将返回true；如果由于障碍而导致移动失败，则操作将返回false
合理无限的动力源（假设它是放置在面向太阳的空间站上的太阳能机器人）始终无上限）
每次运动和旋转都绝对精确（不必担心数据不可靠）
最后，请考虑机器人环境的以下特性：
在无天花板空间站上，房间是安全的，但与经过的彗星的距离令人沮丧，因此灰尘（和冰）不断散落在环境中。 >
有人问我这个问题的简单得多（房间是一个矩形，没有障碍，如何在它上面移动以确保至少可以覆盖每个部分），然后我开始想知道如何处理如果您不能保证形状或障碍物存在，可以采用这种方法。我已经开始使用Dijkstra的算法研究这个问题，但是我很着迷于听到其他人如何解决这个问题（或者对此是否有一个公认的答案？（Roomba是如何做到的？）
#1 楼
据我所知，这个问题尚未“解决”。从形式上讲，这是一个在线覆盖问题。覆盖范围，因为我们必须覆盖地面上的每个点，而在线则是因为我们无法离线访问地图。如果您对最新结果感兴趣，建议您在Google Scholar中查找“机器人在线覆盖算法”（有很多很好的结果）。除了@ embedded.kyle的内容非常丰富多彩（重新），我还将添加一些详细信息（我还将尝试快速找到一些简单的结果）：
Dijkstra将会获得您的道路，但不一定是覆盖范围。例如，如何向Dijkstra指定必须访问图形中的每个点，而不是尽快访问一个点？您可以运行所有对的最短路径，但是有什么用呢？您没有地图。 >没有障碍物，并有一个矩形的房间，并假设您从边界开始，牛对牛（牛的行进）路径是最佳的。
有趣的是农民一直在这样做，对吧？ http://en.wikipedia.org/wiki/Boustrophedon。通过找到没有障碍物的大致矩形区域，可以将其扩展到有障碍物的房间。 Howie Choset对此做了一些努力。
要覆盖未知范围的区域，并假设您不从该范围开始，最佳策略是什么？好吧，想象一下您掉入了世界，看不见周围。您可以一直走直到到达外围，然后做牛牙，对不对？除了现在，您“浪费”了寻找周边的时间，因为您将覆盖该零件两次。这就是机器人趋向于螺旋运动的原因：到边界时，您已经覆盖了很多区域（$ \ pi * d ^ 2 $，其中$ d $是到最近边界的距离，对吗？）。这很有用：现在可以保证找到最接近的边界，并且可以找到它。
这是一个巨大而迷人的区域。抱歉，我无法提供更好的摘要！
最大的问题是您没有地图。如果没有地图，您将只能执行简单的操作，例如周界跟踪和沿路径移动（例如提到的螺旋线）。因此，有一些机器人会在清洁时实际构建地图，将映射出的区域分解为形状，然后覆盖每个形状以确保覆盖范围。请参阅：http://mintcleaner.com/
#2 楼
Roomba开始呈螺旋状直至撞到某物，然后进行周长扫掠。然后它只是反弹。 Roomba是家用机器人真空吸尘器的事实上的标准，我想您可以称其为“可接受的解决方案”。但是从个人经验（我有两个）来看，肯定还有改进的空间。从工作原理上来看：与iRobot市场传播副总裁Nancy Dussault Smith一起：
开始时，您会注意到螺旋状的图案，它会在越来越大的范围内呈螺旋状
直到碰到物体。当它
找到一个对象时，它将沿着该对象的边缘跟踪一段时间，然后将开始进行纵横交错，尝试找出最大的距离可以不撞到另一个物体而去，这
可以帮助它找出空间有多大，但是如果它过长的一段时间
而没有撞到墙壁，它将
重新开始呈螺旋状，因为它认为它位于广阔的开放空间中，并且不断进行计算和计算。
它与下面的污物传感器类似，当其中一个传感器被触发时，它的行为会改变以覆盖该区域。然后，它会
离开，在一条直线路径上寻找另一个脏区。
这些不同的模式相互叠加的方式，我们知道
这是覆盖房间的最有效方法。
我们选择的模式以及该算法的最初开发方法基于麻省理工学院研究动物而产生的基于行为的算法，以及它们如何发展
关于寻找食物的地方。当您查看蚂蚁和
蜜蜂如何散布并搜寻区域时，这些覆盖范围和
确定所有这些都来自该研究。不完全是，
显然，我并不是说我们是蜜蜂，而是对
如何在自然界中进行搜索的理解，这是我们开发自适应技术的基础。
一些带有LED的Roombas的长时间曝光照片说明了其在实践中的工作方式：
评论
$ \ begingroup $
这是链接中的复制粘贴内容吗？
$ \ endgroup $
–乔什·范德·胡克（Josh Vander Hook）
2012年12月5日19:06
$ \ begingroup $
@Josh已从链接的站点复制了回答问题的相关材料，并将其放在blockquote中，以防止链接腐烂。
$ \ endgroup $
–embedded.kyle
2012年12月5日在20:19
#3 楼
Neato使用有组织的方法。使用SLAM和保险杠，它首先映射“当前”房间的周边，然后应用一些算法尽可能有效地进行清洁。我从来没有拥有过Roomba，但是鉴于我对它的算法的了解，我永远都不会从neato切换。neato中的Laser Range Finder通常可以用于机器人技术一个用于SLAM算法的经济高效的传感器。
如果我得到了您的任务，首先，我将根据我拥有的硬件找到合适的SLAM实现。使用CNC ISLAND运动计划算法。我的经验是，它们往往能以最小的移动量非常有效地覆盖任意区域。
评论
$ \ begingroup $
SLAM不适用于此问题，因为它是一种模拟，其中定位没有不确定性。对于真正的机器人，您绝对是正确的。
$ \ endgroup $
–伊恩
2012年12月5日19:25
$ \ begingroup $
我错过了（如果有的话）。实际上，它说以下是未知的；机器人的位置。
$ \ endgroup $
–秒杀3
2012年12月5日19:27
$ \ begingroup $
我以为位置开始时是未知的，但是随着房间拓扑结构的建立，它可能会变得众所周知。
$ \ endgroup $
–詹森·斯珀斯凯（Jason Sperske）
2012年12月5日19:29
$ \ begingroup $
这是一些简单的学术问题，其中，简化产生了奇怪的含义。由于您没有地图，没有起始位置，没有完美的定位，也没有外部实体可以协调，因此绝对位置无关紧要。您可以任意确定（0,0）是您的起点，然后相对于该点构建地图。在现实世界中，这实际上并不实际，但是确实为您提供了一些有关覆盖算法的实践。
$ \ endgroup $
–伊恩
2012年12月5日在19:39
$ \ begingroup $
从系统的角度来看，您的答案是好的。但是，我相信这个问题是一个更好的理论/算法问题。
$ \ endgroup $
–乔什·范德·胡克（Josh Vander Hook）
2012年12月5日在20:07
#4 楼
您需要确定的第一件事是机器人的目标-从您的问题中还不清楚。机器人必须完成两个主要任务：发现可清洁区域的形状，然后对其进行清洁。但是污垢量恒定吗？是否不断添加污垢？您的目标是最大程度地减少平均灰尘停留在地板上的时间或中间时间吗？目标是保持地板同样清洁吗？还是只是尽快清洁一次？您可以测量并利用污垢堆积中的图案来实现目标吗？
这些问题的答案将有助于指导您选择哪种算法。在Roomba机器人的情况下，学习家具的确切布局可能毫无意义，因为家具（如桌子周围的椅子），人和其他障碍物经常移动。但是，根据您的情况，最好探索空间以构建完整的地图（割草机模式与查找边缘的某种组合），然后使用该地图计算通过空间的最短路径（术语为“覆盖范围”，并且有几种方法可以做到这一点，例如生成树算法）。
您还需要担心的另一件事是如何使您所在的空间离散化。因为您可以向任意方向移动-即使使用整数度数和距离的整数单位-您的X和Y位置也可以具有小数值。您需要确定如何在该地图上表示障碍物，而不必使其增长到无限多个数据点。
评论
$ \ begingroup $
好吧，由于我很可悲地使自己难以接受面试，我想我可以提供更多的信息。我喜欢您提出的观点：）
$ \ endgroup $
–詹森·斯珀斯凯（Jason Sperske）
2012年12月5日19:23
#5 楼
我不确定您是否仍然需要它，但是对于那些偶然在google上找到此线程的人，我已经制作了该算法的一个简单版本。基本上，它会尝试构建该地图清洁时，它会使用该区域，并使用地图查找最近的无视节点（房间的一部分）。当找不到任何东西时，意味着房间已经打扫干净（或者机器人无法进入未清理的部分）。
它可能比其他算法慢，但是无论启动什么都可以保证覆盖范围位置，方向和障碍。
https://github.com/dungba88/cleaner_robot
更新：我在这里做了一个演示，并将其与回溯DFS进行了比较。因此，即使我的算法为O（N ^ 2），它在移动和转弯次数方面也进行了优化。 />
评论
$ \ begingroup $
有趣，因此它将房间分成2D网格，我仍在阅读您的代码，您使用哪种路径查找方法来到达未清洁的区域？迪克斯特拉？
$ \ endgroup $
–詹森·斯珀斯凯（Jason Sperske）
17-10-6在16:46
$ \ begingroup $
我使用BFS查找最近的未清洁位置。
$ \ endgroup $
– AnhDũngBùi
17年10月8日在2:30
评论
诸如+ algorithm和+ theory之类的标签将有助于解决此类问题，但我尚无添加它们的名声绝对比Roomba更好的东西
有趣。我有bobsweep，它的编程非常完美momblogsociety.com/meet-newest-addition-family-bobsweep，我建议所有人使用。问候！
这是广告吗？如果不是，您可能需要发布信息，而不仅仅是链接，以说明机器人的行为方式以及为什么它非常完美。