Application analysis of an enhanced Q-learning genetic algorithm in path planning
-
摘要: 针对传统遗传算法在路径规划中存在转向角度过大、转向次数过多、易陷入局部最优等问题，提出一种改进遗传算法。首先，提出一种改进种群初始化策略，即先确定一个过渡点，生成一条从起点到过渡点的路径和一条从过渡点到终点的路径，再将两条路径首尾相连成一条从起点到终点的路径，以生成优秀初始种群，提高前期搜索效率；其次，采用模拟退火算法与区域划分种群相结合的改进锦标赛选择策略，增加种群多样性，防止陷入局部最优；最后，设计一种Q-learning算法与交叉和变异相结合的策略，通过与环境交互，不断学习并优化动作选择策略以此提高算法的全局搜索能力，得到更优种群。路径规划仿真结果表明：相比传统遗传算法、改进自适应遗传算法和改进灾变遗传算法，本文所提改进遗传算法能减少路径长度和转向角度，降低转向次数，从而搜索到更优的路径。Abstract: An improved genetic algorithm is proposed to address the limitations of conventional genetic algorithms in path planning, such as excessive turning angles, redundant turns, and susceptibility to local optima. First, an upgraded population initialization strategy is proposed. This method selects a transitional point to generate a route from the starting point to the transition point and another from the transition point to the endpoint. The segments are then combined to establish a complete route, thereby forming a high-quality initial population and improving early search efficiency. Second, an enhanced tournament selection approach is utilized, which integrates simulated annealing with region-based population segmentation to increase population diversity and mitigate local optima entrapment. Finally, the Q-learning algorithm is incorporated into crossover and mutation operations, enabling the algorithm to interact with the environment, continuously learn, and optimize its action selection strategy. This integration enhances the algorithm’s global search capabilities, leading to the development of superior populations. As demonstrated by path planning simulations, the proposed enhanced genetic algorithm has the capacity to reduce path length and turning angles, decrease the number of turns, and ultimately identify more optimal pathways when compared to traditional genetic algorithms, enhanced adaptive genetic algorithms, and improved catastrophe genetic algorithms.
-
随着科技的进步和社会的发展，移动机器人智能化和自动化的水平逐步提高，在工业复杂环境和日常居家自动导航等问题上，路径规划问题一直是移动机器人研究领域的重要内容，例如精准分析环境、安全避开障碍物、高效快速抵达目标位置等问题[1-3]。路径规划的主要任务是确定一条路径长度最短、转向角度最小、转向次数最少的无障碍路径到达目的地。路径规划算法主要分为传统路径规划算法、基于采样的路径规划算法和智能仿生优化算法三大类[4-6]。传统路径规划算法包括A*算法[7]、人工势场算法[8]；基于采样的路径规划算法包括RRT(rapidly-exploring random trees)算法[9]、PRM(probabilistic roadmap)算法[10]；智能仿生优化算法包括遗传算法[11]、蚁群算法[12]、神经网络算法[13]。相较传统和基于采样的路径规划算法，智能仿生优化算法通过模拟自然界中的生物行为或进化过程来解决复杂问题，其优势在于能够处理高维度、非线性和多目标优化问题，具有较强的全局搜索能力以及适应复杂环境的能力[14-15]。在智能仿生优化算法中，蚁群算法搜索时间较长、容易陷入局部最优并出现停滞现象。神经网络算法适用于动态复杂环境，但参数调节比较困难。遗传算法的全局搜索能力强且具有与其他算法相结合的扩展性和同时执行多个操作的并行性，不易陷入局部最优，易得到全局最优解[16]。因此本文选用智能仿生优化算法中的遗传算法来解决机器人路径规划问题。
目前国内外诸多学者在改善路径规划问题方面已进行大量研究，白晓兰等[17]提出一种融合粒子群算法、遗传算法和人工势场法的混合遗传算法，解决传统智能算法在多障碍物环境下求解路径时存在忽视路径安全性，易陷入局部最优解等问题。Hao等[18]针对标准遗传算法过早成熟、收敛路径质量低、种群多样性差、难以打破局部最优解等问题，提出了一种多种群迁移遗传算法，将大种群随机划分为几个具有相同种群编号的小种群，并将种群之间的迁移机制用于替代选择运算符的筛选机制。田雅琴等[19]提出将跳点搜索算法与改进遗传算法融合的跳点搜索−遗传算法，通过引入自适应交叉算子和变异算子，解决采用传统遗传算法解析最优路径中存在的转折点较多、易陷入局部最优解等问题。Chen等[20]针对洋流对自主水下航行器的路径规划问题提出了一种融合A*算法和遗传算法的路径规划策略，通过制定适合洋流条件的适应度函数和采用自适应突变方法来增强种群多样性和稳定性。黄荣杰等[21]提出一种基于可视图与改进遗传算法的路径规划算法，改善路径的平滑性和避障能力，解决传统遗传算法存在易早熟和路径质量差等缺点。Ding[22]针对足球训练辅助机器人运动路径规划中路径不平滑、计算量大的问题，该文提出了一种基于遗传算法的全局路径规划方法，针对一些特殊的窄通道环境情况，采用遗传算法简单搜索确定动作区域。李艳生等[23]提出一种适用于仓储机器人路径规划的人工蜂群−自适应遗传算法，解决传统遗传算法路径规划的能耗大，路径不平滑等问题。
目前在应用遗传算法解决路径规划问题时，常通过随机生成初始种群的方式，使初始种群分布集中且质量较差，影响前期搜索能力。此外，在确保算法避免陷入局部最优同时，仍然存在路径长度较长、转向角度大、转向次数多的问题。针对这些不足，本文提出了改进Q-learning遗传算法 (improved Q-learning genetic algorithm, IQGA)解决路径规划问题，主要贡献为：1)为了解决随机初始化可能生成的大量冗余解，提出了分段中间过渡点的初始化策略(segmented intermediate transition point, SITP)。SITP通过划分区域并确定过渡点，生成从起点到过渡点的可行路径和从过渡点到终点的可行路径，并连接两者生成一条路径。在路径生成过程中，采用轮盘赌选择策略生成优秀初始种群，提高初始种群质量。2) 提出了一种根据区域划分种群的选择策略，该策略结合模拟退火算法，即通过概率选择劣解，避免算法陷入局部最优，提高种群多样性。3) 采用了一种Q-learning算法与交叉和变异相结合的策略，将状态集由最优路径长度变化情况组成，动作集由交叉和变异策略组成，通过与环境交互，不断学习并优化动作选择策略，以此提高算法的全局搜索能力，得到更优种群。
1. 环境建模和路径规划
1.1 环境建模
在规划路径之前，需要构建移动机器人的环境地图，本文选择栅格图的方法对环境进行建模，如图1所示。通过对环境进行分割，并在栅格地图上展示，可行走区域显示为白色单元格，而障碍物区域显示为黑色单元格，两个黑点分别代表起点和终点。
图 1 栅格地图Fig. 1 Grid map
下载:
全尺寸图片
通过由0和1构成的矩阵
${\boldsymbol{G}}$ 将环境信息记录下来，0代表可行走栅格，1代表障碍物栅格。栅格地图坐标与矩阵坐标关系为$$ {\boldsymbol{M}}\left( {x,y} \right) = {\boldsymbol{G}}\left( {x,y} \right) $$ (1) 1.2 路径规划模型
本文采用实数编码，由最小编号数为0，从左到右、从下到上对栅格图中的单元格进行编号。当前节点坐标
$ \left( {{x_i},{y_i}} \right) $ 与当前节点栅格编号$ {G_i} $ 的关系为$$ \begin{gathered} {x_i} = \left\lfloor {\left( {{G_i} \text{%} s} \right)} \right\rfloor + 1 \\ {y_i} = \left\lfloor {\left( {{G_i}/s} \right)} \right\rfloor + 1 \\ \end{gathered} $$ (2) 式中：
$ {x_i} $ 和$ {y_i} $ 表示当前节点的横坐标和纵坐标，$s$ 为栅格图的列数，“%”表示取余数符号，“/” 表示取商数符号，$\left\lfloor {} \right\rfloor $ 为向下取整符号。可行路径由根据栅格编号
$ {G_i} $ 得到的一连串路径坐标表示，一条连续无障碍可行路径可表示为${\boldsymbol{Z}} = \left[ {\left( {{x_{{\mathrm{start}}}},{y_{{\mathrm{start}}}}} \right) \cdots \left( {{x_i},{y_i}} \right) \cdots \left( {{x_{{\mathrm{end}}}},{y_{{\mathrm{end}}}}} \right)} \right]$ ，如图1所示。2. 基于IQGA的路径规划算法设计
2.1 种群初始化策略
遗传算法的种群初始化对算法解的质量具有一定影响。为了生成种群数量为N的优秀初始种群，首先提出了分段中间过渡点的初始化方法SITP，即根据区域划分确定一个过渡点，生成一条从起点到过渡点的路径a和一条从过渡点到终点的路径b，再将两条路径首尾相连成一条从起点到终点的路径。SITP按以下子步骤执行，种群初始化示例图如图2所示，种群初始化流程图如图3所示。
图 2 种群初始化示例Fig. 2 Population initialization example下载:
全尺寸图片
图 3 种群初始化流程Fig. 3 Flowchart of population initialization下载:
全尺寸图片
$$ \begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {{x_r} = \left\lfloor {\left( {\left( {{x_{\rm{start}}} + {x_{\rm{end}}}} \right)/2} \right)} \right\rfloor } \\ {{y_{r1}} = {\mathrm{rand}}\left( {{y_{\rm{start}}},\left\lfloor {\left( {\left( {{y_{\rm{start}}} + {y_{\rm{end}}}} \right)/3} \right)} \right\rfloor } \right)} \\ {{y_{r2}} = {\mathrm{rand}}\left( {\left\lfloor {\left( {\left( {{y_{\rm{start}}} + {y_{\rm{end}}}} \right)/3} \right)} \right\rfloor ,2 \times \left\lfloor {\left( {\left( {{y_{\rm{start}}} + {y_{\rm{end}}}} \right)/3} \right)} \right\rfloor } \right)} \\ {{y_{r3}} = {\mathrm{rand}}\left( {2 \times \left\lfloor {\left( {\left( {{y_{\rm{start}}} + {y_{\rm{end}}}} \right)/3} \right)} \right\rfloor ,{y_{\rm{end}}}} \right)} \end{array}} \\ {{y_{ri}} \in R,i = 1,2,3} \end{array} $$ (3) 式中：
$\left( {{x_r},{y_{ri}}} \right)$ 为分段中间过渡点坐标，$\left( {{x_{\rm{start}}},{y_{\rm{start}}}} \right)$ 为起点坐标，$\left( {{x_{\rm{end}}},{y_{\rm{end}}}} \right)$ 为终点坐标，${x_r}$ 表示在起点横坐标与终点横坐标之间的随机整数，$R$ 表示$x = {x_r}$ 直线上的所有非障碍坐标，${y_{ri}}$ 表示三段区域划分的纵坐标。步骤1：根据式 (3) 选择一个节点，将该节点设为过渡点，每段区域选择 N/3 次。
步骤2：设置两路径的起点和终点，并将起点加入禁忌表中。按照当前节点确定该节点的八邻域点集合
$J$ ，即在栅格图中包围当前节点的8个坐标点的集合。先后删除$J$ 中超出栅格图范围的节点、以对角线方向越过障碍物的节点、禁忌表中的节点、障碍物所在位置的节点，得到当前节点邻接可选节点集合${H_k}$ 。步骤3：根据以下公式从
${H_k}$ 中按照轮盘赌策略选择下一步移动节点，并将该节点加入到禁忌表中。$$ {v_1} = \left[ {\left( {{x_k},{y_k}} \right) - \left( {{x_m},{y_m}} \right)} \right] $$ (4) $$ {v_2} = \left[ {\left( {{x_z},{y_z}} \right) - \left( {{x_m},{y_m}} \right)} \right] $$ (5) $$ {\theta _k} = \arccos \left( {\dfrac{{{v_1} \times {v_2}}}{{\left| {{v_1}} \right| \times \left| {{v_2}} \right|}}} \right) $$ (6) $$ {P^k} = \left\{ {\begin{array}{*{20}{l}} {\dfrac{{{{\left( {7 - 10 \cdot \ln \left( {{\theta _k}/90} \right)} \right)}^2}}}{{\displaystyle\sum\limits_{s \in {H_k}} {{{\left( {7 - 10 \cdot \ln \left( {{\theta _k}/90} \right)} \right)}^2}} }},{\theta _k} \ne 0} \\ {1 \times {{10}^{15}},{\theta _k} = 0} \end{array}} \right. $$ (7) 式(4)表示当前节点
$\left( {{x_m},{y_m}} \right)$ 到下一步节点$\left( {{x_k},{y_k}} \right)$ 的向量；式(5)表示当前节点$\left( {{x_m},{y_m}} \right)$ 到终点$\left( {{x_z},{y_z}} \right)$ 的向量；式(6)表示${v_1}$ 与${v_2}$ 两向量的夹角；式(7)表示移动到下一节点$\left( {{x_k},{y_k}} \right)$ 的概率，$k = 1,2, \cdots, n$ 。步骤4：通过SITP生成N/8条从起点到过渡点的路径，取最优路径作为路径a。通过SITP生成N/8条从过渡点到终点的路径，取最优路径作为路径b。
步骤5：判断路径a和路径b是否都生成。若是，则删除路径b的起点，连接路径a与路径b生成一个可行解，最后执行步骤6；若否，则更新禁忌表，并返回步骤1。
步骤6：寻路结束后取出所有可行解，作为本改进遗传算法的初始种群。
2.2 应度函数
为了提高移动机器人的工作效率和平稳性，路径规划需要路径长度更小、转向角度更小、转向次数更少。以下为考虑路径长度、转向角度、转向次数的目标函数。
1)路径长度目标函数：
$$ {f_1} = \sum\limits_{i = 0}^{e - 1} {\sqrt {{{\left( {{x_{i + 1}} - {x_i}} \right)}^2} + {{\left( {{y_{i + 1}} - {y_i}} \right)}^2}} } $$ (8) 式中：
$e$ 为节点数量，$ \left( {{x_i},{y_i}} \right) $ 为第i个节点的坐标，i=0,1,$ \cdots $ , e。2)转向角度目标函数：
$$ \begin{array}{*{20}{c}} {{\boldsymbol{a}} = \left( {{x_i},{y_i}} \right) - \left( {{x_{i - 1}},{y_{i - 1}}} \right)} \\ {{\boldsymbol{b}} = \left( {{x_{i + 1}},{y_{i + 1}}} \right) - \left( {{x_i},{y_i}} \right)} \\ {{\theta _i} = \arccos \left( {\dfrac{{{\boldsymbol{a}} \times {\boldsymbol{b}}}}{{\left| {\boldsymbol{a}} \right| \times \left| {\boldsymbol{b}} \right|}}} \right)} \end{array} $$ (9) 式中：
${\boldsymbol{a}}$ 表示点$ \left( {{x_{i - 1}},{y_{i - 1}}} \right) $ 到点$ \left( {{x_i},{y_i}} \right) $ 的向量，${\boldsymbol{b}}$ 表示点$ \left( {{x_i},{y_i}} \right) $ 到点$ \left( {{x_{i + 1}},{y_{i + 1}}} \right) $ 的向量，$ {\theta _i} $ 表示${\boldsymbol{a}}$ 与${\boldsymbol{b}}$ 两向量的夹角。$$ \begin{gathered} {W_i} = \left\{ {\begin{array}{*{20}{l}} 0, \\ {10}, \\ {20}, \\ {50}, \end{array}\begin{array}{*{20}{l}} {}&{\begin{array}{*{20}{l}} {{\theta _i} = 0} \\ {0 < {\theta _i} < 90\text{°}} \\ {{\theta _i} = 90\text{°}} \\ {90\text{°} < {\theta _i} \leqslant 180\text{°}} \end{array}} \end{array}} \right. \\ {f_2} = \sum\limits_{i = 1}^{{\mathrm{len}} - 1} {{W_i}} \\ \end{gathered} $$ (10) 式中
${W_i}$ 表示$ {\theta _i} $ 对应的惩罚值。3)转向次数目标函数：
$$ {f_3} = \sum\limits_{i = 1}^{{\mathrm{len}} - 1} m ,m = \left\{ {\begin{array}{*{20}{l}} {1,\quad{\theta _i} \ne 0} \\ {0,\quad{\theta _i} = 0} \end{array}} \right. $$ (11) 式中
$m$ 为$ {\theta _i} $ 对应的代价值。考虑路径长度、转向角度、转向次数的总目标函数为
$$f=1 / f_1+1 / f_2+1 / f_3$$ (12) 改进遗传算法的适应度函数为
$$ F = f $$ (13) 式中：
$F$ 表示路径的适应度值，适应度最大的路径为最优路径。2.3 选择策略
传统遗传算法通常采用锦标赛选择，但因选择的随机性，锦标赛策略易失去优秀个体。本文提出一种区域划分种群的锦标赛选择策略并融合了模拟退火方法，即通过有概率保留劣解，防止算法陷入局部最优和提高种群多样性。
$$ \begin{array}{*{20}{c}} {{x_{\max }} = \max \left( {{x_{\rm{start}}},{x_{\rm{end}}}} \right),{x_{\min }} = \min \left( {{x_{\rm{start}}},{x_{\rm{end}}}} \right)} \\ {{y_{\max }} = \max \left( {{y_{\rm{start}}},{y_{\rm{end}}}} \right),{y_{\min }} = \min \left( {{y_{\rm{start}}},{y_{\rm{end}}}} \right)} \\ {L = \min \left( {\mathrm{int} \left( {\left| {{x_{\rm{end}}} - {x_{\rm{start}}}} \right|} \right),\mathrm{int} \left( {\left| {{y_{\rm{end}}} - {y_{\rm{start}}}} \right|} \right)} \right)} \\ {l = {{\mathrm{int}}} \left( {L/2} \right)} \end{array} $$ (14) $$ \begin{array}{l}\begin{array}{l}\begin{array}{l}当\left|{x}_{\rm{end}} - {x}_{\rm{start}}\right|\leqslant \left|{y}_{\rm{end}} - {y}_{\rm{start}}\right|\\ \left\{ \begin{array}{l}{x}_{i}\leqslant {x}_{\mathrm{max}}\\ {y}_{i}\geqslant {y}_{\mathrm{min}}\\ {x}_{i} - {y}_{i} + {y}_{\mathrm{min}} - l\geqslant 0\\ \left(l,{y}_{\mathrm{min}}\right),\left({x}_{\mathrm{max}},{x}_{\mathrm{max}} + {y}_{\mathrm{min}} - l\right)\notin {D}_{1}\\ \left({x}_{i},{y}_{i}\right)\in {D}_{1} \end{array}\right.\end{array}\\ \begin{array}{l}当\left|{x}_{\rm{end}} - {x}_{\rm{start}}\right| > \left|{y}_{\rm{end}} - {y}_{\rm{start}}\right|\\ \left\{ \begin{array}{l}{x}_{i}\leqslant {x}_{\mathrm{max}}\\ {y}_{i}\geqslant {y}_{\mathrm{min}}\\ {x}_{i} - {y}_{i} + l - {x}_{\mathrm{max}}\geqslant 0\\ \left({y}_{\mathrm{min}} - l + {x}_{\mathrm{max}},{y}_{\mathrm{min}}\right),\left({x}_{\mathrm{max}},l\right)\notin {D}_{1}\\ \left({x}_{i},{y}_{i}\right)\in {D}_{1} \end{array}\right. \end{array}\end{array}\\ \begin{array}{l}\begin{array}{l}\begin{array}{l}当\left|{x}_{\rm{end}} - {x}_{\rm{start}}\right|\leqslant \left|{y}_{\rm{end}} - {y}_{\rm{start}}\right|\\ \left\{ \begin{array}{l}{x}_{i}\geqslant {x}_{\mathrm{max}}\\ {y}_{i}\leqslant {y}_{\mathrm{min}}\\ {x}_{i} - {y}_{i} + {y}_{\mathrm{max}} - l\geqslant 0\\ \left(l,{y}_{\mathrm{max}}\right),\left({x}_{\mathrm{min}},{x}_{\mathrm{min}} + {y}_{\mathrm{max}} - l\right)\notin {D}_{2}\\ \left({x}_{i},{y}_{i}\right)\in {D}_{2} \end{array}\right.\end{array}\\ \begin{array}{l}当\left|{x}_{\rm{end}} - {x}_{\rm{start}}\right| > \left|{y}_{\rm{end}} - {y}_{\rm{start}}\right|\\ \left\{ \begin{array}{l}{x}_{i}\geqslant {x}_{\mathrm{max}}\\ {y}_{i}\leqslant {y}_{\mathrm{min}}\\ {x}_{i} - {y}_{i} + l - {x}_{\mathrm{min}}\geqslant 0\\ \left({y}_{\mathrm{max}} - l + {x}_{\mathrm{min}},{y}_{\mathrm{max}}\right),\left({x}_{\mathrm{min}},l\right)\notin {D}_{2}\\ \left({x}_{i},{y}_{i}\right)\in {D}_{2} \end{array}\right.\end{array}\end{array} \end{array}\end{array} $$ (15) 式(14)中
$L$ 表示起点和终点构成矩形的短边。式(15)表示三区域划分的范围，${D_i}$ $(i = 1,2,3)$ 表示三区域。首先确定种群初始化后得到的种群
$ p $ ，将种群根据经过的3个区域分为三类${p_i}(i = 1,2,3)$ ，区域划分的范围由式(14)和式(15)确定：在10×10栅格图上根据式(14)和式(15)得到的区域划分如图4所示。
图 4 区域划分图(10×10)Fig. 4 Diagram of area partitioning (10×10)下载:
全尺寸图片
之后确定各类
${p_i}$ 的数量${n_i}$ ，${p_i}$ 通过锦标赛选择策略并融合有概率保留劣解的模拟退火方法，根据式(16)进行${s_i}$ 次选择。最后采用精英保留策略，将记录的种群最优解保留。选择策略为$$ \begin{array}{*{20}{l}} {\begin{array}{*{20}{l}} {\begin{array}{*{20}{l}} {{s_1} = {n_1}}, \\ {{s_1} = N/3}, \\ {{s_2} = {n_2}}, \\ {{s_2} = N/3}, \end{array}}&{\begin{array}{*{20}{l}} {{n_1} \leqslant N/3} \\ {{n_1} > N/3} \\ {{n_2} \leqslant N/3} \\ {{n_2} > N/3} \end{array}} \end{array}} \\ \qquad\quad {{s_3} = N - {s_1} - {s_2}} \end{array} $$ (16) $$ B = {F_{{\mathrm{best}}}} - \dfrac{{21}}{{20}}{F_{{\mathrm{worst}}}} $$ (17) $$ {P_j} = \dfrac{{{F_i} - {F_{{\mathrm{worst}}}}}}{{{F_{{\mathrm{best}}}} - {F_{{\mathrm{worst}}}}}} $$ (18) 式(16)表示各类
${p_i}$ 的数量${n_i}$ 与选择次数${s_i}$ 的关系，其中$N$ 为种群数量。式(17)表示判断当前种群分布均匀程度的数值。
$B > 0$ 则种群分布均匀，反之则种群分布不均匀。${F_{{\mathrm{worst}}}}$ 为当前种群最差个体的适应度值，${F_{{\mathrm{best}}}}$ 为当前种群最优个体的适应度值。式(18)表示选择次优解的概率。
${P_r} < {P_j}$ 时选择次优解，随机概率${P_r}$ 为$0 \sim 1$ 之间的数值，${F_i}$ 为当前个体的适应度值。在种群
${p_i}$ 中随机选择3个个体，将最优解直接保留。若$B > 0$ ，当随机概率${P_r} < {P_j}$ 时，次优解保留，最差解有1/2的概率保留。若$B \leqslant 0$ ，最差解有1/2的概率保留。选择策略流程图如图5所示。
图 5 选择策略流程图Fig. 5 Flowchart of selection strategy下载:
全尺寸图片
2.4 交叉和变异策略
2.4.1 Q-learning框架
本文引用文献[24]的Q-learning框架，在此基础上与遗传算法中的交叉和变异策略相结合，用Q-learning算法动态调整交叉和变异策略，利用强化学习中根据状态奖励选择最优动作，从而提高算法的搜索效率。
马尔可夫决策过程是基本的强化学习模型，组成元素分为状态空间
$S$ 、动作空间$A$ 、回报函数$R$ 、动作选择策略。状态空间
$S$ 是指所有可能的状态的集合，每个状态代表系统所处的特定情况，本文表示为3种状态${s_i}$ 的集合，即$S = \left\{ {{s_1},{s_2},{s_3}} \right\}$ 。状态
${s_i}$ 由每次迭代后种群中最优路径长度的变化情况决定， 3种状态分别为最优路径长度变大、不变、变小。由于初次循环中最优路径长度还未发生变化，所以将初次循环的状态${s_i} = {s_2}$ 。动作空间
$A$ 是指在每个状态下可以执行的所有可能动作的集合。本文表示为3种动作${a_i}$ 的集合，即$A = \left\{ {{a_1},{a_2},{a_3}} \right\}$ ，动作${a_i}$ 由交叉和变异策略构成。${a_1}$ ：交叉方法为双点交叉，变异方法根据随机概率${P_r}$ 确定，当随机概率${P_r}$ ≤0.6为删除算子变异，当0.6<${P_r}$ ≤0.8为中位点变异，当${P_r}$ >0.8为偏转点变异。${a_2}$ ：交叉方法为双点交叉，变异方法根据随机概率${P_r}$ 确定，当随机概率${P_r}$ ≤0.6为中位点变异，0.6<${P_r}$ ≤0.8为删除算子变异，当${P_r}$ >0.8为偏转点变异。${a_3}$ ：交叉方法为双点交叉，变异方法根据随机概率${P_r}$ 确定，当随机概率${P_r}$ ≤0.6为偏转点变异，当0.6<${P_r}$ ≤0.8为删除算子变异，当${P_r}$ >0.8为中位点变异。Q-learning框架如图6所示。Q-learning算法是一种最常用的无模型强化学习算法，公式表示为
图 6 Q-learning框架Fig. 6 Q-learning framework下载:
全尺寸图片
$$ Q\left( {{s_t},{a_t}} \right) \leftarrow Q\left( {{s_t},{a_t}} \right) + \alpha \left( {{r_{t + 1}} + \gamma \max Q\left( {{s_{t + 1}},a'} \right) - Q\left( {{s_t},{a_t}} \right)} \right) $$ (19) 式中：
$\alpha $ 为学习比例，$\gamma $ 为折扣因子，${s_t}$ 为$t$ 时刻的状态，${a_t}$ 为$t$ 时刻的动作，${r_{t + 1}}$ 为在环境状态为${s_t}$ 时执行动作${a_t}$ 获得的回报，$ \max Q\left( {{s_{t + 1}},a'} \right) $ 为Q表中状态为${s_{t + 1}}$ 时最大的Q值，$a'$ 为当前状态下Q值最大的动作，动作选择依赖于Q值。动作选择策略用于平衡探索新策略和利用已知最优策略之间的权衡，本文采用
$\varepsilon \text{-} {\mathrm{greedy}}$ 选择作为动作选择策略，其描述如下：若随机数小于$ \varepsilon $ ，则随机选择一个动作；反之，选择动作$a'$ ，其中随机数在[0，1]中服从均匀分布。当采用动作${a_i}$ 时，如果状态从$u$ 转移到$w$ ，且$w < u$ ，那么该动作就会获得奖励；如果状态从$w$ 转移到$u$ ，那么该动作就会得到惩罚。回报函数$R$ 定义为：$ {r}_{t}=u-w, 其中 {s}_{t}=u,{s}_{t+1}=w $ 。2.4.2 交叉策略
本文采用划分种群的双点交叉策略，交叉操作具体步骤如下。
步骤1：对当代种群按照适应度由小到大进行排序，将当代种群分为优秀群体和较差群体。个体的适应度越大，个体路径质量越优秀，优秀群体是适应度优秀的前20位个体，较差群体为其余个体。优秀群体中的个体可以与任意个体进行双点交叉，较差群体中的个体只能与优秀群体中的个体进行双点交叉。
步骤2：个体根据交叉概率判断是否进行交叉操作。判断方法为：
${P_r}$ 为随机概率，${P_c}$ 为交叉概率，若${P_r}$ <${P_c}$ 则进行交叉操作，反之不进行交叉操作。若进行交叉操作，则子代保留；若不进行交叉操作，则该个体直接保留。双点交叉步骤为：首先找出父代的两个相同节点，父代按照相同节点作为交叉点进行交叉。
双点交叉示例如图7所示，示例中父代的相同节点分别是
$P_{10}$ 、$P_{40}$ 。
图 7 双点交叉方式Fig. 7 Double-point crossing operation下载:
全尺寸图片
2.4.3 变异策略
删除算子变异策略：首先随机选择两个偏转点(
${d_i}$ 和${d_j}$ )，将其前后两点(${d_{i - 1}}$ 和${d_{j + 1}}$ )作为起点和终点进行种群初始化生成一条新路径。$$ \begin{array}{*{20}{c}} {B = \left( {{f_{\max }} - {f_i}} \right)/\left( {{f_{\max }} - {f_{\min }}} \right)} \\ {\left\{ {\begin{array}{*{20}{l}} {\begin{array}{*{20}{l}} {{n_m} = {\mathrm{rand}}\left( {2,0.25\times{n_{{\mathrm{all}}}}} \right)} ,\quad{B < 0.5}\\ {{n_m} = {{\mathrm{int}}} \left( {0.4 \times{n_{{\mathrm{all}}}}\times\left( {{f_{\max }} - {f_i}} \right)/\left( {{f_{\max }} - {f_{\min }}} \right)} \right)}, \quad{B \geqslant 0.5}\\ {2 \leqslant {n_m} \leqslant 10} \end{array}} \end{array}} \right.} \end{array} $$ (20) 式中：
$B$ 表示待变异个体的优劣权重值，${n_m}$ 表示待变异个体的变异点数，其中${n_{{\mathrm{all}}}}$ 为待变异个体的节点数，${f_i}$ 为待变异个体的适应度值，${f_{\max}}、{f_{\min }}$ 为种群中个体的最大适应度值和最小适应度值。中位点${d_{{\mathrm{mid}}}}$ 坐标分别为$$ \begin{array}{*{20}{c}} {{x_{{\mathrm{mid}}}} = {{\mathrm{int}}} \left( {\dfrac{{{x_{k - 1}} + {x_{k + 1}}}}{2}} \right)} \\ {{y_{{\mathrm{mid}}}} = {{\mathrm{int}}} \left( {\dfrac{{{y_{k - 1}} + {y_{k + 1}}}}{2}} \right)} \end{array} $$ (21) 根据式(20)选择
${n_m}$ 个节点${d_k}$ ，确定前后两点(${d_{k - 1}}$ 和${d_{k + 1}}$ )生成两个向量$\left( {{v_1},{v_2}} \right)$ 。当向量之间夹角大于90º时，则删除${d_k}$ 。当向量之间夹角为90º，若${v_1}$ 水平或垂直时，则删除${d_k}$ ，否则，根据式(21)确定中位点${d_{{\mathrm{mid}}}}$ ，若${d_{{\mathrm{mid}}}}$ 在可行位置，则将${d_k}$ 替换为${d_{{\mathrm{mid}}}}$ 。中位点变异策略：首先随机选择两个偏转点(
${d_i}$ 和${d_j}$ )，将其前后两点(${d_{i - 1}}$ 和${d_{j + 1}}$ )作为起点和终点进行种群初始化，生成一条新路径。之后，根据式(20)选择${n_m}$ 个节点${d_k}$ ，确定前后两点(${d_{k - 1}}$ 和${d_{k + 1}}$ )。若前后两点连续（即两节点横纵坐标差的绝对值都不大于1，则删除${d_k}$ 。否则，根据式(21)确定中位点${d_{{\mathrm{mid}}}}$ ，若${d_{{\mathrm{mid}}}}$ 在可行位置，将${d_k}$ 替换为${d_{{\mathrm{mid}}}}$ 。偏转点变异策略：首先随机选择两个偏转点(
${d_i}$ 和${d_j}$ )，将其前后两点(${d_{i - 1}}$ 和${d_{j + 1}}$ )作为起点和终点进行种群初始化，生成一条新路径。待变异个体的变异点数为$$ {n_m} = {\mathrm{rand}}\left( {1,{n_{{\mathrm{diver}}}}} \right) $$ (22) 式中
${n_{{\mathrm{diver}}}}$ 表示偏转点的个数。根据式(22)随机选择
${n_m}$ 个偏转点${d_k}$ ，确定前后两点(${d_{k - 1}}$ 和${d_{k + 1}}$ )。若三节点连续，则删除${d_k}$ 。否则将偏转点替换成前后两节点八邻域的共同点(共同点中不包括障碍物和偏转点)，根据式(21)确定中位点${d_{{\mathrm{mid}}}}$ ，若共同点中有${d_{{\mathrm{mid}}}}$ 且其在可行位置，则将${d_k}$ 替换为${d_{{\mathrm{mid}}}}$ ，否则在共同点中随机选择一点。2.5 IQGA流程图
本文提出的IQGA的流程图如图8所示。
图 8 IQGA流程图Fig. 8 Flowchart of IQGA下载:
全尺寸图片
3. 仿真实验与结果分析
为验证IQGA的有效性，采用VSCode2019平台进行编程仿真。首先对文献[25-29]的算法在不同规模的栅格图(20×20[26]和40×40[29])中进行仿真实验，栅格图单元格长度为1 m，证明IQGA在障碍物环境中可得到合理的仿真效果。再对GA、IAGA (improved adaptive genetic algorithm)[30]、ICGA (improved catastrophe genetic algorithm)[31]、IQGA在不同规模的栅格图(20×20[31]和40×40[31])中进行仿真实验，栅格图单元格长度为1 m，证明IQGA的有效性。算法参数如表1所示。
表 1 参数设置Table 1 Parameter settings算法 种群
数量N迭代
次数n交叉
概率${P_c}$变异
概率${P_m}$学习
比例$\alpha $折扣
因子$\gamma $贪婪
因子$\varepsilon $GA/IAGA/
ICGA40 200 0.9 0.1 — — — IQGA 0.1 0.9 0.1 3.1 种群初始化仿真试验
为验证IQGA的改进种群初始化策略的有效性，将IQGA与GA进行种群初始化仿真对比实验，GA按照随机生成方式得到初始种群。两种算法在规模20×20[31]和40×40[31]的栅格图上进行仿真实验生成30条路径，记录路径长度。栅格图单元格长度为1 m。
由表2可知，通过IQGA的改进种群初始化策略，可以获得初始路径更短的优质种群，有助于提升算法的搜索效率。
3.2 IQGA仿真试验
为验证IQGA可得到合理的仿真效果，在规模20×20[26]和40×40[29]的栅格图上分别进行20次和10次仿真实验。20×20[26]栅格图设置起点为(1,1)，终点为(20,20)。40×40[29]栅格图设置起点为(1,1)，终点为(40,40)。
图9为3种算法在20×20[26]栅格图中的仿真结果，表3是在20×20[26]栅格图中各算法仿真结果统计。
下载:
全尺寸图片
由图9和表3可知，相较文献[25-26]的算法，IQGA算法可生成路径长度小，转向次数少的合理路径。
图10为4种算法在40×40[29]栅格图中的仿真结果，表4是在40×40[29]栅格图中各算法仿真结果统计。
下载:
全尺寸图片
由图10和表4可知，相较文献[27-29]的算法，IQGA算法可生成路径长度小，转向次数少的合理路径。
为验证IQGA的有效性，在规模20×20[31]和40×40[31]的栅格图上进行60次仿真实验。20×20[31]栅格图设置起点为(1,1)，终点为(20,20)。40×40[31]栅格图设置起点为(2,2)，终点为(39,39)。
图11为4种算法在20×20[31]栅格图中的仿真结果，图12为IQGA算法在对应栅格图中的路径长度变化曲线。表5是在20×20[31]栅格图中各算法仿真结果统计。
下载:
全尺寸图片
下载:
全尺寸图片
根据图11～12和表5可知，GA由于易陷入局部最优导致规划的路径质量较差，使GA多余偏转点较多、路径长度最长。IAGA的路径长度、转向角度和转向次数相较GA有所减少，但路径质量仍较差。ICGA的路径长度、转向角度和转向次数相较GA和IAGA有明显降低，而本文IQGA相较ICGA在路径长度方面减少了0.027 m，在转向角度方面减少了5.46%，在转向次数方面降低了35.46%。
图13为4种算法在40×40栅格图中的仿真结果，图14为IQGA算法在对应栅格图中的路径长度变化曲线。表6是在40×40栅格图中各算法仿真结果统计。
下载:
全尺寸图片
下载:
全尺寸图片
根据图13～14和表6可知， GA由于易陷入局部最优使规划的路径质量较差，导致路径的多余偏转点较多、转向角度较大、路径长度最长。IAGA相较GA的路径长度、转向角度和转向次数有所改善，但多余偏转点较多导致路径质量较差。ICGA的路径长度、转向角度和转向次数相较GA和IAGA有明显的降低，而本文IQGA相较ICGA在路径长度方面减少了0.055 m，在转向角度方面减少了25.28%，在转向次数方面降低了33.16%。
4. 结束语
本文针对GA在路径规划应用中存在初始种群质量差、容易陷入局部最优解、转向角度大、转向次数多等问题，提出了以下改进策略：划分区域确定一个过渡点，生成从起点到过渡点的可行路径和从过渡点到终点的可行路径，并连接两者生成一条路径；在路径生成过程中，采用当前节点与下一节点和终点所形成夹角有关的概率选择方法；运用了一种考虑路径长度、转向角度和转向次数的适应度函数，生成路径长度短、转向角度小、转向次数少的优秀解，提高算法解的质量；采用区域划分种群和模拟退火算法结合的锦标赛选择策略，通过概率选择差解避免陷入局部最优，增加种群多样性；提出了一种Q-learning算法与交叉和变异相结合的策略，将强化学习的动作集由交叉和变异组成，通过与环境交互，不断学习并优化动作选择策略，从而提高算法的全局搜索能力，得到更优种群。通过不同规格栅格图的仿真实验证明，本文改进遗传算法在路径长度、转向角度、转向次数方面均优于其他遗传算法及改进遗传算法所得到的结果。
-
图 1 栅格地图
Fig. 1 Grid map
下载:
全尺寸图片
图 2 种群初始化示例
Fig. 2 Population initialization example
下载:
全尺寸图片
图 3 种群初始化流程
Fig. 3 Flowchart of population initialization
下载:
全尺寸图片
图 4 区域划分图(10×10)
Fig. 4 Diagram of area partitioning (10×10)
下载:
全尺寸图片
图 5 选择策略流程图
Fig. 5 Flowchart of selection strategy
下载:
全尺寸图片
图 6 Q-learning框架
Fig. 6 Q-learning framework
下载:
全尺寸图片
图 7 双点交叉方式
Fig. 7 Double-point crossing operation
下载:
全尺寸图片
图 8 IQGA流程图
Fig. 8 Flowchart of IQGA
下载:
全尺寸图片
下载:
全尺寸图片
下载:
全尺寸图片
下载:
全尺寸图片
下载:
全尺寸图片
下载:
全尺寸图片
下载:
全尺寸图片
表 1 参数设置
Table 1 Parameter settings
算法 种群
数量N迭代
次数n交叉
概率${P_c}$变异
概率${P_m}$学习
比例$\alpha $折扣
因子$\gamma $贪婪
因子$\varepsilon $GA/IAGA/
ICGA40 200 0.9 0.1 — — — IQGA 0.1 0.9 0.1 表 2 种群初始化仿真结果统计
Table 2 Statistics of population initialization simulation results
-
[1] 林韩熙, 向丹, 欧阳剑, 等. 移动机器人路径规划算法的研究综述[J]. 计算机工程与应用, 2021, 57(18): 38−48. doi: 10.3778/j.issn.1002-8331.2103-0519 LIN Hanxi, XIANG Dan, OUYANG Jian, et al. Review of path planning algorithms for mobile robots[J]. Computer engineering and applications, 2021, 57(18): 38−48. doi: 10.3778/j.issn.1002-8331.2103-0519 [2] 王梓强, 胡晓光, 李晓筱, 等. 移动机器人全局路径规划算法综述[J]. 计算机科学, 2021, 48(10): 19−29. doi: 10.11896/jsjkx.200700114 WANG Ziqiang, HU Xiaoguang, LI Xiaoxiao, et al. Overview of global path planning algorithms for mobile robots[J]. Computer science, 2021, 48(10): 19−29. doi: 10.11896/jsjkx.200700114 [3] BADAMASI A M, KABIR I K, AHMED G, et al. Autonomous mobile robot path planning techniques: a review: classical and heuristic techniques[J]. IEEE access, 2025, 13: 117999−118022. doi: 10.1109/ACCESS.2025.3579863 [4] 李成进, 王芳. 智能移动机器人导航控制技术综述[J]. 导航定位与授时, 2016, 3(5): 22−26. LI Chengjin, WANG Fang. Review of navigation control technology of intelligent mobile robot[J]. Navigation positioning and timing, 2016, 3(5): 22−26. [5] LIU Lixing, WANG Xu, YANG Xin, et al. Path planning techniques for mobile robots: review and prospect[J]. Expert systems with applications, 2023, 227: 120254. doi: 10.1016/j.eswa.2023.120254 [6] TANG Yuexia, ZAKARIA M A, YOUNAS M. Path planning trends for autonomous mobile robot navigation: a review[J]. Sensors, 2025, 25(4): 1206. doi: 10.3390/s25041206 [7] 赵晓, 王铮, 黄程侃, 等. 基于改进A*算法的移动机器人路径规划[J]. 机器人, 2018, 40(6): 903−910. ZHAO Xiao, WANG Zheng, HUANG Chengkan, et al. Mobile robot path planning based on an improved A* algorithm[J]. Robot, 2018, 40(6): 903−910. [8] SHENG Zhaokang, SONG Tingqiang, SONG Jiale, et al. Bidirectional rapidly exploring random tree path planning algorithm based on adaptive strategies and artificial potential fields[J]. Engineering applications of artificial intelligence, 2025, 148: 110393. doi: 10.1016/j.engappai.2025.110393 [9] 曲胜, 许志远, 张晓鹏, 等. 基于改进RRT算法的无人船路径规划研究[J]. 中国航海, 2024, 47(4): 175−180. doi: 10.3969/j.issn.1000-4653.2024.04.022 QU Sheng, XU Zhiyuan, ZHANG Xiaopeng, et al. Research on unmanned ship path planning based on improved RRT algorithm[J]. Navigation of China, 2024, 47(4): 175−180. doi: 10.3969/j.issn.1000-4653.2024.04.022 [10] XIAO Qianxi, CAI Jiejin. The path-planning in radioactive environment based on HIOSD-PRM method[J]. Annals of nuclear energy, 2022, 171: 109018. doi: 10.1016/j.anucene.2022.109018 [11] 王豪, 赵学军, 袁修久. 基于改进自适应遗传算法的机器人路径规划[J]. 电光与控制, 20, 29(5): 72−76. WANG Hao, ZHAO Xuejun, YUAN Xiujiu. Robot path planning based on improved adaptive genetic algorithm [J]. Electric light & control, 20, 29(5): 72−76. [12] MIAO Changwei, CHEN Guangzhu, YAN Chengliang, et al. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm[J]. Computers & industrial engineering, 2021, 156: 107230. [13] 卫玉梁, 靳伍银. 基于神经网络Q-learning算法的智能车路径规划[J]. 火力与指挥控制, 2019, 44(2): 46−49. doi: 10.3969/j.issn.1002-0640.2019.02.010 WEI Yuliang, JIN Wuyin. Intelligent vehicle path planning based on neural network Q-learning algorithm[J]. Fire control & command control, 2019, 44(2): 46−49. doi: 10.3969/j.issn.1002-0640.2019.02.010 [14] 刘清云, 游雄, 张欣, 等. 移动机器人路径规划算法综述[J]. 计算机科学, 2025, 52(S1): 159−168. doi: 10.11896/jsjkx.240900074 LIU Qingyun, YOU Xiong, ZHANG Xin, et al. Overview of path planning algorithms for mobile robots[J]. Computer science, 2025, 52(S1): 159−168. doi: 10.11896/jsjkx.240900074 [15] QIN Hongwei, SHAO Shiliang, WANG Ting, et al. Review of autonomous path planning algorithms for mobile Robots[J]. Drones, 20, 7(3): 211. [16] UGWOKE K C, NNANNA N A, ABDULLAHI S E. Simulation-based review of classical, heuristic, and metaheuristic path planning algorithms[J]. Scientific reports, 2025, 15(1): 12643. doi: 10.1038/s41598-025-96614-2 [17] 白晓兰, 袁铮, 周文全, 等. 混合遗传算法在机器人路径规划中的应用[J]. 组合机床与自动化加工技术, 2023(11): 15−19. BAI Xiaolan, YUAN Zheng, ZHOU Wenquan, et al. Application of hybrid genetic algorithm in robot path planning[J]. Modular machine tool & automatic manufacturing technique, 2023(11): 15−19. [18] HAO Kun, ZHAO Jiale, YU Kaicheng, et al. Path planning of mobile robots based on a multi-population migration genetic algorithm[J]. Sensors, 2020, 20(20): 5873. doi: 10.3390/s20205873 [19] 田雅琴, 胡梦辉, 刘文涛, 等. 基于跳点搜索−遗传算法的自主移动机器人路径规划[J]. 工程设计学报, 20, 30(6): 697-706. TIAN Yaqin, HU Menghui, LIU Wentao, et al. Autonomous mobile robot path planning based on jump point search-genetic algorithm [J]. Journal of engineering design, 20, 30(6): 697-706. [20] CHEN Ziming, YAN Jinjin, HUANG Ruen, et al. Path planning for autonomous underwater vehicles (AUVs) considering the influences and constraints of ocean currents[J]. Drones, 2024, 8(8): 348. doi: 10.3390/drones8080348 [21] 黄荣杰, 王亚刚. 基于可视图与改进遗传算法的机器人平滑路径规划[J]. 控制工程, 2024, 31(4): 678−686. HUANG Rongjie, WANG Yagang. Smooth path planning for robot based on visibility graph and improved genetic algorithm[J]. Control engineering of China, 2024, 31(4): 678−686. [22] DING Hui. Motion path planning of soccer training auxiliary robot based on genetic algorithm in fixed-point rotation environment[J]. Journal of ambient intelligence and humanized computing, 2020, 11(12): 6261−6270. doi: 10.1007/s12652-020-01877-4 [23] 李艳生, 万勇, 张毅, 等. 基于人工蜂群−自适应遗传算法的仓储机器人路径规划[J]. 仪器仪表学报, 20, 43(4): 282−290. LI Yansheng, WAN Yong, ZHANG Yi, et al. Warehouse robot path planning based on artificial bee colony-adaptive genetic algorithm [J]. Journal of instrumentation and measurement, 20, 43(4): 282−290. [24] 蔡劲草, 王雷, 雷德明. 基于蛙跳算法的分布式装配混合流水车间调度[J]. 华中科技大学学报(自然科学版), 20, 51(12): 37−44. CAI Jincao, WANG Lei, LEI Deming. Distributed assembly hybrid flow shop scheduling based on frog-leaping algorithm [J]. Journal of Huazhong University of Science and Technology (natural science edition), 20, 51(12): 37−44. [25] 江涛, 张志安, 程志, 等. 改进遗传算法与领航跟随法的机器人编队方法[J]. 计算机工程与应用, 2020, 56(3): 240−245. doi: 10.3778/j.issn.1002-8331.1906-0376 JIANG Tao, ZHANG Zhian, CHENG Zhi, et al. Robot formation method with improved genetic algorithm and leader-follower[J]. Computer engineering and applications, 2020, 56(3): 240−245. doi: 10.3778/j.issn.1002-8331.1906-0376 [26] 汤云峰, 赵静, 谢非, 等. 基于改进遗传算法的机器人路径规划方法[J]. 南京师范大学学报(工程技术版), 2021, 21(3): 49−55. TANG Yunfeng, ZHAO Jing, XIE Fei, et al. Robot path planning method based on improved genetic algorithm[J]. Journal of Nanjing Normal University (engineering and technology edition), 2021, 21(3): 49−55. [27] FISTER I, FISTER J, YANG Xinshe, et al. A comprehensive review of firefly algorithms[J]. Swarm and evolutionary computation, 2013, 13: 34−36. [28] ABDELAZIZ A, MEKHAMER S, BADR M, et al. The firefly metaheuristic algorithms: developments and applications[J]. International electrical engineering journal, 2015, 7(13): 1945−195. [29] 魏书鑫, 王群京, 李国丽, 等. 萤火虫算法结合遗传算法的移动机器人路径规划[J]. 制造业自动化, 2024, 46(10): 69−82. doi: 10.3969/j.issn.1009-0134.2024.10.010 WEI Shuxin, WANG Qunjing, LI Guoli, et al. Firefly algorithm combined with genetic algorithm for mobile robot path planning[J]. Manufacturing automation, 2024, 46(10): 69−82. doi: 10.3969/j.issn.1009-0134.2024.10.010 [30] 王雷, 李明. 改进自适应遗传算法在移动机器人路径规划中的应用[J]. 南京理工大学学报, 2017, 41(5): 627−633. WANG Lei, LI Ming. Application of improved adaptive genetic algorithm in mobile robot path planning[J]. Journal of Nanjing University of Science and Technology, 2017, 41(5): 627−633. [31] 徐兴, 俞旭阳, 赵芸, 等. 基于改进遗传算法的移动机器人全局路径规划[J]. 计算机集成制造系统, 2022, 28(6): 1659−1672. XU Xing, YU Xuyang, ZHAO Yun, et al. Global path planning of mobile robot based on improved genetic algorithm[J]. Computer integrated manufacturing systems, 2022, 28(6): 1659−1672.
