Search papers, labs, and topics across Lattice.
This paper introduces Conflict-Based Lazy Search (CBLS), a novel planning algorithm designed to enhance multi-manipulator planning in cluttered environments. By integrating a precomputed lazily evaluated graph and the Lazy Edge-based A* (LEA*) algorithm, CBLS significantly reduces the computational burden associated with edge evaluations, which are critical for efficient planning. Experimental results demonstrate that CBLS outperforms both the traditional Conflict-Based Search (CBS) and the RRT-Connect sampling-based algorithm, achieving faster planning times and improved efficiency in multi-manipulator scenarios.
CBLS achieves unprecedented speedups in multi-manipulator planning by leveraging lazy evaluation techniques, outpacing existing methods like CBS and RRT-Connect.
Employing multiple manipulators can boost efficiency and accomplish tasks that a single manipulator cannot do. However, real-time planning for multiple manipulators in a cluttered workspace still poses significant challenges for planning algorithms. This article proposes a new planning algorithm called Conflict-Based Lazy Search (CBLS) for multimanipulator planning. CBLS is built on Conflict-Based Search (CBS), an efficient multiagent pathfinding (MAPF) algorithm that has shown an order of magnitude speedup over previous approaches [1], [2]. CBS addresses MAPF by solving many single-agent pathfinding (SAPF) problems. Thus, its planning time directly depends on the efficiency of the SAPF algorithm adopted. Our CBLS algorithm enhances CBS with precomputation and lazy search. First, a lazily evaluated graph with controlled sparsity is precomputed for a single manipulator. Second, we propose the Lazy Edged-based A* (LEA*) for efficient SAPF. Since edge evaluation is the computational bottleneck of manipulator planning, LEA* uses lazy search and an edge queue to reduce the number of edge evaluations. We show that LEA* is optimally vertex efficient and has improved edge efficiency compared to A*. We apply the proposed CBLS to multi-manipulator planning problems and show its superior performance by comparing it with CBS and a sampling-based algorithm, namely, RRT-Connect.
