2022年第二十四届华东杯数学建模

C题 多体协同调度问题

原题再现：

  某机器人公司正在研发一款智能小车，为推销产品该公司计划制作一部宣传片。宣传片中需要将 36 辆小车在一个边长为 2 米的正方形区域内排列成指定的图案。小车只能由指挥中心统一调度，无法自行获得其它信息。已知每辆小车的最大线速度为 10 厘米/秒，并且小车在运动过程中严禁碰撞。
  问题 1 如图 1 所示，初始状态下小车以 20 厘米的横向及纵向间距均匀分布在正方形左下方的一个等腰直角三角形区域内。每辆小车视为半径 1 厘米的圆盘。请设计一种调度方案，使得小车以尽可能短的时间排成如图 2 所示的图案，并且小车在曲线上的分布尽量均匀。请以 1 秒为时间步长的快照形式对运动过程进行展示。

  问题 2 如图 3 所示，初始状态下小车以 32 厘米为间距均匀分布在正方形区域内，目标是将它们排列成如图 4 所示的 “SH” 型曲线。每辆小车视为长 10 厘米的有向线段，运动终止时的朝向为曲线的切向正向。
  已知每辆小车设计的最小转弯半径为 15 厘米，但实际有不超过 5% 的相对误差。指挥中心每隔 0.1 秒能获取所有小车当前的位置与朝向，来决定是否需要向小车发布新的指令来纠正其原有的操作指令序列。若指挥中心向小车发出一组新的指令，小车会在指令发出 0.2 秒后收到并响应新的指令，否则小车会按照原有的指令序列来运动。
  请在这种情况下设计控制调度方案，使得小车能用尽可能短的时间排成如图 4 所示的图案，且小车在曲线上的分布尽量均匀。请以 1 秒为时间步长的快照形式对运动过程进行展示。

整体求解过程概述(摘要)

  本文研究了多体协同的最佳调度方案。通过建立路径规划模型，设置了最佳行驶路径规则，避让规则以及指令调节规则，并结合小车速度以及转弯半径的约束构建了以最短运行时间为目标的优化模型并使用改进遗传算法求解。
  针对问题一，建立以各方案中用时最久的小车中的最短时间为目标的优化模型。首先根据心形图案均匀分布目标点并计算了坐标。为了使路程尽可能短，设定小车行驶路径为初始点与原的连线。同时为了防止小车碰撞，本文根据可能发生碰撞的两种情况分别进行研究，计算出了可能发生碰撞的区域范围，并得到了小车在进行躲避时最佳的等待位置。最终，将时间作为目标函数，结合行驶规则和碰撞躲避规则，以及小车体积、速度等物理特性构造优化模型，使用改进的遗传算法进行求解，过程展示见图 13a,图 13b,图 13c,图 13d所示。
  针对问题二，建立了基于问题一的优化模型。由于目标点排列为“SH”型曲线，根据均匀分布的要求，首先计算了各点的坐标。由于小车为有向线段，所以本文使用分段的牛顿插值法计算了曲线的函数，并在目标点处求导，作为该点小车的方向。考虑到小车转弯半径具有 5% 的误差，本文在误差范围内随机生成了 36 辆小车的实际半径。随后，为了使小车的行驶路径最短，本文采用选取最小半径构成的两段圆弧和一段切线作为选取行驶路径。同时由于小车开始运行 0.1s 后才能得知实际状态，且 0.2s 延迟后才能接受指令，本文制定了相应的路径调整规则。再考虑到多种不同的碰撞情形，利用小车行驶时所覆盖的区域结合行驶路径计算出了会发生碰撞的区域，以及小车避让时最佳的等待位置。最后，将各方案用时最长的小车中的最短时间作为目标函数，结合制定的行驶规则，指令调整规则，碰撞躲避规则，以及小车体积、速度、转弯半径等物理特性构造优化模型，同样使用改进的遗传算法进行求解，过程展示见图 29a,图 29b,图 29c,图 29d所示。

模型假设：

  假设 1 小车的速度为 10cm/s，忽略加速和减速过程
  假设 2 小车性能保持不变，不会因为运行过久产生变化
  假设 3 小车抓地力足够，行驶时不会产生漂移现象，完全按照规划的路径行驶。

问题分析：

问题一的分析

  问题一需要让小车在尽可能短的时间内排列至规定的位置，关键在于计算最后一辆到达位置的小车所需要的时间。由于小车目标点均匀分布，可以因此计算各目标点的坐标。随后根据小车不可以发生碰撞的要求，所以需要设置躲避法则，计算最佳躲避区域，以此缩短等待时间，达到效率最大化。对于行驶策略，为使时间最短，可直接认为行驶路径为初始点与对应分配的目标点的连线。最后，为了计算在各方案中用时最长的小车的最短运行时间，本文将其定位目标函数，结合约束条件后，采用改进遗传算法进行求解。

问题二的分析

  问题二需要让小车尽快排列至所需要的位置，关键在于综合考虑圆周运动与直线运动相结合的最短路径规划。首先，需要根据均匀分布的要求计算目标点的坐标，并利用分段牛顿插值函数计算小车的指向。由于小车转弯半径具有 5% 的误差，所以需要随机生成各小车转弯半径。再制定对应的行驶规则，避让规则，指令调节规则，同样以各方案中用时最长的小车的最短运行时间作为目标函数，利用改进遗传算法进行求解。

模型的建立与求解整体论文缩略图

全部论文请见下方“ 只会建模 QQ名片” 点击QQ名片即可

程序代码：(代码和文档not free)

论文及程序仅供学习与参考

function [car] = carforward(car)
%CARFORWARD 此处显示有关此函数的摘要
% 此处显示详细说明
if abs(car.position(1)-car.des(1))>abs(car.step(1))
car.position(1)=car.position(1)+car.step(1);
car.position(2)=car.position(2)+car.step(2);
else
car.position=car.des;
car.state=1;
end
end

function [result] = count2len(w_point,d1,r,k)
%COUNT2LEN 计算到达指定位置总长
% 此处显示详细说明
%获得两个圆心和转角beta
if w_point(1)0
e2=[r*cos(atand(1/k))+d1(1),-r*cos(atand(1/k))+d1(2)];
else
e2=[-r*cos(atand(1/k))+d1(1),r*cos(atand(1/k))+d1(2)];
end
%计算切点
R=[e2(1)+r*cosd(beta),e2(2)+r*sind(beta)];
%计算X1
kee=(e2(2)-e1(2))/(e2(1)-e1(1));
if e2(1)>e1(1)
x1=deg2rad(90-atand(kee))*r;
elseif e2(1)

function [result] = draw(car)
%DRAW 此处显示有关此函数的摘要
% 此处显示详细说明
location=zeros(36,2);
for i=1:36
location(i,:)=car(i).position;
end
% plot(location(:,1),location(:,2),'o','LineWidth',1);
% plot(location(:,1),location(:,2),'xk','LineWidth',1);
plot(location(:,1),location(:,2),'xk',location(:,1),location(:,2),'bo');
grid on
ax=gca;
ax.XLim=[0,200];
ax.YLim=[0,200];
result=getframe(1);
% set(gca, 'xTick', x);
% % set(gca,'XTickLabel',{'0','3','5','10','15','20','25','30'})
% set(gca, 'FontSize', 8);
end