「研究人工智能三十五年来的主要经验是,解决难题很容易,但解决简单的问题很难。」——Pinker (1994),《The Language Instinct》
我认为编程软件智能体收集图表上的宝藏将是一件小事。我完全错了。编程出的智能体不会愚蠢地行动本质上是非常困难的一件事。
一个明确定义的多智能体设置
「智能体是指任何可以通过传感器感知环境并通过效应器在环境中作用的东西。」《Artificial Intelligence: A Modern Approach》 Stuart Russell、Peter Norvig
使用 GraphStream Library (http://graphstream-project.org/) 模拟多智能体系统收集宝藏。
这是一个简单的多智能体问题。让 n 个智能体在完全连接的图形上移动来收集宝藏。智能体的行动,感知和沟通受到限制。它们只能观察并移动到与它们直接相连的节点,只能与足够密切的智能体进行通信。
有三种智能体:探险者,收藏者和无限背包智能体。探险者注定要探索地图,因为它们不允许挑选宝藏。收藏者是可以挑选的,但它们不能携带太多,并且必须将它们收集的宝藏分发给无限背包智能体。
智能体的感知有限但可以记住过去的观察结果。每个智能体都有自己的世界表现形式,自己的图表,这是真实图表的子图。它们的子图是访问过的所有节点的记忆,以及它们曾经见过或捕获的边。它们必须将此图传达给其他智能体,以便它们都可以共享来自所有子图的重建。
JADE (http://jade.tilab.com/)(Java Agent DEvelopement Framework)将用于实现所谓的「行为」(教程可以在这里 (http://jade.tilab.com/doc/tutorials/JADEProgramming-Tutorial-for-beginners.pdf),或这里 (https://gitlab.com/herpsonc/startJade) 找到)。在这个多智能体系统 (https://www.cs.cmu.edu/~softagents/multi.html) 框架中,行为是智能体将要执行的一组指令。在每一次转换中,每个智能体都按顺序执行每个行为。
你的目标:实现智能体的行为,让它们在一定时间内收集尽可能多的宝藏。
看起来很简单,对吗?
(注意:该项目是多智能体系统介绍 (http://androide.lip6.fr/?q=node/21) 的一部分(来自 ANDROIDE 的一门课程,我现在正在 UPMC 读的 AI 硕士学位)。它的灵感来自于生存恐怖游戏 Hunt The Wumpus (https://en.wikipedia.org/wiki/Hunt_the_Wumpus),在该项目的完整版本中,智能体需要处理一个四处游荡的可怕的 Wumpus)。
重要的行为
想象两个智能体在长走廊中朝相反方向移动。图的每个节点只能有一个智能体,所以它们必须协调行为以避免阻碍各自的行动。为了考虑这种情况,我们必须实施一个特定的协议。
模拟中智能体的冲突:MyExplorerAgent2 正在阻止其他两个智能体
协调
智能体的感知有限,并且有不同的能力。因此,合作是必不可少的。发生冲突时,必须应用解除该情况的协议。它们必须分享它们的子图,看看谁更接近高度连接的节点,并同意谁来移动。
探险者智能体必须同意谁来探索未知图形的哪个部分,以优化它们的移动并防止冲突。
信息交换
在多智能体设置中交换信息以便让每个智能体访问全局知识的过程称为战报交流问题 (https://www.sciencedirect.com/science/article/pii/0012365X73901210)。
例如,假设集合 {1,2,......,n} 中的每个智能体都知道一个信息,称为一个秘密。然后,一个非常简单的协议是让智能体 1 呼叫 2,3,......,n 并了解它们的秘密。然后,当 1 知道所有的秘密时,它会呼叫给 2,......,n 来告诉它们这些秘密,然后每个智能体都知道所有的秘密了。总共有 n-1+n-1=2n-2 个呼叫。实际上,最佳解决方案 (https://arxiv.org/abs/1511.00867) 需要 2n-4 个呼叫,这与我们的简单算法非常接近。
然而,在我们的问题中,直到所有节点都被探索之前,总的信息并不完全知道,这使得算法稍微复杂一些,因为总的知识是动态的(智能体探索的图表越多,它们的知识总数越多)。
这就是应用优化折中的地方。为了让所有智能体知道所有秘密,n 个智能体之间必须交换的消息最佳数量是多少?更多的信息意味着更好的全局知识和更好的协调。然而,由于有数千个智能体和数百万个节点,每毫秒发送数千条消息的成本远不能忽略,并且成为一个计算负担。
异步通信
智能体之间的通信是异步的。由于智能体的执行是分布式 (https://en.wikipedia.org/wiki/Distributed_computing) 的,所以没有全局时钟来同步智能体的动作。此外,在交换信息时,每个智能体都有一个邮箱,其中包含来自其他智能体的邮件,所以通信可能会延迟。在此延迟期间,一个智能体可能会移动很远,并且永远不会回复原始信息。
联盟形成
联盟形成的例子:source (https://www.slideshare.net/SurSamtani/coalition-formation-and-price-of-anarchy-in-cournot-oligopolies)
某些目标不能单独实现(比如抬起重物)。因此,智能体可能会同意组成一组智能体,称为联盟,来实现共同目标。
至少有三个具有三种不同必要技能(探索,收集和积累)的智能体的联盟必须组成。因此,创建和更新联盟的协议必须实施。一种可能性是使用 Shapley 值 (https://www.degruyter.com/view/books/9781400881970/9781400881970-018/9781400881970-018.xml)(由智能体联盟创造的剩余额)来确定哪些联盟是最有价值的。
即使是一个简单问题的设置,有几个障碍出现得非常快,算法的复杂性似乎是无法克服的。当尝试构建以人类方式表现的 AI 算法时,这是一个反复出现的现象。
让 AI 表现简单的行为是困难的
「在智力测试或玩棋盘游戏时,让计算机表现出成人水平是相对容易的,而在感知和移动性方面,难以或不可能传授给它们一岁孩子的技能。」Moravec(1988)Mind Mind
如果我们用人类替代智能体,我相信他们很快就会明白如何在这个游戏中取胜,他们会传达他们在图表中所看到的信息,并形成联盟来收集最多的宝藏。然而,对智能代理实施严格的行为规则却是非常困难的。
这是 Moravec 的悖论 (https://en.wikipedia.org/wiki/Moravec%27s_paradox#):
对人类来说容易的事对机器来说会是难以置信的困难。
说到下象棋,AI 表现出了超人类的水平。但是对于基本的人类行为,例如行走或协调行动来探索地图,人工智能算法却出奇地更难。
国际象棋大师 Garry Kasparov 在 Deep Thinking (https://www.amazon.com/Deep-Thinking-Machine-Intelligence-Creativity/dp/161039786X) 中发表以下声明:任何足够先进的算法都不难在同时进行的比赛中击败 20 名顶级棋手。但是没有 AI(在机器人中)可以在拥挤的酒吧中四处走动和自行移动棋子。
来源:DARPA robots falling down (https://www.youtube.com/watch?v=adFd0f7K46w)
机器学习在非常特殊的情况下工作
但是为什么我们不使用最新的机器学习(ML)算法来解决我们的问题?......ML-only* *算法只能被用于特定的任务。
是的,强化学习(RL)算法非常流行,可以解决惊人的难题,例如在 Atari 游戏 (https://storage.googleapis.com/deepmind-media/dqn/DQNNaturePaper.pdf) 或在围棋中 (https://deepmind.com/blog/alphago-zero-learning-scratch/) 展现出超人类的水平。但是这些游戏都是具有小数据输入的全可视性游戏,这与我们的寻宝问题并不相同,因为地图在开始时并不完全可见。
但是,OpenAI 不是在一个多智能体系统上,用机器学习算法在 Dota 2 5 vs 5 中战胜了人类吗?
是的,当在 Dota 2 1 vs 1 中战胜世界冠军时,OpenAI 展现了令人印象深刻的结果。但是这主要是因为它们巨大的计算能力,并不是人工智能的突破 (https://www.quora.com/How-did-OpenAI-create-the-Dota-2-game-bot-that-beats-professionals)。
它们的目标是在 5 vs 5 中获胜,用一个 580 万场比赛的数据集 (https://blog.openai.com/more-on-dota-2/)。所以,它们似乎正在使用全机器学习方法(从人类游戏中学习)研究多智能体问题,并且似乎缺少多智能体系统的自顶向下 (http://www.alanturing.net/turing_archive/pages/reference%20articles/what_is_AI/What%20is%20AI09.html) 方法。
智能体不会推断和概括。纯机器学习可以用于单个智能体或完全可观察的系统,但是多智能体系统不是一个完全已知的世界,必须采用一个更普遍的方法。
我们不知道如何实现可伸缩行为
只有两个智能体在走廊上朝相反方向走,我们遇到了一个问题。实施协议来处理这一特定问题是可能的。
但是在有 400 个节点的地图上的 100 个代理呢?
少数智能体的硬编码功能与多智能体系统的可扩展和可普遍实现之间存在差距。
需要做什么
经过研究,必须开发特定的多智能体协议来解决这类问题。没有先验知识的学习 (https://deepmind.com/blog/alphago-zero-learning-scratch/) 不会教授智能体如何沟通,因为搜索空间太大。纯数据驱动的方法不会导致任何结果。
结论
实现一个能够解决寻宝问题的算法比看起来要困难得多。构思能够解决简单问题的多智能体系统绝非易事。机器学习算法在过去的十年中取得了巨大的成果,但仅凭机器学习无法解决所有的人工智能问题。
联系客服