基于混合遗传算法的移动机器人平滑全局路径规划

Luan P G, Thinh N T. Hybrid genetic algorithm based smooth global-path planning for a mobile robot[J]. Mechanics Based Design of Structures and Machines, 2023, 51(3): 1758-1774.

摘要

全局路径规划任务的目标是为机器人在给定的地图上生成一个最优的安全路径。已有许多全局路径规划方法被研究过。在本文中，我们提出了一种新型的混合遗传算法（HGA），用于为差速轮式机器人生成平滑路径。HGA的主要思想是为普通遗传算法的变异算子提供动态变异率和可切换的全局-局部搜索方法。通过实施这些修改，减少了通用遗传算法的过早收敛和模拟算法的高时间消耗的适应度计算。HGA还通过应用种群替换方法来处理染色体长度（由构建路径的一组点的大小定义）。我们的算法满足路径规划任务中的重要标准：安全和最小长度。基于连续曲率分段立方贝塞尔曲线，HGA直接为差速轮式机器人提供平滑路径。因此，我们提出的算法不需要任何第三方算法来平滑计划路径。关于我们的机器人上提议的算法的几个实验及其结果已进行分析和呈现。

1.引言

1.1.动机

随着潜在应用数量的增加，全局路径规划在机器人领域变得越来越有趣，并在自主移动机器人的导航系统中扮演着重要角色。简而言之，全局路径规划根据机器人和地图的给定几何形状，在初始位置和目标位置之间提供无障碍路径。无障碍路径可以是一组航点或线段，并且它们应该在长度上进行优化，例如。但是，这些形式的计划路径有很多缺点。例如，Pirn /C19ık等人（2015）介绍了一种基于惯性传感器的汽车型机器人的转向控制算法。尽管此算法简单且只需要低成本的惯性传感器，但性能相当高效。然而，由于所需的路径以线段形式提供给算法，机器人很难遵循所需的路径。为了克服这个问题，必须补充另一种算法，以连接并平滑获得的路径。通过应用平滑路径算法，路径可以直接用于导航机器人到目标位置，但它们不再是最优的，或者有可能违反给定地图的部分。

在全局路径规划中的另一个问题是路径规划算法几乎不考虑机器人的航向。如果使用的机器人是全向机器人，这个问题可以得到解决。只要全向轮子按照正确的配置排列，全向机器人就不需要关心它们的航向（Kilin等，2017）。与具有较高机动性的全向机器人不同，差速轮式机器人需要路径的曲率不大，更准确地说，曲率必须与机器人的运动学相对应。这些问题促使我们研究一种新算法。我们提出了一种单一算法，该算法直接搜索给定地图、机器人的初始姿态和目标姿态的长度最优曲线安全路径。非确定性方法实际上主导了需要大量时间和努力的复杂任务，而使用常见的搜索或案例分析方法。随机搜索优化算法广泛应用于复杂结构的优化问题。在这项工作中，我们提出了一种算法，该算法用于直接搜索基于曲线连续分段立方贝塞尔曲线的曲线最优路径，根据给定的地图、初始位置和目标位置。所提出的算法比标准的遗传算法（GA）更为时间有效，但仍然给出相同问题的相同最优结果。GA仅专注于全局搜索（探索可行集以找到最优解），并通过继承种群在代代之间的主导基因来优化解决方案。通过这种方法，种群在可行集中保持其多样性。然而，普通算法不适合进行细微调整，这些细微调整接近于最优解决方案（Goldberg 1989；Garg 2010），尤其是在全局路径规划任务中。纯粹的模拟算法（GA的升级版本）向变异算子添加了局部搜索（利用位于给定个体附近的可行子集），以减少GA的过早收敛问题。但是，局部搜索方法需要很长时间来调整并达到成熟的收敛。受到这些问题的启发，我们提出了混合遗传算法（HGA），这是GA和模拟算法（MA）的升级版本，用于解决差速轮式机器人的全局路径规划任务。在这项工作中还定义并实施了可切换的全局-局部搜索方法和染色体长度自适应方法。

1.2.相关研究

许多基于GA的全局路径规划方法已被广泛研究。使用传统的遗传算法来解决全局路径规划任务的想法由Ismail, Sheta和Al-Weshah (2008)明确描述。另一篇论文也为移动机器人提供了一个想法并由Manikas, Ashenayi和Wainwright (2007)实施。此前，Xin, Hua-Hua和Wei-Kang (2005)提出了一个程序，结合了神经网络模型和遗传算法，以在静态环境中找到全局最优路径。Samadi和Othman (2013)为适应基于网格的静态环境在路径规划任务中实施了修改过的GA。然而，这些算法获得的路径由有限方向的线段组成，当然不能用于差速轮式机器人。尽管已经优化了无碰撞路径的长度，但仍需要添加额外的算法来平滑计划的路径。例如，Gia Luan和Thinh (2020)提到了一种方法，该方法通过应用A星算法和三阶分段立方贝塞尔曲线来为差分移动机器人生成平滑路径。另一方面，一些算法可以直接产生机器人可以立即使用的平滑路径。粒子群优化（PSO）是最著名的全局优化器之一，由Saska等人（2006）实施，用于移动机器人的全局路径规划任务。得到的路径是平滑的，因为它们是直接基于Ferguson Splines构建的，而PSO则发生在此时。但是，找到一个可行的路径并优化路径的长度需要很长时间。Song, Wang和Sheng (2016)提出的研究中已经实施了基于PCBC的GA方法，直接获得最优的平滑路径。然而，整个路径的曲率并不连续，因为两个连接的贝塞尔曲线的连接点处的曲率被手动设置为零。为了克服上述缺陷，曲率连续的PCBC已在第二部分中介绍。

对于全局路径规划问题，如何将路径的表现型编码到染色体中也是一个复杂的问题。Ismail、Sheta和Al-Weshah（2008）介绍的Burchardt的路径染色体结构被用来调整染色体长度。Liu、Liang和Xian（2014）还介绍了同一种群中不同长度的染色体。他们引入了三种新的操作符：修复、剪切和删除，以交叉不同染色体长度的个体。然而，他们的想法目前只适用于定义好的拓扑地图。通过改进Qiongbing和Lixin（2016）提出的称为“相同邻接交叉”的交叉操作符，Lamini、Benhlima和Elbekri（2018）提出了一种改进版的遗传算法，用于路径规划，其中最优路径中的转弯次数减少。我们提出了一种不同的方法来解决染色体长度问题，这在第三节中有明确的描述。

Wang等人（2016）为焊接机器人的路径规划提出了双全局最优遗传算法-粒子群优化方法。该方法证实了可以有效地存档最优长度无碰撞焊接路径。Xue（2018）认为路径规划是一个多目标任务，所以采用了非支配排序遗传算法（NSGA-II）。他们还通过增强许多操作符来适应任务：无效解决方案操作符、短程操作符等。Hao等人（2020）引入的多种群迁移遗传算法也很有趣。他们不是在一个种群上处理，而是同时使用三个不同的种群。这种方法证实了它对未知环境并不敏感，但当该算法应用于真实地图时，这就成了一个大问题。另一方面，这些方法仍然产生由线段或点组成的路径，不能直接用于移动机器人。

1.3. 问题定义

在这项工作中，我们提出了HGA，用于为双轮差动驱动的移动机器人获取与给定地图相对应的长度最优化的平滑安全路径（如图1所示）。所获得的路径还需要与机器人的初始姿态和目标姿态相匹配。该算法涉及以下问题：

• 基于PCBC创建一个曲率连续的路径，
• 通过采用可切换的全局-局部搜索方法，加速收敛过程，同时减少GA的过早收敛率，
• 通过应用种群替代方法，解决路径规划问题中的染色体长度问题，
• 最后，分析和调整算法参数，以便机器人在图2所示的地图中获得最佳性能。

2. 背景知识

2.1. 分段三次贝塞尔曲线

贝塞尔曲线是以法国数学家皮埃尔·贝塞尔命名的，它使用空间中的给定点集$\{p_0,p_1,\cdots,p_n\}$来构造曲线。根据贝塞尔（1986）的描述，贝塞尔曲线的一般表达式如公式(1)所示。

$$B(u) = \sum_{i=0}^{n} \binom{n}{i} (1 - u)^{n-i} u^i P_i \tag{1}$$

其中$u \in [0,1]$，而$P_0$和$P_n$被称为端点。

贝塞尔曲线是一个基于$n+1$个点的$n$阶多项式函数的参数曲线。这些点被称为曲线的控制点。相邻控制点之间连接的线段形成一个控制多边形（第一个点和最后一个点只连接到另一个点）。贝塞尔曲线包含在凸包中 - 控制多边形的乘积。$P_0$和$P_n$被称为固定锚点或端点，因为曲线总是经过这两个点。具有足够高度函数的贝塞尔曲线可以形成各种形状的曲线。然而，为了确切地达到所需的形状，控制高阶贝塞尔的形状是非常复杂的。

此外，当形成路径时，由于凸包的属性，可能存在一些重大风险。因此，直接使用路径规划过程产生的航点（子目标）作为控制点效率低下。高阶贝塞尔曲线的另一个缺点是增加了处理时间和问题复杂性。Shao和Zhou（1996）总结的分段贝塞尔曲线是一种更可行的方法。分段贝塞尔曲线的主要概念是将整个曲线分解为许多部分。不是直接使用航点来形成单个平滑路径，而是建立并连接许多子路径，形成整个平滑路径。每条路径由不同的贝塞尔曲线创建，一对连续的航点定义了曲线段的端点。让$C^j_v$是第$v$个曲线段的第$j$个控制点，形成分段函数（2）。

$$B(u,v) = (1-u)^{k+1}p_v + \sum_{j=1}^{k} \binom{k+1}{j} (1-u)^{k+1-j}u^{j}C^j_v + u^{k+1}p_{v+1} \tag{2}$$ $$u \in [0,1], v \in \{0,1,\dots,n-1\}$$

为了在整个域中获得在v变化时离散的连续函数，该函数必须满足约束（3）。

$$B(1,v)=B(0,v+1)\tag{3}$$

在平滑路径规划任务中，除了为机器人创建一个长度最优的安全路径之外，我们还需要考虑机器人的运动学约束。最小的约束是机器人跟踪的整个路径必须在整个域中具有连续的曲率。这意味着必要条件是表示路径的函数的一阶导数必须可导，并且其导数不是一个常数。为了简化方程（2）并满足必要条件，选择了三次贝塞尔曲线，因为它具有三阶多项式函数。Song、Wang和Sheng（2016）在他们的工作中也使用了三阶分段贝塞尔曲线，但获得的路径在航点（锚点）处具有突变的曲率。获得的路径仍然需要在$v$变化的地方满足另外两个约束。这些约束由（4）和（5）给出。

$$\dot B(1,v)=\dot B(0,v+1)\tag{4}$$ $$\ddot B(1,v)=\ddot B(0,v+1)\tag{5}$$

从方程（2）中，我们可以构造每个贝塞尔曲线段的控制点，以满足条件（3-5）。通过将（2）代入（4）和（5），并简化，（4）和（5）可以分别重写为（6）和（7）。

$$C^1_v+4(C^1_{v+1})+C^1_{v+2}=4P_{v+1}+2P_{v+2}\tag{6}$$ $$||C^2_v|| =||C^1_{v+1}||\tag{7}$$

根据上述方程，我们可以将它们扩展为一个包含$n-2$个方程和$n$个变量的方程系统。为了约束最后的2个变量$C^1_0$和$C^2_{n-1}$，可以考虑贝塞尔曲线的属性，该属性规定第一个和最后一个控制多边形与曲线相切。$C^1_0$和$C^1_{n-1}$分别由（8）和（9）给出。

$$C^1_0=P_0+\begin{bmatrix} cos(\psi_0)\\sin(\psi_0) \end{bmatrix}\frac{||P_1-P_0||}{3}\tag{8}$$ $$C^1_{n-1}=P_{n-1}+\begin{bmatrix} cos(\psi_{n-1})\\sin(\psi_{n-1}) \end{bmatrix}\frac{||P_{n-1}-P_{n-2}||}{3}\tag{9}$$

实验中，$C^1_0$和$C^1_{n-1}$的大小分别由路径上对应点与相邻点之间的笛卡尔距离的三分之一确定。$C^1_{n-1}$并不用于构建PCBC，而是用于完成方程系统。

方程（6-9）结果表明PCBC仅依赖于锚点集和机器人航向。为方便起见，我们将每个曲线段命名如下图所示：

在图3中，固定锚点是曲线两端的点，自由锚点是其余的锚点。为了优化路径的长度，必须定义用于确定PCBC长度的函数。方程（10）定义了相对于u的第t个曲线段的弧长：方程（11）产生了相对于曲线参数的PCBC的总弧长。通过使用这些方程，我们可以获得PCBC的总弧长，以便在后续章节中评估路径的最优水平。

$$l(u,v)=\int^u_0||\dot B(u,v)||du\tag{10}$$ $$L(u,v)=\sum^{v-1}_{v=0}l(1,v)+l(u,v)\tag{11}$$

2.2.通用遗传算法

在最常见的用法中，遗传算法（GA）被视为受到进化过程启发的优化器。遗传算法基于英国博物学家查尔斯·达尔文发展的生物进化理论来模拟自然界中的进化过程。该算法将某些优化问题的潜在解的特征编码为类似染色体的数据。算法编码的数据类型被称为“基因型”。这些特性将确定解的“表现型”。在许多情况下，基因型和表现型将非常不同，选择基因型以确定表现型也会影响结果。为了获得最优结果，遗传算法循环执行多个操作，直到达到某些标准为止，算法将终止。普通的遗传算法具有三个主要操作符：选择操作符、交叉操作符和变异操作符。算法从一个随机种群开始（种群中每个个体的随机基因），种群中包含一定数量的个体。以下是下面操作的迭代过程，直到满足某些给定条件为止：

• 选择操作：种群中的个体将根据所需的优化函数的结果进行评估，该函数称为适应度函数。个体的适应度值越大，它们被选中并放入交配池的概率就越高。在交配池中，将进行交叉操作。还需要注意的是，交配池中的个体可能会重复。

• 交叉操作：在交配池中，选定的个体将配对。然后，个体对将将基因传递给后代。有许多类型的交叉操作符：单点交叉、多点交叉、均匀交叉等。交叉操作符的选择取决于遗传算法的设计者。

• 突变操作：在形成后代后，根据给定的概率，后代可能会由突变操作符引发突变。这意味着后代的基因不会继承父母的基因，而会再次随机化。突变操作符用于保持一代到下一代的遗传多样性。

在交叉操作期间，后代不会继承表现型，而只会继承父母的基因型信息。染色体中的任何基因都将在外部显示其表现型。基于表现型，GA能够计算每个个体的适应度水平。根据适应度值，GA可以继续选择和繁殖后代，为下一代继续进行

3.方法

3.1. 初始化种群

我们可以将路径视为一个个体$x$，具有表示路径“表现型”的分段三次贝塞尔曲线（PCBC）。该问题的预期表现型是针对给定地图、初始姿态和目标姿态，为差动轮移动机器人（图2）创建的最优长度和无障碍PCBC。否则，我们只需要锚点来形成PCBC。因此，锚点集可以表示路径的基因型。在锚点集中，给定的起点和目标点被从染色体中移除，因为它们不可变。染色体中剩余的锚点称为自由锚点集。每个自由锚点充当染色体中的一个基因。染色体的结构可以表示为锚点数组：
在开始时，HGA使用预定义的种群大小m初始化种群，其中每个个体的染色体随机分配在可行集上（部分无碰撞地图）。在随机创建锚点集后，根据方程（6-9）形成PCBC。让$S^n=\{x_i\}^m_{i=1}$表示包含$m$个个体的种群，$\{P^i_j\}^{n-1}_{j=1}$表示路径$x_i$的自由锚点集。在HGA参与过程之前，我们需要考虑以下特殊情况：

• 情况1：如果路径的两个端点不在可行集中，GA将立即终止。
• 情况2：在没有任何自由锚点$（n = 0）$存在的情况下形成的PCBC，HGA将不会被使用，因为染色体的长度取决于自由锚点集的大小。这是PCBC仅包含一个曲线段且路径完全独立于染色体的最简单情况。由于这种情况不太多样化，我们只需要检查是否有障碍物违反了路径。
• 情况3：当$n = 1$时，HGA将忽略交叉操作符，表现为一种随机方法。

3.2. 适应度函数

适应度函数是帮助种群中的个体在多代中能够收敛到理想路径的因素之一。在我们的情况下，HGA将根据安全性和距离优化路径。因此，适应度函数的结果取决于路径的长度和安全级别。基于每个个体的适应度值，算法可以决定好的配对，以便将它们的基因传递给下一代。出于这个原因，我们将建立适应度函数，其中期望值是最高的。
让$L(x_i)$表示由方程（10）和（11）计算得到的曲线路径$x_i$的长度。让$f(x_i)$表示$x_i$的适应度值，适应度函数可以表示为（12）。

$$f(x)=\frac{1}{L(x)+p\cdot q}\tag{12}$$

在上述公式中，$p$是惩罚值，$q$是路径遇到障碍物的次数。根据Wang等人（2002年）的研究，惩罚策略是处理遗传算法中不可行解的常见技术。由于选择安全路径的优先级较高，通常将$p$设置为较大的值，以排除短但不可行的路径。另一方面，在找到可行解的情况下，获得的路径将更有可能在可行解集中具有其潜在的相邻解。为了能够找到这些潜在路径，我们建议了在变异操作符部分明确说明的局部搜索方法。

3.3. 选择操作符

根据适应度值，每个个体被选中用于繁殖下一代的机会都不同。这一任务由选择操作符来保证。设$X$是随机变量，可以以概率密度函数（13）中的任何路径作为其结果。

$$g_X(x_i)=\frac{f(x_i)}{\sum^m_{j=1}f(x_j)}\tag{13}$$

为了从当前种群中以相同大小繁殖下一代，HGA将随机选择$m$个繁殖对，每个个体被选中的概率与密度函数$g_X(x_i)$相对应。繁殖对的集合称为交配池。交配池中的每对个体将经历交叉阶段，以创建下一代。

3.4. 交叉操作符

在HGA中，特定繁殖对的后代染色体是通过组合给定繁殖对的染色体形成的。有许多组合染色体的方法，其中一点交叉是最简单的方法，如图4所示。在一点交叉中，会随机选择两个父代中的共同交叉点，并通过交换两个父代尾部的基因来生成后代。然而，交叉操作符具有随机选择的交叉点，这在路径优化问题中没有意义。我们可以根据PCBC首次遇到障碍物的曲线段索引来确定此值。假设如果某个路径在第$j$个曲线段的某处穿过了障碍物，那么算法将将该路径的前$j-1$个自由锚点传递给后代，其余自由锚点将从另一个路径接收。因此，后代在继承的曲线段中很少会遇到障碍物，因为路径中的任何自由锚点的更改只会影响与该点相邻的几个贝塞尔段。通过这种方式，HGA可以忽略不可行的路径，并重新传递几乎不与障碍物碰撞的贝塞尔曲线段。我们将交配池中的任何繁殖对，例如$x_{i_1}$和$x_{i_2}$，视为下一代的父母。每对只繁殖一个孩子$y$：设$C^{i_1}_{j_1}$和$C^{i_2}_{j_2}$分别是$x_{i_1}$和$x_{i_2}$的PCBC首次违反障碍物的贝塞尔曲线段。如果$j_1 > j_2$，我们将选择$j_1$作为共同的交叉点，$x_{i_1}$将前$j_1-1$个自由锚点传递给后代，其余自由锚点将由$x_{i_2}$传递，反之亦然。如果$j_1=j_2$，则前$j_1-1$个自由锚点将由$x_{i_1}$或$x_{i_2}$随机传递

然而，使用预定的交叉点进行交叉过程会使种群迅速失去多样性，有时意外丢弃一代中的最佳组合。HGA可以通过多代使用高突变率来处理这些问题，这将在下一节中清楚描述。

3.5. 变异操作符

与选择操作符相反，变异操作符在HGA中保持了种群的多样性。变异操作符还弥补了交叉操作符的不足之处，因为它是进程中的最后一个操作符。在这项工作中，变异操作简单地是在经过交叉过程形成的某个后代后随机再生。设$w$为确定每个个体变异概率的变异率。评估和选择$w$会影响算法的收敛性。因此，我们提出了动态变异率方法，以适应种群的每个进化阶段。首先，我们介绍了在这项工作中使用的两种不同类型的变异：

• 全局变异（全局搜索）：从给定地图的整个可行集中随机选择这些点，随机为所选的后代再生自由锚点集。这种类型的变异有助于HGA继续探索以在地图中找到可行解。
• 局部变异（局部搜索）：HGA尝试通过在其局部环境中随机修改这些点来改进所选后代染色体中的每个自由锚点。局部环境是由以正在考虑的锚点为中心的圆形边界定义的封闭球，其半径称为局部搜索范围半径（LSRR）。这种类型的变异有助于HGA利用优势个体的邻居来找到最佳新路径并减少测试数据。

设$x_{best}$是当前一代中具有最高适应度值的路径，称为优势个体。在HGA中，此实例将在下一代中保留，不受变异操作符的影响。设$x_{bestOfBest}$是在连续的几代中具有最高适应度值的路径，称为历史性优势个体。这个特殊实例不会受到变异的影响，并将保留多代，直到被具有更高适应度值的其他优势个体替换。当种群的多样性不能通过多个连续的世代来改善$x_{best}$时，这意味着全局变异不再有意义。设$h$为连续的连续世代数量，其中$f(x_{bestOfBest}) \geq f(x_{best})$。设$h_s$是具有相同历史优势个体的最大连续世代数量。设$h_t$是具有相同历史优势个体的最大连续世代数量。在我们提出的算法中，$h_s$用于切换变异模式，$h_t$用于终止演化过程。基于$h_t$，可以通过（14）形成变异率。

$$w = \frac{h}{h_t}\tag{14}$$

如果$h > h_s$，HGA将从全局变异切换到局部变异。一旦种群切换到局部变异，就不会再切换回全局变异。为了加速收敛，通常的变异在随机重建锚点集时将不会有效，因此将其替换为局部变异（图5）。

3.6 染色体长度自适应

这些过程将一直重复，直到 $h > h_t$。HGA的返回结果是当前的历史优势个体。如果 $x_{bestOfBest}$ 仍然遇到障碍物，那么当前种群中构成个体的锚点数量很可能不能找到可行的解决方案。因此，算法将删除这个种群并用一个新的种群替换它，新种群具有更多的锚点，即在当前染色体中添加一个以上的基因。这个过程将一直重复，直到不止一个 $x_{bestOfBest}$没有与地图中的障碍物发生碰撞。从实验上看，有很多原因可以在这种情况下终止算法。锚点集的大小越大，路径长度优化的时间就越长。然而，算法的最优水平会降低，处理时间会随着锚点集的大小增加而增加。因此，合理的做法是在连续出现两个具有可行解的种群时停止算法并返回结果。算法的结果是在两个种群的$x_{bestOfBest}$中选择的最短路径。