Anterior|Siguiente

Grid A*：A fast path planning algorithm for air-ground cooperative response of emergency rescue in the field

  • role： First author第一作者
  • Affiliation：

    Institute of Remote Sensing and Geographical Information System, Peking University, Beijing 100871, China

  • Email：adhamwang@pku.edu.cn
  • Introduction：王修远， 研究方向为地表可通行性分析与路径规划。E-mail： adhamwang@pku.edu.cn
WANG xiuyuan1,  
  • role： Corresponding author通信作者
  • Affiliation：

    Institute of Remote Sensing and Geographical Information System, Peking University, Beijing 100871, China

  • Email：sunmin@pku.edu.cn
  • Introduction：孙敏， 研究方向为无人机遥感与数字摄影测量学。E-mail：sunmin@pku.edu.cn
SUN min1*,  
  • Affiliation：

    Institute of Remote Sensing and Geographical Information System, Peking University, Beijing 100871, China

LI xiuxian1,  
  • Affiliation：

    Institute of Remote Sensing and Geographical Information System, Peking University, Beijing 100871, China

ZHOU hang1,  
  • Affiliation：

    JIBEIZHONGYUAN Geotechical Engineering Co., Ltd., Langfang 065001, China

ZHAO Renliang2

resumen

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 high-resolution 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.

palabra clave

remote sensing;path planning;Grid A* algorithm;A* algorithm;air-ground coordination;passability cost function

References

  1. 1.
    Choi K, Lee I, Hong J, Oh T and Shin S. 2009. Developing a UAV-based rapid mapping system for emergency response. Proceedings of SPIE 7332, Unmanned Systems Technology XI. Orlando: SPIE
  2. 2.
    Choi K and Lee I. 2012. A UAV based close-range rapid aerial monitoring system for emergency responses. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XXXVIII-1/C22: 247-252
  3. 3.
    Delmerico J, Mueggler E, Nitsch J and Scaramuzza D. 2017. Active autonomous aerial exploration for ground robot path planning. IEEE Robotics and Automation Letters, 2(2): 664-671
  4. 4.
    Fan L L. 2017. Research on Cross-Country Path Planning Technology based on Hexagonal Grid. Zhengzhou: PLA Information Engineering University: 10-53
  5. 5.
    Harabor D and Grastien A. 2011. Online graph pruning for pathfinding on grid maps//Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. San Francisco: AAAI Press, 2011: 1114-1119
  6. 6.
    Li X D. 2017. Terrain traversability analysis in air-ground collaborative emergency. Beijing: Peking University: 41-45
  7. 7.
    Li J Q, Deng G Q, Luo C, Lin Q W, Yan Q and Ming Z. 2016. A hybrid path planning method in unmanned air/ground vehicle (UAV/UGV) cooperative systems. IEEE Transactions on Vehicular Technology, 65(12): 9585-9596
  8. 8.
    Li X X, Sun M, Li X D and Ren X. 2019. Terrain traversability analysis method for Air-ground collaborative emergency. Journal of Shihezi University (Natural Science), 37(1): 12-20
  9. 9.
    Sun Y Z. 2020. Global Path Planning and Trajectory Tracking of Unmanned Wheeled Vehicles on Terrains. Changchun: Jilin University: 17-43
  10. 10.
    Wu T Y, Xu J H, Liu J Y and Liao W. 2013. Research of cross-country path planning based on improved A* algorithm. Application Research of Computers, 30(6): 1724-1726
  11. 11.
    Xi A X, Zhao J, Zhou T and Hu Q X. 2019. Target searching and global path planning in UAV/UGV cooperative systems. Application of Electronic Technique, 45(1): 5-9
  12. 12.
    Yap P, Burch N, Holte R C and Schaeffer J. 2011. Block A*: database-driven search with applications in any-angle path-planning//Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. San Francisco: AAAI Press, 2011: 120-125
  13. 13.
    Zhao D Q, Duan J Y, Chen P Y and Su J H. 2017. Optimal path planning for 3D Map based on A* algorithm. Computer Systems and Applications, 26(7): 146-152

Leer el texto completo

The above content is generated by Large Model Translation. The translated content is for reference only. We do not assume any commercial or legal responsibilty for any consequences arising from the use of our website