DaSH

Overview

Decomposable State Space Hypergraph (DaSH) is a hypergraph-based multi-robot task and motion planning algorithm that uses a directed hypergraph to manage a decomposed state space representation. Graph-based task and motion planning algorithms rely on a composite planning space whose size scales exponentially with the number of planning entities, whereas the hypergraph representation scales linearly, as shown in the figure below. For a problem with 2 robots and 4 objects, the composite (graph) representation of the task space contains 21 vertices and 120/60 directed/bidirectional edges, while the decoupled (hypergraph) representation of the same problem contains only 14 vertices and 24/12 directed/bidirectional hyperarcs.

Framework

DaSH begins by constructing a task space hypergraph that captures the composition and decomposition of the planning spaces, as shown below. Its hyperarcs merge and split planning spaces according to the defined actions (e.g., pick/place and handoff) in the abstract state space (a), and motion planning is performed within these confined planning spaces (b). Using this motion representation, a hypergraph query is performed to find a path from the source to the sink (c).

Experiment Results

The experiments are performed on an object rearrangement problem in which objects must be transported to specific locations using pick/place and handover actions. As shown below, the greedy-query variant of DaSH (Greedy) outperforms the composite multi-robot planning method Synchronized Multi-Arm RearrangemenT (SMART), scaling to more than three times as many objects.

LazyDaSH

Overview

Lazy-DaSH is an extension of DaSH that drastically improves computational efficiency through a hierarchical structure and lazy motion validation. A high-level task planning layer identifies the planning spaces required for task completion, and motion feasibility is validated lazily only within those spaces. This makes representation construction much cheaper, yielding an order-of-magnitude faster planning time and scaling to more than twice as many robots and objects.

Framework

The figure above illustrates the hierarchical structure of Lazy-DaSH, showing two manipulators (R1 and R2) rearranging an object (O1). The task query phase and the task constraint feedback scheme, which distinguish it from DaSH, are highlighted with red lines. The task planning layer first builds a task space representation and uses it to perform a task query, narrowing down the candidate motion planning spaces. The resulting plan is validated by task constraint detection, which preemptively identifies task-level constraints and uses them to refine the task space representation or trigger a new query. The motion planning layer then constructs a lazy roadmap within only these candidate spaces and runs a motion query to check whether feasible motions exist. Finally, the conflict resolution layer detects collisions across the decoupled planning spaces and resolves them by constructing a composite space.

Experiment

Double Shelf: objects must be passed to the other side of the shelf in the correct order.
Sort: robots transport objects to their corresponding bins.
Stocking: a non-monotonic scenario where objects must be temporarily displaced to arrange them in the correct order.
Wall: walls obstruct the robots' interactions, which must be identified to coordinate them.

Lazy-DaSH is validated in four different object rearrangement scenarios, shown above. The results demonstrate that the method scales to more than double the number of robots and objects, and handles a wider variety of scenarios, such as non-monotonic tasks and high degrees of object geometric constraints, compared to DaSH.

Results

Workspace Guided-DaSH

DaSH has also been extended to the problem of multi-robot motion planning in congested environments with narrow passages, a problem without an easily decomposable task space. For details, see Multi-Agent Guided Planning.

Publications

Updated: