Grid A^(*):面向野外空地协同应急处置的快速路径规划

Grid A^(*):A fast path planning algorithm for air-ground cooperative response of emergency rescue in the field

在野外应急救援活动中,灾害现场或事故区域通常缺乏地面交通工具可直达的现成道路,但该区域地表环境仍可满足部分越野车辆的通行。在空地协同系统中,无人机可提供行进路径周边环境的影像,地面终端可快速提取影像中地表类型以及地形起伏等特征信息,通过分析计算便可为车辆提供通往救援目标点的导航路径。本文针对这一应用需求,对现有A^(*)算法进行了改进,主要有3个方面的创新:其一,针对户外地表环境的应用特点,提出一种综合地表类型与地表高程信息的通行性代价函数;其二,针对无人机影像分辨率与实际车辆通行路径之间的尺度关系,提出一种基于格网单元的路径快速搜索算法;其三,在顾及格网单元内部地表类型连通分布特点的基础上,选择格网边缘特征点用于通行性路径规划,在提高算法搜索效率的同时,兼顾了格网单元内部的地形信息,从而使算法在优化计算的同时,能充分利用到无人机影像的细节信息。实验表明,算法搜索得到的可通行路径具有较高的可靠性,从路径三维可视化结果来看,符合越野车辆通行的需要。此外,同等情况下,本算法的运行时间降至传统A^(*)算法的15%,提高了野外应急救援应用的时效性。

Disasters and accidents often occur in remote areas that are inaccessible by conventional transportation.Common map navigation software also fails to provide a passable path.Therefore,only Sport Utility Vehicles(SUVs)can be used in field rescues.However,ground vehicles have limited awareness of their surroundings,so we chose to set up an air-ground cooperative system to overcome these vehicles’shortcoming.In the air-ground cooperative system,Unmanned Aerial Vehicles(UAVs)can provide environmental images surrounding the SUV for the ground terminal to obtain the navigation path of the vehicle by quickly extracting the type of surface and terrain undulations in the images.To better meet the above application requirement,this paper improves the existing A^(*)algorithm with three main innovations.First,we proposed a passability cost function that integrates surface type and surface elevation information considering the application characteristics of the outdoor surface environment.Second,we proposed a fast path search algorithm based on grid cells given the scale relationship between the resolution of UAV images and the actual vehicle paths.Third,we chose the marginal feature points of the grid for the passability path search in view of the connected surface-type distribution inside the grid cell.This approach improves the search efficiency of the algorithm while taking into account the terrain information inside the grid cell,such that the algorithm could make full use of the detailed information of the UAV images and optimize the calculation.The 3D visualization experiments show that the paths searched by the Grid A^(*)algorithm are more reliable and meet the needs of SUVs.The Grid A^(*)algorithm proposed in this paper,aiming at the highresolution images obtained by UAV,synthesizes image classification,slope calculation,and other methods to structure a passability cost function so that the paths are more reliable.In addition,the time cost of the algorithm is reduced to 15%of the traditional A^(*)algorithm,which improves the timeliness of emergency rescue in the field.