A greedy path planning algorithm based on pre-path-planning and real-time-conflict for multiple automated guided vehicles in large-scale outdoor scenarios  

作　　者：王腾达 WU Wenjun YANG Feng SUN Teng GAO Qiang WANG Tengda(Faculty of Information Technology,Beijing University of Technology,Beijing 100124,P.R.China)

机构地区：[1]Faculty of Information Technology,Beijing University of Technology,Beijing 100124,P.R.China [2]The 54th Research Institute of CETC,Shijiazhuang 050081,P.R.China

出　　处：《High Technology Letters》2023年第3期279-287,共9页高技术通讯（英文版）

基　　金：Supported by the National Key Research and Development Program of China(No.2020YFC1807904).

摘　　要：With the wide application of automated guided vehicles(AGVs) in large scale outdoor scenarios with complex terrain,the collaborative work of a large number of AGVs becomes the main trend.The effective multi-agent path finding(MAPF) algorithm is urgently needed to ensure the efficiency and realizability of the whole system. The complex terrain of outdoor scenarios is fully considered by using different values of passage cost to quantify different terrain types. The objective of the MAPF problem is to minimize the cost of passage while the Manhattan distance of paths and the time of passage are also evaluated for a comprehensive comparison. The pre-path-planning and real-time-conflict based greedy(PRG) algorithm is proposed as the solution. Simulation is conducted and the proposed PRG algorithm is compared with waiting-stop A^(*) and conflict based search(CBS) algorithms. Results show that the PRG algorithm outperforms the waiting-stop A^(*) algorithm in all three performance indicators,and it is more applicable than the CBS algorithm when a large number of AGVs are working collaboratively with frequent collisions.

关 键 词：automated guided vehicle(AGV) multi-agent path finding(MAPF) complex terrain greedy algorithm 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置] TP18[自动化与计算机技术—控制科学与工程]