Source-linked AI summary
dRRT*: Scalable and Informed Asymptotically-Optimal Multi-Robot Motion Planning
Rahul Shome, Kiril Solovey, Andrew Dobson, Dan Halperin, Kostas E. Bekris
TL;DR
High-dimensional multi-robot planning in shared workspaces is difficult, and explicitly building composite-space roadmaps is impractical. The paper extends dRRT with rewiring and heuristics to obtain asymptotic optimality and informed search. Experiments report that dRRT* solves more challenging instances than ao-dRRT and demonstrate tightly coupled real-world manipulator problems.
Problem
Explicit composite-space roadmaps are impractical for high-dimensional multi-robot planning, and prior dRRT did not provide path-quality guarantees.
Source: §1 · p. 2Method
The method extends dRRT with rewiring over an implicit tensor-product roadmap and heuristics for informed search.
Source: §5.1 · p. 8, §9 · p. 20Results
Heuristic dRRT* solves more challenging instances than baseline ao-dRRT and was demonstrated on tightly coupled real-world manipulator problems.
Source: §9 · p. 21Takeaways & Limitations
dRRT* reports initial solutions on the order of a fraction of a second for most problems, with path quality improving as computation time increases.
Source: §9 · p. 21The theoretical analysis assumes holonomic individual robot systems; shared degrees of freedom provide less guidance and degrade performance.
Source: §7.2 · p. 15, §9 · p. 21
Abstract
from arXiv · showhide
Many exciting robotic applications require multiple robots with many degrees of freedom, such as manipulators, to coordinate their motion in a shared workspace. Discovering high-quality paths in such scenarios can be achieved, in principle, by exploring the composite space of all robots. Sampling-based planners do so by building a roadmap or a tree data structure in the corresponding configuration space and can achieve asymptotic optimality. The hardness of motion planning, however, renders the explicit construction of such structures in the composite space of multiple robots impractical. This work proposes a scalable solution for such coupled multi-robot problems, which provides desirable path-quality guarantees and is also computationally efficient. In particular, the proposed \drrtstar\ is an informed, asymptotically-optimal extension of a prior sampling-based multi-robot motion planner, \drrt. The prior approach introduced the idea of building roadmaps for each robot and implicitly searching the tensor product of these structures in the composite space. This work identifies the conditions for convergence to optimal paths in multi-robot problems, which the prior method was not achieving. Building on this analysis, \drrt\ is first properly adapted so as to achieve the theoretical guarantees and then further extended so as to make use of effective heuristics when searching the composite space of all robots. The case where the various robots share some degrees of freedom is also studied. Evaluation in simulation indicates that the new algorithm, \drrtstar\, converges to high-quality paths quickly and scales to a higher number of robots where various alternatives fail. This work also demonstrates the planner's capability to solve problems involving multiple real-world robotic arms.
1 Introduction
The introduction frames multi-robot planning for high-dimensional systems in shared workspaces as difficult to solve efficiently while preserving path-quality guarantees. It presents dRRT* as an asymptotically optimal, heuristic-guided extension of dRRT, with extensions for shared degrees of freedom and physical-platform demonstrations.
1 Introduction
- Explicitly building an asymptotically optimal roadmap in the composite space is impractical for high-dimensional multi-robot problems because sample and edge requirements grow rapidly.Asymptotically optimal planners maintain on the order of log n edges per sample; the cited example is a 28-dimensional problem.Source: §1 · p. 2
- Prior dRRT implicitly searches the tensor product of individual-robot roadmaps and finds high-dimensional solutions, but provides no path-quality guarantees.The proposed analysis shows the implicit structure can contain an optimal path, while rewiring is needed for the search to converge to minimum-cost paths.Source: §1 · p. 2
- dRRT* uses heuristics to improve computational efficiency while retaining asymptotic optimality across a broad range of path-cost functions.The convergence claim applies to a broad range of cost functions over paths in the implicit graph.Source: §1 · pp. 2–3
- The manuscript extends the analysis to an additional distance metric and adapts the method for systems with shared degrees of freedom.The shared-DoF case is demonstrated in related work and treated as an extension of the method.Source: §1 · p. 3
- The experimental section adds the new methods and demonstrations on physical platforms.The introduction identifies physical-platform demonstrations among the manuscript extensions.Source: §1 · p. 3
2 Prior Work
Prior multi-robot planning methods trade search efficiency against completeness and path-quality guarantees. Implicit tensor-product roadmaps and dRRT address some scaling challenges, while tight coordination remains difficult for alternatives such as M*; dRRT* builds on this line of work.
2 Prior Work
- Decoupled methods reduce search by solving robot subproblems separately, but typically lack completeness and optimality guarantees; centralized methods offer stronger guarantees but tend to be slower.Some guaranteed hybrid approaches are limited to discrete domains, while collision-avoidance and control methods can scale but lack path-quality guarantees.Source: §2 · p. 3
- Composite-space sampling can handle only a small number of robots, while tensor-product roadmaps represent joint configuration structure using individual-robot roadmaps.The tensor-product roadmap approach is limited by the exponential size of the resulting roadmap.Source: §2 · pp. 3–4
- M* searches only part of the tensor-product roadmap, but becomes less effective as simultaneous coordination increases because it must consider many neighbors.The cited limitation concerns tightly coordinated robot motion.Source: §2 · p. 4
- dRRT explores an implicit tensor product and was reported at least ten times faster than existing algorithms on most tested scenarios; dRRT* extends this approach with path-quality guarantees.The dRRT experiments included scenarios with up to 60 DoFs; the extension is described as asymptotically optimal and efficient.Source: §2 · p. 4
3 Problem Setup and Notation
The problem setup represents coordinated robot motion in a composite configuration space and seeks collision-free trajectories between start and target configurations. It considers robust feasibility and three trajectory cost functions.
3 Problem Setup and Notation
- Composite configurations combine one configuration per robot, while composite free space excludes obstacle collisions and pairwise robot collisions.The composite configuration space is the Cartesian product of the robots’ individual configuration spaces.Source: §3 · p. 4
- A composite trajectory is a tuple of individual robot trajectories, and the paper considers costs based on summed lengths, maximum path length, or composite Euclidean arc length.The three cost functions are the sum of path lengths, the maximum individual path length, and the arc length of the composite trajectory.Source: §3 · p. 4
- An RFCMP query seeks a robustly feasible composite trajectory from start S to target T, subject to a fixed clearance condition.The condition requires a positive δ for configurations along the trajectory relative to the composite obstacle space.Source: §3 · pp. 4–5
- The objective includes asymptotic optimality: as computation progresses, the returned path cost approaches the optimal cost with probability tending to one.The definition states the guarantee for any ε > 0.Source: §3 · p. 5
4 Algorithmic Foundations
The foundations use individual robot roadmaps to represent a composite roadmap implicitly, then search it with dRRT rather than constructing it explicitly.
4.1 Tensor-product roadmap
- The tensor-product roadmap combines individual roadmaps: each composite vertex is a tuple of roadmap vertices, and its edges reflect constituent roadmap edges.This structure captures simultaneous robot placements and motions without requiring an explicit composite-space roadmap.Source: §4.1 · p. 5
- Individual roadmap edges avoid obstacles, but their simultaneous combination can still permit collisions between robots.Thus, composite edges require additional robot-robot collision checking.Source: §4.1 · p. 5
- The product roadmap grows exponentially in vertex count, and its neighborhood size is the product of the constituent neighborhood sizes, making explicit representation generally costly.Using the smaller individual roadmaps to construct the product online is computationally beneficial.Source: §4.2 · p. 5, §4.1 · p. 5
4.2 Discrete RRT
- dRRT grows a tree from the start through the implicit roadmap, using random samples, nearest-tree nodes, and an oracle to select a neighboring product node.The oracle can choose a neighbor without explicitly representing the product roadmap.Source: §4.2 · p. 6
- The direction oracle chooses the product-roadmap neighbor most aligned with the random sample, using information from constituent roadmap neighbors.This avoids traversing the potentially exponential set of product-graph neighbors.Source: §4.2 · p. 6
- dRRT has a Voronoi-bias property: a sample in the intersection of a vertex’s Voronoi and directional regions can generate a specified outgoing neighbor.The relevant sampling volume is Vol(V) = Vor(V) ∩ Vor′(V).Source: §4.2 · p. 6
5 Asymptotically Optimal Discrete RRT
The section adapts dRRT with rewiring for asymptotic optimality, then adds informed search strategies in dRRT* to improve computational efficiency while retaining that guarantee.
5 Asymptotically Optimal Discrete RRT
- ao-dRRT is an uninformed asymptotically optimal dRRT variant that uses a simple rewiring scheme.The section contrasts this simpler version with the more computationally efficient dRRT*.Source: §5 · p. 7, §5.1 · p. 7
- When dRRT’s expansion reaches a node already in the tree, ao-dRRT checks whether rewiring it yields a lower-cost path.The rewiring mechanism refines paths in the tree and reduces costs to reach particular nodes.Source: §5 · p. 7, §5.1 · p. 8
- dRRT* preserves asymptotic optimality while adding branch-and-bound pruning, greedy child propagation, and heuristic guidance to ao-dRRT.Pruning is applied after a solution is found.Source: §5.1 · pp. 8–9
- dRRT* uses shortest paths on constituent roadmaps as heuristics for guiding the tree toward the goal.If the individual shortest paths do not cause robot interactions, their combination is a solution; otherwise, paths may need local deviations near interactions.Source: §5.1 · p. 8
- During guided expansion, dRRT* selects each constituent roadmap’s neighbor with the best heuristic estimate; during exploration, it selects a random neighbor.The informed expansion procedure switches between guided and exploratory behaviors.Source: §5.1 · p. 9
- A node that makes heuristic progress toward the goal is promoted for selection in the next iteration; collision-free individual shortest paths are then greedily attempted first.The paper reports that this behavior proves effective in practice.Source: §5.1 · p. 9
6 Analysis
The analysis establishes asymptotic optimality by showing that the tensor-product roadmap contains near-optimal paths and that the dRRT∗ search eventually discovers them. It extends the convergence argument to Euclidean arc length and linear combinations of arc lengths.
6 Analysis
- The asymptotic-optimality argument combines convergence of the implicit roadmap with eventual discovery of its shortest path by online search.Together, these results establish asymptotic optimality for dRRT∗ and ao-dRRT.Source: §6 · p. 10
6.1 Optimal Convergence of ˆG
- With a suitable connection radius, the tensor-product graph contains asymptotically optimal paths for multi-robot planning.The analysis assumes Euclidean configuration spaces and robust paths; it notes that non-Euclidean and non-holonomic systems require additional rigor.Source: §6.1 · p. 10, §6 · p. 10
6.1.1 Optimal Convergence for a Linear combination of Euclidean arc lengths
- For linear combinations of Euclidean arc lengths, reparameterization preserves the cost bound while avoiding robot–robot collisions.The reparameterization argument establishes the required cost relation for this class of cost functions.Source: §6.1.1 · pp. 11–12
6.1.2 Optimal Convergence for Euclidean arc length
- Equal-measure path partitions let the convergence argument extend to Euclidean arc length.The analysis assumes continuous, bounded-variation coordinate functions and rectifiable paths.Source: §6.1.2 · pp. 12–13
6.2 Asymptotic Optimality of dRRT∗
- With positive transition probabilities along the optimal path, the absorbing-chain argument shows dRRT∗ eventually expands that path in its search tree.For dRRT∗, random neighborhood selection supplies a positive transition probability to the next state.Source: §6.2 · p. 14
7 Extension to Shared Degrees of Freedom
The extension adapts dRRT∗ to robots with shared degrees of freedom by decomposing their configuration space and searching two tensor-product roadmaps. Its analysis carries over robustness and asymptotic-optimality arguments, while the shared-DoF heuristic is less informed.
7 Extension to Shared Degrees of Freedom
- The extension targets high-dimensional systems such as humanoid robots with shared degrees of freedom, grouping the shared DoF with one arm.Shared DoF can represent a torso or mobile base.Source: §7 · p. 14
7.1 Problem Setup and Notation
- The setup combines left-shared and right-shared roadmaps with arm-only roadmaps to form two tensor-product roadmaps.Shared-arm roadmap edges avoid static-geometry and self-collisions; arm-only roadmaps avoid arm self-collisions but do not account for static geometry.Source: §7.1 · pp. 14–15, Figure 8 · p. 15
7.2 Methodology
- The method simultaneously explores both tensor-product roadmaps with two trees; this supports faster convergence than RRT* in the composite space and greater scalability than PRM∗.The shared-DoF dependence makes the heuristic for the arm-only roadmap less informed, degrading performance relative to independent arms, although the method remains faster than composite-space planning.Source: §7.2 · p. 15
7.3 Analysis
- Robustness in the composite space implies robustness in the decomposed spaces, supporting the asymptotic-optimality argument; Euclidean cost is more applicable under shared-DoF coupling.Source: §7.3 · p. 16
8 Experimental Validation
Experiments assess practical convergence, disk-robot scalability, and dual-arm manipulation. The reported benefits persist across the cost metrics used for systems with and without shared degrees of freedom.
8.1 Tests on Systems without Shared DoF
- dRRT* converged to the optimal path over the implicit tensor roadmap, comparable to the explicit roadmap, and converged faster than ao-dRRT.It also quickly found an initial solution of high quality.Source: §8.1 · p. 16, Figure 10 · p. 18
- At N ≥500, dRRT* maintained a 100% success ratio while implicit A* always failed; RRT* failed within 100,000 iterations, and larger roadmaps improved path quality.The dual-arm manipulator test involved two 7-dimensional arms.Source: §8.1 · p. 17
8.2 Tests on Systems with Shared DoF
- All algorithms succeeded on the Motoman tabletop benchmark; smaller dRRT* roadmaps searched and found initial solutions faster than RRT*, while dRRT* converged to better solutions.Figure 15 reports initial solution times and average solution costs over time.Source: §8.2 · p. 18, Figure 15 · p. 20
- On the Motoman shelf benchmark, RRT* had a poor success ratio, while da-dRRT* achieved lower solution costs than average PRM* and RRT*; larger roadmaps slowed its convergence.PRM* found initial solutions fastest when only online cost was considered.Source: §8.2 · p. 18
- For mobile Baxter, RRT* found no solution and PRM* had very low success; da-dRRT* solved the problem at n = 1000 and beat successful PRM* instances in initial and converged costs.The benchmark required navigating a cramped, walled room while carrying long objects to a shelf.Source: §8.2 · pp. 18–19
8.1 Tests on Systems without Shared DoF
- R = 10: dRRT* found solutions, while implicit A* failed even at 3 robots, composite-space RRT* failed for R ≥6, and dRRT success declined from R ≥4.Figure 11 compares success and relative solution cost for R = 3 to 10 robots.Source: §8.1 · p. 17, Figure 11 · p. 19
8.3 Real world experiments
- Real-system demonstrations used dRRT* for four-arm pre-grasp planning and for coordinated arm movements around a pole; the offline solutions were replayed open-loop.The pole setup required the arms to approach at alternating heights, swap heights, and return to their start states.Source: §8.3 · pp. 19–20
9 Discussion
The discussion presents asymptotic optimality over implicit multi-robot roadmaps and informed search as the basis of the proposed planner. It highlights practical results while noting performance and theoretical scope boundaries.
9 Discussion
- ao-dRRT achieves asymptotic optimality by expanding a spanning tree over an implicit tensor-product roadmap and using a simple rewiring scheme.Source: §9 · p. 20
- dRRT* uses heuristics to focus composite-space search, and da-dRRT* extends the method to systems with shared degrees of freedom.Source: §9 · p. 20
- Heuristic guidance lets dRRT* solve more challenging instances than ao-dRRT, and the approach is demonstrated on highly coupled real-world manipulator problems.Source: §9 · p. 21
- Initial solutions often arrive within a fraction of a second, and solution quality improves with more computation; shared-DoF problems provide less guidance and degrade performance.Source: §9 · p. 21
- The theoretical analysis assumes holonomic individual systems; extending it to non-holonomic systems is left for future work.Source: §9 · p. 21