清洁和油漆的智能代理

Question

我记得当我上大学时，我们遇到了一些问题，其中有一个智能代理位于方格网格上，它必须清理方格。它因清洁而获得积分。还因搬家被扣分。它必须时不时地加油，最后它根据网格上有多少格子是脏的或干净的得到最终分数。

我正在尝试研究这个问题，因为当我在大学看到它时它非常有趣，但是我在维基百科或在线任何地方都找不到任何内容。您知道该问题有具体名称吗？或者也许这只是我的老师在课堂上想出的东西。

我正在寻找AI清洁剂和类似的东西，但我没有找到任何东西。我不知道，我想也许它还有其他名字。

Answer 1

也许“污名化”的做法与你的问题密切相关。有一个起点这里，你可以通过在谷歌学者上搜索“死蚂蚁”和“机器人”来找到一些东西。

基本上：您不是对精确的策略进行建模，而是采用概率方法。蚂蚁（可能）会根据一个简单的规则堆积来收集尸体，例如“如果那里有一堆死蚂蚁，我就把这具尸体带到这里；否则，我会再堆一堆”。您可以从简化您的“清洁”情况开始，然后看看您会做什么。

此外，我认为（另一种？）合适的方法可以使用精心选择的适应度函数组合通过遗传算法进行建模，例如：

• “干净”瓷砖的结束数量
• 机器人行走的步数

当然，如果机器人因饥饿“死亡”，它会自动将自己从基因库中删除，这是达尔文奖:)

您可以从建模一个非常非常简单的基因型开始，它将被“计算”成一种行为。考虑使用简单的 GA，例如 Inman Harvey 的“this one”，然后为每个基因分配策略的一部分或完整的行为。例如：如果基因A变为1，则机器人将尝试随机徘徊；如果基因B也变成1，那么就会优先自充电，除非距离X处有脏瓷砖。或者使用浮点数和模型概率。您的里程可能会有所不同，但我可以保证这会很有趣:)

Answer 2

Shakey

，尽管涉及到清洁（就像Roomba——一种也可以通过编程来执行这些任务的设备）。 如果“问题空间”（或房间）足够小，您可以使用简单的基于 A* 的搜索来求解最佳解决方案，但很可能不会，因为这不会留下非常有趣的问题。

这里建议的使用遗传算法的机器学习方法是一种有趣的方法。给定问题域，你只会有一个“规则”（一个

move-to

动作，因为

clean

可以通过隐式清理你移动到的任何脏方块来消除），所以你的学习者本质上是在学习如何在一个环境。问题在于建立一个能够适应任何给定平面图的学习器，而不是仅仅精通清洁一个非常特定的空间。无论你采用什么方法，如果问题集足够大，我也会考虑进行进一步的元推理步骤，并使用分区方法将地板划分为不同的区域，然后一次征服它们。

你能用技术来创建数据以供“离线”使用吗？在这种情况下，我什至会考虑创建一个最佳路线的“数据库”，用于清洁某些地板空间（1x1 到 5x5），其中包括所有可能的起始和结束方块。这类似于“游戏终局数据库”，一旦游戏达到一定深度，游戏 AI 就会使用它来有效地“解决”游戏（参见

Chinook

）。

Answer 3

这个

。 《复杂性》一书中简要提到了类似的问题，作为遗传算法的示例。这些版本虽然经过简化，但没有考虑燃油消耗。