HPSO-ACO算法：仓库巡检机器人路径优化方法

作者：Jianxian Liu，Hongyuan Liu

编辑：东岸因为@一点人工一点智能公众号

图片

论文地址：https://www.tandfonline.com/doi/full/10.1080/08839514.2023.2254048

随着智能化的日益普及，许多企业的仓库检查工作都是通过机器人完成。但是，由于仓库检查存在多个目标点，智能机器人检查路径规划的低效率则成了亟需解决的问题。

为了解决这个问题，本文提出了一种基于混合粒子群算法（HPSO）的HPSO-ACO算法，对蚁群算法（ACO）的参数进行了优化，并建立了仓库管理中巡检机器人的路径优化模型。

实验结果表明，在相同条件下，与HPSO算法和ACO算法相比，所提出的方法具有更快的收敛速度、更少的迭代次数和更短的最优路径，为巡检机器人的路径优化提供了理论参考。

01 简介

随着物流业的快速发展，对标准化仓库管理的需求越来越大。随着智能化的日益普及，许多企业综合利用物联网和人工智能技术实现对巡检机的控制，使用仓库巡检机器人进行日常巡检工作。巡检的路径规划是机器人自动导航中的一个关键问题，目的是在多目标条件下为机器人选择最短、最高效的移动过程。然而，由于缺乏高效的路径规划算法作为技术支撑，传统的巡检机器人在路径自动规划中存在计算能力弱、资源消耗高等问题。巡检机器人的多目标路径规划本质上是一个旅行商问题，因此使用启发式算法来解决这个问题已经成为一个重要的研究方向。

针对上述问题，Dugulana，M.等人将Q-Learning与神经网络算法相结合，实现了移动机器人在不确定工作空间中的无碰撞轨迹规划。Xiong，N.Z.等人提出了一种时间禁忌ACO算法，改善了动态环境下ACO路径规划的收敛速度慢、全局搜索能力差的问题。Huang，M.D.等人提出了一种结合角度因子和可见性的机器人路径规划方法；实验结果表明，该算法在全局路径规划方面优于遗传算法和传统蚁群算法。Porta，G.M.等人提出了一种基于简单ACO的新方案。实验结果表明，该方法有效地提高了路径规划的速度。Xuan，R.Z.等人提出了一种利用蚁群算法优化A * 算法的机器人路径规划方法，实验结果表明该方法的搜索路径优于A * 算法）。

通过文献调查发现，优化算法在机器人路径规划中有着广泛的应用，可以为机器人提供最优的路径规划。几种常见优化算法的比较如表1所示。禁忌搜索优化（TSO）和模拟退火（SA）算法是单体优化算法，它们在解域（the solution domain）中的搜索空间较小，求解效率较低。蚁群算法（Ant Colony Optimization，ACO）是一种算法结构，而混合粒子群优化（Hybrid Particle Swarm Optimization，HPSO）是基于群体协作的随机搜索算法。HPSO和ACO的特点是群体优化算法，它们可以以单个单位的形式接收次优解，即跳出局部最优解；因此，它们在解决检查机器人的路径规划问题中应用更为广泛。

图1 几种常见优化算法对比

Ming，L.Y.等人提出了一种基于自适应ACO和HPSO的融合模型，实现了智能机器人在扰动环境中的路径规划。Wei，P.C.等人提出了一种基于HPSO算法和ACO算法的网格调度优化算法，有效地提高了任务调度的效率。Kuo，R.J.等人提出了一种新的将ACO和HPSO相结合的HPSO，有效地解决了车间调度问题。Wu，C.Z.等人引入了一种改进的ACO来代替道路因素，有效地降低了9.73%~13.63%的平均城市道路拥堵率。

现有文献更多地关注解决实际问题，但在机器人路径自动规划过程中，算力和资源消耗问题尤为重要，却很少受到关注。同时，通过文献调查发现，HPSO算法和ACO算法的结合可以提高算法的整体性能。因此，本文提出了一种基于HPSO的巡检机器人路径规划方法来优化ACO，以解决传统巡检机器人路径规划能力较弱的问题。在该方法中，使用HPSO来优化ACO的参数。同时，对信息点更新方法进行了改进，提高了蚁群算法的收敛迭代速度和局部搜索能力。

本文的贡献如下：

· 将HPSO和ACO相结合，建立了HPSO-ACO算法，提高了HPSO算法和ACO算法的优化能力。

· 基于HPSO-ACO算法，建立了智能仓库巡检机器人路径优化模型，实现了多目标条件下巡检机器人的路径优化。

文章其余部分的结构如下。第二章建立了相关模型，介绍了基于HPSO的改进ACO。第三章对上述模型和算法进行了比较仿真分析，最后提出了结论和讨论。

02 模型建立

2.1 ACO

ACO的原理结构如图1所示。根据气味轨迹不断优化路径，直到找到最佳路径。

图1 ACO原理架构

$P^k_{ij}(t)$ 是指ant（机器人）$k$当前处于第$i$ 个巡逻点时选择移动到第$j$个巡逻点的概率，公式如下：

2.2 HPSO

粒子群优化（PSO）是一种群智能算法，它将优化问题的解抽象为没有质量和体积的粒子，每个粒子都表现出三个特征值：位置、速度和适应度函数值。设粒子数为$N$，在$D$维搜索空间中，粒子$i$的位置为$X_i=[x_{i,1},x_{i,2},...,x_{i,d}]$ ，速度为$V_i=[v_{i,1},v_{i,2},...,v_{i,d}]$ 。这受粒子本身的最佳位置和全局最佳位置的控制，并不断更新，直到找到最佳解。更新粒子位置和速度的方法，如

在优化过程中，传统的粒子群优化算法可能会收敛到局部最优解，导致计算误差较大。借鉴遗传算法中混合（hybridization）的概念，在每次迭代中，根据混合的概率，将指定数量的粒子放入混合池中，并将池中的粒子相互交叉混合，生成相同数量的子粒子，这些子粒子取代了父粒子，如图2所示。

图2 HPSO原理架构

子位置$child(x)$和子速度$child(v)$更新如下：

图片

当被困在不同局部最优中的两个粒子进行混合操作时，它们往往可以脱离局部最优。因此，引入混合算法可以提高种群的全局优化能力。

2.3 HPSO-ACO

ACO根据信息点浓度的变化求出最优路径。由于属于经典的概率算法，算法的初始参数是根据人们的经验随机给定的，导致算法的稳定性较差。相反，与ACO不同，HPSO具有快速跳出局部最优的能力，能够快速有效地优化ACO的参数。因此，本文使用HPSO对ACO的参数$\alpha,\beta,\rho$ 进行优化，以解决智能巡检路径优化问题。

图3 HPSO-ACO解决方案流程图

HPSO-ACO的流程如图3所示，具体步骤如下：

2.4 智能巡检机器人路径规划模型的建立

智能巡检机器人想要巡检仓库中的每个巡检点，每个巡检点只巡检一次，最后返回到初始巡检点，找到最短的巡检路径。数学模型如下：

如果访问m个巡检点的路径由L表示，$L=(L_1,L_2,...,L_m)$，$L_m=(x_m,y_m)$，则两个巡检点$i$和$j$之间的距离为：

巡检路径的总距离为：

方程（6）是针对本文中设计的算法要优化的模型。信息点更新方法的选择对ACO的解决方案质量有着非常重要的影响。以下是更新传统ACO信息点的公式：

本文的信息点更新公式：

$G_k$表示“蚂蚁”在检查过程中的总距离，$Q$表示信息素含量。针对传统ACO无法在短时间内积累足够信息点的问题，信息点在整个算法求解过程中不断更新。当参数发生变化时，信息点不会重新初始化。这种方法可以在短时间内保留和积累足够的环境信息，大大减少ACO迭代次数，减少时间消耗。当没有最优解时，信息点更新公式如等式（7）和等式（8），所示。当出现更好的解决方案时，“蚂蚁”留下的信息点密度会提高，信息点会根据以下公式更新：

在等式（10）中，$\tau_{ij}(t)$是从等式（9）中获得的。$\Delta \tau_{ij}(t)'$ 是蚂蚁在路径迭代求解过程中在最优路径$[i,j]$ 上留下的信息点密度，包括：

图片

因此，步骤2可以改为：将每个初始粒子对应的参数值返回给ACO。一个粒子对应于一组参数$\alpha,\beta,\rho$ ，使用这组参数来操作ACO。当参数发生变化时，信息点将不会重新初始化。

03 实验结果与分析

ACO、HPSO、HPSO-ACO三个模型的实验结果的性能比较如表2所示。HPSO在939次迭代后收敛，这大于ACO算法的55次迭代。然而，HPSO-ACO的迭代次数明显好于HPSO算法的939次迭代和ACO的55次迭代，表明HPSO-ACO节省了更多的计算资源。

表2 三种模型的实验结果对比

HPSO-ACO的计算时间比ACO算法和HPSO算法的计算时间短，表明HPSO-ACO的计算速度快于ACO算法或HPSO算法。

HPSO-ACO计算出的最优路径长度为120.58 m，比HPSO的最佳路径长度短36.75 m比ACO的最优路径长度短。可以解释为，HPSO-ACO算法的计算结果更接近全局最优解，优化效果更好。

通过分析可以看出，HPSO-ACO与ACO相比减少了2.21%的路径，与HPSO相比减少了6.91%的路径。总之，HPSO-ACO算法的性能优于HPSO和ACO算法。

04 结论与讨论

随着企业仓库管理对自动化的需求不断增加，许多检查任务都是通过机器人完成的。然而，由于仓库检查的目标点多，在路径自动规划中存在计算能力弱和资源消耗等问题。为了实现检测机器人的自动路径规划，提出了一种基于HPSO和ACO的路径优化方法。基于X企业仓库的映射模型，实验分析表明，与ACO和HPSO算法相比，HPSO-ACO算法在优化闭曲线检测路径方面节省了更多的计算资源，计算速度更快。这种方法不仅提高了机器人的检测效率，而且降低了检测成本。

ACO算法具有正反馈的特点，容易导致算法陷入局部最优，参数选择更依赖于经验和试错。初始参数不当会削弱算法的优化能力。HPSO算法的初始收敛速度相对较慢，但其内部混合机制不依赖于问题信息，可以很好地促进算法跳出局部最优。HPSO-ACO算法可以依靠HPSO的混合机制，使ACO算法更容易跳出局部最优，加快了算法的整体求解速度，提高了算法的优化能力。

本文的研究成果也存在一定的局限性。为了便于实验，对地图进行了简化，在实际的仓库环境中，不可避免地会出现各种障碍。在有障碍物的地图环境中，要实现机器人路径规划和自动避障，需要将其与其他新算法相结合，HPSO-ACO模型的适应性有待进一步研究。另一方面，该项目使用二维地图。如果实际的仓库地图是三维空间地图，则需要进一步的实验来证明HPSO-ACO模型的性能。

HPSO-ACO算法能够在现有基础上有效提高其全局优化能力，对解决旅行商问题具有一定的指导意义。同时，本研究的研究成果在城市道路规划、商品配送、无人机自动导航等方面也具有一定的推广价值。