无人系统中智能体自主路径规划的优化方法和系统

摘要

本发明提供无人系统中智能体自主路径规划的优化方法和系统，涉及无人系统技术领域。该方法包括以下步骤：获取智能体的路径优化函数；基于不动点定理，将智能体的路径优化函数转换为等价的不动点方程；基于不动点方程，获取完备单纯形序列；基于完备单纯形序列确定粒子群优化算法的初始种群规模和粒子初始位置，获取智能体的最优路径规划。本发明将智能体路径优化函数的极值优化问题转换为不动点方程组求解问题，再以完备单纯形序列确定粒子群优化算法的初始参数。完备单纯形序列几乎包含到了路径优化函数的全部极值点，保证了种群的多样性和粒子搜索方向的有效性，从而提高无人系统中智能体路径规划过程的鲁棒性和寻找到最优路径的效率。

说明书

技术领域

本发明涉及无人系统技术领域，具体涉及一种无人系统中智能体自主路径规划的优化方法和系统。

背景技术

随着人工智能和智慧制造加工领域研究的不断创新与突破，在社会各个领域中，诸如智能体、智能汽车和无人机等智能无人系统的应用也越来越普及。在智能无人系统的控制过程中，如何实现自主导航一直是研究的重点领域。路径规划作为自主导航的重要组成部分，其主要目标是：在避免碰撞障碍物的情况下，寻找到一条最优的路径使智能无人系统在工作环境中从起始位置移动到目标位置。

在现有技术研究中，粒子群优化算法(Particle Swarm Optimization，PSO)被广泛应用于智能体的路径规划。然而PSO作为一种经典的群智能算法，也面临着共开采和开发的平衡问题，即粒子如何在搜索过程中分配向未知区域进行全局搜索和继续在原先搜索轨迹进行局部搜索的能力。为了解决这一问题，众多学者通过不断优化算法设计，期望实现智能无人系统移动路径的最优规划。在现有的参数改进研究中，动态自适应的调整策略能较大幅度提高PSO运用在智能体路径规划上的鲁棒性，已成为当前研究主流。

然而，现有关于PSO参数设置的研究，各参数设置方式相对独立，且粒子种群初始状态、飞行速度等其余算法参数的调整策略多以经验参考或随机生成的方式确定，不可控性高，降低了智能体在路径规划过程中的鲁棒性。

(一)解决的技术问题

针对现有技术的不足，本发明提供了一种无人系统中智能体自主路径规划的优化方法和系统，解决了现有技术体系中智能体路径规划及优化过程中鲁棒性较低的问题。

(二)技术方案

为实现以上目的，本发明通过以下技术方案予以实现：

本发明提供一种无人系统中智能体自主路径规划的优化方法，该方法由智能体执行，包括以下步骤：

S1、获取智能体的路径优化函数；

S2、基于不动点定理，将所述智能体的路径优化函数转换为等价的不动点方程；

S3、基于所述不动点方程，获取完备单纯形序列；

S4、基于所述完备单纯形序列确定粒子群优化算法的初始种群规模和粒子初始位置，实现智能体的最优路径规划。

优选的，所述步骤S2具体为：

基于构造不动点方程F(X)＝X-f'(X)；根据不动点定理，若X*是不动点方程的解，则满足f'(X*)＝0，使得路径优化函数y＝f(X)在点X*处取得极小值；

其中：

f(X)为智能体的路径优化函数；

X为n维度优化变量；

g_i(X)为函数可行域空间内的m个约束函数。

优选的，所述步骤S3具体为：

根据不动点定理，引入近似不动点概念替代精确不动点：设任意ε>0，若|X-f′(X)|<ε，则称X是f(X)的一个近似不动点，|X-f′(X|表示向量的模；具体过程如下：

S301、对不动点方程的搜索空间进行划分，具体为：

在n维欧式空间Rⁿ中，用n族直线x_i＝mh_i(i＝1，2，…，n)将不动点方程的搜索空间划分为均匀的多面体，其中m为精度控制；

S302、对划分后的搜索空间进行单纯剖分，得到单纯形，具体为：

对于欧式空间Rⁿ，N＝{1，2，…，n}，π是N的置换，Rⁿ的n个基底向量：u¹，…，uⁿ，满足：u＝u¹+…+uⁿ＝(1，…，1),是n阶单位矩阵的n列；设为Rⁿ中整点集，若以k₁(y⁰,π)记n维单纯形<y⁰，y¹，…，yⁿ>，其中yⁱ＝y^i-1+u^π(i)，i∈N，记k₁(y⁰,π)组成的集合为K₁；

S303、对单纯形进行标号，输出完备单纯形序列，具体为：

采用整数标号法或向量标号法对单纯形进行标号，根据逻辑判别式，得到满足标号要求的完备单纯形序列，以完备单纯性序列的取值范围作为更新的搜索空间。

优选的，所述步骤S4具体为：

在n维解空间内，每个粒子位置为：完备单纯形序列x_i＝(x_i1，x_i2，...，x_in)，完备单纯形序列的个数表示种群规模；飞行速度：v_i＝(v_i1，v_i2，...，v_in)；粒子个体最优位置记作p_best＝(p_i1，p_i2，...，p_in)，全局最优位置g_best＝(p_g1，p_g2，...，p_gn)，则当前粒子根据以下公式调整微粒当前位置x_id和当前速度v_id；

v_id(t+1)＝ωv_id(t)+c₁(p_id-x_id)+c₂(p_gd-x_id)

x_id(t+1)＝x_id(t)+v_id(t+1)

其中：

p_id是当前粒子个体最优位置；

p_gd是当前全局最优位置；

v_max表示粒子最大飞行速度；

-v_max表示粒子最小飞行速度；

ω为惯性权重；

c₁、c₂为加速常数。

优选的，以完备单纯性序列的取值范围作为飞行速度的取值范围。

优选的，所述惯性权重的设置方式为：

采用惯性递减权重，权重ω值在迭代过程中逐步减小，具体为：

其中：

ω_max＝0.9；

ω_min＝0.4。

本发明还提供一种无人系统中智能体自主路径规划的优化系统，所述系统包括智能体，所述智能体包括：

至少一个存储单元；

至少一个处理单元；

其中，所述至少一个存储单元中存储有至少一条指令，所述至少一条指令由所述至少一个处理单元加载并执行以实现以下步骤：

S1、获取智能体的路径优化函数；

S2、基于不动点定理，将所述智能体的路径优化函数转换为等价的不动点方程；

S3、基于所述不动点方程，获取完备单纯形序列；

S4、基于所述完备单纯形序列确定粒子群优化算法的初始种群规模和粒子初始位置，实现智能体的最优路径规划。

(三)有益效果

本发明提供了一种无人系统中智能体自主路径规划的优化方法和系统。与现有技术相比，具备以下有益效果：

本发明提出一种无人系统中智能体自主路径规划的优化方法和系统，将智能体的路径优化函数极值优化问题转换为不动点方程组求解问题，再以完备单纯形序列确定粒子群优化算法的初始种群规模和粒子初始位置。完备单纯形序列几乎包含到了路径优化函数的全部极值点，保证了种群的多样性和粒子搜索方向的有效性，从而提高无人系统中智能体路径规划过程的鲁棒性和寻找到最优路径的效率。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例一种无人系统中智能体自主路径规划的优化方法的流程图；

图2a为10×10栅格地图；

图2b为20×20栅格地图；

图3a两种策略收敛曲线图；

图3b标准PSO算法策略路径规划；

图3c本发明实施例策略路径规划；

图4a两种策略收敛曲线图；

图4b标准PSO算法策略最优路径；

图4c本发明实施例策略最优路径。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本申请实施例通过提供一种无人系统中智能体自主路径规划的优化方法和系统，解决了现有技术中的智能体在路径规划过程中的鲁棒性过低的问题，实现提高智能无人系统在路径规划中鲁棒性。

本申请实施例中的技术方案为解决上述技术问题，总体思路如下：

本发明实施例提出一种无人系统中智能体自主路径规划的优化方法和系统，将智能体路径优化函数的最优极值问题转换为不动点方程组求解问题，再以完备单纯形序列确定粒子群优化算法的初始种群规模和粒子初始位置。完备单纯形序列几乎包含了路径优化函数的全部极值点，保证了种群的多样性和粒子搜索方向的有效性，从而提高无人系统中智能体路径规划过程的鲁棒性和寻找到最优路径的效率。

为了更好的理解上述技术方案，下面将结合说明书附图以及具体的实施方式对上述技术方案进行详细的说明。

本发明实施例提供一种无人系统中智能体自主路径规划的优化方法，该方法由智能体执行，如图1所示，上述方法包括以下步骤：

S1、获取智能体的路径优化函数；

S2、基于不动点定理，将所述智能体的路径优化函数转换为等价的不动点方程；

S3、基于所述不动点方程，获取完备单纯形序列；

S4、基于所述完备单纯形序列确定粒子群优化算法的初始种群规模和粒子初始位置，实现智能体的最优路径规划。

本发明实施例在具体实施时，将智能体的路径优化函数极值优化问题转换为不动点方程组求解问题，再以完备单纯形序列确定粒子群优化算法的初始参数(初始种群规模和粒子初始位置)。完备单纯形序列几乎包含到了路径优化函数的全部极值点，保证了种群的多样性和粒子搜索方向的有效性，从而提高智能无人系统在路径规划中的鲁棒性和寻找到最优路径的效率。

下面对各步骤进行详细描述：

本发明实施例是一种无人系统中智能体自主路径规划的优化方法，该方法由智能体执行，智能体是指驻留在某一环境下，能持续自主地发挥作用，具备驻留性、反应性、社会性、主动性等特征的计算实体。该方法包括步骤S1～S4：

S1、获取智能体的路径优化函数。

具体的，智能体的内部的数据处理模块根据智能体的行驶空间、速度、当前位置等数据构建智能体的优化函数。

S2、基于不动点定理，将智能体的路径优化函数转换为等价的不动点方程。

其中，

不动点定理为：

定理1：设X是Rⁿ的一个子集，若对于X中每一点x，都有确定的f(x)∈X与之对应，则f是X的一个自映射，记作f：X→X。

定理2：设X是非空集合，f：X→X为其自映射，若存在x*∈X，满足f(x*)＝x*，则称x*为f的一个精确不动点。

定理3：设(X，ρ)为一度量空间，T∶X→X为一映射，若存在L∈[0，1)，使得任意x，y∈X，有ρ(T(x)，T(y))≤Lρ(x，y)，则称T是X上的压缩映射。

定理4：近似不动点：设ε为任意正数，若对于压缩映射T∶X→X，|x-f(x)|表示n维欧式空间Rⁿ的中向量x-f(x)的模，若存在点x*满足|x^*-f(x^*)|<ε，则称x*为f的一个近似不动点。

定理5：对n维欧式空间进行剖分，寻求这样一种多面体，在映射f的作用下它第一个顶点的第一个坐标分量下降，第二个顶点的第二个坐标分量下降，第n个顶点的第n个坐标分量下降，第n+1个顶点的n个坐标分量都保持不减，若这种多面体直径足够小，其n+1个顶点在映射f作用下的变化情况相差不会太远，称这样的多面体为完备单纯形，每个顶点都可以视为不动点。

Banach不动点定理：又称压缩映射定理，设(X，ρ)为一非空的完备度量空间，T∶X→X为一压缩映射，则T在X中存在惟一的不动点，Banach不动点定理指出了不动点方程T(x)＝x解的存在性和惟一性。

将智能体的路径优化函数转换为等价的不动点方程为：

其中：

f(X)为智能体的路径优化函数；

X为n维度优化变量；

g_i(X)为函数可行域空间内的m个约束函数。

求路径优化函数y＝f(X)最值(最大值与最小值可以相互转换，本发明实施例以最小值为例)，若路径优化函数在定义域内处处可导，则最值必然出现在f'(X)＝0的位置，反之，f'(X)＝0的点可能是极值、拐点等，不一定是最值。通过构建不动点方程，筛选出f'(X)＝0的点，再通过路径优化函数判断，可极大程度降低算法搜索空间。因此，构造不动点方程F(X)＝X-f'(X)，根据不动点定理中的定理2，若函数F(X)存在精确不动点X*，必然满足F(X*)＝X*-f'(X*)＝X*，由此可得f'(X*)＝0，路径优化函数y＝f(X)在点X*处取得值。

S3、基于所述不动点方程，获取完备单纯形序列。

具体的，在很多现实问题中，往往虽然能够证明不动点的存在，但若要通过数值计算求出其精确解，计算开销往往很大。比如，x²-2＝0精确解是无限循环的，必须近似取值才能参与随后的计算。因此，为保证求解过程能够稳定收敛，根据不动点定理中的定理4，引入近似不动点概念替代精确不动点：设任意ε>0，如果|X-f′(X)|<ε，则称X是f(X)的一个近似不动点，|X-f′(X)|表示向量的模。通过单纯剖分搜索近似不动点集的算法框架如图2所示。具体包括步骤S301～S303：

S301、对不动点方程的搜索空间进行划分，具体为：

在n维欧式空间Rⁿ中，用n族直线x_i＝mh_i(i＝1,2,…,n)将不动点方程的搜索空间划分为均匀的多面体，其中m为精度控制，对于特定领域内的高精度优化可适当细化步长，但步长过细会增加算法复杂度，降低运算效率，本发明实施例以完备单纯性序列的取值范围作为更新的搜索空间，这样缩小了搜索空间的范围，提高求解效率。

S302、对划分后的搜索空间进行单纯剖分，得到单纯形，具体为：

对于n维欧式空间Rⁿ，N＝{1，2，…，n}，π是N的置换。Rn的n个基底向量：u¹，…，uⁿ，满足：u＝u¹+…+uⁿ＝(1，…，1),是n阶单位矩阵的n列。设为Rⁿ中整点集(所有坐标分量均为整数的点的集合)，若以k₁(y⁰，π)记n维单纯形<y⁰，y¹，…，yⁿ>，其中yⁱ＝yⁱ-¹+u^π(i)，i∈N。记所有k₁(y0，π)的集合形成一个K₁剖分。

对划分后的搜索空间按进行单纯剖分，由于N的置换π的变化，从Rⁿ中每个整点y⁰出发，向正侧形成n！个n维单纯剖分，总起来就得到整个Rⁿ的一个K₁剖分。

S303、对单纯形进行标号，输出完备单纯形序列，具体为：

对K₁剖分后所得单纯形进行顶点标号，通过逻辑规则找出完备单纯形即可识别出不动点。标号规则有两种：整数标号法与向量标号法。

整数标号比向量标号的迭代次数多好几倍，但单次算法循环的复杂度低；向量标号法的单次循环比整数标号复杂，但迭代次数较少。对于复杂函数，计算迭代要占用大量机器时间，必须使迭代次数尽可能少，此时向量标号法优于整数标号法；若函数计算简单，则整数标号更省时间。具体规则如下：

向量标号法：据l(x)＝f(x)-x，可得(n+1)×(n+1)矩阵：记为n维单纯形σ＝<y⁰，y¹，…，yⁿ>的标号矩阵。若线性方程L_σw＝v有解，v＝(1，2，…，0)^T，则单纯形为完备单纯形，为一个近似不动点。

整数标号法：根据公式对单纯形每个顶点进行标号，可得序列：Lσ＝(0，1，2…)，记为n维单纯形σ＝<y⁰，y¹，…，yⁿ>的标号序列。在欧式空间Rⁿ中，标号为序列为(0，1，2，…，n)的单纯形为完备单纯形，单纯形每个顶点可视为近似不动点。

在无人系统路径规划的应用中，根据路径优化函数和约束函数的复杂程度，分别采用不同的标号方式进行不动点求解，平衡算法的运算速度和求解精度。

S4、基于所述完备单纯形序列确定PSO的初始种群规模和粒子初始位置，获取智能体的最优路径规划，具体为：

利用基于所述完备单纯形序列确定粒子群优化算法的初始种群规模和粒子初始位置；

在n维解空间内，每个粒子位置为：完备单纯形序列x_i＝(x_i1，x_i2，...，x_in)，完备单纯形序列的个数表示种群规模，飞行速度：v_i＝(v_i1v_i2，...，v_in)，粒子个体最优位置记作p_best＝(p_i1，p_i2，...，p_in)，全局最优位置g_best＝(p_g1，p_g2，…，p_gn)，则当前粒子根据以下公式调整微粒当前位置x_id和当前速度v_id；

v_id(t+1)＝ωv_id(t)+c₁(p_id-x_id)+c₂(p_gd-x_id)

x_id(t+1)＝x_id(t)+v_id(t+1)

其中：

p_id是当前粒子个体最优位置；

p_gd是当前全局最优位置；

v_max表示粒子最大飞行速度；

-v_max表示粒子最小飞行速度；

ω为惯性权重；

c₁、c₂为加速常数。

寻找出的全标单纯形都是近似最优解，即应分布在真实最优解附近，因此，需要以较小的步长进行局部搜索，即最大速度v_max的取值应偏小。遍历所有近似不动点，求出近似优化解的取值范围[-x_jmax,x_jmax]，即飞行速度取值范围为[-x_jmax,x_jmax]，设定最大速度v_max等于v_max＝x_jmax。

设置递减c₁或递增c₂的学习因子选择策略：通过单纯剖分求出的近似不动点分布在不动点方程局部极值点附近，因此在粒子群优化算法初始阶段，应更加关注粒子个体认知，设置较大的学习因子c₁，进行更加深入的局部搜索；在粒子群优化算法后期，更关注全局最优粒子，设置较大的学习因子c₂，避免陷入局部收敛。

与学习因子选择策略相似，需要在前期设置较大的惯性权重，且随着迭代次数增加逐渐变小。因此本发明实施例采用惯性递减权重，权重ω值在迭代过程中逐步减小，采用惯性递减权重，权重ω值在迭代过程中逐步减小，具体为：

其中：

ω_max＝0.9；

ω_min＝0.4。

本发明实施例还提供一种无人系统中智能体自主路径规划的优化系统，所述系统包括智能体，所述智能体包括：

至少一个存储单元；

至少一个处理单元；

其中，所述至少一个存储单元中存储有至少一条指令，所述至少一条指令由所述至少一个处理单元加载并执行以实现以下步骤：

S1、获取智能体的路径优化函数；

S2、基于不动点定理，将所述智能体的路径函数转换为等价的不动点方程；

S3、基于所述不动点方程，获取完备单纯形序列；

S4、基于所述完备单纯形序列确定粒子群优化算法的初始种群规模和粒子初始位置，实现智能体的最优路径规划。

将上述实施例用于对智能机器人的自主路径规划进行优化，具体过程如下：

为了验证本发明实施例的有效性，在两种相同的环境模型下将本发明实施例提供的路径规划的优化方法与传统粒子群优化算法进行对比。实验以Makline为平台，Python3-4.4.0为编程环境进行仿真。实验硬件为：Intel Core i7，3.60GHz CPU，8GB内存，2T硬盘，windows 7操作系统。其中本发明实施例的策略为FP-PSO(Fixed-point Particle SwarmOptimization，不动点粒子群优化算法)。

用栅格法对机器人运动空间进行建模，将二维区域划分成一系列的以基本元素为单元的最小栅格。二维区域的自由区域取值为0，机器人可通行，在图中用白色表示；障碍物区域取值为1，机器人不可通行，用黑色表示。图2a采用10×10的栅格环境，障碍物较少，栅格粒度较大的机器人运动空间；图2b采用20×20的栅格环境，障碍物较多，栅格粒度密集的机器人运动空间。

设m为机器人路径实现经过的栅格数，α_start，α_end分别为预设的机器人运动起始栅格与终点栅格。相邻两个栅格的运动必须通过中心连接，中心点直接以欧式距离进行度量：

机器人路径优化函数：

路径规划目标：机器人经过最少栅格数，实现运动目的，即使得函数F取极小值的m。

对于10×10栅格地图，m取值范围[0:100]，标准粒子群优化算法参数为：粒子数n＝20，最大飞行速度v_max＝20，粒子位置随机确定。设置最大迭代次数为80次，两种参数选择策略的实验结果如图3所示：

对于20×20栅格地图，m取值范围[0:400]，标准粒子群优化算法参数为:粒子数n＝50，最大飞行速度v_max＝100，粒子位置随机确定。设最大迭代次数为160次，两种参数选择策略的实验结果如图4所示：

从实验结果可以看出，本专利提出的基于不动点单纯形法的粒子群参数优化策略，在规划机器人最优路径的过程中，收敛速度和收敛精度上均明显优于标准粒子群优化算法，且鲁棒性较高，在复杂环境下效果更加显著。

综上所述，与现有技术相比，具备以下有益效果：

本发明实施例将智能体的路径优化函数极值优化问题转换为不动点方程组求解问题，再以完备单纯形序列确定粒子群优化算法的初始参数。完备单纯形序列几乎包含到了路径优化函数的全部极值点，保证了种群的多样性和粒子搜索方向的有效性，从而提高无人系统中智能体路径规划过程的鲁棒性和寻找到最优路径的效率。

本发明实施例中，由于初始种群几乎分布在各极值点边缘附近，需要在算法前期倾向于开采，赋予其较强的局部搜索能力；在算法后期倾向于开发，赋予其较强的全局搜索能力，据此原则设置其余相关参数的选择策略，可以极大程度的提高算法整体稳定性。

本发明实施例利用单纯剖分法较强的搜索能力对函数可行域空间进行筛选，提高初始参数质量，降低算法进化代数；同时，本发明的不动点定理条件一般比较弱，但结论却很强，利用其优秀的数学收敛性，平衡算法后期收敛，提高粒子群优化算法跳出局部收敛的能力。

需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。

以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。