重庆网站建设 狐灵科技,app开发价格要多少钱,查询关键词排名软件,迈创网站建设2012年国赛高教杯数学建模
D题 机器人避障问题 图1是一个800800的平面场景图#xff0c;在原点O(0, 0)点处有一个机器人#xff0c;它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物#xff0c;障碍物的数学描述如下表#xff1a…2012年国赛高教杯数学建模
D题 机器人避障问题 图1是一个800×800的平面场景图在原点O(0, 0)点处有一个机器人它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物障碍物的数学描述如下表 在图1的平面场景中障碍物外指定一点为机器人要到达的目标点要求目标点与障碍物的距离至少超过10个单位。规定机器人的行走路径由直线段和圆弧组成其中圆弧是机器人转弯路径。机器人不能折线转弯转弯路径由与直线路径相切的一段圆弧组成也可以由两个或多个相切的圆弧路径组成但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞同时要求机器人行走线路与障碍物间的最近距离为10个单位否则将发生碰撞若碰撞发生则机器人无法完成行走。 机器人直线行走的最大速度为vv(ρ)v_0/(1e(10-0.1ρ2 ) )个单位/秒。机器人转弯时最大转弯速度为 其中 是转弯半径。如果超过该速度机器人将发生侧 翻无法完成行走。 请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中4个点O(0, 0)A(300, 300)B(100, 700)C(700, 640)具体计算 (1) 机器人从O(0, 0)出发O→A、O→B、O→C和O→A→B→C→O的最短路径。 (2) 机器人从O (0, 0)出发到达A的最短时间路径。 注要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。
整体求解过程概述(摘要) 针对机器人避障问题本文分别建立了机器人从区域中一点到达另一点的避障的最短路径、最短时间路径的非线性0-1整数规划模型。同时本文为求带有NP属性的非线性0-1整数规划模型构建了有效启发式算法利用MATLAB软件编程求得了O→A、O→B、O→C、O→A→B→A→C的最短路径同时得到了O→A的最短时间路径求得的各类最短路径均是全局最优。 针对区域中一点到达另一点的避障的最短路径问题首先本文证明了圆弧位置设定在需要绕过障碍物的顶角上且圆弧半径为10个单位时能够使得机器人从区域中一点到达另一点的行进路径最短其次本文将最短路径选择问题转化成了最短路径的优选问题根据避障条件建立了具有较高普适性的避障最短路径的优化模型。为便于求解本文巧妙地将此优化模型转化成了以可行路径不与障碍物边界相交、不与圆弧相交为约束条件以机器人从区域中一点达到另一点避障路径最短为目标的0-1规划模型再次本文构建了两种有效的启发式算法利用MATLAB软件编程求得了O→A、O→B、O→C、O→A→B→A→C的最短路径最短路径长分别为471.0372、853.7001、1088.1952、2725.1596其中O–A的最短路径为(0,0)→(70.5063,213.1405) →(75.975,219.1542)→300,300)对应圆弧的圆心坐标为(80,210)O→B的最短路径对应圆弧的圆心坐标(60,300)、(150,435)、220、470、(220,530)、(150,600) O→C经过的圆心(410,100)、(230,60)、(720,520)720,600(500,200) O→A→B→C→O经过的圆心(410,100)(230,60) (80,210)(220,530)(150,600)(270,680)(370,680) (430,680)(670,730)(540,730)(720,520)(720,600)(500,200)。 针对最短时间路径问题我们建立了从o点出发到任意目标点的0-1非线性整数规划模型同时针对题意要求具体构建了从o点出发到A的最短时间路径的0-1非线性整数规划模型利用LINGO软件求解获得了机器人从o点出发到达A的最短时间路径求得最短时间路径下转弯半径为12.9885 同时最短时间路径时间长为94.2283个单位。相应圆弧的圆心坐标为82.1414207.9153两切点坐标分别为69.8045211.9779、77.7492,220.1387。
模型假设 1.将机器人看成一个质点 2.半径不变时机器人在行进、转弯过程中能一直保持最大的速度 3.机器人行走过程中不会意外停止 4.忽略影响机器人行走非最小转弯半径以及最小安全距离因素。
问题分析 求取最短路径的分析 本问题要求机器人从区域中一点到达另一点的避障最短路径。机器人只要做到转弯时的圆弧半径最小为10个单位、与障碍物最近距离单时刻保持大于10个单位那么可行走的路径就有无数条若想求得机器人从区域中一点到达另一点的避障最短路径则需要建立避障的最短路径模型而建立避障的最短路径模型有一定难度。根据对问题的分析我们认为可以从简单做起先确定小范围内最短路径条件如圆弧位置的影响圆弧半径的大小避免与障碍物碰撞条件等通过确定最短路径条件来建立避障的最短路径模型。对于最短路径的求取我们可以通过确定穷举原则利用穷举法来求解当然也可以通过构建启发式算法的进行求解。 最短时间路径的分析 对于要建立最短时间路径模型来说我们容易知道影响的因素有直线行走速度、转弯速度同时还需要考虑使得最短时间路径条件如圆弧位置坐标的影响圆弧半径的大小避免与障碍物碰撞条件等。对于直线行进我们希望行进速度越大越好对于机器人转弯时转弯速度要有约束要保证机器人不能发生侧翻。我们发现圆弧半径的大小与转弯速度紧密相连从转弯速度公式来分析当转弯半径增大时最大转弯速度也增大为在更短时间内行进到目标点我们希望转弯速度为机器人的最大转弯速度较好但有很大的可能是行进的路径不是最短的即行进路径有很大可能在增加。于是我们需要做的工作是在满足最短时间路径条件时找到一个圆弧的坐标位置同时确定半径的大小以求得最短时间路径。
模型的建立与求解整体论文缩略图 全部论文请见下方“ 只会建模 QQ名片” 点击QQ名片即可
程序代码
function minddistancebetweenlines(A,B,C,D,M)
AxA(1);AyA(2);
BxB(1);ByB(2);
CxC(1);CyC(2);
DxD(1);DyD(2);
if (A(1)-B(1))~0k(By-Ay)/(Bx-Ax);bBy-k*Bx;ABXXLlinspace(A(1),B(1),M);ABYXLk.*ABXXLb;
elseABXXLlinspace(A(1),B(1),M);ABYXLlinspace(A(2),B(2),M);
end
if (C(1)-D(1))~0k(Dy-Cy)/(Dx-Cx);bDy-k*Dx;CDXXLlinspace(C(1),D(1),M);CDYXLk.*CDXXLb;
elseCDXXLlinspace(C(1),D(1),M);CDYXLlinspace(C(2),D(2),M);
end
mind100000;
for i1:Mfor j1:Mif sqrt((ABXXL(i)-CDXXL(j))^2(ABYXL(i)-CDYXL(j))^2)mindmindsqrt((ABXXL(i)-CDXXL(j))^2(ABYXL(i)-CDYXL(j))^2);endend
endclear
clc
close all
theta0:pi/100:2*pi;
zb{1}[300 400;500 400;500 600;300 600];
zb{2}[550 450;70 70];
zb{3}[360 240;400 330;540 330;500 240];
zb{4}[280 100;345 210;410 100];
zb{5}[80 60;80 15060;15080 15060;15080 60;];
zb{6}[60 300; 150 435;235 300];
zb{7}[0 470;220 470;220 530;0 530];
zb{8}[150 600;240 600;270 680;180 680];
zb{9}[370 680;430 680;430 800;370 800];
zb{10}[540 600;670 600;670 730;540 730];
zb{11}[640 520;720 520;720 600;640 600];
zb{12}[500 140;800 140;800 200;500 200];
zb{13}[0 0;0 800;800 800;800 0;];
zb{14}[0 0 79];
zb{15}[300 300 65];
zb{16}[100 700 66];
zb{17}[700 640 67];
for i1:length(zb)tempzb{i};if size(zb{i},1)2xtemp(2,1)*cos(theta)temp(1,1);ytemp(2,2)*sin(theta)temp(1,2);plot(x,y,r-);hold onelseif size(zb{i},1)3for j1:length(temp)plot([temp(:,1);temp(1,1)],[temp(:,2);temp(1,2)],b-);hold onendelseif size(zb{i},1)4for j1:length(temp)plot([temp(:,1);temp(1,1)],[temp(:,2);temp(1,2)],b-);hold onendelseif size(zb{i},1)1plot(temp(1),temp(2),r.,MarkerSize,12);text(temp(1)10,temp(2)20,char(temp(3)));hold onendif i12i~2for j1:size(temp,1)temp1temp(j,:);x10*cos(theta)temp1(1);y10*sin(theta)temp1(2);plot(x,y,r-);hold onendend
end
axis([0 800 0 800]);grid on
hold off
%下面计算切点坐标
for i1:4x[];y[];kk1;tempzb{13i};Atemp(1:2);for j1:12temp2zb{j};if j2r70;temp2temp2(1,:);elser10;endfor k1:size(temp2,1)Btemp2(k,:);if ~ismember(B(1),[0,800]) ~ismember(B(2),[0,800])[x(:,kk) y(:,kk)]qiedian(A,B,r);kkkk1;endendendqdzb(:,:,i)[reshape(x,1,2*length(x));reshape(y,1,2*length(y))];
end全部论文请见下方“ 只会建模 QQ名片” 点击QQ名片即可
