2019年研究生数学建模国赛的一些想法。

比赛时间

• 开始：9月19日8：00 a.m.

• 结束：9月23日12：00 a.m.

• 时长：100小时整

比赛试题

• A：典型的机器学习的题目

• B：懒得看题

• C：CV题，测距

• D：汽车工况，数据处理题

• E：全球变暖题，直接DNN？

• F：多约束条件下的优化算法，看似好做（最终选择）

解法

第一问

• 先对点集构建KD-Tree，方便后期搜索
• 定义cost function使用$A^*$进行搜索，权衡跳数和欧式距离
• 从open set中取出cost值最小的节点并放入close set
• 遍历$k$邻近的节点，计算cost并更新垂直和水平误差，判断是否可达，可达节点放入open set
• 搜索宽度，直接用KD-Tree查询当前节点的KNN，时间复杂度可以达到$klog(n)$
• 可以先对数据进行一遍预处理，计算每个点对之间到达的可能性
• 可以根据当前的水平和垂直误差，来判断下一个选择的点是水平还是垂直校正点
• 最后一步到达$B$点的条件适当放宽

第二问

• 方法同一，但是更换了cost function
• 引入了最小转弯半径，两点之间的路径不能直接采用直线
• 根据文献，这里计算了两点之间的Dubins曲线的长度
• Dubins曲线计算参数
  • 当前坐标$(x_i,y_i,z_i)$，方向角和攻角$(\varphi_i, \gamma_i)$
  • 下一跳坐标$(x_i,y_i,z_i)$，方向角和攻角$(\varphi_j, \gamma_j)$
  • 最小转弯半径$R_{min}$
• 二维Dubins曲线的计算比较简单，现成的库函数比较多，不多做赘述
• 三维Dubins曲线比较复杂，只在Github上找到零星几个勉强可用的代码
  • 本来想看论文手写的，但是看到各种LSR、RSR等情况判断还有复杂的几何计算，觉得在有限时间内实现不太现实，果断放弃
  • 老实说这里花费的代码时间比较多，花费了整整两天，近乎一半的比赛时间，事后回忆起来貌似有点得不偿失
  • 最后使用的代码还存在角度问题，会使生成的曲线不一定是最短的，本想改变一下角度进行多次计算取最优，但是经过实践发现跑一次杜宾斯曲线+$A^*$都要花费仅半个小时，果断放弃
  • 虽然收敛的解和第一问的差别并不大
  • 题目规定的$R_{min}$和点集的数量级相差太大，导致最终画出的曲线看起来像是折线段

[1] Owen M, Beard R W, McLain T W. Implementing dubins airplane paths on fixed-wing uavs[J]. Handbook of Unmanned Aerial Vehicles, 2015: 1677-1701.

[2] Pharpatara P, Hérissé B, Bestaoui Y. 3D-shortest paths for a hypersonic glider in a heterogeneous environment[J]. IFAC-PapersOnLine, 2015, 48(9): 186-191.

第三问

• 在第一问的基础上，引入随机因素

• 计算出路径后使用蒙特卡洛来计算成功率

• 第二题的数据，坏点大部分都集中在和之间的路径上，导致成功率和路径较难权衡

• 玄学调参

赛后反思

• 工欲善其事必先利其器，赛前没有做好充分准备，未提前熟悉官方的latex模板，导致赛时各种基于google的latex写作，尤其是图片插入，不知为什么从draw.io上导出的png图片无法直接插入，浪费了很多时间导致早上在通宵的状态下急忙赶稿，还有subfigure的问题

• 别用Texpad！！！经过这次的比赛发现Texpad不适合快速写作，不能用Vim编辑是最大的痛点，以后直接上Visual Studio Code + Xelatex

• 三人分工安排略有不均，论文开始时间较晚

• 以后可以考虑用matlab

• 队友如果不会latex的话以后还是直接上word吧

• 保持充足的睡眠很重要，尤其不要通宵赶稿（但是感觉不太现实）

结果

果然拿铁了