多智能体强化学习综述阅读笔记

本文是探索多智能体强化学习领域的一些论文的翻译和总结，更多会偏向开源的代码，便于实现，另外根据我的方向，对于论文的选择会具有一定的倾向，一些方面可能介绍的不是很完全。对于一些测试和基准的介绍可能也不会很多

文章共7,847字 · 阅读需要大约27分钟

一键AI生成摘要，助你高效阅读

问答

CBLXXX

1444人浏览 · 2023-10-14 17:41:02

CBLXXX · 2023-10-14 17:41:02 发布

多智能体强化学习

1 本文的目的

本文是探索多智能体强化学习领域的一些论文的翻译和总结，更多会偏向开源的代码，便于实现，另外根据我的方向，对于论文的选择会具有一定的倾向，一些方面可能介绍的不是很完全。对于一些测试和基准的介绍可能也不会很多，此外，由于懒得打latex大多数公式是直接复制或截图的。本文目前可能还不是很完善，如果有建议和修改可以私聊我。

2 简介

多代理强化学习（MARL）算法处理的是由多个智能体（agent）组成的系统，这些代理与共同的环境相互作用。每个代理都会在每个时间步做出决策，并与其他代理一起实现各自的预定目标。MARL算法的目标是为每个代理学习一种策略，使所有代理共同实现系统的目标。特别是，代理是可学习的单元，其目标是通过与环境的交互，即时学习最优策略，以最大化长期累计贴现回报。由于环境的复杂性或问题的组合性，训练代理通常是一项具有挑战性的任务，MARL 所处理的几个问题被归类为 NP-Hard 问题

深度强化学习（RL）在很多方面方面取得了成功，包含围棋、象棋、路径规划、游戏等领域。解决这些问题的一种简单方法是将问题转换成单智能体理问题。然而，在这种方法中，行动的数量通常会呈指数级增长，从而使问题变得难以解决。因为在多能体博弈中想要达到纳什均衡是很困难

在多代理系统建模中，系统有几个重要的特性

集中控制OR分散控制
完全可观察环境OR部分可观察环境
合作环境OR竞争环境

注：

Markov Decision Process (MDP) :

下面的描述均摘自维基百科，简单理解。就是投掷一枚硬币，S为硬币可能的状态：正+反+直立，A是投掷硬币的动作：砸、扔、甩等等，P是硬币在你采取某种动作后，硬币变为正的概率，Ra是投掷硬币后你是否投掷到想要的面，从而获得的奖励。

动态规划：

简单概括：走一步看一步

可以参考下面的链接继续深入学习

动态规划在LLM领域的应用

动态规划需要考虑的问题：

Optimal substructure: 子问题的最优解可用来解决整体问题
Overlapping sub-problems: 子问题重复出现多次。子问题的解决方案可以存储和重复使用

比如上图，如果需要达到累加最优值，存在一条路径可以达到最优值

NP困难（NP-hardness, non-deterministic polynomial-time hardness）问题是计算复杂性理论中最重要的复杂性类之一。如果所有NP问题都可以多项式时间归约到某个问题，则称该问题为NP困难。

因为NP困难问题未必可以在多项式时间内验证一个解的正确性（即不一定是NP问题），因此即使NP完全问题有多项式时间的解P=NP，NP困难问题依然可能没有多项式时间的解。因此NP困难问题“至少与NP完全问题一样难”。（摘自维基百科）

来自stackoverflow.com的解释

P

P is a complexity class that represents the set of all decision problems that can be solved in polynomial time.

That is, given an instance of the problem, the answer yes or no can be decided in polynomial time.

Example

Given a connected graph G, can its vertices be coloured using two colours so that no edge is monochromatic?

Algorithm: start with an arbitrary vertex, color it red and all of its neighbours blue and continue. Stop when you run out of vertices or you are forced to make an edge have both of its endpoints be the same color.

NP

NP is a complexity class that represents the set of all decision problems for which the instances where the answer is “yes” have proofs that can be verified in polynomial time.

This means that if someone gives us an instance of the problem and a certificate (sometimes called a witness) to the answer being yes, we can check that it is correct in polynomial time.

Example

Integer factorisation is in NP. This is the problem that given integers n and m, is there an integer f with 1 < f < m, such that f divides n (f is a small factor of n)?

This is a decision problem because the answers are yes or no. If someone hands us an instance of the problem (so they hand us integers n and m) and an integer f with 1 < f < m, and claim that f is a factor of n (the certificate), we can check the answer in polynomial time by performing the division n / f.

NP-Complete

NP-Complete is a complexity class which represents the set of all problems X in NP for which it is possible to reduce any other NP problem Y to X in polynomial time.

Intuitively this means that we can solve Y quickly if we know how to solve X quickly. Precisely, Y is reducible to X, if there is a polynomial time algorithm f to transform instances y of Y to instances x = f(y) of X in polynomial time, with the property that the answer to y is yes, if and only if the answer to f(y) is yes.

Example

3-SAT. This is the problem wherein we are given a conjunction (ANDs) of 3-clause disjunctions (ORs), statements of the form
```
(x_v11 OR x_v21 OR x_v31) AND 
(x_v12 OR x_v22 OR x_v32) AND 
...                       AND 
(x_v1n OR x_v2n OR x_v3n)
```
where each x_vij is a boolean variable or the negation of a variable from a finite predefined list (x_1, x_2, ... x_n).

It can be shown that every NP problem can be reduced to 3-SAT. The proof of this is technical and requires use of the technical definition of NP (based on non-deterministic Turing machines). This is known as Cook’s theorem.

What makes NP-complete problems important is that if a deterministic polynomial time algorithm can be found to solve one of them, every NP problem is solvable in polynomial time (one problem to rule them all).

NP-hard

Intuitively, these are the problems that are at least as hard as the NP-complete problems. Note that NP-hard problems do not have to be in NP, and they do not have to be decision problems.

The precise definition here is that a problem X is NP-hard, if there is an NP-complete problem Y, such that Y is reducible to X in polynomial time.

But since any NP-complete problem can be reduced to any other NP-complete problem in polynomial time, all NP-complete problems can be reduced to any NP-hard problem in polynomial time. Then, if there is a solution to one NP-hard problem in polynomial time, there is a solution to all NP problems in polynomial time.

Example

The halting problem is an NP-hard problem. This is the problem that given a program P and input I, will it halt? This is a decision problem but it is not in NP. It is clear that any NP-complete problem can be reduced to this one. As another example, any NP-complete problem is NP-hard.

My favorite NP-complete problem is the Minesweeper problem.

P = NP

This one is the most famous problem in computer science, and one of the most important outstanding questions in the mathematical sciences. In fact, the Clay Institute is offering one million dollars for a solution to the problem (Stephen Cook’s writeup on the Clay website is quite good).

It’s clear that P is a subset of NP. The open question is whether or not NP problems have deterministic polynomial time solutions. It is largely believed that they do not. Here is an outstanding recent article on the latest (and the importance) of the P = NP problem: The Status of the P versus NP problem.

The best book on the subject is Computers and Intractability by Garey and Johnson.
纳什均衡（英语：Nash equilibrium，或称纳什均衡点）是指在包含两个或以上参与者的非合作博弈（Non-cooperative game）中，假设每个参与者都知道其他参与者的均衡策略的情况下，没有参与者可以透过改变自身策略使自身受益时的一个概念解。

3 单智能体强化学习

注：由于篇幅有限制，具体的详细细节和内容建议去参考文献的CS234课件里去看

RL 考虑的是一个代理与环境交互的连续决策问题。代理在时间段 t 观察状态 st∈ S（其中 S 是状态空间），采取行动 at∈ A(st)（其中 A(st) 是状态 st 的有效行动空间），并在环境中执行该行动以获得奖励 r(st,at,st+1)∈R，然后转移到新状态 st+1∈ S。马尔可夫决策过程（Markov Decision Process，MDP）为描述和研究这个问题提供了一个框架，在这个框架中，代理对状态具有完全可观测性。

马尔可夫决策过程示意图：

MDP的目的：获得一个策略，能够从状态S，映射到A：

根据下面的公式获得一个较好的长期奖励（公式里面的参数不多介绍，需要的可以参看贝尔曼方程的推导）：

其中gama是折现因子，代表了未来的奖励换算到当下的折扣比

以 V π (s) 表示的从状态 s 开始并遵循策略 π 的价值函数由以下公式给出

如果给定行动a，Q值可以通过如下公式获得

给定已知的状态转换概率分布 p(st+1|st, at) 和奖励矩阵 r(st, at)、下式对任何时间 t 的所有状态 st 都成立，包括最优值也是如此

其中，s′表示 st 的后继状态。通过对行动的最大化，可以得到最优状态值和最优策略

同样的最优Q值也可以得到

通过直接学习 Qπ∗（st，at），可以得到最优策略 π∗。相关方法称为value-based 的方法。然而在现实世界中，通常无法获得环境知识，即 p(s′|st，at)，因此无法使用公式获得最优策略。为了解决这个问题，通常的做法是通过采样来学习状态值或 Q 值。这种近似方法只需要从与环境的交互中获得状态、行动和奖励的样本。在早期的方法中，每个状态/状态-行动的值都存储在一个表中，并通过迭代的方式进行更新。值迭代和策略迭代是这类方法中两个著名的算法，可以达到最优策略。然而，由于维数诅咒，这些方法对于状态/行动空间巨大的任务来说并不实用。这个问题可以通过函数逼近来解决。参数 θ 的函数近似器会产生策略πθ (a|s)。带有参数θ 的函数近似器可以是简单的线性回归模型，也可以是深度神经网络。给定函数近似值后，RL 算法的目标可以改写为最大化效用函数

其中，期望值取自行动和状态占用的分布

在另一类称为基于策略的方法中，策略是直接学习的，它决定了在给定状态下选择行动的概率。无论是哪种方法，其目标都是通过抽样学习找到参数θ，从而最大化效用函数 J (θ)。我将在后面分别简要介绍基于价值和基于策略的方法。需要注意的是，关于单机 RL 算法的文献很多，只回顾使用较多的算法。

对于上述所有符号和描述，我们都假定环境是完全可观测的。但是，在智能体只访问部分状态的情况下，可以将其归类为具有部分可观测性的决策问题。这种情况在很多多代理系统中都会出现，本文将对此进行讨论。

注：

贝尔曼方程的简单理解

维数灾难

3.1 Value approximation

在值逼近中，目标是学习一个函数来估计 V (s) 或 Q(s,a),这里将以比较经典的有DQN算法，由于资料较多，就不班门弄斧了

注：

参考的一些资料：

https://github.com/Curt-Park/rainbow-is-all-you-need（最核心的）

https://mofanpy.com/tutorials/machine-learning/reinforcement-learning/intro-DQN

https://pytorch.org/tutorials/intermediate/reinforcement_q_learning.html

DM-DQN: Dueling Munchausen deep Q network for robot path planning（论文阅读笔记待续）_CBLXXX的博客-CSDN博客

https://wanjun0511.github.io/2017/11/05/DQN/

3.2 Policy approximation

在基于价值的方法中，关键在于学习最优价值函数或 Q 函数，并由此获得贪婪策略。换句话说，我们可以将策略参数化，建立一个函数，并尝试通过监督学习过程优化该函数与政策参数之间的关系。这一类 RL 算法被称为基于策略的方法，它提供了行动的概率分布。资料也较多，下面放上我学习时候的一些参考资料，由于我需要的动作离散就可以之前也用的DQN算法，这里将不作为重点来处理。仅仅介绍Actor-critic

Actor-Critic 类方法。具体来说，两个网络，一个负责生成策略的 Actor 和一个负责评价策略的 Critic。Actor负责在舞台上表演，critic负责在台下评论，两者一起进步。

The “Critic” estimates the value function. This could be the action-value (the Q value) or state-value (the V value).
The “Actor” updates the policy distribution in the direction suggested by the Critic (such as with policy gradients)

而且Critic 和 Actor 函数都是通过神经网络进行参数化的。

下面是AC算法的伪代码（摘自paddleEdu）

注：

参考的一些资料：

https://towardsdatascience.com/reinforcement-learning-policy-approximation-f5606ad3d909

https://web.stanford.edu/class/cme241/lecture_slides/PolicyGradient.pdf

https://blog.csdn.net/qq_30615903/article/details/80774384

https://towardsdatascience.com/understanding-actor-critic-methods-931b97b6df3f

https://proceedings.neurips.cc/paper_files/paper/1999/file/6449f44a102fde848669bdd9eb6b76fa-Paper.pdf、

easy-rl/notebooks/A2C.ipynb at master · datawhalechina/easy-rl (github.com)

深度强化学习 – Actor-Critic 类算法（基础篇） - 知乎 (zhihu.com)

https://chrispiech.github.io/probabilityForComputerScientists/en/part1/log_probabilities/

https://paddlepedia.readthedocs.io/en/latest/tutorials/reinforcement_learning/Actor-Critic.html

4 多智能体强化学习

本段将是最近文献调研的重点方向，更多的偏向于开源 and 离散动作空间，近期的论文，表现效果较好的，因此不可能过于全面，请谅解

首先用元组 < N, S, A, R,P, O, γ > 表示多代理环境，其中 N 是代理数量，S 是状态空间，A = {A1, . , AN} 是所有代理的行动集，P 是状态间的转换概率，Ris 是奖励函数，O = {O1, . , ON} 是所有代理的观察空间集合。

与单个代理的情况类似，每个代理都能学习最优 Q 值或最优随机策略。然而，由于每个代理的策略会随着训练的进行而改变，因此从任何单个代理的角度来看，环境都是非稳态的。

当任何 πi ∕= πi′ 时，将不符合 MDP 的基本假设（状态转移概率仅依赖于当前状态和动作，而与历史状态无关）。这意味着每个智能体的经验涉及不同的共同玩家策略，因此我们不能固定这些策略并训练一个代理，以至于任何试图训练这种模型的尝试都会导致训练的难以收敛和不稳定。

另一方面，每个代理的策略在训练过程中都会发生变化，也就会导致一些技巧，比如经验回放无法运用。同时由于噪声和方差的加大，训练会不稳定，也会导致policy gradient algorithm 的失效

A multi-agent reinforcement learning example in a cyber way

5 分类

首先，一个很简单的将单智能体拓展为多智能体的方式，即将每个智能体视为独立的学习者，将其他智能体的行动视为环境的一部分。这种方法被称为独立Q学习（IQL）。然而，IQL面临的最大挑战是非稳态性，因为其他智能体的行动会影响环境转移。因此，IQL需要解决非稳态性问题。

为了处理非稳态的问题，一种方法是假设所有评论家都观察到所有智能体的全局状态和动作，这被称为完全可观测的评论家模型。在这种情况下，评论家模型学习真实的状态值，并且当与演员配对时，可以用于找到最优策略。当奖励在所有智能体之间共享时，只需要一个评论家模型；但是，在私有本地奖励的情况下，每个智能体都需要为自己训练一个本地评论家模型。该段落还提到了这种方法的算法的示意图，如图所示，其中评论家网络观察其他智能体的所有观察结果。

考虑多代理问题的设置，其中代理的目标是最大化单个联合奖励，或者假设有可能将多代理问题简化为单代理问题。在这种简化设置中，通常的 RL 算法可能无法找到全局最优解。主要原因是，在这种情况下，代理不知道其行动的奖励分配，因此，一些代理可能出现懒惰的行为。此外，策略不佳的代理之间的探索会影响团队奖励，从而限制策略良好的代理向最优策略进化。解决这个问题的一个办法是计算出每个代理在全局奖励中所占的份额。这一解决方案被正式表述为价值函数因式分解(Value Function Factorization )，即从全局奖励中学习分解函数。

完全可观察批判者模式的另一个缺点是通信成本。特别是，随着智能体数量的增加，由于通信带宽和内存的限制，在批评者中收集所有状态/行动信息可能是一项令人望而却步的任务。当观察和行动被共享时，同样的问题也会发生在行动者身上。因此，问题在于如何解决这一通信问题，并改变拓扑结构，使智能体能够在学习最优策略时进行合作和通信。关键的思路是把智能体放在一个连接稀疏的网络上，在这个网络上，每个智能体可以与一小部分智能体进行通信，智能体在与邻居达成共识的前提下寻求最优解。通过通信，最终整个网络达成一致的策略，从而产生最优策略，如下两图

另一个研究方向被称为 “学会交流”（Learn to Communicate），它可以让代理学会发送什么信息、何时发送以及发送给哪些代理。特别是，除了对环境的行动之外，代理还可以学习另一种行动，即交流行动。图中的虚线表示链接

6 Fully observable critic

环境的非稳态性是多代理问题和 MARL 算法的主要问题。解决这一问题的常用方法之一是使用fully observable critic 。其包含所有代理的观察和行动，因此，即使其他代理的政策发生变化，环境也是静止的。换句话说，即使 πi ∕= πi′，P（s′|s，a1，…，aN，π1，…，πN）= P（s′|s，a1，…，aN，π1′，…，πN′），因为无论其他智能体的的策略如何变化，环境都会返回相等的下一状态。根据这一思路，可以有 1 个或 N 个批判者模型：(i) 在完全合作的问题中，训练一个中心批判者；(ii) 当每个代理观察到局部奖励时，每个代理可能需要训练自己的批判者模型，从而产生 N 个批判者模型。无论哪种情况，一旦批判者完全可观测，批判者的非稳定性问题就解决了。

利用这一思想，针对该问题提出了一种无模型多代理强化学习算法，其中代理 i 在执行的时间步长为 t 时访问自己的局部观察、局部行动和局部奖励。他们考虑了合作博弈、竞争博弈和竞争与合作混合博弈，提出了多智能体 DDPG方法（MADDPG）算法

6.1MADDPG:

论文：

Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments: https://arxiv.org/abs/1706.02275

代码：

基于飞桨的强化学习套件PARL实现的MADDPG算法：https://blog.csdn.net/zbp_12138/article/details/107440531
基于TensorFlow的MADDPG算法代码分析：https://blog.csdn.net/qq_41871826/article/details/110678626
基于TensorFlow的MADDPG算法代码实现：https://www.cnblogs.com/initial-h/p/9429632.html

拓展：

Graph MADDPG with RNN for multiagent cooperative environment: This extension combines the MADDPG algorithm with graph convolutional networks and recurrent neural networks to improve its performance in multi-agent cooperative environments2.
Decomposed Multi-Agent Deterministic Policy Gradient (DE-MADDPG): This extension proposes a decomposition function to learn the share of each individual agent into the global reward, which can improve the performance of the MADDPG algorithm in problems with combined individual and team reward3.
MADDPG-GCPN: This extension combines the MADDPG algorithm with graph convolutional policy networks (GCPN) to improve its performance in multi-agent systems4.
Revisiting MADDPG: This extension explores the hypothesis that Gumbel-Softmax hinders MADDPG’s performance for discrete actions and proposes an alternative multi-agent actor-critic (MAAC) algorithm designed for discrete actions5.
Comparative Analysis of Reinforcement Learning Algorithm based on Tennis Environment: This extension uses the MADDPG algorithm to train a tennis model and compares its performance with other reinforcement learning algorithms, such as PPO and SAC6.
DEC-POMDP: In this model, each agent observes a local state and takes actions based on its local policy. The fully observable critic involves the observations and actions of all agents, making the environment stationary even though the policy of other agents changes. 7

太多了类似的，列举到这里

由于 MADDPG 在批判者中串联了所有局部观测数据，因此在增加智能体数量时会面临维度诅咒。为了解决这个问题，提出了多角色注意力批判（MAAC ）算法，该算法能随着智能体数量的增加而有效扩展。其主要思想是使用中央计算的评论家来训练分散的策略。MAAC算法使用了注意力机制，以选择每个智能体在每个时间步的相关信息，从而使其在复杂的多智能体环境中具有更有效和可扩展的学习能力。文中涉及到的一张对比图

MAAC算法的相关资料：

论文：Actor-Attention-Critic for Multi-Agent Reinforcement Learning (https://arxiv.org/abs/1810.02912)
代码：Multi-Actor-Attention-Critic (MAAC) (https://github.com/shariqiqbal2810/MAAC)
文献阅读：Actor-Attention-Critic for Multi-Agent Reinforcement Learning (https://www.semanticscholar.org/paper/Actor-Attention-Critic-for-Multi-Agent-Learning-Iqbal-Sha/929bef0066bad871ba971b673c053112d055d29f)
文章：Multi-Actor-Attention-Critic Reinforcement Learning for … (https://www.cs.unm.edu/~lukey11/2021IJCNN_final.pdf)

6.2 COMA算法的相关资料

我也不熟悉，还在学，主要是摘要，具体算法和流程图建议回论文中看

Articles

COMA（二）：Counterfactual Multi-Agent Policy Gradients 论文讲解 - This article provides an explanation of the COMA algorithm and its use in learning non-centralized, partially observable multi-agent control policies.
COMA: Counterfactual Multi-Agent Policy Gradients笔记 - This article provides notes on the COMA algorithm and its main contribution in solving the problem of global reward allocation in a centralized training, decentralized decision-making framework.
Counterfactual Multi-Agent Policy Gradients (COMA) paper: https://arxiv.org/abs/1705.08926

Papers

Counterfactual Multi-Agent Policy Gradients - This is the original paper that introduces the COMA algorithm and its use in multi-agent reinforcement learning.

自己的理解（重要的几个点）

反事实基线：COMA overcomes these limitations by using a centralized critic to compute an advantage function that compares the Q-value for the current action to a counterfactual baseline that marginalizes out a single agent’s action while keeping the other agents’ actions fixed1. This allows COMA to compute a separate baseline for each agent that relies on the centralized critic to reason about counterfactuals in which only that agent’s action changes, without the need for extra simulations or assumptions regarding appropriate default actions（我觉得英文的解释会更加合适一点）
使用集中的critic评估：批判者只在学习过程中使用，而执行过程中只需要行动者。由于学习是集中进行的，因此我们可以使用一个集中的批评者，它以联合行动和所有可用的状态信息为条件，而每个行动者的策略只以自己的行动观察历史为条件。
COMA uses a critic representation that allows the counterfactual baseline to be computed efficiently. In a single forward pass, it computes the Q-values for all the different actions of a given agent, conditioned on the actions of all the other agents. Because a single centralised critic is used for all agents, all Q-values for all agents can be computed in a single batched forward pass

CM3算法的相关资料

paper

https://arxiv.org/pdf/1809.05188.pdf

code

https://github.com/011235813/cm3

7 其他

我们讨论了分层多智能体强化学习（MARL）的概念。在这种设置中，问题被分解成一个任务层次结构，其中较简单的任务位于较低层次，而在较高层次学习选择这些任务的策略。因此，在分层设置中，高层次的决策比低层次的决策更少地进行，后者通常在每一步都发生。高层次的策略主要关注长期规划，涉及层次结构低层次的多个一步任务。遵循这种方法，在单智能体分层强化学习中，高层次的元控制器学习选择任务序列的策略，而在低层次为每个任务训练一个单独的策略。

对于分层多智能体系统，有两种可能的情景是同步和异步。在同步分层多智能体系统中，所有高层次的智能体同时采取行动。换句话说，如果一个智能体比其他智能体更早地完成其低层次的行动，它必须等待所有智能体完成其低层次的行动。如果智能体数量很大，这可能是一个限制性的假设。另一方面，异步分层多智能体系统没有这种限制。然而，在异步情况下实现高层次的合作可能具有挑战性。

8 Consensus

个人感觉这个章节的原文生搬硬凑的比较多，因为每段一个文献，所以描述的比较少

distributed Actor-Critic ：无代码，不做细究

paper

https://arxiv.org/pdf/2110.12306.pdf

总结

提出了一种名为Diff-DAC的完全分布式架构，该架构可以将单智能体Actor-Critic算法转换为完全分布式实现，可以应用于多任务强化学习（MRL）问题，并且即使在地理分布式数据的情况下，也能优雅地扩展到大量任务1。
从对偶理论推导出Diff-DAC，并为标准Actor-Critic框架提供了新的见解，表明它实际上是对偶上升方法的一个实例1。
研究了Diff-DAC架构的渐近收敛性，并证明了即使对于非线性策略和价值函数表示，所有智能体也会收敛到一个共同的策略。在更严格的假设下，还表明这个共同策略近似于多任务强化学习目标的一个稳定点1。
将Diff-DAC架构应用于两种算法：简单的Actor-Critic（SiAC）和优势Actor-Critic（A2C）——Mnih等人（2016）提出的A3C的同步版本——以研究扩散机制的稳定性和正则化能力1。
在机器人控制任务上进行了多次实验，结果表明，即使是Diff-DAC实现的SiAC（Diff-SiAC）也优于完全分布式多任务强化学习的Dist-MTPS；Diff-DAC架构比集中式方法更稳定，通常能够实现更好的局部最优；并且Diff-DAC具有有趣的泛化特性1。

9 APPLICATION

主要讨论机器人路径规划方面的应用、

先讨论一下主要的分类：

解决多智能体路径寻找（MAPF）问题的算法通常可以分为三类：耦合方法，解耦方法和动态耦合方法。

耦合方法：这种方法将MAPF问题视为一个高维度的智能体，这导致了复杂性的指数级增长。也就是说，随着智能体数量的增加，寻找解决方案的复杂性呈指数级增长。
解耦方法：这种方法为每个智能体获取一个独立的路径，并调整路径以实现零碰撞的目标。这些方法能够快速为大问题找到解决方案。它们使用像“速度规划”这样的技术，该技术修改每个智能体在其路径上的速度配置以避免碰撞，以及“优先级规划”，该规划允许优先级较高的智能体使用最快的路径和速度。然而，由于它们只考虑了联合配置空间的一小部分，并在低维度空间中进行搜索，所以效果并不是很好。
动态耦合方法：这种方法被提出来解决这些问题。这些方法介于耦合方法和解耦方法之间。例如，基于冲突的搜索（CBS）通过构建一组约束并为每个智能体进行规划，而无需在高维度空间中搜索，就可以找到最优或次优路径。此外，允许在规划过程中按需增加搜索空间也是另一种方法。

如果考虑障碍物，可以分为动态障碍物和静态障碍物，我还在搞，有想法的欢迎交流

待续（毕业再说）