技术领域：
本发明涉及在未知环境下基于蚁群和vo算法的路径规划方法，能够实现在环境中存在未知静态障碍物，动态障碍物情况下，进行实时路径规划，属于智能优化算法技术领域。
背景技术：
：
蚁群算法是一种启发式搜索算法，最早由dorigo在1991年提出。该算法模拟自然界中蚂蚁觅食行为。蚁群中的蚂蚁会在自己行进路径上留下信息素，后续蚂蚁也会根据路径上的信息素浓度选择前进方向，通过路径上信息素的积累，蚁群最终会找到一条觅食路径。
社会性动物的群集活动往往能产生惊人的自组织行为，如个体行为显得简单、盲目的蚂蚁组成蚁群以后能够发现从蚁巢到食物源的最短路径。生物学家经过仔细研究发现蚂蚁之间通过一种称之为“外激素”的物质进行间接通讯、相互协作来发现最短路径。受这种现象启发，意大利学者m.dorigo，v.maniezzo和a.colorni通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法——蚁群算法。该算法的出现引起了学者们的巨大关注，在过去的短短二十余年时间内，蚁群算法已经在组合优化、函数优化、系统辨识、网络路由、机器人路径规划、数据挖掘以及大规模集成电路的综合布线设计等领域获得了广泛的应用，并取得了较好的效果。
marcodorigo和thomasstutzle等针对蚁群算法的不足之处做了大量的研究工作，为能够更有效地解决不同领域不同特征的优化问题，提出了精英蚁群优化算法、最大最小蚂蚁系统等多种改进策略[1](参见maniezzov,gambardellalm,luigifd.antcolonyoptimization.newoptimizationtechniquesinengineering[m].springerberlinheidelberg,2004:422-423.)；修正蚁群算法(acs)是一种采用更新局部信息素策略的蚁群算法，能够提高未经访问的路径被选的概率和加强算法的全局搜索能力；应用空间全局信息素更新策略,加强已获得局部最优路径上的信息素的浓度,以致于能够增强算法的正反馈作用以及加快算法的收敛速度[2](参见dorigom,gambardellalm.antcolonysystem:acooperativelearningapproachtothetravelingsalesmanproblem[j].ieeetransonevolutionarycomputation,1997,1(1):53-56.)；针对连续域问题，为提高搜索全局最优解和收敛速度的能力，以及平衡收敛速与收敛速度，提出了一种自适应调整信息素挥发的解更新方式与信息分享机制的改进蚁群算法[3](参见周袅,葛洪伟,苏树智.基于信息素的自适应连续域混合蚁群算法[j].计算机工程与应用,2017,53(6):156-161.)；张纯等人提出了一种利用遗传算法较强的全局搜索能力以及结合蚁群算法的反馈机制的改进算法。应用遗传算法能够进行交叉和变异的能力，在满足一定的条件下对蚂蚁群体进行交叉变异操作得到新的种群，该新种群作为蚁群算法的初始种群对配电网状态进行精细估计，能够更准确的反应配电网状态[4](参见张纯,王立斌.遗传-蚁群算法的配电网状态估计[j].现代电子技术,2016,39(19):165-168)；合理的改进蚁群算法在寻优过程中路径的选择策略，有利于减小蚁群算法易陷入局部最优的可能性，以及有利于提高算法的性能。
技术实现要素：
：
为了保障在未知环境下智能体在规划路径上移动的安全性和可靠性，本发明提供一种基于蚁群算法和vo算法的路径规划设计方法，从而实现在环境中存在未知动态静态障碍物，动态障碍物情况下，安全可靠地进行实时路径规划。本发明利用模拟蚁群觅食策略，通过在地图环境中留下信息素，找出可靠路径，并通过维护全局已知地图矩阵，当在探测半径内发现新的静态障碍物时再进行新一轮路径规划，降低运算开销。同时通过结合vo避障策略，完成在路径规划的同时，对动态障碍物进行有效规避，并且通过设计路径追踪策略，优化智能体移动路线，使其移动路线更加平滑，同时解决了蚁群算法中可能存在的迂回路线问题。
为了实现上述目的，本发明的技术方案如下：在未知环境下基于蚁群和vo算法的路径规划方法，所述方法包括以下步骤：
步骤1.根据已知地图信息构建初始化矩阵map；其中，存在静态障碍物的区域值为1，其他区域值为0；
步骤2.利用蚁群算法，计算全局路径pathlist；
步骤3.得到全局路径后，智能体根据追踪策略进行路径追踪；为每个路径点设置序号，通过trackid记录目前追踪的全局路径上的路径点；
步骤4.根据vo算法，找出下一时刻智能体的运动速度；
步骤5.根据步骤4所算出来的速度，智能体进行移动；
步骤6.若探测半径内没有出现新的静态障碍物，则转向步骤3；若出现新的静态障碍物，则更新map,转向步骤2，进行新一轮路径规划；
进一步地，步骤2中由起点到终点的全局路径具体构建方法为：
步骤2-1.设置蚁群算法迭代次数g，蚂蚁数量n，信息素挥发系数ρ参数信息；
步骤2-2.根据矩阵map的大小，构建同等大小的信息素浓度矩阵pheromonemap，设其初始值为1，构建同等大小的临时信息素存储矩阵temppheromonemap，设其初始值为0；
步骤2-3.在起点处放置数量为n的蚂蚁,依次让序号为0到n-1的蚂蚁进行路径搜索，记录每只蚂蚁选择的路径；
步骤2-4.根据矩阵map大小，构建同等大小的禁忌表recordmap，用于记录蚂蚁已走过的位置；
步骤2-5.根据map和recordmap信息，计算出可选方向集合availabledirection；并根据状态转移概率公式从availabledirection集合中挑选出最佳方向，作为移动方向；若availabledirection集合为空，即无可走方向，则转向步骤2-3，开始下一个蚂蚁的路径规划过程；
其中，
同时为了加快算法收敛速度，采用如下状态转移方式，其中q表示1到100之间的随机数，q1是一个取值在1到100之间的常数，m表示采用轮盘赌的方式选择下一节点；
步骤2-6.若蚂蚁当前所处位置和最终位置相同，则根据记录路径，根据信息素计算公式计算信息素数值，并在临时信息素存储矩阵存储相应信息素，临时信息素存储矩阵存储值为一次迭代中全部蚂蚁在路径上留下的信息素和；否则则执行步骤2-5；
步骤2-7.此时n只蚂蚁已完成了寻路过程，根据临时信息素存储矩阵更新信息素浓度矩阵；若已达迭代次数，则执行步骤3；否则执行步骤2-3；
τij(t δt)＝(1-ρ)τij(t) δτij(t)
步骤2-8.放置一只寻路蚂蚁在起点，让其按照信息素浓度选择移动方向，记录其移动路线，此路线就是全局路径pathlist；
进一步地，步骤3智能体根据追踪策略进行路径追踪的具体设计为：
步骤3-1.若trackid等于路径上的最大序号，则任务完成；
步骤3-2.若智能体与路径点的距离小于dmin时，则trackid递增；若智能体与路径点的距离大于dmax时,则将距离智能体最近的路径点重新设置为追踪路径点；
步骤3-3.根据trackid设置智能体追踪路径点target；
进一步地，步骤4中，下一时刻智能体的运动速度的步骤具体为：
步骤4-1.随机初始化候选速度集合，设置安全因子参数；
步骤4-2.从集合中选取候选速度，以该速度去计算智能体与所有动态障碍物，静态障碍物的碰撞时间，并记录最小碰撞时间t；若智能体与所有障碍物均无碰撞，则碰撞时间t为无穷大；根据惩罚函数计算惩罚数值；
其中，μ为安全因子，vpre为理想速度，tar为追踪路径点位置，position为智能体位置，||vmax||为智能体最大速度；
步骤4-3.若遍历完速度候选集合，则选出惩罚数值最小的速度候选，作为下一时刻智能体的速度；若还未遍历完速度候选集合，则转至步骤4；
相对于现有技术，本发明的优点如下：本发明公开了一种基于蚁群算法和vo算法的路径规划设计方法，从而实现在环境中存在未知动态静态障碍物，动态障碍物情况下，安全可靠地进行实时路径规划。本发明利用模拟蚁群觅食策略，通过在地图环境中留下信息素，找出可靠路径，并通过维护全局已知地图矩阵，当在探测半径内发现新的静态障碍物时再进行新一轮路径规划，降低运算开销。同时通过结合vo避障策略，完成在路径规划的同时，对动态障碍物进行有效规避，并且通过设计路径追踪策略，优化智能体移动路线，使其移动路线更加平滑，同时解决了蚁群算法中可能存在的迂回路线问题。
附图说明
图1是本发明在未知环境下基于蚁群和vo算法的路径规划方法的流程示意图；
图2是本发明利用qt仿真模拟智能体已知环境路线规划图，且该环境中存在未知静态障碍物和动态障碍物；
图3(a)是本发明matlab构建的智能体已知环境路线规划图，图3(b)是实际存在未知障碍物环境图；
图4(a)是本发明利用qt仿真模拟的智能体二次规划路径图，图4(b)是智能体二次规划路径局部放大图；
图5是本发明利用matlab构建的智能体二次规划路径对比图；
图6(a)是本发明利用qt仿真模拟的智能体在遇到未知动态障碍物时预测会产生碰撞时的运动行为示意图，图6(b)是智能体在遇到未知动态障碍物时预测可以通过时的运动行为示意图；
具体实施方式
实施例1：下面将结合附图就本发明的发明目的、技术方案、发明优点作进一步详细说明。
目前，智能体的应用越来越广泛，对智能体路径规划的安全性和可靠性要求越来越高。在传统的经典路径规划算法中，往往需要获取环境全部信息。但在实际的运行环境中，往往会存在未知的静态障碍物和动态障碍物，这对于智能体的路径规划提出了更高的要求。因此，研究可靠安全，高效的路径规划算法就必须克服运行环境下出现未知障碍物的问题。
基于以上考虑，本发明首先利用模拟蚁群觅食策略，通过在地图环境中留下信息素，找出可靠路径，并通过维护全局已知地图矩阵，当在探测半径内发现新的静态障碍物时再进行新一轮路径规划，降低运算开销。同时通过结合vo避障策略，完成在路径规划的同时，对动态障碍物进行有效规避，并且通过设计路径追踪策略，优化智能体移动路线，使其移动路线更加平滑，同时解决了蚁群算法中可能存在的迂回路线问题。
图1表示了本发明在未知环境下基于蚁群和vo算法的路径规划方法，其方法具体如下执行：
步骤1.根据已知地图信息构建初始化矩阵map，其中，存在静态障碍物的区域值为1，其他区域值为0；
步骤2.利用蚁群算法，计算全局路径pathlist；
所述步骤2包括：
步骤2-1.设置蚁群算法迭代次数g，蚂蚁数量n，信息素挥发系数ρ参数信息；
步骤2-2.根据矩阵map的大小，构建同等大小的信息素浓度矩阵pheromonemap，设其初始值为1；构建同等大小的临时信息素存储矩阵temppheromonemap，设其初始值为0；
步骤2-3.在起点处放置数量为n的蚂蚁,依次让序号为0到n-1的蚂蚁进行路径搜索，记录每只蚂蚁选择的路径；
步骤2-4.根据矩阵map大小，构建同等大小的禁忌表recordmap，用于记录蚂蚁已走过的位置；
步骤2-5.根据map和recordmap信息，计算出可选方向集合availabledirection；并根据状态转移概率公式从availabledirection集合中挑选出最佳方向，作为移动方向；若availabledirection集合为空，即无可走方向，则转向步骤2-3，开始下一个蚂蚁的路径规划过程；
其中，
同时为了加快算法收敛速度，采用如下状态转移方式，其中q表示1到100之间的随机数，q1是一个取值在1到100之间的常数，m表示采用轮盘赌的方式选择下一节点；
步骤2-6.若蚂蚁当前所处位置和最终位置相同，则根据记录路径，根据信息素计算公式计算信息素数值，并在临时信息素存储矩阵存储相应信息素，临时信息素存储矩阵存储值为一次迭代中全部蚂蚁在路径上留下的信息素和；否则则执行步骤2-5；
步骤2-7.此时n只蚂蚁已完成了寻路过程，根据临时信息素存储矩阵更新信息素浓度矩阵；若已达迭代次数，则执行步骤3；否则执行步骤2-3；
τij(t δt)＝(1-ρ)τij(t) δτij(t)
步骤2-8.放置一只寻路蚂蚁在起点，让其按照信息素浓度选择移动方向，记录其移动路线，此路线就是全局路径pathlist；
步骤3.得到全局路径后，智能体根据追踪策略进行路径追踪；为每个路径点设置序号，通过trackid记录目前追踪的全局路径上的路径点；
所述步骤3包括：
步骤3-1.若trackid等于路径上的最大序号，则任务完成；
步骤3-2.若智能体与路径点的距离小于dmin时，则trackid递增，这样可以避免一些打结路径，同时可以使智能体的运动路线更加平滑；若智能体与路径点的距离大于dmax时，则将距离智能体最近的路径点重新设置为追踪路径点，这样可以在躲避动态障碍物偏离追踪路径点后，重新进行路径点追踪，而不需要返回原先位置；
步骤3-3.根据trackid设置智能体追踪路径点target；
步骤4.根据vo算法，找出下一时刻智能体的运动速度；
所述步骤4包括：
步骤4-1.随机初始化候选速度集合，设置安全因子参数；
步骤4-2.从集合中选取候选速度，以该速度去计算智能体与所有动态障碍物，静态障碍物的碰撞时间，并记录最小碰撞时间t，若智能体与所有障碍物均无碰撞，则碰撞时间t为无穷大；根据惩罚函数计算惩罚数值；
其中，μ为安全因子，vpre为理想速度，tar为追踪路径点位置，position为智能体位置，||vmax||为智能体最大速度；
步骤4-3.若遍历完速度候选集合，则选出惩罚数值最小的速度候选，作为下一时刻智能体的速度；若还未遍历完速度候选集合，则转至步骤4；
步骤5.根据步骤4所算出来的速度，智能体进行移动；
步骤6.若探测半径内没有出现新的静态障碍物，则转向步骤3；若出现新的静态障碍物，则更新map,转向步骤2，进行新一轮路径规划；
以下是本发明所设计的在未知环境下基于蚁群和vo算法的路径规划方法模拟仿真验证。
为了证明在未知环境下基于蚁群和vo算法的路径规划方法的可行性和有效性，本发明通过qt进行智能体路径规划仿真实验。通过设置地图环境，模拟存在未知静态障碍物和动态障碍物的情况。实验中算法的各参数信息在表1中列示，实验结果在图2～6显示。
表1算法的参数设置
由图2～6可以看出，在存在未知静态障碍物和动态障碍物的环境中，基于蚁群算法和vo算法的路径规划方法表现良好，能够快速高效的进行实时路径规划和安全可靠的规避动态和静态障碍物。
综合仿真实验，本发明所设计的基于蚁群算法和vo算法的路径规划方法能够在存在未知静态障碍物和动态障碍物的情况下快速高效的进行实时路径规划和安全可靠的规避障碍物。
本发明提供了一种基于蚁群算法和vo算法的路径规划方法，将地图栅格化后，利用模拟蚁群觅食策略，通过在地图环境中留下信息素，找出可靠路径，并通过维护全局已知地图矩阵，当在探测半径内发现新的静态障碍物时再进行新一轮路径规划，降低运算开销。同时通过结合vo避障策略，完成在路径规划的同时，对动态障碍物进行有效规避，并且通过设计路径追踪策略，优化智能体移动路线，使其移动路线更加平滑，同时解决了蚁群算法中可能存在的迂回路线问题。
需要说明的是，在附图或说明书正文中，未绘示或描述的实现方式，均为所属技术领域中普通技术人员所知的形式，并未进行详细说明。此外，上述对各元件和方法的定义并不仅限于实施例中提到的各种具体结构、形状或方式，本领域普通技术人员可对其进行简单地更改或替换。
以上仅是本发明的具体实施例，应当指出，以上实施列对本发明不构成限定，相关工作人员在不偏离本发明技术思想的范围内，所进行的多样变化和修改，均落在本发明的保护范围内。
1.一种在未知环境下基于蚁群和vo算法的路径规划设计方法，其特征在于，所述方法包括以下步骤：
步骤1.根据已知地图信息构建初始化矩阵map；其中，存在静态障碍物的区域值为1，其他区域值为0；
步骤2.利用蚁群算法，计算全局路径pathlist；
步骤3.得到全局路径后，智能体根据追踪策略进行路径追踪；为每个路径点设置序号，通过trackid记录目前追踪的全局路径上的路径点；
步骤4.根据vo算法，找出下一时刻智能体的运动速度；
步骤5.根据步骤4所算出来的速度，智能体进行移动；
步骤6.若探测半径内没有出现新的静态障碍物，则转向步骤3；若出现新的静态障碍物，则更新map,转向步骤2，进行新一轮路径规划。
2.如权利要求1所述在未知环境下基于蚁群和vo算法的路径规划设计方法，其特征在于，步骤2中由起点到终点的全局路径具体构建方法为：
步骤2-1.设置蚁群算法迭代次数g，蚂蚁数量n，信息素挥发系数ρ参数信息；
步骤2-2.根据矩阵map的大小，构建同等大小的信息素浓度矩阵pheromonemap，设其初始值为1，构建同等大小的临时信息素存储矩阵temppheromonemap，设其初始值为0；
步骤2-3.在起点处放置数量为n的蚂蚁,依次让序号为0到n-1的蚂蚁进行路径搜索，记录每只蚂蚁选择的路径；
步骤2-4.根据矩阵map大小，构建同等大小的禁忌表recordmap，用于记录蚂蚁已走过的位置；
步骤2-5.根据map和recordmap信息，计算出可选方向集合availabledirection；并根据状态转移概率公式从availabledirection集合中挑选出最佳方向，作为移动方向；若availabledirection集合为空，即无可走方向，则转向步骤2-3，开始下一个蚂蚁的路径规划过程；
其中，
同时为了加快算法收敛速度，采用如下状态转移方式，其中q表示1到100之间的随机数，q1是一个取值在1到100之间的常数，m表示采用轮盘赌的方式选择下一节点；
步骤2-6.若蚂蚁当前所处位置和最终位置相同，则根据记录路径，根据信息素计算公式计算信息素数值，并在临时信息素存储矩阵存储相应信息素，临时信息素存储矩阵存储值为一次迭代中全部蚂蚁在路径上留下的信息素和；否则则执行步骤2-5；
步骤2-7.此时n只蚂蚁已完成了寻路过程，根据临时信息素存储矩阵更新信息素浓度矩阵；若已达迭代次数，则执行步骤3；否则执行步骤2-3；
τij(t δt)＝(1-ρ)τij(t) δτij(t)
步骤2-8.放置一只寻路蚂蚁在起点，让其按照信息素浓度选择移动方向，记录其移动路线，此路线就是全局路径pathlist。
3.如权利要求1所述在未知环境下基于蚁群和vo算法的路径规划设计方法，其特征在于，步骤3智能体根据追踪策略进行路径追踪的具体设计为：
步骤3-1.若trackid等于路径上的最大序号，则任务完成；
步骤3-2.若智能体与路径点的距离小于dmin时，则trackid递增；若智能体与路径点的距离大于dmax时,则将距离智能体最近的路径点重新设置为追踪路径点；
步骤3-3.根据trackid设置智能体追踪路径点target。
4.如权利要求1所述在未知环境下基于蚁群和vo算法的路径规划设计方法，其特征在于，步骤4中，下一时刻智能体的运动速度的步骤具体为：
步骤4-1.随机初始化候选速度集合，设置安全因子参数；
步骤4-2.从集合中选取候选速度，以该速度去计算智能体与所有动态障碍物，静态障碍物的碰撞时间，并记录最小碰撞时间t；若智能体与所有障碍物均无碰撞，则碰撞时间t为无穷大；根据惩罚函数计算惩罚数值；
其中，μ为安全因子，vpre为理想速度，tar为追踪路径点位置，position为智能体位置，||vmax||为智能体最大速度；
步骤4-3.若遍历完速度候选集合，则选出惩罚数值最小的速度候选，作为下一时刻智能体的速度；若还未遍历完速度候选集合，则转至步骤4。
技术总结