在电动汽车充电、智能配电网和自主仓库等领域，多个智能体共享相同的资源。在规划这些资源的使用时，智能体需要处理这些领域的不确定性。尽管文献中提出了几种模型和算法，用于解决不确定条件下的这种受限多智能体规划问题，但仍不清楚何时可以应用哪种算法。在这项调查中，我们将这些领域概念化，并建立了一个基于马尔科夫决策过程的通用问题类别。我们确定并比较了该类问题的规划文献中的算法可以应用的条件：约束是软的还是硬的，智能体是否连续连接，领域是否完全可观察，约束是瞬间的（瞬时的）还是预算的，以及约束是对单一资源还是对多种资源。此外，我们还讨论了这些算法的优点和缺点。最后，我们确定了与概念化领域直接相关的开放问题，以及相邻研究领域的问题。
最近，人工智能（AI）作为一个家喻户晓的术语出现，一些列重要成果影响着人们的生活，如数字个人助理（Hoy，2018）、媒体推荐系统（Möller等人，2018）以及能够超越人类专家的游戏AI（Silver等人，2018）等知名例子。然而，这些例子的共同点是它们与用户一对一地互动。预计，人工智能系统将很快导致更多的多智能体系统，其中多个智能体在做决策时进行互动。在这样的系统中，由于共享资源的存在，智能体可能会遇到限制，限制了其潜在决策。
带有资源约束的多智能体系统在当今社会的很多领域出现。例如，在自主仓库中，有多个机器人收集物品进行运送，这些机器人受到诸如时间限制、地点和他们使用的设施的制约（Claes等人，2017）。另一个例子可以在配电网中找到，其中聚合器控制多个自主电动车的充电，这些电动车不允许违反配电网约束（De Weerdt等人，2018）。带有约束条件的多智能体决策也发生在在线广告中，为了使转换率最大化，应将有限的广告预算分配给在线用户（Boutilier & Lu, 2016）。最后，机场的监控任务需要在考虑多个自主对手的情况下，用有限的安保人员来完成（Pita等人，2008）。除了存在i）或多或少独立的智能体和ii）资源限制，iii）不确定性的来源，在做决策时需要考虑这些决定可能会相互影响的顺序，以及iv）有机会提前协调。这四个特性确定了本文所讨论的问题类型。
马尔科夫决策过程（MDPs）为具有不确定性的决策问题提供了一个经过充分研究的框架（Puterman, 1994; Boutilier, 1996）。多年来，人们提出了许多扩展方案，通过对最优策略的额外约束来增强该框架。Altman(1999)全面概述了受限马尔科夫决策过程的特性。在本文中，我们调查了建立在这些模型基础上的工作，这些工作从多智能体的角度出发，强调了智能体之间关于资源的协调方面。此外，我们还定义了在任何情况下必须绝对成立的约束条件。这些不同约束条件的定义大多被孤立地研究，这使得我们不清楚文献中提出的算法如何相互比较，以及在什么情况下它们可以用于解决规划问题。
在这项调查中，我们旨在建立对可被建模为受限多智能体马尔科夫决策过程的问题以及文献中提出的相关算法的一般理解。第一个目的是进一步了解哪种（类型的）算法对哪种类型的领域最有效。此外，该综述使我们能够确定该领域未开发的领域以及在未来研究中可以追求的有前途的研究方向。
本文贡献
首先，提出了一个基于马尔科夫决策过程受限多智能体规划问题的一般概念化。这一概念化描述了在具有共享约束的环境中进行规划时需要考虑的资源和规划领域的所有方面。这应用了分类法，文献中开发的所有相关技术都可以放在其中。
其次，我们对规划文献中出现的解决方案算法进行了广泛的概述，并确定和比较了这些算法可以应用的条件。我们进一步讨论了这些算法的优点和缺点。
第三，我们确定了开放的研究方向，可以在未来推进该研究领域的发展。这一讨论确定了目前存在的开放问题，以及与之密切相关的研究领域。这些领域与本调查所涉及的研究领域有很强的联系，而且这两个领域在未来可能会相互加强。
从更普遍的角度来看，我们的调查还旨在为该领域的新研究人员提供一个全面的概述，这样他们就能迅速掌握文献中的主要概念和解决方案。这使他们能够了解受限规划领域目前的情况，并确保他们能够迅速确定开放的问题和研究方向，以便开展工作。
提纲
本调查的结构如下。在第2节中，我们从涉及多个智能体、不确定性和约束的激励性应用领域开始，分析了这些领域的属性，并介绍了一般的潜在解决方法，使智能体能够根据资源的可用性非正式地协调其行动。在第3节中，我们介绍了捕捉所确定的领域属性的正式模型。潜在的解决方法为第4节提供了起点，在这一节中，我们描述了几种算法，可以用来计算或实现有资源约束的多智能体系统的解决方案。在第5节中，我们描述了相关的问题和算法，这些问题和算法不在本调查的重点范围内。在第6节中，我们描述了开放的研究方向和关于受限规划的一般领域的重要观察。最后，我们在第7节中对调查进行了总结和归纳。
原文
相关内容
微信扫码咨询专知VIP会员