机器人与目标匹配问题及解决 1. 问题描述2. 环境模型3. 博弈模型4. 虚拟动力学求纳什平衡5. Q-Learning 解决问题6. 仿真实验
1. 问题描述
在世界各地，由于自然灾害或者各种突发事件等原因，灾难经常发生。例如在森林火灾救援的过程中，消防人员必须保证以最短时间以及在自身能力允许的情况下尽可能地扑灭所有的火，防止火势蔓延造成更大的损失。如今随着科技的进步，机器人的应用范围越来越广泛，如多机器人同样也可以使用于上述的救灾场景之中。
如上图所示，模拟了一个森林的实际环境场景，其中三角形标示该森林中意外起火的火灾点，每个火灾点的火势情况不一样，而蓝色圆形标示目前该森林中 处于不同位置的可用于扑灭火灾的机器人，每个机器人的救援能力也有所差异。 由图1可得，模拟的实际环境情况为：在红色框的森林区域范围内，有五个意外起火的火灾点，现在森林中有五台处于不同位置的灭火机器人。为完备智能体工作环境以及实际情况，进行以下假设：
（1）假设机器人只能观测到1千米以内的火灾情况；
（2）每个机器人扑灭火灾的概率与其距离火灾点的距离有关，在本问题中 定义扑灭火灾概率为：
式中，i 表示机器人 i，j 表示火灾点 j；
（3）每个火灾点的火势有所不同，因此每个火灾点扑灭后的收益Vj有所不 同。现在需要对各台机器人以及火灾点进行匹配以救援这次火灾，任务需要实现的总目标为：最大化本次灭火任务的收益，尽可能挽救火灾。
为了方便后续的操作，首先对机器人实际运行环境进行离散化处理，对实际的环境进行合适的分割及抽样，忽略环境中其他不影响结果的干扰环境信息，选取环境中的关键节点来构建环境模型。
如下图所示，为依据1中的所示的实际环境情况构建的模型。在火灾救援多机器人环境中，机器人之间需要通过协调合作以最大的收益完成任务。环境地图模型中的栅格通过坐标来表示，根据机器人和火灾点等坐标位置来描述它们之间的联系。其中，图中黄色圆形图标代表火灾点分布，蓝色圆形图标代表机器人位置分布。
根据如上所述的定义，可将1中所描述的问题建模如下：
接下去采用虚拟动力学（如下公式定义），每个机器人记录每一步其他机器人的动作，并以此统计出机器人使用每个动作的频率，作为自己调整下一步动作的依据。
由上述的博弈模型中个体的有限可选动作集可以初始化每个机器人选择火灾点的次数为，即表示初始时刻每个机器人选择各自动作集内的动作的概率是一样的。由于机器人数量为 5 个（ y1, y2 , y3 , y4 , y5 ），火灾点数量也为 5 个（T1,T2 ,T3 ,T4 ,T5），数量过多不便之后的阐述，因此阐述具体步骤时假设简化为环境中仅有（ y1, y2 , y3）三个机器人，其余情况保持不变。具体步骤如下：
（1）假定在如图 2 所示的环境模型中，机器人的位置坐标依次为： [2.7,1.5] [2.7,2.7] [1.5,2.7] [1.5,3.9] [2.7,3.9]
火灾点的坐标依次为： [2.2,2.1] [2.2,3.3] [1.8,3.5] [1.9,3.1] [3.0,3.9]
因此可由公式（1）计算得到机器人 i 扑灭火灾 j 的概率 pij 为：
假定火灾点 1-5 火势逐渐变旺，即扑灭火灾点 j 的收益为：
（2）时刻 0（初始化）：
（3）时刻 1：
机器人 y1选取动作：
a. 机器人 y1选取火灾点T1的期望收益为 0.098：当机器人 y1选取火灾点T1 时，机器人 y2 和 y3 的联合动作有12 种可能，每种动作的概率为1/21，在机器人 y2和 y3 每种联合状态下机器人 y1选取火灾点T1 的收益为：
机器人 y1选取火灾点T1 的期望收益为：
1/12 * 1 * 0.11 * (0.53 * 3 + 9 * 1) = 0.098
b. 同理可得机器人 y1选取火灾点T3的期望收益为:
1/12 * 3 * 0.5 * (0.85 + 0.85 + 0.98 + 0.98 + 0.98 + 0.85 * 0.98 + 6 * 1) = 1.43
c. 同理可得机器人 y1选取火灾点T4的期望收益为:
1/12 * 4 * 0.08 * (0.92 + 0.92 + 0.78 + 0.78 + 0.78 + 0.78 * 0.92 + 6 * 1) = 0.29
因此，机器人 y1在时刻 1 选取火灾点T3，
…
在每个时刻机器人记录每一步其他机器人的动作，并以此统计出机 器人使用每个动作的频率，作为自己调整下一步动作的依据，直至动作序列收敛， 收敛于的动作序列即为纳什均衡。最终的纳什均衡为：
机器人 y1选择火灾点T3，机器人 y2选择火灾点T2 ，机器人 y3 选择火灾点T1
若 1中描述的问题采取 Q-Learning 方法进行解决，在考虑采用多个体Q值学习时，因为若构造马尔科夫博弈模型，则由于本任务环境状态的定义与多智能体各自选择救援一火灾点有关，故根据智能体选择火灾点来定义系统状态时，描述环境的状态集 S 只有机器人选择火灾点后的状态这一元素，此时即为常规博弈模型。经思考后，觉得解决本问题可以尝试使用单智能体的 Q 值学习方法应用于本多智能体场景，具体思路如下：
（1）在构建的博弈模型中，已计算得每个智能体的动作集，若根据每个智能体的位置来定义系统的状态S，则系统有 108种状态， 因此可以构建一张大小为108的Q值表；
（2）每个智能体的动作集各不相同，联合动作为 a = a1 * a2 * ,…, * an ，其中ai 为智能体 i 从可选动作集 Ai中选择的动作；
（3）状态转移是确定性的；
（4）Q 值学习的更迭
（5）回报函数 R 此处相较于 1中所述的假设中再多加了一个约束条件，在保证所有火灾点都有机器人匹配的情况下，使得总目标收益最大化，因此回报函数如下：
（6）基于具体步骤如下所示：
1）初始化大小为 108 的 Q 值表 Q(s,a)=0，a 为所有智能体的联合动作；
2）初始化状态为任意值；
3）重复
基于ε-greedy 策略选择行为 a
执行行为 a 并转移到下一状态 s’ ，得到回报 r
设s = s’
直到完成特定步数或 s 到达终止状态
4）Q 值表构建完成后，选取 Q 值最大的联合动作
虚拟动力学求纳什均衡：
Q-Learning：