电子商务的爆发性增长催生了快递物流需求的激增，特别是在人口密集区，传统快递配送面临严峻挑战：效率瓶颈、客户满意度下降。针对此，我们探索智能无人系统解决方案，旨在通过自动化取件机器人提升物流效率和用户体验。本项目采用多智能体系统，比较不同策略，以求在复杂环境中找到最优的快递收取路径。
我们主要聚焦于机器人前往取件点的路径规划问题。简化后的问题如下：在 x*x 的区域上，有些地方有要取走的 j 个快递，标记为 m，m 为快递大小；有些地方有 k 个智能机器人，标记为 n，n 代表背包余量。机器人的数目及容量和快递的数量及大小是可以改变的，对于不同数量的小车代码都应该可以实现找到最优解。假设每个快递都是只有一个重量固定的整体，即不可以分批次拿，这也符合现实中用户希望一次就全部取走快递的期望。
我们使用网格地图模拟实际的街区环境，机器人的动作选择包括：上、下、左、右。同时，我们将连续的时间离散化为时间步，一步中所有智能体可进行一种动作。 同时对最优解的定义如下：完成问题的时间步最少。
我们将问题进一步现实化，在地图中还会出现障碍物。同时我们试图实现不同智能体之间防止碰撞的功能。从而我们发现了下列算法：
Q-learning 是一种基于策略的强化学习算法，它通过学习智能体在当前状态下采取特定动作的预期回报来改进策略。其关键在于维护一个以状态-动作值函数 Q(s, a)的列表，其中 s 表示当前状态，a 表示当前状态下选择的动作，Q(s, a) 表示采取动作 a 在状态 s 下的期望回报。 对奖励函数的设定如下：
-
对于每一步移动,给予一个小的负奖励(-10),作为鼓励智能体尽快到达目标的惩罚机制。
-
如果第 i 个智能体的新坐标是其目标位置。
- 给予一个很大的正奖励(+10000),并将 dones[i] 设为 1,表示该智能体已完成当前情节。
-
如果第 i 个智能体的新坐标位于障碍物处(maze_map[x][y] == 1)。
- 给予一个很大的负奖励(-100000),并将 dones[i] 设为 1,终止该智能体的当前情节。
-
如果第 i 个智能体的新坐标与第 j 个智能体的坐标相同(发生碰撞),且不是同一个智能体。
- 给予较大负奖励，并将dones[i]设为 1，终止当前情节实现防碰撞的功能。
对于 q-learning 算法我们更关注于此算法核心的实现及性能，所以问题进行了一定的简化：每一个robot的背包是无限大的，每一个快递的大小也是一样的。此功能可以通过改变奖励机制增加。
对于没有简化的问题，即每一个robot背包大小有限，每一个快递的大小不同，这个代码的奖励函数如下：
def step(self, agent, actions, dones):
new_positions = []
rewards = [0]*self.n_agents
for i, action in enumerate(actions):
x, y = self.agent_positions[i]
if dones[i] == 1:
new_positions.append([x,y])
continue
if action == 0 and (y-1)>=0 :
y -= 1
elif action == 1 and (y+1)<len(self.maze_map[0]) :
y += 1
elif action == 2 and (x-1)>=0 :
x -= 1
elif action == 3 and (x+1)<len(self.maze_map) :
x += 1
rewards[i] -= 10
for j in range(0,self.n_agents):
if (x,y) == self.agent_positions[j] and i!=j:
rewards[i] -= 1000
dones[i] = 1
if self.maze_map[x][y] == 1:
#print('fall')
rewards[i] -= 100000
dones[i] = 1
if (x, y) == agent[i].goal:
if(self.maze_map[x][y] > agent[i].contain):
rewards[i] -= 100000 * maze_map[x][y]
dones[i] = 1
else:
rewards[i] += 10000 * maze_map[x][y]
agent[i].contain -= maze_map
dones[i] = 1
new_positions.append([x, y])
self.agent_positions = new_positions
return new_positions, rewards, dones, {}
即假如robot可以拿走子在那个地方的快递，就rewards[i] += 10000 * maze_map[x][y]，但是假如不可以就要远离这个地方，所以rewards[i] -= 100000 * maze_map[x][y]。
对于原问题中任务分配的功能，通过贪心算法不断选取距离最近的任务，分配形成智能体的目标点列表。学习中发现：ε下降后，q表会发生混乱，表现为若根据q表行进会陷入循环。分析可能原因是：若单个智能体有多个目的地，那么对于不同的目的地，q表会被多次更新，最大值动作索引也会改变，更加混乱。
代码的分配函数如下：
def goal_distribution(agent, goals, n_agents, n_goal, pos):
while len(goals):
for i in range(n_agents):
x, y = pos[i]
key, dm = 0, 999999
for j in range(n_goal):
xt, yt = goals[j]
d = np.sqrt((x - xt) ** 2 + (y - yt) ** 2)
if dm > d:
key = j
dm = d
agent[i].goal.insert(0, goals[key])
agent[i].n_goal += 1
goals.pop(key)
n_goal -= 1
于是，我们试图从另一个角度思考方法：对于每个目的地都单独训练维护一张q表。使用时智能体只需根据对应目的地的q表行进。但是这带来了新的问题，即目的地过量以及防碰撞机制失效的问题。
除了以上的缺点，q-learning面对尺寸更大的图时，会存在问题，因为q表会很大，从而程序难以运行。所以，引入神经网络模型来代替q表。即拟合出一个函数，输入智能体的状态，输出所选择动作的索引。即为DQN算法。
DQN（Deep Q-Network）是深度学习与强化学习相结合的一种算法。其核心思想是使用深度神经网络，来动态估计动作-值函数（action-value function），即Q函数。
- 初始化Q网络和目标Q网络：使用两个相同的深度神经网络，其中目标Q网络的权重是Q网络的权重在特定步数后的副本，用于稳定训练过程。
- 初始化经验回放缓冲区：一个用于存储经验回放的缓冲区，容量为N。每个经验回放是一个四元组（s, a, r, s'），其中s是状态，a是动作，r是奖励，s'是下一个状态。
- 初始化状态s：开始一个新的游戏片段或回合。
- 选择动作：
- 根据ε-贪婪策略选择动作a。ε是一个概率值，表示以ε的概率随机选择动作，以(1-ε)的概率选择具有最大Q值的动作。
- 执行动作a，观察新的状态s'和奖励r。
- 将转换（s, a, r, s'）存储在回放缓冲区中。
- 将状态更新为s'。
- 训练Q网络：
- 从回放缓冲区中随机抽取一批转换（minibatch）。
- 使用目标Q网络计算目标值y（即执行动作后的奖励加上下一个状态的Q值）。
- 使用梯度下降更新Q网络的权重，以最小化预测的Q值与目标值y之间的差异。
- 更新目标Q网络：每隔一定步数，使用Q网络的权重更新目标Q网络的权重。
代码网址: https://www.luogu.com.cn/paste/bqbu3opz
实际算法操作实践中发现：
- 优点：
- 可以处理高维度状态空间，扩展了Q-Learning的应用范围。
- 使用经验回放和固定Q-目标技术，有效地稳定了训练过程，解决了数据相关性和目标不稳定问题。
- 缺点：
- 对超参数的选择非常敏感，如学习率、回放缓冲区大小、折扣因子等，使得网络较难收敛