摘 要：自动引导小车（Automated Guided Vehicle，AGV）在工厂中承担不同节点之间的物料运输工作，在考虑全局路径最优的情况下需要对AGV进行多起点多终点的路径规划。针对现有的深度强化学习算法研究多考虑单起点达到单终点的路径规划情况，涉及多起点多终点的情况时泛化性能较差的问题，提出一种基于DQN(Deep Q-Networks)的AGV全局路径规划求解模型。首先通过改进算法的输入的AGV状态和改进奖励函数的设置提升算法收敛的效率；再利用改变训练初始点位置的方式提升数据的丰富度和模型对环境的感知程度，并以此提升模型对不同起点单个终点环境下路径规划的泛化能力；最后在训练过程中插入不同终点下AGV的状态数据，以获得模型对多终点路径规划的能力。通过在不同规模的环境下的仿真与A*和快速扩展随机树算法的对比实验和模型的扩展性实验，验证了该方法在多终点情况下的路径规划能力。
关键词:深度强化学习;DQN;多终点;AGV路径规划;
DQN-based AGV path planning for situations with multi-starts and multi-targets
HUANG YansongYAO Xifan JING Xuan HU Xiaoyang
School of Mechanical and Automobile Engineering, South China University of Technology
Abstract：The Automatic Guided Vehicle (AGV) undertakes the material transportation between different places in a factory. For the optimal global path, AGV needs to perform path planning with multiple starting points and multiple ending points. To solve the problem that exists in deep reinforcement learning algorithms mostly considering the path planning from a single starting point to a single ending point, and the poor generalization performance for the situation with multiple ending points, a Deep Q-Network (DQN) based solution model for the global optimization of AGV path planning was proposed. First, the algorithm convergence was promoted by introduction of the AGV state and improved reward function; then the starting point position was altered to enhance the data richness and the model's perception of the environment, which aimed to improve the model's generalization ability of path planning under the environment of different starting points and a single ending point; finally, states of AGVs at different targets were inserted in the training process to achieve the multi-target path planning. Compared with A* and Rapidly-exploring Random Tree (RRT) algorithm under different scale environments and model expansion experiments, the proposed path planning method was verified in the case of multiple targets.
Keyword：deep reinforcement learning; Deep Q-Networks; Multi-targets; AGV path planning;
1引言
近年来，AGV因其响应快、可控性强、工作效率高、安全性好的特点带来的高柔性和自动化程度高的优势[1]，使其作为物料运输工具在仓储系统[2]与制造工厂[3]中都起到了重要作用。路径规划算法研究是AGV研究内容中最重要的技术之一，其研究的目的是在已知的AGV起点和终点之间，根据不同的需求规划出一条最优或者次优的AGV移动线路，以保证运输过程的通畅与高效[4]。对于路径规划的求解方法众多，包括以收集局部环境信息作动态路径规划的人工势场法[5,6]、模糊算法[7]以及A*及其衍生算法[8,9]，和以收集全局环境信息作静态路径规划的遗传算法[10]、人工蜂群算法[11]和快速随机搜索树[12]等，还包括能够面对未知动态环境进行路径规划的深度强化学习算法[13]。
在工厂和仓库中，AGV的运行不只是局限于从单一起点到单一终点的路径，而是能够满足从不同的起点（待机点）出发经过不同的终点完成相应的运输任务后返回待机点，这就需要AGV具有能够进行多终点路径规划的能力。这通常被定义为旅行商问题（Travelling Salesman Problem，TSP）的一个子问题：即在确定多个目标点的抵达顺序后，规划一条经过所有目标点的路径[14]。有学者已利用各种算法对该问题进行了求解，但使用深度强化学习涉及该问题的研究还相对较少。Liu等[15]提出一种分支检测算法（Branch-Detected Algorithm）用于局部最优路径的搜索，并将该算法用于求解包含障碍栅格TSP问题中的多终点路径规划问题。Janos等[16]针对多终点路径规划问题提出一种基于采样的规划器空间填充森林（Space-Filling Forest，SFF*），该方法从多个终点生成RRT构建森林，并尝试寻找树之间的连接以形成路径。Yu等[17]提出一种改进离散布谷鸟算法进行多终点的全局规划，并与粒子群算法和人工蜂群算法的结果进行比较，展现了该算法的求解有效性和较高的效率。Lv等[18]使用改进粒子群算法进行多终点路径规划，克服了算法早熟的缺点，提升了求解的准确性和稳定性。Kim等[19]提出一种基于D*算法的多中间点路径规划方法，用以确保AGV能够安全地到达动态环境中的一个目标终点。Zhu等[20]改进了传统D* Lite算法，将估计的距离和实际的目标点和当前位置距离进行比较以此优化路径，实现了在未知的复杂环境下多终点路径规划和动态障碍的避障。
随着制造业向着智能化与智慧化的方向发展，强化学习与深度学习作为最近炙手可热的技术也被引入AGV路径规划问题的求解中，或者与诸如A*算法等传统的智能优化算法结合构建出混合的路径规划算法。强化学习与深度学习结合构成深度强化学习方法众多，包括基于值函数的DQN算法和基于策略梯度的DDPG(Deep Deterministic Policy Gradient)等算法。Aleksandr等[21]首先提出一种将人工神经网络应用在网格路径规划问题求解的方法，利用卷积神经网络进行智能体状态提取，通过DQN进行网络训练更新网络参数，在不断的训练中最终找到一条通往终点的路径。Lei等[22]利用深度强化学习的Double DQN（DDQN）方法结合卷积神经网络针对动态的环境对AGV进行路径规划，为了避免奖励的稀疏性，采取了不断增加起点与终点之间距离的训练方式。吴夏铭[23]使用了基于探索噪声层的DQN和基于对抗网络的Dueling DQN算法分别对AGV路径规划进行求解，噪声的加入提升了网络初期探索的训练效率，对抗网络和优势函数的加入降低了对Q值估计的误差。孟晨阳等[24]改进了基于DDPG的AGV路径规划算法，将经验回放机制引入DDPG中并结合ϵ贪心和玻尔兹曼探索策略，提高了算法的收敛速度和解决了陷入局部动作最优的问题。Wang等[25]结合深度强化学习与A*算法进行动态环境下的路径规划，A*算法用于全局路径规划找出一条最优路径，深度强化学习算法辅助AGV躲避动态障碍物。Guo等[26]将DDQN嵌入Dueling网络结构中，并使用优先经验回放机制，构建了Dueling DDQN-PER算法，该算法提升了AGV在有障碍物的环境中自主路径规划的成功率和避障能力。
当前的研究中，多起点多终点路径规划问题求解多用传统的智能算法，但在面对未知环境和动态环境下，深度强化学习能够适应高维复杂的环境信息且有较好的求解性能[13,27]。深度强化学习在模型的训练过程中需要不断与环境进行互动试错，导致模型容易陷入过拟合同时模型的泛化性较低，所以在面对多目标点的路径规划时常常表现较差。常见的基于深度强化学习方法是针对单起点单终点的问题进行求解，面对适应实际工业场景中可能出现的多起点与多终点的情况时表现不佳，常常需要重新训练模型以适应不同的初始输入条件（即不同的起点和终点）。本文提出一种基于改进DQN的多起点多终点AGV路径规划算法，对模型的输入状态和奖励函数进行了设计并改进了模型的训练方法，该算法能够在给定不同的初始输入条件下，保证AGV以较优的路径有效地到达终点，同时还具有一定的扩展性，在环境中的终点数量增加时仍能有效地对模型进行扩展而不用重新训练。
2 AGV多起点多终点路径规划问题
2.1 问题描述
AGV路径规划问题的栅格环境如图1所示，其中黑色代表AGV不能通行的障碍物并以状态值-1表示，白色代表能够通行的通道以状态值0表示，蓝色代表AGV，绿色表示的是终点，状态值为1。AGV只能出现在格点内，并在相邻八个格点之间进行移动。路径规划问题的目标是在给定起始点pS和可到达的终点pG后，找到一条由一系列相邻的白色格点组成的路径P，并尽量保证路径的长度最小[21]。
P=(pS,pG)=(pS,neigh(pS),neigh(neigh(pS)),...,pG)（1）
式中neigh(p)表示格点p的后继节点，且该后继节点为p的邻接节点。在TSP问题中，旅行商人需要以最短的成本经过不同的城市，最后回到起点处。此时路径规划的终点不再是只有一个而是有n个，即
P=(pS,pS)=(pS,neigh(pS),neigh(neigh(pS)),...,pG1,...,pG2,...,pGn,...,pS)（2）
随着TSP问题的研究不断深入，该问题被分为以下四类：确定起点，返回起点；确定起点，不返回起点；非确定起点，返回起点；非确定起点，不返回起点[15]。其中在实际工厂中，AGV的路径规划可看成第四类非确定起点，不返回起点类型的TSP问题。
P=(pS,pGn)=(pS,neigh(pS),neigh(neigh(pS)),...,pG1,...,pG2,...,pGn)（3）
2.2状态空间设置
深度强化学习网络的输入为智能体的当前状态，针对AGV路径规划问题，该输入一般为AGV的当前位置信息或者是AGV视野内部的网格信息。通常情况下，在栅格地图中可以通过格点的横纵坐标确定位置，所以AGV的状态空间为2维，其范围与地图大小相关。在改进的算法中，网络的输入为10维的AGV状态，其中前2个维度表示AGV与终点之间的位置关系用以描述当前位置与终点的方位关系，指引AGV前进的方向；后8个维度表示当前AGV所在格点周围的8个格点代表的值，用以描述环境，引导AGV躲避障碍。10维状态向量s的表示如式（4）所示
式中xA，xG分别表示当前AGV和终点的横坐标值，yA，yG分别表示当前AGV和终点的纵坐标值，M()表示环境的状态函数，根据位置输出当前位置的状态值，ai表示AGV动作空间的动作值，p'A(ai)表示采取动作ai后AGV的位置。改进的切入点是将原本的具体位置信息转换为相对特征信息，并将AGV的周围环境信息融入其中，利用卷积神经网络也能够做到这一点，但却无法在输入的AGV状态中包含终点的位置信息。
2.3动作空间设置
AGV在栅格地图中移动，其运行方式有8种，如图1所示，其动作空间为{0,1,2,3,4,5,6,7}。所以在强化学习中AGV作为智能体，其动作空间为8维，采用one-hot编码方式。相较于正向动作，斜向的动作在一定程度上可以更有效地减少到达终点的步数，所以在智能体的训练过程中更倾向于采取斜向的动作。不过这并不符合实际的情况，斜向的动作走过的路程更长，所以对于斜向动作的选取也需要受到一定的限制，这在奖励函数的设计上有所体现。因为可选取的动作中包含了斜向的移动，所以在AGV运行过程中也会遇到转角和死角的情况，如图2所示，本文中规定AGV可斜向移动通过转角但无法通过死角，即当AGV采取通过死角的动作时会停留在原地。动作的选择使用ϵ贪心策略，如式（5）
a={argmaxaQ(s,a,θ),c≥ϵrandomaction,c<ϵ（5）
式中Q()表示DQN中的Q值网络，θ表示网络参数，s和a分别表示网络的输入状态和动作，c为(0,1)的随机数，ϵ随着训练过程依据式（6）逐渐降低
ϵ=f+(1−f)e−tk（6）
式中f表示ϵ降低的非0最小值，保证模型具有一定的随机性能够跳出局部最优，t表示训练步数，k表示ϵ折扣因子用以调整的下降速率。随着ϵ逐渐降低，模型的动作选择策略从探索阶段的随机选取转变为根据网络输出选择最大Q值索引。
2.4奖励函数设计
奖励函数的设计是强化学习中最重要的步骤之一，合理地设置奖励函数能够提升强化学习的训练效率。在本算法中，奖励函数由4部分组成：r1，因阻塞而不能移动的惩罚，即判断相对上一状态有无改变位置，有则置0，无则置-5，其中包含了碰到环境中的障碍物和移动到环境的边界外两种情况；r2, 斜向动作的移动距离平衡惩罚，斜向动作则置-0.5，非斜向动作则置0，斜向移动相比于正向运动需要消耗更多的资源，通过这一奖励函数因子的设置进行模拟；r3, 比较当前状态和上一状态分别与终点的曼哈顿距离，若距离有减少，则根据减少的距离设置奖励值，否则置-1，这里将终点位置作为强化学习模型训练的先验知识，能够减少训练过程中奖励稀疏性问题，提升训练的效率；r4, 到达终点的奖励，到达则置10，否则置-1，在未到达终点时给予惩罚的目的是保证训练的策略使智能体能够尽快地到达目标点。最终奖励函数由这4部分相加得出，如式（7）所示。
式中p表示当前位置，p'则表示前一时刻的位置，x和y分别表示具体的横纵坐标，下标A代表此为AGV的属性，G代表终点，小写字母a表示AGV执行的动作。
3 本文算法
3.1 DQN算法
DQN算法将强化学习的Q-learning与深度学习进行结合，利用深度的网络结构对Q值进行预测，以此确定智能体的行为策略[28]。在Q-learning中，智能体处于某一状态下执行某一动作对后续过程的影响记为Q值，Q值被记在Q值表中，并通过与环境的互动不断更新。当Q值表完成迭代后，智能体根据每个时刻的最大Q值确定其动作。Q值的计算如式（8）
Qπ(s,a)=Eπ[Gt|St=s,At=a]（8）
式中，G表示回报函数，是在状态s下执行动作a后对后续影响的度量，G定义为后续奖励函数的总和，间隔越远的奖励函数对当前回报函数的影响越小，即
G(t)=∑k=0∞γkRt+k+1=Rt+1+γG(t+1)（9）
式中，γ表示奖励函数折扣因子，可以看出在Q-learning中对Q值的计算是复杂的，需要在遍历了几乎所有的情况后，才能收敛到最优的Q值表。所以Q-learning在面对大规模的环境时，计算的效率会随规模增加而呈指数级降低。DQN创新性地将人工神经网络引入了强化学习，通过构建深度Q值网络将Q值的计算转化为对网络参数的计算，将Q值表的更新抽象化为深度网络模型的训练，即
Q(s,a,θ)≈Q∗(s,a)（10）
DQN算法包含两个重要的机制：target网络和经验回放。target网络是Q值网络的复制，不同之处在于target网络的参数更新频率更低，其作用是在训练过程中保存近期的最优Q值，并作为Q值网络的目标值参与计算损失函数，如式（11）
式中，L表示损失函数，r表示智能体在状态s下执行动作a运行到状态s'获得的环境奖励，θ−代表target网络参数。经验回放机制定义了一个用以Q值网络训练的可更新数据集，该数据集中存储智能体与环境交互过程与结果的数据，如智能体的状态、动作和奖励等。每次训练从数据集中随机抽取一部分数据用以计算损失函数并更新网络参数，并以此打破数据之间的关联性。
3.2算法整体框架
AGV路径规划问题求解目的是确定一条从初始点到达终点的最优路径，在强化学习中可看作是训练一个智能体使其拥有从起点到终点的最优策略，即该智能体（AGV）能够在运行的过程中找到去往终点的最优动作。利用DQN进行AGV路径规划的具体流程如图3所示。图中方块表示算法中的组件，椭圆表示向组件输入或从组件输出的具体的参数值。算法的流程主要分为两个部分：强化学习部分和深度学习部分，这两个部分同时运行相辅相成。强化学习部分的主要功能是与环境交互提供深度学习的训练数据，深度学习部分的主要功能是利用经验回放机制和target网络对Q值网络进行训练，不断完善AGV在环境中运行的策略参数θ。
基于强化学习的路径规划算法通常解决的是单起点到单终点的问题，面对不同起点的问题时因为强化学习容易陷入过拟合的缺陷，求解的效果较差。在深度学习的训练中，深度学习网络参数训练的数据由强化学习中智能体和环境交互提供。在训练初期的探索阶段，随机的动作能够提供大量不同的信息。当训练进入利用阶段，模型逐渐收敛同时智能体的动作逐渐靠近最优的策略，此时深度网络获得的数据会局限在最优策略指引下的智能体运行过程的周围，所以根据单起点的深度强化学习路径规划算法会容易陷入过拟合[29]。若一个模型陷入过拟合，则该模型的泛化性较低，提升模型泛化性能的技巧包含增加训练数据量和适当的dropout。本文针对多起点多终点的问题采用提升训练数据量的方式来提高模型的泛化性。在深度强化学习提升训练数据量可以通过增加训练过程的初始起点来实现，通过选择相关性较低的初始点可以有效提升获得数据的丰富程度，以提升模型的泛化能力。本文使用的算法的伪代码如算法1所示。
3.3 算法性能比较
将本文提出的改进算法与未改进的DQN算法[28]、DDQN算法和Dueling-DQN算法进行收敛性能的比较，构建20×20的复杂随机环境如图4（a）所示，起点位于左上角位置，终点位于右下角位置，文中具体的训练过程的参数设置皆如表1所示，算法的训练平台为PyCharm，CPU为i7-6500U，显卡为GeForce 940M。最终各算法的训练结果如图4（b）所示，可以看出本文的改进DQN算法（绿色线表示）相较于其他深度强化学习算法提升了奖励函数的收敛效率，对模型的快速训练完成有促进作用。
4 仿真实验
为了验证算法针对多起点规划的有效性，设计了评价指标完成率（DR，Done Rate）。DR表示在环境中所有可行走的格点中，能够以该格点为起点到达终点的格点的比例，如式（12）所示。
式中，N表示环境中所有状态值为0的格点数量，μθ表示模型的策略，可根据输入的位置输出下一个位置坐标，pi表示不同的初始点位置，在给定的步数内若模型策略能从初始点到达终点则其值f置为1，否则置为0。
使用传统DQN算法在如图5（a）所示的8×8的网格网络中，验证了单起点路径规划模型的效果。由单起点训练的模型最终收敛时的完成率在0.75附近波动，还有大量如图5（b）所示的黄色格点不能通过训练好的模型到达终点。基于DQN的AGV路径规划算法存在的问题最主要是泛化性能较差[29,30]，即通过DQN算法训练得到的AGV智能体，对于预设的起点与终点之间的路径规划良好，但对于未预设的起点或者终点则执行结果较差，难以适应起点或者终点变化的复杂工业实际环境需求。
本文的实验由两部分构成，首先针对不同数量和位置的初始点对单终点环境完成率的影响进行测试（4.1节和4.2节），以验证初始点数量与位置的设置对模型的泛化性能有提升作用，并且模型在单终点环境下泛化能力的提高有助于提升多终点环境下模型的扩展性。随后为了验证提出的方法在多终点环境下的可行性，对不同多终点环境下模型的路径规划能力进行测试，并通过增加新节点的方式测试了模型的扩展性（4.3节）。提高的完成率在多终点的环境中，可提升模型的扩展性，当有新的终点加入时可通过训练单终点的模型对原模型进行扩展完成包含新终点的路径规划，而不需要重新训练多终点模型。
4.1初始节点数量和位置对完成率的影响
在8×8的环境中，利用不同的单个起点进行实验，如图6（a），完成率结果如图7所示。可以看出当其他条件一致的情况下，从不同的起点开始进行训练，其结果完成率也有所不同。对于与终点相距最远的初始点(8,1)，由于从该节点出发的智能体到达终点需要走过的格点数量更多，相应的完成率也有所提升。同时在收敛后的路径周围的部分格点也能够由于探索阶段和些许利用阶段的随机动作产生的数据以及靠近收敛路径的便利性使其能够成为提升模型完成率的一部分。对于初始点在(8,8)的情况，由于其到达终点的路径集中在环境的上半部分，所以完成率较低，最高也只有0.62。由于强化学习过程在探索阶段的随机性，在相同的条件下，每次训练结果都不尽相同，探索得相对充分时，相应训练完成后的完成率结果也相对较好。
在8×8的环境中，利用不同的两个起点进行实验，如图6（b），完成率结果如图7所示。当初始点数量提升了之后，在训练时间相同的条件下，模型的完成率也得到了一定的提升，并且已经出现能够保证所有格点都能到达终点的模型。从一个初始点增加到两个初始点的训练过程，提升了智能体对环境的感知范围，提升了给予网络学习的数据的丰富性，第二个初始点周围的环境数据在只有一个初始点时是难以获得的边缘数据，缺乏数据支撑的模型难以为这部分格点提供到达终点的有效策略。从表2未完成节点的统计也能看出，当初始点为其中两个角落时，另一个角落的格点不能完成的概率较大，因为那一部分的格点数据是缺失的，对模型来说是未知的领域。
在8×8的环境中，利用不同的多个起点进行实验，完成率结果如图7和表3所示。当初始点的数量进一步提升之后，模型的完成率也随之升高到0.9以上，即智能体以大部分格点作为起点已能够到达终点。未完成格点的次数下降到50%以下，这主要是智能体在训练过程中的路径选择不同带来的影响。表3所示的第一列，初始点分别占了三个角落，最后得出的模型未完成次数前三名的格点多数分布在右下角(8,1)格点周围。以该格点作为起点，到达终点可通过三条不同的路径，如图6（c）所示路径①②③，其中格点(7,3)在路径②上，(7,1)和(6,1)在路径①上，可以看出在该初始点下模型倾向于通过路径③移动到终点。随后在三个初始点的基础上继续增加前述实验中未完成次数较多的格点作为初始点，构成四个初始点的训练实验，其结果如表3二、三、四列，但最后的效果却提升甚微。
综上所述，初始点数量的提升增加了智能体在训练过程中接触的数据种类，扩大了智能体对环境的感知范围，对智能体在单一环境下的强化学习模型的泛化性能有提高的作用。同时在数量限制的条件下，初始点位置的选择对模型完成率有一定的影响，但随着初始点数量的提升，这种影响也会逐渐降低。
4.2单终点路径规划
多起点单终点的路径规划求解等价于提升对单起点单终点路径规划算法的泛化性能，即在训练过程中增加初始点的数量。针对路径规划问题，初始点的选取有两种方式，基于规则挑选和随机挑选。基于相关性低规则的挑选通常选取地图四角作为初始点进行训练，这种方式在地图规模较小时能起到较好的作用，而在地图较大环境较复杂时表现较差，且选取与环境中障碍物位置相关，操作繁琐；随机挑选不能保证起点的相关性低，所以数据丰富度相对较低，但选取的简便性使得随机挑选可以通过增加初始点数量规避这点。在后续的实验中，采用随机初始点的训练方法在每完成一次训练后会随机生成一个新的起点。面对较大的环境，可通过划分环境区域的训练方式，如图8（c）所示。在训练过程中不断扩大初始点所在的区域同时逐渐地提升与终点的距离，越靠近终点的区域训练过程越简单高效，同时靠近终点的区域的训练结果也能为后续远离终点区域的训练提供先验的知识，以提高较远距离区域的训练效率[22]。
在改进的DQN算法下，分别对10×10、30×30和60×60的环境进行单终点的完成率测试实验。10×10 的环境如图8（a）所示，是随机生成的复杂地图。对单、双、三起始点和随机起点的模型分别进行了训练以及测试，得到的完成率如图9所示。相较于简单且规则的8×8大小的环境，在较复杂的环境下，模型的收敛所需的时间更长。单起始点和双起始点模型的训练曲线在训练中期时波动明显，这是由于缺乏丰富的环境信息造成对环境某一部分的决策敏感，即每当模型参数更新时都可能对这部分的决策造成影响，在训练的后期，模型逐渐收敛。从图8可以看出无论是哪种训练方式，完成率曲线都有较为明显的阶梯变化过程，这与环境的障碍分布相关，随机分布的障碍可能将环境划分为多个区域，同一个区域内的格点前往终点的策略是相近的。当模型训练出了区域内的其中一个格点到达终点的路径后，区域内的其他大部分格点也能通过这条路径到达终点，从而实现完成率阶梯式提升。最后，就收敛效率来说，三起始点模型的收敛效率最高，其次是随机起点模型，随机起点由于无法控制选取起始点的有效性，可能产生对模型收敛收效甚微的训练步，从而影响其收敛的效率。
30×30的环境是随机生成的复杂地图，如图8(b)所示。由于环境较大，包含的格点数量过多，本文没有将每一网格训练后的完成率以曲线的形式展示，而是选取了特定的训练步数统计了不同训练进程中不同模型的完成率数值，如图10所示。在较大较复杂的环境中，单起点模型（曲线单起点1）难以收敛，完成率保持在较低的水平，这与终点位置刁钻有较大关系。为了提高模型的收敛效率，在通往终点的小径外部(0,23)位置设置了一个辅助初始点，通过这个辅助初始点模型能够提前学习到终点周围的格点该如何到达终点，这为模型在初始点较远的策略提供了一个有效的先验知识，模型只需指引智能体到达终点附近的位置，即可通过这个先验的知识到达终点。该方法的完成率（曲线单起点2）相较于前者有了大幅提高，最终完成率在0.6左右波动。三起点1模型的完成率曲线与单起点2差不多一致，这是由于以右下角红色格点为起始点的情况均未能够到达终点，即模型收敛不完整，缺少针对右下角大部分格点的策略，所以完成率与单起始点类似。调整右下角初始点位置到(29,23)，模型的训练曲线为三起点2，相比未改变位置的情况完成率整个训练过程中都有明显的提升，并最终稳定在0.9左右。随机起点模型的曲线与三起点2相近，不过在训练次数较低时完成率较低。确定的单起点或三起点模型虽然在大规模复杂环境下也能有较好的性能，但是需要寻找适当的初始位置，显得过于繁琐。而随机起始点的效果也不错且操作简便，不失为大规模环境下一种较好的起始点选取方法。
60×60的环境如图8（c）所示，环境的规模和复杂度相较于前两者环境更进一步，若使用特定的少量起始点训练方法，模型将难以收敛且计算消耗大、效率低。增加特定初始点数量也会同时增加选取时的试错成本，确定合理的初始点位置才能有效的提升模型的完成率。所以在规模更大、更复杂的环境下，本文采用随机起点的训练方法，同时对环境进行如图7（c）所示的区域划分，以提高模型的收敛效率。训练的结果如图11所示，由左图奖励曲线可以看出在分区域的训练方式下，模型更快地开始收敛且平均奖励更高。在右图的完成率曲线看来，分区域训练的模型在初期较快就能获得一个较高的完成率，最后的完成率结果也相近。
4.3多终点路径规划实验
相较于单终点，多终点的路径规划问题包含的多个不同终点导致了智能体在相同的位置因为目标的不同会产生不同的状态和奖励，这使得传统以智能体的当前位置或者基于卷积神经网络的以智能体周围视野作为状态输入的方法难以取得较好的效果。同时因为多个终点之间的策略不相容性，无法对比多约束的问题采用帕累托最优[31]的方法进行求解。所以针对多终点路径规划的深度强化学习求解，本文提出两步求解的方法：
①多目标问题转换为单目标问题。将智能体的运行策略以到达多个终点的多目标策略转换为以到达任意一个终点的单目标策略，无论到达哪个终点都给予奖励，并且在智能体状态中加入终点坐标，即使在同一位置，不同的终点也代表智能体的不同状态。初始点随机选取得出，终点则依次变更，通过初始点和终点即可依据式（4）计算出智能体的初始状态，并将终点坐标加入状态中构成12维向量如式（13）。模型通过状态给出动作，智能体依据动作运行到下一状态，同时更新自身参数，依次循环往复直到抵达终点或者超过最大运行步数。接下来随机选取起始点，同时变更终点，计算出新一轮的初始状态并开始新一轮强化学习模型的训练，如此循环至模型收敛到满意的结果。
②对模型进行扩展。每当有新的终点加入环境时，以该终点为目标通过4.2节的方法构建其高完成率的模型，并尽量保证其他的终点都包含在可完成格点中。在智能体运行时，根据目标终点选取相应的模型的策略，在到达终点后便以当前终点为新的起点，同时更换下一个目标终点及相应的策略模型，以满足更换终点后的路径规划，通过以上方式可实现多终点的AGV路径规划，并有着良好的扩展性。
分别在10×10、30×30和60×60的复杂环境下进行了4终点、4终点和10终点的路径规划实验，结果如图12和表3所示。图12（a）、（b）、（c）展示了整体环境，其中深红色的格点代表该环境中AGV的终点目标，以不同颜色的格点搭配黑色的引导线显示了AGV在训练结果模型指引下通往不同终点的路径。可以看出基于本文提出的方法，在不同的环境下训练得到的模型具有良好的路径规划能力，均能有效地引导AGV前往位置不同的终点，且与终点的选取顺序无关。将本文提出的算法与传统路径规划A*算法和RRT算法的比较，可以看出在求解的路径步数上，改进DQN算法规划的路径大部分略逊于A*算法，稍好于RRT算法，少量规划的路径能好于A*算法，证明了改进DQN算法在多起点多终点路径规划上的可行性。
在30×30的环境中对模型进行扩展，增加格点(16,2)作为终点，具体参数设置见表3。利用4.2节的方法对终点为(16,2)的模型进行训练，训练结果的奖励函数曲线如图13(a)所示，将训练完成的模型与原模型结合对多终点环境进行路径规划，规划的结果如图13(b)所示。从路径规划的结果可以看出在新增终点后，通过训练单终点模型对原模型进行扩展，包含新终点环境下的多终点路径规划问题也能够有效解决。
5 结束语
本研究在基于深度强化学习的AGV路径规划基础上，通过实验验证了在AGV路径规划中，初始点数量和位置的选择能够影响深度学习训练模型的泛化性能，适当地提高初始点数量并且选择合适的位置可以有效提高模型的完成率；并提出一种基于DQN的多终点AGV路径规划算法，通过提升环境构建中状态的表示维度和训练过程中初始点的数量以及选取方式，有效地提升了DQN算法在同一环境下路径规划问题求解上的泛化性能；最后在此基础上针对多终点AGV路径规划问题在不同规模下的环境都进行求解，并对模型的扩展性进行了验证，验证了该算法对不同的环境都能够给出一个较好的路径规划结果。
虽然所提出的算法为求解多终点路径规划问题提供了一种基于深度强化学习DQN的方案，但也存在进一步改进的空间。在后续的研究中可针对路径的规划对算法进行改进，以减少一些冗余的路径；其次当前考虑的实验环境相较实际还是属于简化的理想环境，可以再考虑动态或者多AGV环境下的算法构建和改进。
[1] Liu W M. The Research of AGV path planning and scheduling system[D]. Guangzhou: South China University of Technology, 2016.
[2] Sun Y J, Zhao N. Centralized scheduling approach for multi-AGV system based on digital twin[J]. Computer Integrated Manufacturing Systems, 2021, 27(2): 569-584.
[3] Li K P, Liu T B, Ruan Y Q. Research on intelligent AGV routing scheduling with applications in semi-conductor production[J]. Computer Integrated Manufacturing Systems, 2021, (in press): 1-17.
[4] Wang C, Mao J. Summary of AGV path planning[C]//3rd IEEE International Conference on Electronic Information Technology and Computer Engineering(EITCE), Piscataway: IEEE, 2019: 332-335.
[5] Shi W R, Huang X H, Zhou W. Path planning of mobile robot based on improved artificial potential field[J]. Journal of Computer Application, 2010, 30(08): 2021-2023.
[6] Xu F. Research on robot obstacle avoidance and path planning based on improved artificial potential field method[J]. Computer science, 2016, 43(12): 293-296.
[7] Chen W D, Zhu Q G. Mobile robot path planning based on fuzzy algorithms[J]. Acta Electronica Sinica, 2011, 39(04): 971-974+980.
[8] Wang H B, Yi P H, Deng W, et al. Mobile robot path planning based on improved A* algorithm and dynamic window method[J]. Robot, 2020, 42(03): 346-353.
[9] Le A T, Bui M Q, Le T D, et al. D Lite with Reset: Improved Version of D Lite for Complex Environment[C]//2017 First IEEE International Conference on Robotic Computing (IRC), Piscataway: IEEE, 2017: 160-163.
[10] Santiago R M C, Ocampo A L D, Ubando A T, et al. Path planning for mobile robots using genetic algorithm and probabilistic roadmap[C]//2017IEEE 9th International Conference on Humanoid, Nanotechnology, Information Technology, Communication and Control, Environment and Management (HNICEM), Piscataway: IEEE, 2017: 1-5.
[11] Sun J, Yu Y, Xin L. Research on Path Planning of AGV Based on Improved Ant Colony Optimization Algorithm[C]//2021 33rd Chinese Control and Decision Conference (CCDC), Piscataway: IEEE, 2021: 7567-7572.
[12] Zhang T, Wang J, Meng M Q H. Generative Adversarial Network Based Heuristics for Sampling-Based Path Planning[J]. IEEE/CAA Journal of Automatica Sinica, 2022, 9(1): 64-74.
[13] Garaffa L C, Basso M, Konzen A A, et al. Reinforcement Learning for Mobile Robotics Exploration: A Survey[J]. IEEE Transactions on Neural Networks and Learning Systems, 2021(Early Access): 1-15.
[14] Yu J B, Liu G D, Xu J P, et al. A Hybrid Multi-Target Path Planning Algorithm for Unmanned Cruise Ship in an Unknown Obstacle Environment[J]. Sensors, 2022, 22(7), 2429.
[15] Liu H Y, Jiang X, Ju H H, et al. Multi-Goal Path Planning Algorithm for Mobile Robots in Grid Space[C]. 25th Chinese Control and Decision Conference (CCDC) , Piscataway: IEEE, 2013: 2872-2876.
[16] Janos J, Vonasek V, Penicka R. Multi-Goal Path Planning Using Multiple Random Trees[J]. Ieee Robotics and Automation Letters, 2021, 6(2): 4201-4208.
[17] Yu J, Wang Y, Ruan X, et al. AGV multi-objective path planning method based on improved cuckoo algorithm[C]// 2019 IEEE 4th Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), Piscataway: IEEE, 2019: 556-561.
[18] Lv Q, Yang D. Multi-target path planning for mobile robot based on improved PSO algorithm[C]//2020 IEEE 5th Information Technology and Mechatronics Engineering Conference (ITOEC), Piscataway: IEEE, 2020: 1042-1047.
[19] Kim C, Nguyen Huy H, Kim D H, et al. Path planning for automatic guided vehicle with multiple target points in dynamic environment[C]// 2nd International Joint Conference on Advanced Engineering and Technology, France: EDP Sciences, 2018: 02029.
[20] Zhu X H, Yan B, Yue Y. Path Planning and Collision Avoidance in Unknown Environments for USVs Based on an Improved D* Lite[J]. Applied Sciences-Basel, 2021, 11(17): 7863.
[21] Panov A I, Yakovlev K S, Suvorov R. Grid Path Planning with Deep Reinforcement Learning: Preliminary Results[J]. Procedia Computer Science, 2018, 123: 347-353.
[22] Lei X Y, Zhang Z, Dong P. Dynamic Path Planning of Unknown Environment Based on Deep Reinforcement Learning[J]. Journal of robotics, 2018, 2018(1): 5781591.1-5781591.10.
[23] Wu X M. Research on path planning algorithm based on deep reinforcement learning[D]. Changchun: Changchun University of Science and Technology, 2020.
[24] Meng C Y, Hao C Q, Li R, et al. Research on AGV path planning method in complex environment based on imptoved DDPG algorithm[J]. Application Research of Computers, 2022, 39(3): 681-687.
[25] Wang B, Liu Z, Li Q, et al. Mobile Robot Path Planning in Dynamic Environments Through Globally Guided Reinforcement Learning[J]. IEEE Robotics and Automation Letters, 2020, 5(4): 6932-6939.
[26] Guo X D, Ren Z G, Wu Z Z, et al. A Deep Reinforcement Learning Based Approach for AGVs Path Planning[C]. Chinese Automation Congress (CAC) , Piscataway: IEEE, 2020: 6833-6838.
[27] Xin J, Zhao H, Liu D, et al. Application of deep reinforcement learning in mobile robot path planning[C]// 2017 Chinese Automation Congress (CAC), Piscataway: IEEE, 2017: 7112-7116.
[28] Mnih V, Kavukcuoglu K, Silver D, et al. Playing Atari with Deep Reinforcement Learning[C]//Processdings of the NIP Workshop on deep learning. Lake Tahoe: MIT Press, 2013: 201-210.
[29] Pan X, Wang W, Zhang X, et al. How you act tells a lot: privacy-leakage attack on deep reinforcement learning[C]// 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS). New York: Assoc Computing Machinery, 2019: 368-376.
[30] Tamar A, Yi W, Thomas G, et al. Value Iteration Networks[C]//Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI), San Francisco: Margan Kaufmann, 2017: 4949-4953.
[31] Yang C, Zhang T, Pan X, et al. Multi-objective mobile robot path planning algorithm based on adaptive genetic algorithm[C]// 2019 Chinese Control Conference (CCC), Piscataway: IEEE, 2019: 4460-4466.