基于算法融合的多机器人多目标路径规划研究

Research on multi-robot multi-objective path planning based on algorithm fusion

摘要

针对多机器人多目标路径规划问题，提出基于算法融合的多机器人多目标路径规划算法.算法采用改进A^*算法进行全局路径规划，采用改进模拟退火算法规划多机器人在组合全局路径最优的情况下，保证最远机器人路径最短，采用DWA算法进行局部路径规划，实现机器人局部运动避障.为了验证所提算法的可行性和优越性，对其进行仿真实验，实验结果表明，改进A^*算法比经典A^*算法在转弯次数、转弯角度、遍历节点、规划距离分别减少16.66%、41.24%、23.3%、0.77%，改进模拟退火算法与传统模拟退火算法在仿真时间、最长路径长度、总路径分别减少12.09%、22.26%、5.74%,DWA算法能够实现多机器人局部路径规划与避障.

关键词

多机器人 / 多目标 / A^*算法 / 模拟退火算法 / 路径规划 / DWA算法

Key words

multi - robot / multi - objective / A^* algorithm / simulated annealing algorithm / path planning / DWA algorithm

随着对机器人路径规划研究不断的深入，机器人路径规划可分为全局路径规划和局部路径规划，其中，全局路径规划常用算法包括基于图搜索的Dijkstra算法^［1］、A^*算法^［2］、D^*算法^［3］等算法，基于采样的RRT算法^［4］和智能算法如粒子群算法^［5］、遗传算法^［6］、神经网络算法^［7］等算法.局部路径规划算法包括人工势场法^［8］、动态窗口算法（DWA）^［9］、时间弹性带算法（TEB）^［10］等算法.全局路径规划是对静态地图进行最优路径规划，无法满足真实环境下的路径规划，而基于局部规划的方法可能会导致路径局部最优而不是全局最优，从而限制了机器人的导航能力^［11］.针对这种情况，单一算法已经无法满足人们对复杂环境应用的需求，全局路径规划与局部路径规划融合算法研究进入机器人路径规划研究的热门核心.其中，A^*与人工势场融合算法能够实现机器人全局路径与局部路径规划，但是人工势场法容易陷入局部最小值问题^［12］.A^*与DWA融合算法能够实现局部路径规划，但A^*算法还存在冗余节点需要进一步优化^［13］.A^*与智能算法融合算法复杂度太高，规划时间较长，效率不高^［14］.这些算法大多应用在一个机器人完成一个任务的功能需求上，而在多机器人多任务中的应用较少.

针对多机器人多任务分配问题，求解算法有单品拍卖和组合拍卖方式，单品拍卖容易陷入局部最优问题，很难求出全局最优解，其中组合拍卖是常用的一种典型的组合优化问题求解算法，常用的组合拍卖算法有遗传算法、模拟退火算法等算法^［15-16］.对于任务分配问题，Otte等^［17］提出了拍卖算法解决多机器人任务分配问题，并对各种拍卖算法进行对比，评估了在不同的拍卖目标以及不同通信模型下系统拍卖绩效；严李平等^［18］提出一种基于CVT和模拟退火的多机器人均匀部署算法，通过模拟退火算法进行机器人部署，验证算法的有效性.杨玮等^［19］提出了变邻域模拟退火算法构建多任务多目标优化模型，通过领域扰动拓展搜索范围结合概率突变特性跳出局部最优；孟浩德等^［20］提出了基于改进的模拟退火算法与A^*算法相结合的多目标路径规划方法，在复杂环境下多目标遍历路径规划拥有良好的效果，不易陷入局部最优.

本文基于多机器人多任务路径规划问题，提出算法融合的多机器人多任务路径规划算法，算法采用改进A^*算法进行全局路径规划，采用改进模拟退火算法规划多机器人在组合全局路径最优的情况下，保证最远机器人路径最短，采用DWA进行局部路径规划，实现机器人局部障碍物避障.

1 A^*算法仿真

1.1 经典A^*算法

A^*算法最早在1968年论文《A Formal Basis for the Heuristic Determination of Minimum Cost Paths》^［21］中被首次提出，A^*算法是启发式搜索算法，A^*算法将广度优先搜索（BFS）和Dijkstra算法相结合，引入启发式函数，以此来衡量实时搜索位置和目标位置的距离关系，使搜索方向优先朝向目标点所处方向，最终达到提高搜索效率的效果.

A^*算法栅格估价函数如公式（1）所示.

f ( n ) = g ( n ) + h ( n ).（1）

式中f（n）为第n个栅格的总代价，g（n）是初始栅格到第n个栅格的实际代价，h（n）是第n个栅格到目标栅格的预估代价.

1.2 改进A^* 算法

为了进一步提高搜索效率和搜索节点数，本文采用A^* - 曼哈顿距离算法和A^* - 切比雪夫距离算法相融合的距离算法，通过动态加权，实现算法优势互补，优化节点与搜索效率.改进后的距离策略如公式（2）所示.

d = \alpha d_M + \beta d_C.（2）

其中，d是本文采用的距离计算方式， d_M是当前节点和目标点的曼哈顿距离， d_C是当前节点和目标点的切比雪夫距离， \alpha， \beta为动态权重因子.

坐标差积S的计算如公式（3）所示.加权函数w（n）如公式（4）所示.

S = \left(x_g-x_c\right) \times \left(y_g-y_c\right).（3）

w ( n ) = \left(\mathrm{1}+d/S\right).（4）

式（3）中， \left(x_g,y_g\right)是目标点的横纵坐标， \left(x_c,y_c\right)是机器人所在位置的当前横纵坐标.

优化后的评估函数如公式（5）所示.

f ( n ) = g ( n ) + h ( n ) \times w ( n ).（5）

其中加权函数为w（n）.

1.3 冗余节点优化

经典A^*算法是由连续搜索节点组成，势必冗余不必要节点，增加机器人转弯次数，影响机器人运行效果，因此需要删除冗余节点，冗余节点优化分为2步.

1） 根据A^*算法搜索节点进行遍历，依次选取3个节点，并把第1个节点与第3个节点连接，判断连线与障碍物的距离，当连线与障碍物距离小于设定的安全距离时，说明路径规划不满足要求，保留第2个节点.当连线与障碍物距离大于设定的安全距离时，说明线路规划成功，删除中间节点.

2） 依次循环，直至遍历所有节点，保留剩余节点，生成路径.

1.4 算法仿真

建立栅格地图如图1所示，其中黑色是障碍物，蓝线为算法规划路径，灰色为算法遍历节点.对经典A^*算法和改进后的A^*算法进行仿真，其中，图1a是经典A^*算法仿真，图1b是改进A^*算法仿真.

从图1和表1可知，改进A^*算法相较于经典A^*算法在转弯次数方面减少了16.66%，有效减少因频繁转向而造成的能耗与时间损耗.在转弯角度上减少了41.24%，规划路径更加平滑.遍历节点数减少23.3%，算法搜索效率得到一定的提升，避免大量冗余节点的无效探索，极大地节省了计算资源.规划距离减少了0.77%，改进A^*算法能够规划出一条更优路径.根据数据表明，改进算法在转弯次数、转弯角度、遍历节点和规划距离方面都有一定的优化.

2 模拟退火算法

2.1 目标任务分配

多机器人多任务目标分配问题是指把多目标任务分配给多各机器人，在多种组合中使得机器人全局总路径最优.本文研究机器人与任务目标数量相同，并且每个机器人只能选择一个目标任务的情况^［18］.假设机器人和任务数量都为N，每个机器人到任务目标点的距离定义为L，则机器人任务的代价矩阵可表示为公式（6）.

\mathit{L} = \left[\begin{array}{l}{L}_{\mathrm{11}}{L}_{\mathrm{12}}\cdots L_{\mathrm{1}\mathrm{N}}\\ L_{\mathrm{21}}{L}_{\mathrm{22}}\cdots L_{\mathrm{2}\mathrm{N}}\\ ⋮⋮\cdots ⋮\\ L_{\mathrm{N}\mathrm{1}}{L}_{\mathrm{N}\mathrm{2}}\cdots L_{\mathrm{N}\mathrm{N}}\end{array}\right].（6）

2.2 模拟退火算法

模拟退火（simulated annealing，SA）算法是一种概率型优化算法，启发式的随机寻优算法，是对局部搜索算法的扩展，是基于固体物质退火过程与组合优化问题相似性，提出的一种通用优化算法^［18］.SA算法主要包括升温过程、等温过程和冷却过程，升温过程对应算法初始状态，等温过程对应Metropolis准则抽样过程，冷却过程对应降温状态，其中Metropolis准则以一定概率接收恶劣解，使算法能够跳出局部最优，保证SA算法能够找到全局最优解^［19］.模拟退火算法目标函数F（S）如式（7）所示，概率P如式（8）所示.

F ( S ) = {\displaystyle \sum _i^n} L(i,x(i)).（7）

P = {\mathrm{e}}^{(\frac{-\left|F({\mathrm{S}}^{\text{'}})-F(\mathrm{S})\left|\right.\right.}{T_t})}.（8）

其中，T {}_t为衰减函数， L ( i , x ( i ) )为第i个机器人对应的任务代价.

2.3 算法仿真对比

根据模拟退火算法，创建25 × 25的栅格地图，在栅格地图中分别创建6个机器人与任务目标点，如图所示，6个机器人初始坐标为（3，1），（23，16），（15，2），（8，9），（16，8），（3，22），6个机器人目标坐标为（16，20），（16，24），（20，20），（20，24），（24，20），（24，24），黑色栅格表示静态障碍物.根据改进A*算法对每个机器人到每个目标位置进行全局路径规划，规划距离如表2所示.

R ₁ ~ R ₆代表机器人序号，M ₁ ~ M ₆代表任务目标序号.针对A*算法进行全局路径规划后，对组合优化算法单物品拍卖、遗传算法、模拟退火算法分别进行仿真，如图2所示.

从图中可看出，3种算法都能够找到规划路径，3种算法的规划路径总长度与仿真时间，如表3所示.

从图2和表3可知，模拟退火算法比单物品拍卖算法在仿真时间、规划路径总长度分别减少24.56%、3.08%，而最长路径长度增加了12.75%；比遗传算法在仿真时间减少99.06%，规划路径总长度、最长路径长度两种算法相同.单物品拍卖算法无法找到全局最优路径，遗传算法仿真时间较长，模拟退火算法在保证全局路径最优的情况下，无法保证最长距离最短，综合考虑，本文选用模拟退火算法作为路径分配算法，需要进一步优化算法.

3 改进模拟退火算法

传统模拟退火算法在路径规划总长度和仿真时间上要优于其他2种算法，传统模拟退火算法能够找到全局最优总路径，但是，不能保证在全局总路径最优的情况下，机器人最长路径也是最短的，需要对传统模拟退火算法进行改进.

3.1 改进目标函数

重新构造目标函数，把机器人最长路径约束加入到目标函数中，优化目标函数，如公式（9）所示.

\left\{\begin{array}{l}\mathrm{F}(x)={\displaystyle \sum _i^n}L(i,x(i));\\ \mathrm{m}\mathrm{i}\mathrm{n}(\mathrm{m}\mathrm{a}\mathrm{x}(M)).\end{array}\right. （9）

式中，M为分配好的任务序列，max（M）为任务序列中最大的任务.

改进模拟退火步骤如下：

Step 1：初始化：设定初始温度T、最大迭代次数M、每个T下迭代次数K，并任取初始解S.

Step 2：算法迭代：随机扰动当前解x生成新解x'，计算当前解x和新解x'的目标函数值F（x）和F（x'）.如果F（x） > F（x'），则接受新解x'.如果F（x） < F（x'），则以概率P接受新解x'，否则保留当前解x；并进行判断全局最优路径中机器人最长路径的长度，直至找到最短路径，并更新最短路径.

Step 3：降温策略：按照公式（10）的降温策略降低温度T.

T_t = \alpha T_{t-\mathrm{1}}.（10）

其中α为常数，可以取值为 0.5~0.99， T_{t-\mathrm{1}}是当前迭代温度.

Step 4：算法停止：当温度降到预定值或者达到最大迭代次数时，停止算法.

3.2 改进模拟退火算法仿真

根据改进的模拟退火算法，仿真如图3所示，其中图3a是改进退火算法仿真图，图3b是路径平滑处理仿真图.

各改进算法仿真时间、最大路径和总路径进行对比，如表4所示.

从图3和表4可知，改进模拟退火算法与传统模拟退火算法在仿真时间、最长路径长度、总路径分别减少1.39%、16.07%、0%；路径平滑处理后与传统模拟退火算法在仿真时间、最长路径长度、总路径分别减少12.09%、22.26%、5.74%.数据表明，改进及平滑处理后的算法在各方面较传统模拟退火算法均有明显优化.

4 DWA算法

4.1 改进DWA算法

A^*算法只完成全局路径规划，对于复杂未知环境A^*算法无法正常规划路径，就需要根据具体的环境采用合适的局部路径规划算法.DWA算法其原理是对线速度和角速度建立运动学模型，充分考虑机器人运动中的速度、加速度等物理属性限制约束条件，并对速度空间进行多组采样，模拟多组速度在一定时间内的一簇运动轨迹，再通过评价函数选取最优的轨迹和速度，实现机器人局部路径规划^［22］.

4.1.1 机器人运动学模型

巡逻机器人采用差分运动，规定机器人只有X方向的线速度，和Z轴的旋转角速度.在时间很短的一段运行轨迹中，可以把机器人运动看成直线运动^［23］.假定很短的一段时间 ∆ t，以恒定的速度 v做直线运动，建立运动学模型如公式（11）所示.

\left\{\begin{array}{c}{x}_{t+\mathrm{1}}=x_t+v∆t\mathrm{c}\mathrm{o}\mathrm{s}{\alpha }_t;\\ y_{t+\mathrm{1}}=y_t+v∆t\mathrm{s}\mathrm{i}\mathrm{n}{\alpha }_t;\\ {\alpha }_{t+\mathrm{1}}={\alpha }_t+w∆t.\end{array}\right. （11）

式中， x_t、 y_t、 {\alpha }_t是机器人当前的位置与方向角； x_{t+\mathrm{1}}、 y_{t+\mathrm{1}}、 {\alpha }_{t+\mathrm{1}}是机器人下一时刻的位置与方向角. v和 w是t时刻的线速度与角速度.公式表明在一定的时间窗口内，机器人的位姿是由当前速度与航向角共同决定，由于不同的速度和航向角组合可以产生不同的机器人位姿，形成不同的运动轨迹.由于速度和航向角不受任何条件的约束，这种组合可以达到无数种，显然不是设计的目标，需要进行速度约束来优化机器人运动.

4.1.2 速度采样

速度采样就是为了能够把采样区间控制在一定的范围内，以生成若干组有限的速度和加速度组合，建立机器人约束条件^［24］.

1） 速度、角速度约束条件

机器人根据自身条件和运动环境，建立最小、最大速度和角速度约束条件，如公式（12）所示.

\left\{\begin{array}{c}{v}_{\mathrm{m}\mathrm{i}\mathrm{n}}\le v\le v_{\mathrm{m}\mathrm{a}\mathrm{x}};\\ w_{\mathrm{m}\mathrm{i}\mathrm{n}}\le w\le w_{\mathrm{m}\mathrm{a}\mathrm{x}}.\end{array}\right. （12）

式中， v_{\mathrm{m}\mathrm{i}\mathrm{n}}、 v_{\mathrm{m}\mathrm{a}\mathrm{x}}是最小和最大速度， w_{\mathrm{m}\mathrm{i}\mathrm{n}}、 w_{\mathrm{m}\mathrm{a}\mathrm{x}}是最小和最大角速度.

2） 加减速约束条件

机器人由于电机性能影响，存在最大加减速度的限制，建立机器人加减速约束条件，如公式（13）所示.

\left\{\begin{array}{c}{v}_c-a_{\mathrm{m}\mathrm{i}\mathrm{n}}∆t\le v\le v_c+a_{\mathrm{m}\mathrm{a}\mathrm{x}}∆t;\\ w_c-a_{\mathrm{m}\mathrm{i}\mathrm{n}}∆t\le w\le w_c+a_{\mathrm{m}\mathrm{a}\mathrm{x}}∆t.\end{array}\right. （13）

式中， v_c、 w_c、 a_{\mathrm{m}\mathrm{i}\mathrm{n}}、 a_{\mathrm{m}\mathrm{a}\mathrm{x}}分别表示当前速度、当前角速度、机器人最大减速度和最大加速度.

3） 刹车距离约束条件

基于机器人运动的安全性，在机器人运动到障碍物时，需要在一定的距离内使机器人运动停止，完成刹车避免机器人与障碍物发生碰撞.建立机器人刹车距离约束条件^［25］，如式（14）所示.

v \le \sqrt[]{\mathrm{2}\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\left(v,w\right)\times a_{\mathrm{m}\mathrm{i}\mathrm{n}}}.（14）

式中， \mathrm{d} \mathrm{i} \mathrm{s} \mathrm{t} \left(v,w\right)是机器人在速度组合为 \left(v,w\right)对应的轨迹与障碍物的最小距离.

4.1.3 传统评价函数

速度采样获得若干可行的速度组合轨迹，通过评价函数对这一簇的轨迹进行打分，筛选出最优的路径，建立评价函数方程如公式（15）所示.

G \left(v,w\right) = \sigma ( \alpha \mathrm{h} \mathrm{e} \mathrm{a} \mathrm{d} \left(v,w\right) + \beta \mathrm{d} \mathrm{i} \mathrm{s} \mathrm{t} \left(v,w\right) + \gamma \mathrm{v} \mathrm{e} \mathrm{l} ( v , w ) ).（15）

式中， \sigma是平滑函数， \alpha、 \beta、 \gamma是各函数的加权因子. \mathrm{h} \mathrm{e} \mathrm{a} \mathrm{d} \left(v,w\right)是航向角评价函数，是机器人当前速度组合下的位置与目标点所成夹角，该角度值越小，则方位角评价函数值越高，该速度组合对应的运动轨迹越好. \mathrm{d} \mathrm{i} \mathrm{s} \mathrm{t} \left(v,w\right)是障碍物距离评价函数.设dist为速度组合 \left(v,w\right)对应的轨迹曲线与障碍车的最小距离，数值越大，则评价函数值越高，表明此速度组合对应的运动轨迹越好. \mathrm{v} \mathrm{e} \mathrm{l} ( v , w )是速度评价函数.机器人正常行驶过程中与目标速度越接近越好.

4.1.4 改进评价函数

评价函数是机器人路径选择的决定性因素，传统DWA算法是基于局部路径，通过航向角、障碍物距离和速度评价函数来评价路径轨迹，忽略了全局路径对机器人的引导作用^［26］，本文在此基础上引入全局路径评估函数，改进机器人路径选择.改进后的评估函数如式（16）所示.

\mathrm{G} \left(v,w\right) = \sigma ( \mathrm{\alpha } \mathrm{h} \mathrm{e} \mathrm{a} \mathrm{d} \left(v,w\right) + \beta \mathrm{d} \mathrm{i} \mathrm{s} \mathrm{t} \left(v,w\right) + \gamma \mathrm{v} \mathrm{e} \mathrm{l} \left(v,w\right) + \delta \mathrm{p} \mathrm{a} \mathrm{t} \mathrm{h} \left(v,w\right) ).（16）

式中， \delta是权重因子， \mathrm{p} \mathrm{a} \mathrm{t} \mathrm{h} \left(v,w\right)是全局路径评估函数.

4.1.5 归一化

为了统一各评价函数的占比优势，使没有可比性的评价函数变得具有可比性，对各评价函数进行归一化处理，归一化处理方程如公式（17）所示.

\left\{\begin{array}{l}\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{a}\mathrm{l}\_\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{d}\left(i\right)=\frac{\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{d}\left(i\right)}{{\sum }_{i=\mathrm{1}}^n\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{d}\left(i\right)};\\ \mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{a}\mathrm{l}\_\mathrm{d}\mathrm{i}\mathrm{s}\left(i\right)=\frac{\mathrm{d}\mathrm{i}\mathrm{s}\left(i\right)}{{\sum }_{i=\mathrm{1}}^n\mathrm{d}\mathrm{i}\mathrm{s}\left(i\right)};\\ \mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{a}\mathrm{l}\_\mathrm{v}\mathrm{e}\mathrm{l}\left(i\right)=\frac{\mathrm{v}\mathrm{e}\mathrm{l}\left(i\right)}{{\sum }_{i=\mathrm{1}}^n\mathrm{v}\mathrm{e}\mathrm{l}\left(i\right)};\\ \mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{a}\mathrm{l}\_\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}\left(i\right)=\frac{\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}\left(i\right)}{{\sum }_{i=\mathrm{1}}^n\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}\left(i\right)}.\end{array}\right. （17）

式中， \mathrm{n} \mathrm{o} \mathrm{r} \mathrm{m} \mathrm{a} \mathrm{l} \_ \mathrm{h} \mathrm{e} \mathrm{a} \mathrm{d} ( i )、 \mathrm{n} \mathrm{o} \mathrm{r} \mathrm{m} \mathrm{a} \mathrm{l} \_ \mathrm{d} \mathrm{i} \mathrm{s} ( i )、 \mathrm{n} \mathrm{o} \mathrm{r} \mathrm{m} \mathrm{a} \mathrm{l} \_ \mathrm{v} \mathrm{e} \mathrm{l} ( i )和 \mathrm{n} \mathrm{o} \mathrm{r} \mathrm{m} \mathrm{a} \mathrm{l} \_ \mathrm{p} \mathrm{a} \mathrm{t} \mathrm{h} ( i )分别为归一化后的航向角、障碍物距离、速度以及全局路径评价函数.

4.2 算法仿真

采用改进A^*算法进行全局路径规划，采用改进模拟退火算法进行组合优化，采用改进DWA进行局部路径，融合算法仿真如图4所示，其中蓝线为DWA局部规划路径，红色虚线为改进A^*算法和改进模拟退火算法进行组合优化后的最优路径.

通过仿真实验表明，融合后的算法能够实现多机器人多任务路径规划.多机器人在本文算法的统筹调配下，能够在栅格地图中精准规划出行进路线.与此同时，DWA算法在局部障碍物避障方面表现卓越的路径规划能力，实时规划避障路径，使机器人能够安全避障.验证了融合算法以及DWA算法在多机器人多任务路径规划与局部障碍物避障应用场景中的可行性.

5 结语

提出一种算法融合的多机器人多目标路径规划算法，采用改进A^*算法实现全局路径规划，采用改进模拟退火算法规划出一条多机器人全局路径组合最优路径，并在全局路径最优的同时保证机器人最长路径的最短.在全局路径规划的基础上使用DWA实现机器人局部路径规划，并对所用算法进行仿真.仿真表明，改进A^*算法与改进模拟退火算法能够规划出一条全局最优路径，并在算法仿真时间、最长路径长度上明显优于其他算法，验证所提算法的优越性，最后针对局部路径规划算法DWA进行仿真，验证了算法的可行性.

参考文献

[1] DUDEJA C， KUMAR P. An improved weighted sum-fuzzy Dijkstra's algorithm for shortest path problem （iWSFDA）［J］.Soft Computing， 2022，26（7）：3217 - 3226.

[2] FAN X C， LING X Y， HUANG H B. Robot path planning based on improved A^* algorithm and artificial potential field method［J］. Artificial Intelligence Technology Research， 2024（2）：36 - 43.

[3] 郑川川，柯福阳，汤琴琴.融合改进D^*与Gmapping算法的自主导航仿真研究［J］.计算机仿真.2023，40（10）：452 - 457 + 518.

[4] ZHANG R， GUO H， ANDRIUKAITIS D， et al. Intelligent path planning by an improved RRT algorithm with dual grid map［J］. Alexandria Engineering Journal， 2024，88：91 - 104.

[5] 莫杰，徐天奇，李琰，基于退火优化粒子群算法的负荷辨识方法［J］.云南民族大学学报（自然科学版），2024，33 （5） ：630 - 637.

[6] 黄荣杰，王亚刚.基于可视图与改进遗传算法的机器人平滑路径规划［J］.控制工程，2024，31（4）：678 - 686.

[7] MILAD N， ESMAEEL K， SAMIRA D. Multi - objective multi - robot path planning in continuous environment using an enhanced genetic algorithm［J］. Expert Systems with Applications， 2019，115（1）：106 - 120.

[8] RAFAL S， TOMASZ T， KRYSTIAN E. Energy efficient local path planning algorithm based on predictive artificial potential field［J］. IEEE， 2022，10（1）：39729 - 39742.

[9] ZHANG L Y， HAN Y， JIANG B. Research on path planning method of unmanned boat based on improved DWA algorithm［J］. Journal of Sensors， 2022，2022：1 - 10.

[10] 郭志军，尹亚昆，李亦轩，融合改进A^*和TEB算法的移动机器人路径规划［J］.河南科技大学学报（自然科学版），2023，44（4）：57 - 65.

[11] TANG Z Z， MA H Z. An overview of path planning algorithms［J］. Iop Conference Series： Earth and Environmental Science， 2021，804（2）：022024.

[12] SANG H Q， YOU Y S， SUN X J， et al. The hybrid path planning algorithm based on improved A^* and artificial potential field for unmanned surface vehicle formations［J］. 2021，223（1）：108709.

[13] YIN X， CAI P， ZHAO K， et al. Dynamic path planning of AGV based on kinematical constraint A^* algorithm and following DWA fusionalgorithms［J］. Sensors， 2023，23（8），4102.

[14] 李三平，袁龙强，吴立国，基于改进融合蚁群算法的移动机器人路径规划［J］.机械设计，2023，40（10）：76 - 84.

[15] 有维宝，徐哲，刘东宁.基于拍卖谈判机制的分布式多技能多项目调度［J］.运筹与管理，2024，33（1）：1 - 8.

[16] 陈剑，孙明月，马文静，基于VCG拍卖的智能车间主动调度机制研究［J］.工业工程与管理，2024，29（1）：1 - 11.

[17] OTTE M， KUHLMAN M J， SOFGE D. Auctions for multi - robot task allocation in communication limited environments［J］.Autonomous Robots， 2010，44（3/4）：547 - 584．

[18] 严李平，吴玉秀，张文忠.基于CVT和模拟退火的多机器人均匀部署［J］.现代信息科技，2022，6（17）：143 - 149.

[19] 杨玮，李然，张堃.基于变邻域模拟退火算法的多自动导引车任务分配优化［J］.计算机应用，2021，41（10）：3056 - 3062.

[20] 孟浩德，吴征天，吴闻笛，基于改进模拟退火算法的灭火小车多目标路径规划［J］.计算机与数字工程，2024，52（2）：394 - 398.

[21] 白俊峰，白一辰，席嘉璐，基于改进A^*算法的车间物料配送路径规划［J］.吉林大学学报（理学版），2024，62（6）：1401 - 1410.

[22] 姜海猛，张志安，潘孝斌.基于A^*与DWA算法的融合优化策略研究［J］.机械与电子，2024，42（10）：15 - 21.

[23] 牛晶，申传艳，张利鹏，基于改进ACO - DWA算法的轮式植保机器人避障路径研究［J］.电子测量与仪器学报，2024，38（5）：188 - 200.

[24] ZHANG W， WANG N X， WU W H. A hybrid path planning algorithm considering AUV dynamic constraints based on improved A^* algorithm and APF algorithm［J］. Ocean Engineering， 2023，285（1）：115333.

[25] FAN X C， YU Y Q， LI T. Research on path planning of patrol robot based on multi - algorithm fusion［J］.Journal of Artificial Intelligence Practice， 2024，7（3）：48 - 61.

[26] KARLIJN F， JOOST V E. Efficient path planning for automated guided vehicles using A^* （Astar） algorithm incorporating turning costs in search heuristic［J］.International Journal of Production Research， 2023，61（3）：707 - 725.

基金资助

安徽省高等学校省级自然科学研究计划项目(2023AH052918)

安徽省高等学校省级自然科学研究计划项目(2024AH050637)

安徽信息工程学院青年科研基金项目(24QNJJJ012)