Scholarlink

<p>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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

GPU-accelerated Conflict-based Search for Multi-agent Embodied Intelligence

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年7月25日

查看全文
  • Mingkai Tang,
  • Ren Xin,
  • Chao Fang,
  • Yuanhang Li,
  • Hongji Liu,
  • Jin Wu

摘要

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.