(转载)基于蚁群算法的三维路径规划(matlab实现)

news/2024/4/15 8:35:19

1 理论基础

1.1 三维路径规划问题概述

        三维路径规划指在已知三维地图中,规划出一条从出发点到目标点满足某项指标最优,并且避开了所有三维障碍物的三维最优路径。现有的路径规划算法中,大部分算法是在二维规划平面或准二维规划平面中进行路径规划。一般的三维路径规划算法具有计算过程复杂、信息存储量大、难以直接进行全局规划等问题。已有的三维路径规划算法主要包括A*算法、遗传算法、粒子群算法等,但是A*算法的计算量会随着维数的增加而急剧增加,遗传算法和粒子群算法只是准三维规划算法。
        蚁群算法具有分布计算、群体智能等优势,在路径规划上具有很大潜力,在成功用于二维路径规划的同时也可用于三维路径规划,本章采用蚁群算法进行水下机器人三维路径规划。

1.2 三维空间抽象建模

        三维路径规划算法首先需要从三维地图中抽象出三维空间模型,模型抽象方法如下:首先把三维地图左下角的顶点作为三维空间的坐标原点A,在点A中建立三维坐标系,其中,x轴为沿经度增加的方向,y轴为沿纬度增加的方向,z轴为垂直于海平面方向。在该坐标系中以点A为顶点,沿x轴方向取三维地图的最大长度AB,沿y轴方向取三维地图的最大长度AA',沿z轴方向取三维地图的最大长度AB,这样就构造了包含三维地图的立方体区域ABCD-A'B'C'D',该区域即为三维路径的规划空间。三维路径规划空间如图1所示。三维路径空间建立起来之后,采用等分空间的方法从三维空间中抽取出三维路径规划所需的网格点。首先沿边AB把规划空间ABCD-A'B'C'D'进行等分,得到n+1个平面Ⅱi(i=1,2,…,n),然后对这n+1个平面沿边AD进行m等分,沿边AA'进行l等分,并且求解出里面的交点。平面划分如图2所示。
        通过以上步骤,整个规划空间ABCD-A'B'’C'D'就离散化为一个三维点集合,集合中的任意一点对应着两个坐标,即序号坐标a1(i,j,k)(i=0,1,2,…,n,j=0,1,2,…,m,k=0,1,2, …,l)和位置坐标a2 (xi ,yi, zi), 其中,i,j,k分别为当前点a沿边AA,边AD,边AA'的划分序号。蚁群算法即在这些三维路径点上进行规划,最终得到连接出发点和目标点满足某项指标最优的三维路径。

2案例背景

2.1问题描述

        采用蚁群算法在跨度为21 km×21 km的一片海域中搜索从起点到终点,并且避开所有障碍物的路径,为了方便问题的求解,取该区域内最深点的高度为0,其他点高度根据和最深点高度差依次取得。路径规划起点坐标为(1,10,800),终点坐标为(21,4,1 000),规划环境和起点、终点如图3所示。整个搜索空间为21 km×21 km的海域,其中,起点坐标为(1,10,800),终点坐标为(21,4,1 000)。
        基于蚁群算法的三维路径搜索算法的算法流程如图4所示。

        其中,三维环境建模模块根据1.2节抽取出三维环境数学模型;搜索节点模块根据启发函数搜索下个节点;信息素更新模块更新环境中节点的信息素值。

2.3 信息素更新

        蚁群算法使用信息素吸引蚂蚁搜索,信息素位置设定及更新方法对于蚁群算法的成功搜索具有非常重要的意义。在1.2节中已经把整个搜索空间离散为一系列的三维离散点,这些离散点为蚁群算法需要搜索的节点。因此,把信息素存储在模型的离散点中,每个离散点都有一个信息素的值,该点信息素的大小代表对蚂蚁的吸引程度,各点信息素在每只蚂蚁经过后进行更新。信息素的更新包括局部更新和全局更新两部分,局部更新是指当蚂蚁经过该点时,该点的信息素就减少,局部更新的目的是增加蚂蚁搜索未经过点的概率,达到全局搜索的目的。局部信息素更新随着蚂蚁的搜索进行,信息素更新公式为

2.4可视搜索空间

        取α轴方向作为三维路径规划的主方向,水下机器人沿工轴方向前进,为了降低规划复杂程度,将水下机器人的运动简化为前向运动、横向运动和纵向运动三种运动方式。在前向运动一定单位长度距离Lx,max情况下,设定机器人最大横向移动允许距离为Ly,max,最大纵向移动距离为Lz,max。这样,当蚂蚁沿着α轴方向前进时,当位于点H(i,j,k)时,对下一个点的搜索就存在一个可视区域,可视区域如图5所示。


        这样,当蚂蚁由当前点向下一个点移动时,可搜索的区域限制在蚂蚁搜索可视区域之内,简化了搜索空间,提高了蚁群算法的搜索效率。

2.5 蚁群搜索策略

        蚂蚁从当前点移动到下一个点时,根据启发函数来计算可视区域内各点的选择概率,启发函数为

3 MATLAB程序

        根据蚁群算法原理,在MATLAB中编程实现基于蚁群算法的三维路径规划算法。

3.1 启发值计算函数

        该函数主要用于计算可视区域内各点的启发值。
function qfz=CacuQfz(Nexty,Nexth,Nowy,Nowh,endy,endh,abscissa,HeightData)
%% 该函数用于计算各点的启发值
%Nexty Nexth    input    下个点坐标
%Nowy Nowh      input    当前点坐标
%endy endh      input    终点坐标
%abscissa       input    横坐标
%HeightData     input    地图高度
%qfz            output   启发值%% 判断下个点是否可达
if HeightData(Nexty,abscissa)<Nexth*200S=1;
elseS=0;
end%% 计算启发值
%D距离
D=50/(sqrt(1+(Nowh*0.2-Nexth*0.2)^2+(Nexty-Nowy)^2)+sqrt((21-abscissa)^2 ...+(endh*0.2-Nexth*0.2)^2+(endy-Nowy)^2));
%计算高度
M=30/abs(Nexth+1);
%计算启发值
qfz=S*M*D;

3.2适应度计算函数

        适应度计算函数主要用于计算每条路径的适应度值。
function fitness=CacuFit(path)
%% 该函数用于计算个体适应度值
%path       input     路径
%fitness    input     路径[n,m]=size(path);
for i=1:nfitness(i)=0;for j=2:m/2%适应度值为长度加高度fitness(i)=fitness(i)+sqrt(1+(path(i,j*2-1)-path(i,(j-1)*2-1))^2 ...+(path(i,j*2)-path(i,(j-1)*2))^2)+abs(path(i,j*2));end
end

3.3 路径搜索

        路径搜索函数采用蚁群算法根据信息素和启发值搜索从出发点到终点的三维路径。

function [path,pheromone]=searchpath(PopNumber,LevelGrid,PortGrid,pheromone,HeightData,starty,starth,endy,endh)
%% 该函数用于蚂蚁蚁群算法的路径规划
%LevelGrid     input    横向划分格数
%PortGrid      input    纵向划分个数
%pheromone     input    信息素
%HeightData    input    地图高度
%starty starth input    开始点
%path          output   规划路径
%pheromone     output   信息素%% 搜索参数
ycMax=2;   %蚂蚁横向最大变动
hcMax=2;   %蚂蚁纵向最大变动
decr=0.9;  %信息素衰减概率%% 循环搜索路径
for ii=1:PopNumberpath(ii,1:2)=[starty,starth];  %记录路径NowPoint=[starty,starth];      %当前坐标点%% 计算点适应度值for abscissa=2:PortGrid-1%计算所有数据点对应的适应度值kk=1;for i=-ycMax:ycMaxfor j=-hcMax:hcMaxNextPoint(kk,:)=[NowPoint(1)+i,NowPoint(2)+j];if (NextPoint(kk,1)<20)&&(NextPoint(kk,1)>0)&&(NextPoint(kk,2)<20)&&(NextPoint(kk,2)>0)qfz(kk)=CacuQfz(NextPoint(kk,1),NextPoint(kk,2),NowPoint(1),NowPoint(2),endy,endh,abscissa,HeightData);qz(kk)=qfz(kk)*pheromone(abscissa,NextPoint(kk,1),NextPoint(kk,2));kk=kk+1;elseqz(kk)=0;kk=kk+1;endendend%选择下个点sumq=qz./sum(qz);pick=rand;while pick==0pick=rand;endfor i=1:25pick=pick-sumq(i);if pick<=0index=i;break;endendoldpoint=NextPoint(index,:);%更新信息素pheromone(abscissa+1,oldpoint(1),oldpoint(2))=0.5*pheromone(abscissa+1,oldpoint(1),oldpoint(2));%路径保存path(ii,abscissa*2-1:abscissa*2)=[oldpoint(1),oldpoint(2)];    NowPoint=oldpoint;endpath(ii,41:42)=[endy,endh];
end

3.4 主函数

        主函数主要用于蚁群算法的全局寻优,通过迭代寻找全局最优解,主要程序如下:
%% 该函数用于演示基于蚁群算法的三维路径规划算法%% 清空环境
clc
clear%% 数据初始化%下载数据
load  HeightData HeightData%网格划分
LevelGrid=10;
PortGrid=21;%起点终点网格点 
starty=10;starth=4;
endy=8;endh=5;
m=1;
%算法参数
PopNumber=10;         %种群个数
BestFitness=[];    %最佳个体%初始信息素
pheromone=ones(21,21,21);%% 初始搜索路径
[path,pheromone]=searchpath(PopNumber,LevelGrid,PortGrid,pheromone, ...HeightData,starty,starth,endy,endh); 
fitness=CacuFit(path);                          %适应度计算
[bestfitness,bestindex]=min(fitness);           %最佳适应度
bestpath=path(bestindex,:);                     %最佳路径
BestFitness=[BestFitness;bestfitness];          %适应度值记录%% 信息素更新
rou=0.2;
cfit=100/bestfitness;
for i=2:PortGrid-1pheromone(i,bestpath(i*2-1),bestpath(i*2))= ...(1-rou)*pheromone(i,bestpath(i*2-1),bestpath(i*2))+rou*cfit;
end%% 循环寻找最优路径
for kk=1:100%% 路径搜索[path,pheromone]=searchpath(PopNumber,LevelGrid,PortGrid,...pheromone,HeightData,starty,starth,endy,endh); %% 适应度值计算更新fitness=CacuFit(path);                               [newbestfitness,newbestindex]=min(fitness);     if newbestfitness<bestfitnessbestfitness=newbestfitness;bestpath=path(newbestindex,:);end BestFitness=[BestFitness;bestfitness];%% 更新信息素cfit=100/bestfitness;for i=2:PortGrid-1pheromone(i,bestpath(i*2-1),bestpath(i*2))=(1-rou)* ...pheromone(i,bestpath(i*2-1),bestpath(i*2))+rou*cfit;endend%% 最佳路径
for i=1:21a(i,1)=bestpath(i*2-1);a(i,2)=bestpath(i*2);
end
figure(1)
x=1:21;
y=1:21;
[x1,y1]=meshgrid(x,y);
mesh(x1,y1,HeightData)
axis([1,21,1,21,0,2000])
hold on
k=1:21;
plot3(k(1)',a(1,1)',a(1,2)'*200,'--o','LineWidth',2,...'MarkerEdgeColor','k',...'MarkerFaceColor','g',...'MarkerSize',10)
plot3(k(21)',a(21,1)',a(21,2)'*200,'--o','LineWidth',2,...'MarkerEdgeColor','k',...'MarkerFaceColor','g',...'MarkerSize',10)text(k(1)',a(1,1)',a(1,2)'*200,'S');
text(k(21)',a(21,1)',a(21,2)'*200,'T');
xlabel('km','fontsize',12);
ylabel('km','fontsize',12);
zlabel('m','fontsize',12);
title('三维路径规划空间','fontsize',12)
set(gcf, 'Renderer', 'ZBuffer')
hold on
plot3(k',a(:,1)',a(:,2)'*200,'--o')%% 适应度变化
figure(2)
plot(BestFitness)
title('最佳个体适应度变化趋势')
xlabel('迭代次数')
ylabel('适应度值')

3.5 仿真结果

        采用蚁群算法进行三维路径规划,规划空间范围为20km×20 km的海域,根据1.2节的内容把规划空间抽象为21km×21km×21km的规划空间,其中,x轴,y轴方向每个节点的间距为1km,z轴方向每个节点间距为200m。路径起点在规划空间的序号为[1 10 4], 终点在规划空间的序号为[21 4 5]。算法的基本设置为种群规模为20,算法迭代为400次,路径规划结果和最优个体适应度变化如图6和图7所示。

4 总结

        以蚁群算法为代表的群智能已成为当今分布式人工智能研究的一个热点,许多源于蜂群和蚁群模型设计的算法已越来越多地被应用于企业的运转模式的研究。美国五角大楼正在资助关于群智能系统的研究工作——群体战略(swarm strategy),它的一个实战用途是通过运用成群的空中无人驾驶飞行器和地面车辆来转移敌人的注意力,让自己的军队在敌人后方不被察觉地安全活动。英国电信公司和美国世界通信公司以电子蚂蚁为基础,对新的电信网络管理方法进行了试验。群智能还被应用于工厂生产计划的制订和运输部门的后勤管理。美国太平洋西南航空公司采用了一种直接源于蚂蚁行为研究成果的运输管理软件,结果每年至少节约1000万美元的费用开支。英国联合利华公司率先利用群智能技术改善其一家牙膏厂的运转情况。美国通用汽车公司、法国液气公司、荷兰公路交通部和美国一些移民事务机构也都采用这种技术来改善其运转。

5.完整代码

基于蚁群算法的三维路径规划(matlab实现)


http://www.ppmy.cn/news/327159.html

相关文章

华为手机怎么使用读卡器_华为G7手机OTG功能详细使用教程

您可能感兴趣的话题&#xff1a; 华为G7 核心提示&#xff1a;简而言之就是让你的华为G7连续USB设备如U盘、键盘等USB设备&#xff0c;连续上这些功能即可实现数据交换及功能的应用。下面小编整理了华为G7 OTG功能详解希望对大家有所帮助。 华为G7手机OTG功能详细使用教程 华为…

华为 android 5.0系统下载地址,华为Mate8 EMUI5.0系统专用官方原版recovery下载和刷入...

下面整理的是有关华为Mate8手机的EMUI5.0系统Android7.0专用的官方原版的recovery&#xff0c;有的机友不知道什么时候才用官方的recovery&#xff0c;当大家的手机在进行官方的系统升级的时候&#xff0c;手机里面必须是官方原版的recovery才行的&#xff0c;如果你之前刷了第…

华为p6电信版 android 4.5,华为p6电信版驱动

这是华为p6电信版驱动下载&#xff0c;如果手机想要通过电脑ROOT、刷Recovery、刷机&#xff0c;必须先安装USB驱动。此为华为P6的USB驱动&#xff0c;不过推测P7也可以使用&#xff0c;推荐需要的用户下载。 软件说明 这一种方法是直接下载一个驱动程序安装在电脑上&#xff0…

算法刷题-链表-链表相交

链表相交 面试题 02.07. 链表相交思路其他语言版本JavaPythonGojavaScript 面试题 02.07. 链表相交 同&#xff1a;160.链表相交 力扣题目链接 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点&#xff0…

最新版CleanMyMac X4.13.4中文版Mac清理软件

cleanmymac是一款强大的Mac系统垃圾清理工具,可以清除Mac系统多余的语言包,系统缓存,应用程序!可智能清理mac磁盘垃圾和多余语言安装包&#xff0c;快速释放电脑内存&#xff0c;轻松管理和升级Mac上的应用。同时CleanMyMac X可以强力卸载恶意软件&#xff0c;修复系统漏洞&…

基于Java+SpringBoot的鞋类商品购物商城系统设计与实现

博主介绍&#xff1a;✌擅长Java、微信小程序、Python、Android等&#xff0c;专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&#x1f3fb; 不然下次找不到哟 Java项目精品实战案…

融合黄金正弦和随机游走的哈里斯鹰优化算法(GSHHO)-附代码

融合黄金正弦和随机游走的哈里斯鹰优化算法(GSHHO) 文章目录 融合黄金正弦和随机游走的哈里斯鹰优化算法(GSHHO)1.哈里斯鹰优化算法2.改进哈里斯鹰优化算法2.1 黄金正弦算法2.2 非线性能量指数递减策略2.3 高斯随机游走策略 3.实验结果4.参考文献5.Matlab代码6.python代码 摘要…

【Socket】express里使用Socket.io | socket广播

Socket简介 后端、前端实时推送、发送消息 用作场景&#xff1a; 用户A给用户B点赞、评论时 &#xff0c;用户B收到用户A的点赞、评论通知用户在线、离线状态聊天、群聊相关等… socket官方 - https://socket.io/zh-CNnpm - https://www.npmjs.com/package/socket.io socket.…

AndroidT(13) init 进程 -- first stage init 的初始化 (二)

1.概览 第一阶段的 init 工作主要用于读取系统启动阶段需要的配置信息(例如 linux的bootconfig&#xff0c;cmdline等配置信息&#xff09;、挂载文件系统、安装 kernel 中的模块驱动&#xff0c;最后就是启动第二阶段的 init 来进行 Android 系统相关的组件。第一阶段的 init …

安装算量按桥架布线_算量软件按桥架布线操作方法

按桥架布线的操作方式主要是在布置电线或电缆的时候&#xff0c;只需要指定进入桥架的起点和出桥架的终点后桥架部分的电线电缆自动完成布置&#xff0c;且桥架内部分软件不计算配管&#xff0c;即达到了快速计算工程量的目的&#xff0c;同时也保证了工程量计算准确。当计算配…

安装路平石在基层工序的一些需要强调的部分

先将公路在建设中的细节和需要注意的部分提炼出&#xff0c;进而根据相应的对策来进行工作就会顺利很多&#xff0c;安装的位置需要准确、牢固以及稳定&#xff0c;各方向的尺寸也要符合要求&#xff0c;以便于实现工程建设的目标。 基层的建设工作一般是没有大难度&#xff0c…

JGJ202-2010 建筑施工工具式脚手架安全技术规范 免费下载

【资源介绍】 资源名称&#xff1a;JGJ202-2010 建筑施工工具式脚手架安全技术规范 资源分类&#xff1a; 建筑工程标准规范 其他简介&#xff1a;JGJ202-2010 建筑施工工具式脚手架安全技术规范 【资源下载】 链接&#xff1a;https://pan.baidu.com/s/12PIhCXxFRAy43_fH…

集装箱码头作业流程

1 相关术语&#xff1a; 集装箱堆场&#xff1a;container yard&#xff0c;CY 堆场&#xff1a;yard&#xff0c;图一堆场用的stack 岸桥&#xff1a;quay crane&#xff0c;QC 场桥堆垛起重机&#xff1a;straddle carriers&#xff0c;SC 轨道式自动堆垛起重机&#xf…

安装脚手架详细步骤

首先下载node 具体步骤 1、基于node环境 查看node版本: node -V查看npm版本: npm -V![在这里插入图片描述](https://img-blog.csdnimg.cn/c4447d9c3ffd4f0f9928c241621be79f.png#pic_center)2、全局下 安装vue-cli脚手架 npm i -g vue/clinpm uninstall -g vue/cli3、创建脚…

砼匠无人值守称重系统说明

砼匠无人值守称重系统说明 1.送货车辆进出务必过称&#xff0c;不允许不过称进去。 2.当称上有车辆在操作时&#xff0c;请将车辆与道闸杆保持至少5米的距离。 打开百度APP看高清图片 3.称重时&#xff0c;请看LED屏提示及语音提示进行操作。 4.如遇到车牌没有识别的情况&…

怎么卸载脚手架_脚手架施工方案钢丝绳卸载

《脚手架施工方案钢丝绳卸载》由会员分享&#xff0c;可在线阅读&#xff0c;更多相关《脚手架施工方案钢丝绳卸载(5页珍藏版)》请在人人文库网上搜索。 1、脚手架施工方案钢丝绳卸载12020 年 4 月 19 日文档仅供参考&#xff0c;不当之处&#xff0c;请联系改正。外脚手架 卸 …

包工头一般怎样接工程?如何找工程包工平台?

什么叫包工头&#xff1f; “包工头”&#xff0c;顾名思义&#xff0c;把工作包揽过来&#xff0c;招人作业&#xff0c;他自己当头&#xff0c;是特殊历史条件下的特殊“产物”。当城市发展需要大量外来务工人员&#xff0c;而农村剩余劳动力迫切需要进城找工作之时&#xf…

电缆桥架安装要求及规范指导

电缆桥架安装要求及规范指导 1、电缆桥架作为布线工程的一个配套项目,目前尚无专门的规范指导,个生产厂家的规格程式缺乏通用性,因此,设计选型过程应根据弱电各个系统缆显得类型、数量,合理选定适用的桥架。 (1)确定方向&#xff1a; 根据建筑平面布置图,结合空调管线和电气管…

外架小横杆外露长度规范要求_脚手架工程现场施工的标准做法-宿城区嘉伟钢管租赁服务部...

脚手架工程施工现场分为落地式外脚手架、外脚手架里面防护、悬挑式脚手架、附着式脚手架、外脚手架水平保护、外脚手架连墙件设置、电梯井操作架、电梯井防护的标准搭设。今天,嘉伟钢管小编就带大家了解一下施工现场脚手架标准做法。 脚手架工程施工现场的标准做法如下: 一、…

多功能杆云平台设计规范

多功能杆&#xff08;也叫智慧灯杆&#xff09;作为未来智慧城市必备的公共市政设施&#xff0c;在执行基本的照明与通信覆盖的同时&#xff0c;也进行对城市公共环境的大量数据采集、数据传输、信息发布。多功能杆同时需要搭配一套整体管理平台&#xff0c;覆盖对所有杆载设备…
最新文章