清洁和油漆的智能代理
我记得当我上大学时，我们遇到了一些问题，其中有一个智能代理位于方格网格上，它必须清理方格。它因清洁而获得积分。还因搬家被扣分。它必须时不时地补充能量，最后它根据网格上有多少格子是脏的或干净的得到最终分数。
我正在尝试研究这个问题，因为当我在大学看到它时它非常有趣，但是我在维基百科或在线任何地方都找不到任何内容。您知道该问题有具体名称吗？或者这只是我的老师在课堂上想出的东西。
我正在寻找人工智能清洁剂和类似的东西，但我没有找到任何东西。我不知道，我想也许它还有别的名字。
I remember when I was in college we went over some problem where there was a smart agent that was on a grid of squares and it had to clean the squares. It was awarded points for cleaning. It also was deducted points for moving. It had to refuel every now and then and at the end it got a final score based on how many squares on the grid were dirty or clean.
I'm trying to study that problem since it was very interesting when I saw it in college, however I cannot find anything on wikipedia or anywhere online. Is there a specific name for that problem that you know about? Or maybe it was just something my teacher came up with for the class.
I'm searching for AI cleaning agent and similar things, but I don't find anything. I don't know, I'm thinking maybe it has some other name.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
也许“耻辱”方法与您的问题密切相关。 这里有一个起点，您可以通过搜索“dead”找到一些东西Google 学术。
基本上：您不是对精确的策略进行建模，而是采用概率方法。蚂蚁（可能）会根据一个简单的规则堆积来收集尸体，例如“如果那里有一堆死蚂蚁，我就把这具尸体带到这里；否则，我会再堆一堆”。您可以从简化您的“清洁”情况开始，然后看看您会做什么。
另外，我认为（另一种？）合适的方法可以使用精心选择的适应度函数组合，通过遗传算法进行建模，例如：
当然，如果机器人“因饥饿而死亡，它会自动从基因库中删除自己，这是达尔文奖:)
您可以从建模一个非常非常简单的基因型开始，该基因型将被“计算”成一种行为。考虑使用简单的 GA，例如 Inman 的这个哈维，然后为每个基因分配策略的一部分或完整的行为。例如：如果基因A变为1，则机器人将尝试随机徘徊；如果B基因也变成1，那么就会优先自充电，除非距离X处有脏瓷砖。或者使用浮点数和模型概率。您的里程可能会有所不同，但我可以保证这会很有趣:)
Perhaps a "stigmergy" approach is closely related to your problem. There is a starting point here, and you can find something by searching for "dead ants" and "robots" on google scholar.
Basically: instead of modelling a precise strategy you work toward a probabilistic approach. Ants (probably) collect their deads by piling up according to a simple rule such as "if there is a pile of dead ants there, I bring this corpse hither; otherwise, I'll make a new pile". You can start by simplifying your 'cleaning' situation with that, and see where you go.
Also, I think (another?) suitable approach could be modelled with a Genetic Algorithm using a carefully chosen combination of fitness functions such as:
of course if the robots 'dies' out of starvation it automatically removes itself from the gene pool, a-la darwin awards :)
You could start by modelling a very, very simple genotype that will be 'computed' into a behaviour. Consider using a simple GA such as this one by Inman Harvey, then to each gene assign either a part of the strategy, or a complete behaviour. E.g.: if gene A is turned to 1 then the robot will try to wander randomly; if gene B is also turned to 1, then it will give priority to self-charging unless there are dirty tiles at distance X. Or use floats and model probability. Your mileage may vary but I can assure it will be fun :)
这个问题让人想起Shakey，尽管涉及到清洁（就像Roomba - 也可以通过编程来执行这些任务的设备）。
如果“问题空间”（或房间）足够小，您可以使用简单的基于 A* 的搜索来求解最佳解决方案，但很可能不会，因为这不会留下非常有趣的问题。
这里建议的使用遗传算法的机器学习方法是一种有趣的方法。给定问题域，您将只有一个“规则”（一个
move-to操作，因为clean可以通过隐式清除您移动到的任何脏方块来消除）所以你的学习者本质上是在学习如何在环境中移动。问题在于建立一个能够适应任何给定平面图的学习器，而不是仅仅精通清洁一个非常特定的空间。无论您采用哪种方法，如果问题集足够大，我还会考虑进行进一步的元推理步骤，并使用分区方法将地板划分为不同的区域，然后一次解决一个问题。
你能用技术来创建数据以供“离线”使用吗？在这种情况下，我什至会考虑创建一个最佳路线的“数据库”，用于清洁某些地板空间（1x1 到 5x5），其中包括所有可能的起始和结束方块。这类似于“残局数据库”，一旦游戏达到一定深度，游戏 AI 就会使用它来有效地“解决”游戏（参见 奇努克）。
The problem is reminiscent of Shakey, although there's cleaning involved (which is like the Roomba -- a device that can also be programmed to perform these very tasks).
If the "problem space" (or room) is small enough, you can solve for an optimal solution using a simple A*-based search, but likely it won't be, since that won't leave for very interesting problems.
The machine learning approach suggested here using genetic algorithms is an interesting approach. Given the problem domain you would only have one "rule" (a
move-toaction, sincecleancould be eliminated by implicitly cleaning any square you move to that is dirty) so your learner would essentially be learning how to move around an environment. The problem there would be to build a learner that would be adaptable to any given floor plan, instead of just becoming proficient at cleaning a very specific space.Whatever approach you have, I'd also consider doing a further meta-reasoning step if the problem sets are big enough, and use a partition approach to divide the floor up into separate areas and then conquering them one at a time.
Can you use techniques to create data to use "offline"? In that case, I'd even consider creating a "database" of optimal routes to take to clean certain floor spaces (1x1 up to, say, 5x5) that include all possible start and end squares. This is similar to "endgame databases" that game AIs use to effectively "solve" games once they reach a certain depth (c.f. Chinook).
这个问题让我想起这个。 复杂性一书中简要提到了类似的问题，作为遗传的例子算法。这些版本虽然经过简化，但没有考虑燃油消耗。
This problem reminds me of this. A similar problem is briefly mentioned in the book Complexity as an example of a genetic algorithm. These versions are simplified though, they don't take into account fuel consumption.