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...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.展开更多
As the number of automated guided vehicles(AGVs)within automated container terminals(ACT)continues to rise,conflicts have becomemore frequent.Addressing point and edge conflicts ofAGVs,amulti-AGVconflict-free path pla...As the number of automated guided vehicles(AGVs)within automated container terminals(ACT)continues to rise,conflicts have becomemore frequent.Addressing point and edge conflicts ofAGVs,amulti-AGVconflict-free path planning model has been formulated to minimize the total path length of AGVs between shore bridges and yards.For larger terminalmaps and complex environments,the grid method is employed to model AGVs’road networks.An improved bounded conflict-based search(IBCBS)algorithmtailored to ACT is proposed,leveraging the binary tree principle to resolve conflicts and employing focal search to expand the search range.Comparative experiments involving 60 AGVs indicate a reduction in computing time by 37.397%to 64.06%while maintaining the over cost within 1.019%.Numerical experiments validate the proposed algorithm’s efficacy in enhancing efficiency and ensuring solution quality.展开更多
Embodied intelligence applications,such as autonomous robotics and smart transportation systems,require efficient coordination of multiple agents in dynamic environments.A critical challenge in this domain is the mult...Embodied intelligence applications,such as autonomous robotics and smart transportation systems,require efficient coordination of multiple agents in dynamic environments.A critical challenge in this domain is the multi-agent pathfinding(MAPF)problem,which ensures that agents can navigate conflict-free while optimizing their paths.Conflict-based search(CBS)is a well-established two-level solver for the MAPF problem.However,as the scale of the problem expands,the computation time becomes a significant challenge for the implementation of CBS.Previous optimizations have mainly focused on reducing the number of nodes explored by the high-level or low-level solver.This paper takes a different perspective by proposing a parallel version of CBS,namely GPU-accelerated conflict-based search(GACBS),which significantly exploits the parallel computing capabilities of GPU.GACBS employs a task coordination framework to enable collaboration between the high-level and low-level solvers with lightweight synchronous operations.Moreover,GACBS leverages a parallel low-level solver,called GATSA,to efficiently find the shortest path for a single agent under constraints.Experimental results show that the proposed GACBS significantly outperforms CPU-based CBS,with the maximum speedup ratio reaching over 46.展开更多
基金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.
基金supported by National Natural Science Foundation of China(No.62073212)Shanghai Science and Technology Commission(No.23ZR1426600).
文摘As the number of automated guided vehicles(AGVs)within automated container terminals(ACT)continues to rise,conflicts have becomemore frequent.Addressing point and edge conflicts ofAGVs,amulti-AGVconflict-free path planning model has been formulated to minimize the total path length of AGVs between shore bridges and yards.For larger terminalmaps and complex environments,the grid method is employed to model AGVs’road networks.An improved bounded conflict-based search(IBCBS)algorithmtailored to ACT is proposed,leveraging the binary tree principle to resolve conflicts and employing focal search to expand the search range.Comparative experiments involving 60 AGVs indicate a reduction in computing time by 37.397%to 64.06%while maintaining the over cost within 1.019%.Numerical experiments validate the proposed algorithm’s efficacy in enhancing efficiency and ensuring solution quality.
文摘Embodied intelligence applications,such as autonomous robotics and smart transportation systems,require efficient coordination of multiple agents in dynamic environments.A critical challenge in this domain is the multi-agent pathfinding(MAPF)problem,which ensures that agents can navigate conflict-free while optimizing their paths.Conflict-based search(CBS)is a well-established two-level solver for the MAPF problem.However,as the scale of the problem expands,the computation time becomes a significant challenge for the implementation of CBS.Previous optimizations have mainly focused on reducing the number of nodes explored by the high-level or low-level solver.This paper takes a different perspective by proposing a parallel version of CBS,namely GPU-accelerated conflict-based search(GACBS),which significantly exploits the parallel computing capabilities of GPU.GACBS employs a task coordination framework to enable collaboration between the high-level and low-level solvers with lightweight synchronous operations.Moreover,GACBS leverages a parallel low-level solver,called GATSA,to efficiently find the shortest path for a single agent under constraints.Experimental results show that the proposed GACBS significantly outperforms CPU-based CBS,with the maximum speedup ratio reaching over 46.
