移动障碍场景的路径搜索算法

之前报名了天池大数据的比赛：

https://tianchi.aliyun.com/competition/information.htm?spm=5176.100067.5678.2.3d246108F4wkZF&raceId=231622

我的网盘中数据下载链接：链接:https://pan.baidu.com/s/1Wdbzktr8la5XMRpjrTotTQ  密码:sd42

可是只是做了最开始一部分。就被其他的事情耽搁了。

不过已经做的东西还是想记录一下，或许有人遇到类似的问题，可以帮助到他。

那么现在我们的问题是：在指定时间内完成货运任务。

给定出发城市和十个目的城市坐标，如图：

给定当天03:00-21:00内每小时的天气变化数据（当前区域内每一像素坐标风速），给的是一个csv文件，我把数据画出来方便分析：

上图是某一时刻的天气，黑色的部分表示风速<15，而白色的部分表示无人机无法通过。

要求规划出最优飞行路径。若无人机所在区域风速>15，则无人机坠毁。

那就是一个路径搜索算法，而且场景中的障碍物位置是变化。不过障碍区域是可以预知的。在一个二维的地图中，拥有变化的障碍物，实际上我们可以把时间看做第三维。那么问题就明朗了起来，实际上就是一个三维空间中的路径搜索，因为障碍物是可以预知的了。

用A星算法进行路径规划，根据需要更改局部的避障条件。

在A星算法中计算的代价为F=G（从出发位置到当前位置的代价）+H（从当前位置到终点位置的代价）。

这里我们计算代价要注意的是，我们不希望规划的航线是紧贴着障碍物的，因为这次的路径规划是在认为我们拟合的天气数据准确的前提下进行的，但是天气数据不可能100%准确。所以，还是和障碍物保持一点距离比较好。

那么就在代价函数中考虑一下增加一点局部障碍物的影响。

 T=最近的障碍物和当前位置的距离

 F=G+H+T

实际上为了达到比较好的效果，我们需要调整T的权重。可以令T=float(T)*(5.0+T)，二次的函数对大距离更敏感，调节常量5.0相当于调节T权重。

另外，在A星算法中，我们需要注意对非法位置的定义，应该是当前时刻风速>15的位置。这就需要得知我们已经规划的路径步数。所以我存储路径的方式为：

 t_point={'位置':(50,50),'代价':10000,'父节点':(50,50),'索引':[0,0],'风速':0,'时刻':3}#索引[0]为自身节点，[1]为父节点

这个字典记录了路径中某一节点的位置、代价、他的父节点、他的索引（也就是他是当前路径中的第几步）、父节点的索引、风速（方便最后输出观察路径是否合理）、时刻（走到当前位置的时间，实际上知道索引就可以得到时刻，因为飞行器的速度是固定的，走过的步数即代表话费的时间）。

这里记录索引的目的是：因为走过每一步后，周围的天气发生了改变，我们需要根据时刻搜索当前的障碍（风速>15的位置）。如果每次在开头都逆向搜索下当前路径花费的步数，到后期会花费特别多的时间，因为这是一个迭代的过程，closelist越来越大，计算出结果越来越慢。在这里以空间换时间吧。

最后搜索的路径：

黄色部分表示周围无障碍物区域。

代码和数据在：https://github.com/yimingstyle/Search-the-path-in-a-mobile-obstacle-scene

文件夹In_situ中是可视化的天气数据，利用函数def In_situ()根据In-situMeasurementforTraining_20171124.csv生成。

文件夹road中存放最后输出的路径结果，也是图像。文件名的含义为：10informap表示第一天目的地为城市0，23informap第二天目的地为城市3。而文件名为10informapshow这种图片，其中的灰色区域只是03:00时刻的天气，

比赛中的原始数据很大，是一些csv文件。在最上面的链接中可以下载。

函数city_location（）、In_situ()、Forecastdata（）都是可视化一些数据的函数，Forecastdata（）这个不要管它了。