Accelerating Search-Based Planning for Multi-Robot Manipulation by Leveraging Online-Generated Experiences

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-05 20:18:22

Abstract: An exciting frontier in robotic manipulation is the use of multiple arms at once. 
However, planning concurrent motions is a challenging task using current methods. The high-dimensional composite state space renders many well-known motion planning algorithms intractable.
Recently, multi-agent path finding (MAPF) algorithms have shown promise in discrete 2D domains, providing rigorous guarantees. However, widely used conflict-based methods in MAPF assume an efficient single-agent motion planner. This poses challenges in adapting them to manipulation cases where this assumption does not hold, due to the high dimensionality of configuration spaces and the computational bottlenecks associated with collision checking.
To this end, we propose an approach for accelerating conflict-based search algorithms by leveraging their repetitive and incremental nature -- making them tractable for use in complex scenarios involving multi-arm coordination in obstacle-laden environments. 
We show that our method preserves completeness and bounded sub-optimality guarantees, and demonstrate its practical efficacy through a set of experiments with up to 10 robotic arms.

Main paper: 
 introduction: 
 The synchronous use of multiple robotic arms may enable new application domains in robotics and enhance the efficiency of tasks traditionally carried out by a single arm. For example, in pick-and-place tasks, multiple arms can potentially be more efficient than a single one, and in a manufacturing setting, multiple arms can be used to assemble a product collaboratively, unlocking the capability to perform tasks that are beyond the scope of a single arm. However, the inherent complexity of single-agent motion planning for robot manipulation (Canny 1988 ) makes it challenging to plan for multiple arms while ensuring collision-free paths, and thus has left the Multi-Robot-Arm Motion Planning (M-RAMP) problem a relatively under-explored frontier in robotics.To enable the use of multiple arms in more complex scenarios, we propose a method for accelerating multi-robotarm motion planning. Our approach capitalizes on a key observation: widely-used multi-agent path-finding algorithms exhibit a significant degree of repetitive planning. We exploit this repetitiveness by developing an approach that leverages experiences gathered during the planning process. Unlike previous approaches that utilize incremental search techniques (Boyarski et al. 2021) , we allow the use of bounded Figure 1 : A team of 8 robotic manipulators, each of 7-DOF, collaborating in a shelf-rearrangement task. Planning concurrent motions for all arms requires a motion planner capable of efficiently exploring the high-dimensional state space of a single arm, and also reasoning about the motions of multiple robots operating in the shared task space.sub-optimal search techniques, which are crucial for exploring high-dimensional state spaces. To this end, we accel-45 erate the single-agent planning process by reusing onlinegenerated path experiences to speed up multi-agent search, ensuring both completeness and solution quality guarantees Our contributions in this paper are threefold. First, we introduce a novel method for multi-robot-arm motion plan-50 ning. Second, we provide a comprehensive theoretical analysis of our proposed framework, demonstrating its bounded sub-optimality guarantees. Third, we offer an empirical evaluation of our method and other algorithms in various multiarm manipulation scenarios that include deadlock avoid-55 ance, cluttered environments, and closely interacting goals.The literature has extensively examined path planning for both single and multi-agents. In the context of single-agent search, decades of research have yielded algorithms capable 60 of scaling successfully to high-dimensional and computationally expensive search spaces. However, efforts in multiagent path planning have generally been applied to domains such as 2D-grid worlds, resulting in algorithms that often rely on assumptions such as fast single-agent planning and informative heuristics. These assumptions may not always hold in other scenarios such as robotic manipulation. In this study, we introduce a method aimed at speeding up multiagent path planning in contexts where single-agent planning is hard.In practice, planning for multi-arm manipulation is often done with coupled methods or prioritization methods. In coupled methods, the state of all arms is seen as a single composite state, and the search is performed in this space with algorithms such as A* (Nilsson 1980) , Rapidlyexploring Random Trees (RRT) (Karaman and Frazzoli 2011) , and their variants (e.g., weighted A*, RRT* (Karaman and Frazzoli 2011), RRT-Connect (Kuffner and LaValle 2000), etc.) . With the addition of more arms the search space grows exponentially, and in general, coupled methods are not scalable to large numbers of arms.In scenarios where coupled planning is rendered intractable due to the exponential growth of the search space, prioritization methods may be effective in reducing its dimensionality. In prioritized planning (PP) (Erdmann and Lozano-Perez 1987) , each arm is assigned a priority, and the lower-priority arms must respect the plans of all higherpriority arms. In the general case, solving the prioritized planning problem is more efficient than the coupled case, as the search space is reduced to the space of each single arm. However, the price paid for this dimensionality reduction is the loss of completeness. In scenarios requiring close coordination between arms completeness may be important.Recently, planning algorithms have been proposed for teams of high-dimensional agents and applied to multi-arm settings. These methods explore the search space via preconstructed single-agent roadmaps (probabilistic roadmaps (PRM) (Kavraki et al. 1996) and potentially task-informed roadmaps (Solano et al. 2023 )), which may need to be arbitrarily resampled (Solis et al. 2021 ) to find collision-free paths in complex environments. In (Shome et al. 2020) , the authors present dRRT*, a method for exploring the composite state-space of agents by traversing individual agents' roadmaps towards sampled configurations with goal bias. In 105 (Solis et al. 2021) , the authors present CBS-MP, a variant of Conflict Based Search (CBS) (Sharon et al. 2015 ) that imposes new constraints on the search space to resolve conflicts between agents. Specifically, to resolve a conflict between two agents, CBS-MP requires one agent to avoid the 110 colliding configuration of the other at the time of conflict.Multi-agent path finding (MAPF) is the problem of finding collision-free paths for a set of agents on a graph (e.g., on a grid world) (Stern 2019) . MAPF has been studied exten-115 sively, and optimal (e.g., CBS (Sharon et al. 2015 )), bounded sub-optimal (e.g., ECBS (Barer et al. 2014 )), and suboptimal but effective (e.g., MAPF-LNS2 (Li et al. 2022 )) algorithms have been proposed. Some work has also been done to generalize MAPF algorithms to non-point robots 120 (Li et al. 2019) , however, the most common domain is still in 2D. Arguably, the most influential family of algorithms is CBS and its extensions (Sharon et al. 2015; Barer et al. 2014; Li, Ruml, and Koenig 2021) . CBS is a two-level search algorithm, where at the low level, each agent is assigned a 125 single-agent path planning problem. At the high level, conflicts between single-agent solutions are resolved by imposing constraints on the low-level planners. CBS is known to provide completeness and optimality guarantees. However, CBS is also known to be computa-130 tionally expensive as it requires repeated low-level searches upon additions of constraints. Given this inefficiency, CBS is often regarded as impractical for domains, like in manipulation, where planning for a single agent requires the exploration of a high-dimensional space and does not enjoy in-135 formed heuristics. In this work, we capitalizing on this repetition and propose a method for accelerating multi-agent path finding algorithms by reusing online-generated previous search solutions.Streamlining motion planning from experience encompasses a wide range of motion planning algorithms. These generally benefit from either utilizing offline-generated data (i.e., precomputation), from leveraging online-generated data, or both.Precomputation as Experience The utilization of offline computations for enhancing online search efficiency is well exemplified by the PRM algorithm and its variants. Another novel approach is found in the Constant-time Motion Planners (CTMP) family of algorithms, which operates on precomputed data structures to achieve constant-time path generation in online scenarios (Islam, Salzman, and Likhachev 2021; Islam et al. 2021b,a; Mishani, Feddock, and Likhachev 2023) . In recent research, a significant focus has been on the offline decomposition of the configuration space into collision-free convex sets (Dai et al. 2023) . This decomposition enables planning smooth trajectories within these sets using optimization methods (Marcucci et al. 2023 (Marcucci et al. , 2022)) . Furthermore, various algorithms based on precomputed trajectories (Phillips et al. 2012; Berenson, Abbeel, and Goldberg 2012) , have been employed to expedite the search process. When extending these techniques to plan for multi-arm setups, it becomes essential to decompose the composite configuration space for computing collision-free trajectories. However, challenges arise when the environ-165 ment or the robot undergoes changes, which can be as simple as rotating a bin or altering the robot's geometry by grasping an item. These changes may require resource-intensive operations like redoing pre-computation or propagating changes, emphasizing a drawback inherent to using offline-generated experiences.Online-Generated Experiences Anytime algorithms, like Anytime Repairing A* (ARA*) (Likhachev et al. 2008) , can be seen as methods that utilize online-generated experiences to enhance solution quality over time. ARA* carries out a sequence of searches that, given enough time, converge to the optimal solution. A recent anytime approach inspired by (Likhachev et al. 2008; Phillips et al. 2012) , and presented in (Mishani, Feddock, and Likhachev 2023) , employs both precomputation and online experience. Their algorithm computes an initial, potentially sub-optimal, path within a (short) constant time and improves the quality of the path using the current best solution as an experience.Drawing inspiration from the way the approach in (Mishani, Feddock, and Likhachev 2023) capitalizes on the flexibility seen in online-generated experiences, and with the observation that CBS-based algorithms inherently exhibit repetition in the form of nearly identical single-agent planning queries, we propose a method for accelerating multi-agent path finding algorithms by reusing online-generated experiences.In this paper, we propose a method for solving the M-RAMP problem by extending the CBS algorithm and its variants to reuse search efforts. We first describe the problem formulation and then detail the CBS algorithm.Consider Q i ⊆ R d as the configuration space of a single robotic arm R i with d degrees of freedom (DoF), and let the composite configuration space of n robotic manipulators beQ = Q 1 × Q 2 × • • • Q n .With all manipulators operating within the same environment W ⊂ R 3 , let Q free be the set of all collision-free configurations (both with the environment and between robots):Q free = {q ∈ Q | q is collision-free}Given an initial composite configuration q start ∈ Q free and a composite goal configuration q goal ∈ Q free , we want to find a valid path Π : [0, T ] → Q free where Π(0) = q start and Π(T ) = q goal . A discrete analog of the problem is to find a sequence of configurations Π = {q 0 , q 1 , • • • , q T } such that ∀t ∈ [0, T ], q t ∈ Q free , each interpolated configuration between q t and q t+1 is collision-free, and q 0 = q start and q T = q goal .Instead of addressing the motion planning problem in the high-dimensional composite state space, it is possible to decompose the problem into a set of single-agent motion planning problems and locally resolve conflicts between the paths of agents. The resulting solution can be represented asΠ = {π 1 , π 2 , • • • , π n }, where π i = {q i 0 , q i 1 , . . . , q i T | q i t ∈ Q i free ∀t = 0, . . . , T } is a path for agent R i from its start q i start ∈ Q i to its goal q i goal ∈ Q i configuration.CBS is a complete and optimal two-level best-first search algorithm solving the MAPF problem. It utilizes single-agent planners, also known as low-level planners, to compute individual paths for each agent and employs a high-level search to resolve conflicts between the proposed paths. CBS begins by querying a path π i for a given agent R i between its start and goal configurations without regard to other agents. This solution Π is a candidate solution for the problem, and it is stored in the OPEN list of the highlevel search. A high-level node, called a constraint-tree (CT) node, holds within it a set of paths Π for all agents, and a set of constraints C imposed on the low-level planners. The cost of a CT node is the sum of the costs of its stored paths.CBS proceeds iteratively, selecting least-cost solutions from OPEN and evaluating them for conflicts. If there are no conflicts found in a solution, then it is accepted as valid and the algorithm terminates. Otherwise, the conflict is used to create two new CT nodes, which are added to OPEN. Given a conflict between two agents R i and R j at time t, for example, because their configurations q i t and q j t are in collision, then two vertex-constraints are created. Either ⟨i, q i t , t⟩, forbidding R i from being at q i t at time t, or ⟨j, q j t , t⟩, forbidding R j from being at q j t at time t. If a conflict is found during a transition between times t and t + 1, then edgeconstraints are created and take the form ⟨i, q i t , q i t+1 , t⟩ or ⟨j, q j t , q j t+1 , t⟩. Each edge-constraint forbids R i or R j from moving between q i t and q i t+1 at time t. Given the two new constraints created from the detected conflict, CBS and its variants create two new CT nodes. In each, the new constraint is added to the constraint set C, and the low-level planners are invoked to find a new path for each newly constrained agent. The new paths are stored in the new CT node, and the two created nodes are added to OPEN.Enhanced CBS (ECBS) (Barer et al. 2014 ) is a widely used bounded sub-optimal variant that minimizes conflicts within a specified suboptimality bound. It employs focallists in low-and high-level searches, ordering nodes based on conflict minimization.In CBS and its variants, new low-level planner invocations closely resemble previous ones. Initially invoked with constraintsC i = {c ∈ C | c involves R i } for agent R i , the next invocation includes C i ∪ ⟨i, q it , t⟩ when an additional vertex constraint is introduced. This slight difference suggests potential benefits from reusing parts of the previous solution. Iterative-Deepening CBS (IDCBS) (Boyarski et al. 2021 ) leverages this insight in the 2D case using Lifelong Planning A* (LPA*) (Koenig, Likhachev, and Furcy 2004) . However, this approach faces challenges in manipulation cases where bounded sub-optimal search is employed to navigate the high-dimensional search space (Likhachev and Koenig 2005) .Our main contribution in this work is an experienceacceleration framework for CBS-based algorithms. We instantiate this framework in two incarnations, xCBS and xECBS, accelerating CBS and ECBS, respectively. In this section, we present the general form of our acceleration method in an intuitive manner grounded by Algorithm 1 and Algorithm 2, and then provide a theoretical analysis of its performance alongside its instantiations xCBS and xECBS.Our framework follows the CBS structure and informs new low-level planner calls with the experience generated in previous search efforts. In the high-level search (Alg. 1), each node, called a CT node, contains a set of paths Π, one for each manipulator, and a set of constraints. Upon obtaining a new node from OPEN it is checked for conflicts (line 13). If there are none, the node is a goal node and the paths are returned (line 15). Otherwise, a set of constraints is derived from the conflicts (line 16). Usually, CBS proceeds by creating a new CT node, one with an added constraint from the constraint set (lines 18-19), and replans a single-agent path for each affected agent from scratch (line 21). However, we recognize that a considerable portion of the previously generated paths remains valid and can be effectively reused. Thus, to speed up the search, we cache a copy of the previously computed paths as experience, which are in turn passed to the low-level motion planner (lines 17, 21). The experiences are time-agnostic, meaning that they do not include a time dimension but only the topology of the path. We Algorithm 1: High-level Planner Input : n: Number of manipulators (agents) q start = {q 0 start , . . . q n start } q goal = {q 0 goal , . . . q n goal }Output: have experimented with reusing experiences from the previous search effort, from all previous search efforts on the CT branch, and globally from the CT, and seen that reusing the 305 previous path yields the best performance.Path Π = {π 1 , π 2 , • • • , π n }The low-level of our acceleration framework, namely xWA * , is detailed in Algorithm 2 and illustrated in Fig. 2 . Each node expansion (lines 17-32) adds a set of successors to the OPEN list. Additionally, upon a node expansion, 310 xWA* attempts to accelerate the search by also adding a subset of the experience path to the OPEN list.Upon a choice of a node for expansion (line 17), the search terminates if it is a goal state (lines 18-21). Otherwise, we check if the expanded state belongs to the experi-315 ence path (line 23). The experience and the goal are strictly spatial, so state equivalence does not include time. If the expanded state belongs to the experience, and at least one consecutive state in the experience is feasible, we say that the state satisfies the addition-condition. Subsequently, starting 320 from that state, we aim to add as much of the experience as possible to the OPEN list (line 25). This process is also applied to the start state (line 14) and essentially provides a "warm start" to the search effort.Given an expanded state s that satisfies the additioncondition, we first propagate the time and cost of the experience to begin at the values of s (line 3). Then, we attempt to add consecutive states from the experience (line 5) until we encounter the termination-condition, namely, violating constraints.The effect of adding an experience path to the OPEN list of a bounded sub-optimal search algorithm, such as weighted A*, could be a rapid exploration of states that are closer to the end of the experience path (and consequently, closer to the goal). Figure 2 illustrates this effect. Such exploration results in the algorithm "jumping" over previously explored regions and avoiding redundant search efforts, directing its focus closer to the end of the experience.Collision checking against the static environment, a significant factor in the slowness of planning for manipulation, can also be directly accelerated with experience. To this end, our acceleration framework also keeps track of the configurations (q i t , q i t+1 ) in all valid transitions (s t , s t+1 ) for each robot R i . With this information, the successors set (line 26) can be computed more rapidly by only checking the validity of edges previously unseen. Since it is possible for one single-agent search to revisit the same configuration at different times, such experience reuse also speeds up the first search.In this section, we discuss the theoretical foundation of our algorithm. We show that it is complete and provide bounded sub-optimality guarantees. First, we define the CBS framework using focal-search and introduce some of the properties of CBS and its bounded sub-optimal variants. Subsequently, we demonstrate that our accelerated variant maintains these properties.We formally define the problem for both levels of CBS as a focal-search (Cohen et al. 2018) . Focal search employs two priority queues: OPEN and FOCAL. OPEN mirrors the A* queue using f 1 as its priority function, while FOCAL comprises a subset of OPEN defined as FOCAL = {n|f 1 (n) ≤ w • f 1min }, where w denotes the sub-optimality factor. Then, FOCAL utilizes the priority function f 2 to order its nodes. Assuming the admissibility of f 1 , we are guaranteed that the returned solution is at most wC * , where C * is the cost of the optimal solution (Pearl and Kim 1982) . Consequently, to reason about the total sub-optimality bound of CBS variants, it would suffice to formulate their high-and low-level planners as instances of focal search each contributing a factor to the total sub-optimality bound. In the following paragraphs, we define the sub-optimality factor contribution by a focal search, detail the total sub-optimality bound of a two-level focal search, and finally show the completeness and sub-optimality bounds of xCBS and xECBS.Definition 1. We say that a sub-optimality factor contributed by a focal-search with admissible f 1 function is a g(s ′ ) = ∞ 29 if g(s ′ ) > g(smin) + c(s, s ′ ) then 30 g(s ′ ) = g(smin) + c(s, s ′ ) 31 if s ′ / ∈ CLOSED then 32 insert s ′ into OPEN 33 return πconstant w, such that for every expanded node N :f 1 (N ) ≤ wC *Let us first define the high-level search as focal search withf 1 = f H 1 = g(n), where g(n) is the cost of the CT 380 node (sum of agents' path costs), and f 2 = f H 2 to be some priority function. Such a focal search contributes a given sub-optimality factor w H . Lemma 1. Let w H , w L be the sub-optimality factor contributed by the high-and low-level focal searches, respec-385 tively. For any w H , w L ≥ 1, the cost of the solution is at most w H w L C * .Proof. Let N be a node in FOCAL of the high-level search. Additionally, Let k be the number of agents (manipulators) each having a returned cost. We denote the returned cost of the i th agent low-level planner as cost(i) and its optimal cost as cost * (i). Lastly, let f L 1,i (s|n) be the i th agent low-level planner's priority function, within a given high-level node n, and let s g,i be the goal state for agent i.N.cost = g(N ) = f H 1 (N ) ≤ w H min n∈OP EN f H 1 (n) 395 = w H min n∈OP EN k i=1 cost(i) = w H min n∈OP EN k i=1 f L 1,i (s g,i |n) ≤ w H k i=1 w L cost * (i) = w H w L C *Lemma 1 implies that proving the bounded sub-optimality of our approach necessitates showing that both the highlevel search and the low-level search are focal searches each 400 contributing a sub-optimality factor.We commence by establishing the bounded suboptimality of the low-level planner xWA * , which leverages past experiences and contributes a factor of w L . To allow for the use of inflated heuristics using a weighted OPEN (Veer-405 apaneni, Kusnur, and Likhachev 2023) list, which is common in manipulation, we expand our analysis to low-level planners with w 1 -admissible (Pearl and Kim 1982) priority function f 1 . Lemma 2. Considering a focal search that employs aw 1 -admissible function f 1 (s) (w 1 ≥ 1) and FOCAL= {s|f 1 (s) ≤ w 2 min s ′ ∈OP EN f 1 (s ′ )}, the contributed sub- optimality factor is w 1 • w 2 .Proof. Let n 0 be a node on an optimal path which resides in OPEN. For every expanded node N :f 1 (N ) ≤ w 2 min n∈OP EN f 1 (n) ≤ w 2 f 1 (n 0 ) = = w 2 (g(n 0 )+w 1 h(n 0 ) ≤ w 2 w 1 (g(n 0 )+h(n 0 ) ≤ w 2 w 1 C *Hence, our remaining task is to show that incorporating experiences in xWA * does not impact the contributed suboptimality factor, nor sacrifices completeness.Lemma 3. Consider a best-first search storing frontier states in an OPEN list. When systematically incorporating successors into OPEN, if additional nodes are introduced along with their associated f values, the properties of completeness and bounded sub-optimality persist.Proof. As we introduce new nodes to OPEN, the original OPEN of weighted A * becomes a subset of the modified OPEN. Moreover, the algorithm maintains its systematic nature, ensuring completeness. Furthermore, we also know that FOCAL will only be populated by nodes from OPEN that are within the specified sub-optimality bound. Consequently, when a goal state is expanded, the solution remains bounded sub-optimal.Theorem 1. xWA * is complete and bounded sub-optimal, contributing w L = w 1 w 2 .Proof. Since xWA * is a focal search, which employs a weighted OPEN (w 1 -admissible f 1 ), the proof follows directly from Lemma 2 and 3We initially assumed that the high-level search is given and that it is bounded sub-optimal contributing factor of w H . In what follows we will discuss the conditions under which the high-level search algorithm presented in Alg. 1 is complete and bounded sub-optimal.To show the completeness of the high-level search of CBS-variants, we turn our attention to the way they impose constraints on the low-level searches. A CBS-variant's highlevel search is complete if, when it creates constraints c 1 and c 2 for resolving a conflict, then there exists no valid solution that invalidates c 1 and c 2 . Otherwise, valid solutions with respect to conflicts will be marked as invalid with respect to constraints. Interestingly, by viewing the high-level completeness of CBS variants in this way, it can be shown that some CBS variants, such as CBS-MP, gain efficiency by sacrificing completeness despite initially claiming otherwise1 .Theorem 2. Our proposed acceleration framework is complete and bounded sub-optimal.Proof. Assuming the use of valid constraints, the focal list on the high-level is complete and bounded sub-optimal with a factor of w H , as shown in (Barer et al. 2014) . From Theorem 1, we have that xWA * is complete and bounded suboptimal by w L . Therefore, Lemma 1 shows a sub-optimality upper bound of w H w L C * for xCBS.Under this structure, we will show that CBS and ECBS are complete and (bounded sub-) optimal and show that xCBS and xECBS are complete and bounded sub-optimal.CBS the suboptimality factor contributed by the low-level search is w L = 1 since it is usually an optimal search (e.g., A*), and the high-level search does not employ a focal-list and prioritizes CT nodes according to their sum-of-costs. CBS is complete since it imposes constraints only on the vertex or edge that was in conflict (Sharon et al. 2015) ; invalidating both constraints leads back to the conflicting configuration found in the first place. Thus, we restate that CBS is complete and optimal.ECBS the suboptimality factor contributed by the lowlevel search is a user-defined constant w L , implemented as a focal-list. In the high-level, an adaptive focal list steers the search but does not contribute an additional sub-optimality factor (i.e., w H = 1) due to its dependence on the lower bound of the low-level searches (Barer et al. 2014) . ECBS is complete since it imposes similar constraints to CBS.xCBS At the high-level, xCBS is identical to CBS in both its CT node prioritization (according to their sum-of-costs) and its constraint generation function. Thus, it contributes a w H = 1 and maintains completeness. At the low level, our xWA* is complete and contributes a sub-optimality factor of w L , as shown in Theorem 1.xECBS At the low level, xWA* contributes a suboptimality factor of w L = w 1 w 2 . At the high-level, the contributed sub-optimality factor is w H = 1 owing to the adaptive bound used in ECBS. Completeness is guaranteed for the same reasons as xCBS. xECBS terminates the addition of experiences at detected collisions with other agents traveling on their previously computed paths. Since ECBS prioritizes low-level search states based on their added conflicts, we refrain from creating new conflicts when reusing experiences.In this light, we have shown that xCBS and xECBS maintain completeness and bounded sub-optimality guarantees while also being accelerated.To evaluate xECBS and xCBS, we created collaborative manipulation tasks with varying numbers of robots, obstacle density, and robot-robot interaction complexity. Each robot in our experiments is a Franka Panda manipulator with 7-505 DOF. The experiments were conducted on an Intel Core i9-12900H with 32GB RAM (5.2GHz).Our experiments focus on testing the scalability of algorithms as well as their applicability for real-world use. We 510 set up 7 scenes, each with 50 planning problems defined by starts q start ∈ Q free and goals q goal ∈ Q free .To test the applicability of algorithms for real-world scenarios, we evaluated algorithms in two sample tasks: shelf rearrangement with 8 arms and bin-picking with 4 arms. For 515 each scene, we randomly sampled 50 start and goal states from a set of task-specific configurations (e.g., pick and place configurations at different bins or positions in between shelves). Given that the robots operate within the same taskspace, these configurations require motion plans with substantial proximity between arms.To shed light on how algorithms scale with the number of arms, we tested their performance in free or lightly cluttered scenes with 2, 4, 6, 8, and 10 arms as shown in Figure 4 . The starts and goals for each agent are in the shared workspace region. In each setup, robots were organized in a circle, and in the cases with 6, 8, and 10 robots, a thin obstacle was placed in the circle to encourage interaction.To show the efficacy of our method, we compare it both to ubiquitous algorithms commonly used to solve the M-RAMP problem, as well as to other algorithms recently applied to M-RAMP.We include PRM and RRT-Connect, which are arguably the most commonly used algorithms for planning in manipulation. For both, the search space is the composite state space Q. We use the OMPL (Sucan, Moll, and Kavraki 2012) implementation of PRM and RRT-Connect. Additionally, we include dRRT* (Shome et al. 2020) , a more recent algorithm applied to M-RAMP that explores the composite state space via transitions on single-agent roadmaps. In our implementation, the singleagent roadmaps contain a minimum of 1500 nodes, with increments of 1000 more being sampled if the roadmap cannot be connected to the start or goal configurations.Search-Based Methods We include PP, CBS, ECBS, and CBS-MP in our comparison, as well as our proposed methods xCBS and xECBS. For all, the single agent planners are weighted A* with a uniform cost for transition and an L 2 joint-angle distance as a heuristic. The heuristic inflation value is 50 and in ECBS and xECBS the sub-optimality bound is set to 1.3. Our implementation of CBS-MP differs slightly from the original in that, here, agents plan on uniformly discretized implicit graphs and not on precomputed roadmaps. This has been done to compare all search algorithms on the same planning representation. All edge transitions on the implicit graphs are said to take one timestep.We are interested in the scalability and solution quality of algorithms. To this end, for each scene, we report the mean and standard deviation for planning time and solution cost across all segments, alongside the success rate of each algorithm in the scene. All algorithms were allocated 60 seconds for planning, after which a plan was considered a failure. The cost is the total motion carried out by the joints, in radians. In our scalability analysis, we also add metrics for the number of collision checks carried out by a subset of the algorithms.All solutions are post-processed with a single pass of a simple incremental shortcutting algorithm. One by one, each agent's solution path is shortcutted without creating new conflicts. Starting from the beginning of the path, the algorithm attempts to replace path segments by linear interpolations while avoiding obstacles and other agents. This standard shortcutting algorithm is often used to refine paths yielded by sampling-based planners.We observe that xECBS solves real-world multi-arm manipulation planning problems faster and with a higher success rate compared to other evaluated methods while keeping solution costs low. Figure 3 (middle) illustrates this result. The figure shows the pairwise relative cost and runtime of all successful algorithms, where the values are computed over jointly successful problems. xECBS demonstrates faster planning speed (values above 100%) while delivering low-cost solutions comparable to those achieved by other conflict-based approaches (values around to 100%).Comprehensive statistics for all runs are provided in the accompanying tables.Our scalability analysis shows that xECBS scales to scenes with many agents better than competing methods, consistently finding solutions for more problems. We note that xCBS improves on CBS in general, however, xECBS offers a much larger boost in performance and is more suitable for planning for multi-arm manipulation. Popular multi-agent motion planning algorithms like CBS and ECBS assume fast single-agent planners, which may not be available in multi-arm manipulation tasks. To address this, we propose to accelerate conflict-based algorithms by reusing online-generated path experiences and demonstrate their benefits in xCBS and xECBS. These adaptations improve performance in multi-arm manipulation tasks while ensuring bounded sub-optimality guarantees. Our experiments demonstrate the proposed method's effectiveness in 605 various multi-arm manipulation tasks with up to 10 arms. We observe that xECBS is particularly effective in realworld scenarios such as pick and place and shelf rearrangement, achieving higher success rates and lower planning times than currently available methods. We have discussed CBS-MP's theoretical guarantees with the authors and reached this conclusion. 
 
 Appendix:  


Decision: The paper investigates a challenging  Multi-Robot-Arm Motion Planning (MRAMP) problem and suggests a variant of the prominent multi-agent pathfinding (MAPF) algorithm, Conflict-Based Search (CBS), tailored to solve MRAMP. Specifically, the authors suggest to leverage the experience (in the form of single-arm paths) gained while solving the current MRAMP problem to speed-up the further search. The resultant variants of CBS/ECBS are proven to return optimal/bounded suboptimal solutions and are shown to notably outperform competitors while solving challenging practically-inspired tasks involving 4 and 8 armed robots (each having 7 degrees of freedom).  

The main strength of the paper is that the authors show how a very challenging high-DOF planning problem can be efficiently tackled. The quality of writing is, generally, clear. The suggested methods are studied both theoretically and empirically. Overall, the paper seems to provide value to the ICAPS community (especially for those who are interested in non-trivial MAPF variants) and is worth including into the program. Addressing the concerns raised by the reviewers (including better explaining the empirical setup and the obtained results, providing more background to the readers who are not familiar with CBS-like planners, etc.) does not require a second round of reviewing and will further increase the quality of the paper.

Reviews: review: strength_weakness: strength_weakness: I would imagine the performance of the proposed approach highly depends on the set of experience being used. But, there seems to be no mention on the effect of different sets nor on suitable criteria for this experience set. 

Related to the above, given the use of experience in this paper seems quite analogous to the use of replay buffers in Reinforcement Learning, it would be useful to elaborate how the use and perhaps effects of experience in planning is similar or differ from the use of replay buffers in Reinforcement Learning.

It would be useful to provide planning time.
questions: questions: Please elaborate on the effect of varying experience set to the performance of the overall algorithm. Specifically, what are the suitable criteria, perhaps in terms of coverage, for the experience set.

I've read the authors' rebuttal and am happy to keep my initial score.
strength_weakness: strength_weakness: This paper has several weaknesses:

- It would be useful to include a bit more intuition in the M-RAMP problem formulation section of the paper, especially for readers who are not experts in this area. The focus on different types of search in the paper should make it accessible to a wide range of planning researchers, but making the ideas in the formal description of the problem clear would be helpful (e.g., properties of the environment, the notion of configurations).

- The notion of conflicts in the CBS description is only briefly mentioned. I wasn't sure if these were simply collision points or if there was a more general notion of collision being used (e.g., overlapping 3D regions, points that are close but not strictly speaking in collision). Perhaps this could be discussed a bit more in the text.

- Conflict based search is described in the paper but the original CBS and ECBS algorithms are not provided. The text seems to suggest that the new high-level and low-level algorithms only replace parts of the original CBS/ECBS algorithms, but this isn't completely clear. It would be useful to more directly indicate what is changed with these algorithms and what is retained from the original CBS/ECBS algorithms.

- In the high-level planning algorithm, when the "Planner" is invoked for each agent in line 3, it wasn't completely clear what planner is being used here. Line 21 seems to invoke the low-level planner but line 3 wasn't clear.

- In the description of the experiments, it would be good to clarify whether they were done in simulation or using real robots (or possibly a combination of both). If they were done in simulation, it would be interesting to know what software was used.

- For the empirical results, it might be useful to break down the planning times for the different experiments, to illustrate the scalability of the approaches. Right now, the planning times seem to be combined in a single runtime value in the tables.
questions: questions: 1) Perhaps the authors could comment on which parts of the original CBS/ECBS algorithms are kept and what their new algorithms replace/change (possibly referring to lines in the provided algorithms)? This wasn't completely clear in the text.

2) Are the experiments performed in simulation or using real robots (or a combination of both)?

3) Were there particular tasks that were particularly challenging for the new algorithms? It's difficult to tell from the combined results. Perhaps the authors could comment on this point.

Post-rebuttal comments: I thank the authors for their answers to my questions, which have been very helpful. I stand by my comments and score.
strength_weakness: strength_weakness: •	Experiments results not clearly explained, 
•	Misplaced figures.
questions: questions: Major: 
•	In Experimental Results, 
-	It is not clear to me what are time ratio and cost ratio. Please provide definitions. 
-	It is not clear to me how to read the middle part of Figure 3. Please elaborate. 
•	For self-rearrangement, please elaborate why
-	xCBS has such a low success rate; 
-	xCBS has a higher time consumption than most other methods; 
-	xECBS has a higher cost than most other methods; 
•	For bin-picking, please elaborate why
-	xCBS has a low success rate; 
-	xCBS has higher time consumption than dRRT*; 
-	xECBS has a higher cost than some algorithms.  

Manor: 
•	Figure 1 is not ever referenced. 
•	In Figure 2, ‘(c) shows two steps: …’ it seems the two steps are shown by (c) and (d), 
•	In Algorithmic Approach Line 335, Figure 2 is placed too far. 
•	In Experiments Line 525, Figure 4 is referenced before Figure 3. Could you rearrange the figures such that the experiment scenarios are introduced first.