2019 GMCM有感

2019年09月23日 218点热度 1人点赞 0条评论

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吧

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

结果

果然拿铁了

Plus

Think Different

文章评论