[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN117109622B - 一种多障碍物下双向搜索的uuv蚁群路径规划方法 - Google Patents

一种多障碍物下双向搜索的uuv蚁群路径规划方法 Download PDF

Info

Publication number
CN117109622B
CN117109622B CN202311228563.1A CN202311228563A CN117109622B CN 117109622 B CN117109622 B CN 117109622B CN 202311228563 A CN202311228563 A CN 202311228563A CN 117109622 B CN117109622 B CN 117109622B
Authority
CN
China
Prior art keywords
pheromone
ants
entering
path
node
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN202311228563.1A
Other languages
English (en)
Other versions
CN117109622A (zh
Inventor
孙明晓
肖啸天
栾添添
张晓霜
吴宝奇
吴凯
连厚鑫
王潇
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Shenzhen Wanzhida Technology Co ltd
Original Assignee
Harbin University of Science and Technology
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Harbin University of Science and Technology filed Critical Harbin University of Science and Technology
Priority to CN202311228563.1A priority Critical patent/CN117109622B/zh
Publication of CN117109622A publication Critical patent/CN117109622A/zh
Application granted granted Critical
Publication of CN117109622B publication Critical patent/CN117109622B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • GPHYSICS
    • G01MEASURING; TESTING
    • G01CMEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/26Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
    • G01C21/34Route searching; Route guidance
    • G01C21/3446Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes

Landscapes

  • Engineering & Computer Science (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Automation & Control Theory (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

本发明旨在解决传统蚁群方法在路径规划上容易陷入局部最优路径和迭代时间过长等问题,公开了一种多障碍物下双向搜索的UUV蚁群路径规划方法,具体包括:在传统蚁群方法基础上,针对大多数障碍物形状不规则,理想为栅格状且大小一致的障碍物;当传统蚁群方法,从起始点出发向目标点寻找路径上,引入一条从目标点出发向起始点的寻优路线,在两条寻优路径的加持下加快了寻优速度;并且引入了交叉点以及交叉点之间连通关系,同时在交叉点的数量上也加以限制避免计算缓慢,最后通过交叉点以及连通关系和信息素浓度值的快速回溯,找到最优路径。本发明减少了传统蚁群方法在路径规划上迭代时间,以及减少了易陷入局部最优解的可能性。

Description

一种多障碍物下双向搜索的UUV蚁群路径规划方法
技术领域
本发明涉及无人潜器(Unmanned underwater vehicle,UUV)路径规划领域,尤其涉及一种多障碍物下双向搜索的UUV蚁群路径规划方法。
背景技术
随着技术的发展,当今社会对海洋领域的探索和开发越来越重视,UUV应用领域越来越广,不仅是运用在军事领域,在科学探索和商业领域也出现越来越多的UUV,国家对于海洋资源的开发以及海洋安全和国防投入越来越多,那么在UUV路径规划上就需要更完善的方法来帮助UUV更准确快速的到达指定目标。
常用的路径规划方法有D*算法、灰狼算法、禁忌搜索算法、A*算法、粒子群算法、RRT树状算法、蚁群方法等。蚁群方法较其他算法而言,具有简单便于理解、适应性强、鲁棒性好等方面的优势。但是蚁群方法在路径规划领域的应用有如下问题:
(1)收敛速度问题,蚁群方法需要大量的迭代,大量的计算,才能找到较优路径,因此收敛速度慢成了它的一个不可避免的缺点;
(2)局部最优解问题,由于蚁群方法是局部搜索算法,所以容易出现最终的路径未达到最小值而是次优解。
同时,相较于本发明,以下方法存在不足如下:
论文《基于Dijkstra-蚁群算法的泊车系统路径规划研究》提供的改进方法,有以下缺点:首先进行Dijkstra搜索路径,增加了搜索时间;
专利CN 116643566 A《一种基于蚁群算法的D*人工势场融合的路径规划方法》提供的改进方法,有以下缺点:多模块配合运作,花费大量成本;计算复杂,路径更新速度更慢。
本发明一种多障碍物下双向搜索的UUV蚁群路径规划方法,减小了搜索时间,并且降低了传统蚁群方法易陷入局部最优解的可能性。
发明内容
本发明为了解决上述路径规划过程中收敛速度慢、易出现局部最优解等问题,提出以下技术方案:设计了一种多障碍物下双向搜索的UUV蚁群路径规划方法,在传统蚁群方法基础上,对蚁群方法数据预处理时,在起始点和目标点都放置一批蚂蚁,进行从起始点向目标点搜索和从目标点向起始点搜索,达到快速的搜索地图,解决搜索速度慢的问题;同时,当两批蚂蚁向着各自目标点搜索路径产生相遇交叉点时,创建一个集合,记录交叉点的位置坐标和两点之间的信息素浓度大小以及交叉点之间的连通关系,通过交叉点之间信息素浓度大小的记录,然后回溯所有交叉点,通过信息素浓度值最大对应的交叉点找到最优路径,解决传统蚁群方法易陷入局部最优路径的问题。具体包括以下步骤:
步骤1:
建立UUV所处同一平面环境下的二维平面栅格地图,栅格都是1m*1m同等大小,地图大小则是X*Y,其中每个栅格都有标号XiYj,其中i,j代表标号角标,由于栅格大小都是1m*1m,m表示长度单位米,所以每个栅格的中心点坐标表示为:
步骤2:
参数进行初始化,并定义一个集合J;
步骤3:
将蚂蚁等分为两组T1和T2,分别投放至起始点A以及目标点B,其中T1组蚂蚁由A向B搜寻路径,T2组蚂蚁由B向A搜寻路径,然后进入步骤4;
步骤4:
采用轮盘赌的方式为两组蚂蚁寻找下一到达的节点,其中状态转移函数如下:
其中,是蚂蚁从节点i选择到节点j的概率;τij(t)是节点i和节点j路径上的信息素所含浓度大小;allowedk是蚂蚁选择下一节点的解空间;α是信息素重要程度因子;β是启发函数重要程度因子;ηij(t)是启发函数式,其表达式为:
ηij(t)=1/dij (3)
其中,dij是i,j之间的距离;
步骤5:
判断两组蚂蚁是否相遇,如果相遇则将其交叉点存放在集合J,并且将交叉点之间的连通关系以及信息素浓度值也存放在集合J,然后进入步骤6;否则回到步骤4;
步骤6:
判断蚂蚁是否完成路径,如果完成路径则进入步骤7;否则回到步骤4;
步骤7:
判断交叉点数量是否达到饱和,如果交叉点已经达到饱和,进入步骤11;否则进入步骤8;
步骤8:
判断蚂蚁是否达到最大数量,是则进入步骤9;否则回到步骤3;
步骤9:
进行信息素的更新,更新信息素采用公式如下:
τij(t+1)=(1-ρ)*τij(t)+ Δτij (5)
其中,τij(t)是节点i和节点j路径上的信息素所含浓度大小;表示第k只蚂蚁在i,j之间释放的信息素浓度;Δτij表示蚂蚁在i,j之间信息素浓度之和;ρ表示信息素挥发系数,取值一般为0到1之间;N表示蚂蚁最大数量,然后进入步骤10;
步骤10:
判断是否达到最大迭代次数,是则进入步骤11;否则回到步骤3;
步骤11:
定义并初始化集合S,进入步骤12;
步骤12:
将与起始点A之间信息素浓度最大的交叉点放入S,并且将其交叉点从J中删除,进入步骤13;
步骤13:
比较S中交叉点与J中交叉点直接相连的信息素浓度大小,进入步骤14;
步骤14:
判断是否删除J中信息素浓度明显低的交叉点,删除后则进入步骤15;否则进入步骤12;
步骤15:
判断是否遍历完J中所有交叉点,是则进入步骤16;否则回到步骤12;
步骤16:
回溯S中存在的交叉点坐标,计算理论最短路径,然后输出最短路径,结束。本发明具有如下有益效果:
1.本发明所述方法在传统蚁群方法从起始点向目标点进行搜索路径基础上,引入一条从目标点向起始点进行搜索路径,加快了寻优速度,并且降低了单向搜索易陷入局部最优的可能性;
2.本发明所述方法在利用传统蚁群方法信息素浓度的基础上,引入交叉点和连通关系,通过交叉点之间的联系,进行路径搜索,减少了易出现局部最优路径的概率;
3.本发明所述方法引入交叉点之间的连通关系以及记录其之间的信息素浓度值,并通过交叉点之间连通关系的信息素浓度大小迭代寻找最优路径,提升了路径搜索的效率,从而缩短了搜索时间。
附图说明
图1为一种多障碍物下双向搜索的UUV蚁群路径规划方法流程图;
图2为栅格编号示意图;
图3为两组蚂蚁寻找各自的目标点路径图;
图4为两组蚂蚁相遇后显示交叉点图;
图5为两组蚂蚁多次寻找目标点产生交叉点及其连通关系图;
图6为最终形成的路径图;
图7为收敛曲线变化图。
具体实施方式
图1为本发明一种多障碍物下双向搜索的UUV蚁群路径规划方法流程图,包括以下步骤:
步骤1:
建立UUV所处同一平面环境下的二维平面栅格地图,将障碍物理想化成为栅格地图中的黑色栅格,其中未满一格的障碍物膨胀为一格,超出一格部分的障碍物用多个栅格组成,白色栅格代表可通行区域,黑色栅格代表障碍物,UUV无法通行,并且栅格都是1m*1m同等大小(m表示长度单位米),地图大小则是X*Y,其中每个栅格都有标号XiYj,其中i,j代表标号角标,如图2栅格a的表示方法为X1Y1,由于栅格大小都是1m*1m,所以每个栅格的中心点坐标表示为:
步骤2:
参数进行初始化,蚁群数量N=100,信息素重要程度因子α=1,启发函数重要程度因子β=7,信息素挥发因子p=0.3,信息素释放总量d=0,最大迭代次数Nmax=80,并定义一个集合J用来存放两组蚂蚁的相遇点也称为交叉点及其信息素相关信息;
步骤3:
将蚂蚁等分为两组T1和T2,分别投放至起始点A以及目标点B,其中T1组蚂蚁由A向B搜寻路径,T2组蚂蚁由B向A搜寻路径。并且初始化禁忌表,将起始点A以及目标点B放入禁忌表中,然后进入步骤4;
步骤4:
通过当前信息素浓度大小,以及禁忌表中存在的节点,采用轮盘赌的方式为两组蚂蚁寻找下一到达的节点,其中状态转移函数如下:
其中,是蚂蚁从节点i选择到节点j的概率;τij(t)是节点i和节点j路径上的信息素所含浓度大小;allowedk是蚂蚁选择下一节点的解空间;α是信息素重要程度因子,是蚂蚁在选择下一节点时对信息素浓度的重视程度,α的值越大,蚂蚁会选择信息素浓度越大的路径进行下一节点的选择;β是启发函数重要程度因子,是蚂蚁在选择下一节点时对启发函数信息素的重视程度,β越大,蚂蚁更加倾向于选择启发函数信息素值较大的位置进行移动,ηij(t)是启发函数式,其表达式为:
ηij(t)=1/dij (3)
其中,dij是i,j之间的距离;
步骤5:
通过判断禁忌表中存放的点坐标值,来判断两组蚂蚁是否相遇,如果相遇则将其交叉点存放在集合J,并且将交叉点之间的连通关系以及信息素浓度值也存放在集合J,然后进入步骤6;否则回到步骤4;
步骤6:
判断蚂蚁是否完成路径,如果完成路径则进入步骤7;否则回到步骤4;
步骤7:
通过比较这回合交叉点数量与上回合交叉点数量大小来判断交叉点数量是否达到饱和,如果数量大小不发生变化,则说明交叉点已经达到饱和,进入步骤11;否则进入步骤8;
步骤8:
判断蚂蚁是否达到最大数量,是则进入步骤9;否则回到步骤3;
步骤9:
由于此时蚂蚁数量已经达到最大数量,此时进行信息素的更新,其中更新信息素采用全局信息素更新,公式如下:
τij(t+1)=(1-ρ)*τij(t)+Δτij (5)
其中,τij(t)是节点i和节点j路径上的信息素所含浓度大小;表示第k只蚂蚁在i,j之间释放的信息素浓度;Δτij表示蚂蚁在i,j之间信息素浓度之和;ρ表示信息素挥发系数,取值一般为0到1之间;N表示蚂蚁最大数量,然后进入步骤10;
步骤10:
判断是否达到最大迭代次数,是则进入步骤11;否则回到步骤3;
步骤11:
定义并初始化集合S,进入步骤12;
步骤12:
将与起始点A之间信息素浓度最大的交叉点放入S,并且将其交叉点从J中删除,进入步骤13;
步骤13:
比较S中交叉点与J中交叉点直接相连的信息素浓度大小,进入步骤14;
步骤14:
通过步骤13的比较,可以清楚得到交叉点之间信息素浓度大小关系,判断是否删除J中信息素浓度明显低的交叉点,删除后则进入步骤15;否则进入步骤12;
步骤15:
判断是否遍历完J中所有交叉点,是则进入步骤16;否则回到步骤12;
步骤16:
回溯S中存在的交叉点坐标,计算理论最短路径,然后输出最短路径,结束。通过Matlab软件对本发明方法进行仿真,图3、图4、图5分别为UUV在多障碍物下进行搜索路径的仿真图,坐标轴单位为m。图3为两组蚂蚁寻找各自的目标点路径图,图中可以看出,蚂蚁从起始点A向目标点B进行寻优过程,以及从目标点B向起始点A进行寻优的过程。图4为两组蚂蚁相遇后显示交叉点图,图中可以看出,蚂蚁在编号为X11Y10和编号为X15Y12的栅格产生交叉点,此时将记录在集合J中。图5为两组蚂蚁三次寻找目标点产生交叉点及其连通关系图,图中可以看出,蚂蚁在三次迭代后产生了21处交叉点以及交叉点之间存在连通关系。图6、图7分别为UUV在多障碍物下进行搜索路径的最终结果图和收敛曲线图,图中可以看出,迭代次数在30次之前,路径长度浮动较大;迭代次数在30次后,路径长度逐步稳定;在迭代到35次时,达到最小路径,体现了寻优速度快,此时最小路径长度为30.2m达到稳定。

Claims (1)

1.一种多障碍物下双向搜索的UUV蚁群路径规划方法,其特征在于,包括以下步骤:
步骤1:
建立UUV所处同一平面环境下的二维平面栅格地图,栅格都是1m*1m同等大小,m表示长度单位米,地图大小则是X*Y,其中每个栅格都有标号XiYj,其中i,j代表标号角标,由于栅格大小都是1m*1m,所以每个栅格的中心点坐标表示为:
步骤2:
参数进行初始化,并定义一个集合J;
步骤3:
将蚂蚁等分为两组T1和T2,分别投放至起始点A以及目标点B,其中T1组蚂蚁由A向B搜寻路径,T2组蚂蚁由B向A搜寻路径,然后进入步骤4;
步骤4:
采用轮盘赌的方式为两组蚂蚁寻找下一到达的节点,其中状态转移函数如下:
其中,是蚂蚁从节点i选择到节点j的概率;τij(t)是节点i和节点j路径上的信息素所含浓度大小;allowedk是蚂蚁选择下一节点的解空间;α是信息素重要程度因子;β是启发函数重要程度因子;ηij(t)是启发函数式,其表达式为:
ηij(t)=1/dij (3)
其中,dij是i,j之间的距离;
步骤5:
判断两组蚂蚁是否相遇,如果相遇则将其交叉点存放在集合J,并且将交叉点之间的连通关系以及信息素浓度值也存放在集合J,然后进入步骤6;否则回到步骤4;
步骤6:
判断蚂蚁是否完成路径,如果完成路径则进入步骤7;否则回到步骤4;
步骤7:
判断交叉点数量是否达到饱和,如果交叉点已经达到饱和,进入步骤11;否则进入步骤8;
步骤8:
判断蚂蚁是否达到最大数量,是则进入步骤9;否则回到步骤3;
步骤9:
进行信息素的更新,更新信息素采用公式如下:
τij(t+1)=(1-ρ)*τij(t)+Δτij (5)
其中,τij(t)是节点i和节点j路径上的信息素所含浓度大小;表示第k只蚂蚁在i,j之间释放的信息素浓度;Δτij表示蚂蚁在i,j之间信息素浓度之和;ρ表示信息素挥发系数,取值一般为0到1之间;N表示蚂蚁最大数量,然后进入步骤10;
步骤10:
判断是否达到最大迭代次数,是则进入步骤11;否则回到步骤3;
步骤11:
定义并初始化集合S,进入步骤12;
步骤12:
将与起始点A之间信息素浓度最大的交叉点放入S,并且将其交叉点从J中删除,进入步骤13;
步骤13:
比较S中交叉点与J中交叉点直接相连的信息素浓度大小,进入步骤14;
步骤14:
判断是否删除J中信息素浓度明显低的交叉点,删除后则进入步骤15;否则进入步骤12;
步骤15:
判断是否遍历完J中所有交叉点,是则进入步骤16;否则回到步骤12;
步骤16:
回溯S中存在的交叉点坐标,计算理论最短路径,然后输出最短路径,结束。
CN202311228563.1A 2023-09-21 2023-09-21 一种多障碍物下双向搜索的uuv蚁群路径规划方法 Active CN117109622B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202311228563.1A CN117109622B (zh) 2023-09-21 2023-09-21 一种多障碍物下双向搜索的uuv蚁群路径规划方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202311228563.1A CN117109622B (zh) 2023-09-21 2023-09-21 一种多障碍物下双向搜索的uuv蚁群路径规划方法

Publications (2)

Publication Number Publication Date
CN117109622A CN117109622A (zh) 2023-11-24
CN117109622B true CN117109622B (zh) 2024-03-26

Family

ID=88796509

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202311228563.1A Active CN117109622B (zh) 2023-09-21 2023-09-21 一种多障碍物下双向搜索的uuv蚁群路径规划方法

Country Status (1)

Country Link
CN (1) CN117109622B (zh)

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN106225788A (zh) * 2016-08-16 2016-12-14 上海理工大学 基于路径拓展蚁群算法的机器人路径规划方法
WO2021189720A1 (zh) * 2020-03-23 2021-09-30 南京理工大学 基于改进蚁群算法的泊车agv路径规划方法
CN114567914A (zh) * 2022-02-24 2022-05-31 广州杰赛科技股份有限公司 无线传感网络的信息传输路径规划方法及装置
CN115423324A (zh) * 2022-09-05 2022-12-02 哈尔滨工程大学 一种基于改进蚁群优化的uuv集群任务规划方法
CN116739196A (zh) * 2023-05-24 2023-09-12 西安建筑科技大学 一种基于改进蚁群算法的塔机路径规划方法

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN106225788A (zh) * 2016-08-16 2016-12-14 上海理工大学 基于路径拓展蚁群算法的机器人路径规划方法
WO2021189720A1 (zh) * 2020-03-23 2021-09-30 南京理工大学 基于改进蚁群算法的泊车agv路径规划方法
CN114567914A (zh) * 2022-02-24 2022-05-31 广州杰赛科技股份有限公司 无线传感网络的信息传输路径规划方法及装置
CN115423324A (zh) * 2022-09-05 2022-12-02 哈尔滨工程大学 一种基于改进蚁群优化的uuv集群任务规划方法
CN116739196A (zh) * 2023-05-24 2023-09-12 西安建筑科技大学 一种基于改进蚁群算法的塔机路径规划方法

Also Published As

Publication number Publication date
CN117109622A (zh) 2023-11-24

Similar Documents

Publication Publication Date Title
CN112650237B (zh) 基于聚类处理和人工势场的船舶路径规划方法和装置
CN110244733B (zh) 一种基于改进蚁群算法的移动机器人路径规划方法
CN111024092B (zh) 一种多约束条件下智能飞行器航迹快速规划方法
CN107622327B (zh) 基于文化蚁群搜索机制的多无人机航迹规划方法
CN111310999B (zh) 一种基于改进蚁群算法的仓库移动机器人路径规划方法
CN114964261B (zh) 基于改进蚁群算法的移动机器人路径规划方法
CN109357678B (zh) 一种基于异质化鸽群优化算法的多无人机路径规划方法
CN111176286B (zh) 一种基于改进D*lite算法的移动机器人路径规划方法及系统
CN104462190A (zh) 一种基于海量空间轨迹挖掘的在线的位置预测方法
CN107229287A (zh) 一种基于遗传蚂蚁算法的无人机全局路径规划方法
CN110345960B (zh) 一种规避交通障碍的路线规划智能优化方法
CN110196602A (zh) 目标导向集中优化的快速水下机器人三维路径规划方法
CN113985888A (zh) 一种基于改进蚁群算法的叉车路径规划方法及系统
CN112666957A (zh) 一种基于改进蚁群算法的水下机器人路径规划方法
CN114167865A (zh) 一种基于对抗生成网络与蚁群算法的机器人路径规划方法
CN108388250A (zh) 一种基于自适应布谷鸟搜索算法的水面无人艇路径规划方法
CN114489052B (zh) 一种改进rrt算法重连策略的路径规划方法
CN114509085B (zh) 一种结合栅格和拓扑地图的快速路径搜索方法
Geng et al. A kind of route planning method for UAV based on improved PSO algorithm
CN116909318B (zh) 一种基于高精度三维点云的无人机自主巡检航线规划系统
CN117516575B (zh) 一种基于基可达图的多智能体最优任务分配与规划方法、装置及系统
CN113778090A (zh) 基于蚁群优化和prm算法的移动机器人路径规划方法
CN113341998A (zh) 一种改进蚁群算法的三维水下欠驱动auv路径规划方法
CN112330068A (zh) 一种基于蚁群算法与地理信息系统的变电站输电线路规划方法
CN117109622B (zh) 一种多障碍物下双向搜索的uuv蚁群路径规划方法

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant
TR01 Transfer of patent right
TR01 Transfer of patent right

Effective date of registration: 20240929

Address after: 518000 1002, Building A, Zhiyun Industrial Park, No. 13, Huaxing Road, Henglang Community, Longhua District, Shenzhen, Guangdong Province

Patentee after: Shenzhen Wanzhida Technology Co.,Ltd.

Country or region after: China

Address before: 150080 No. 52, Xuefu Road, Nangang District, Heilongjiang, Harbin

Patentee before: HARBIN University OF SCIENCE AND TECHNOLOGY

Country or region before: China