PaperlayerView exact revision on arXiv

Source-linked AI summary

PushAround: Collaborative Path Clearing via Physics-Informed Hybrid Search

Zili Tang, Zongyuan Li, Zishao Qiao, Meng Guo

arXiv:2610.35062v1cs.RO

TL;DR

Large vehicles can be blocked by movable obstacles, and NAMO methods often omit physical constraints needed for executable plans. PushAround couples W-clearance gap reasoning with physics-evaluated collaborative pushing; it reports higher success and lower combined planning-and-execution time than evaluated baselines, while finite sampling does not guarantee optimality.

  • Problem

    Many NAMO approaches abstract obstacle displacements while neglecting robot dimensions, object mass, contact geometry, forces, and dynamics, which can produce physically unrealizable plans.

    Source: §I · p. 1

  • Method

    PushAround couples W-clearance connectivity and frontier-gap reasoning with direct or recursive pushing candidates evaluated through physics-informed hybrid search.

    Source: D. Problem Statement · p. 2, C. Pushing Mode Generation and… · p. 4, 3) Node Expansion with Parallel… · p. 5

  • Results

    PushAround achieves a 97.5% success rate and the lowest combined planning-and-execution time among the evaluated Scenario 1 baseline variants.

    Source: 5) Comparisons · p. 7

  • Takeaways & Limitations

    The framework demonstrates collaborative corridor clearing with physics-informed verification, including hardware execution with feedback replanning.

    Source: §V · p. 8

    Finite sampling does not guarantee optimality, and the clearance duration excludes vehicle traversal.

    Source: D. Problem Statement · p. 3

Abstract

from arXiv · show

Large vehicles in cluttered environments are often blocked by movable obstacles, motivating mobile robot teams to clear traversable corridors. Navigation Among Movable Obstacles (NAMO) approaches often abstract obstacle displacements while neglecting robot dimensions, obstacle mass, contact geometry and forces, yielding physically infeasible plans. PushAround is a physics-informed hybrid search that couples geometric connectivity reasoning with short-horizon simulation to construct executable clearing plans. Repeated W-clearance connectivity graph (WCCG) queries expose frontier gaps requiring widening and rank them by estimated downstream costs. The search generates direct or recursive pushing candidates, selecting obstacles, directions, contacts and forces, and admits physics-evaluated candidates. Numerical experiments validate WCCG against standard connectivity checks and demonstrate scaling to denser clutter and teams of up to four robots, with robustness to simulated execution-side physical-parameter mismatch.

I. INTRODUCTION

Movable obstacles block large vehicles, while many NAMO approaches omit physical constraints and collaborative pushing introduces coupled motions. PushAround combines geometric gap reasoning with physics-informed pushing search to plan corridor clearing.

1) Navigation Among Movable Obstacles:

  • NAMO plans obstacle displacements, but many formulations omit robot geometry, object mass, contact geometry, forces, and dynamics, risking physically unrealizable plans.Conventional planners assume static obstacles and fail when routes are blocked.Source: §I · p. 1, 1) Navigation Among Movable Obstacles · p. 1

2) Collaborative Pushing:

  • Collaborative pushing can provide an alternative when large robots cannot reach obstacle boundaries or small robots lack force, but simultaneous pushes can trigger coupled obstacle motions.Prior collaborative-pushing studies focus on a prescribed object rather than multi-object corridor clearing.Source: §I · p. 1, 2) Collaborative Pushing · p. 1

3) Physics-Informed Planning:

  • Physics-informed planning has explored dynamics, contact reasoning, simulation, and physical priors, typically for a prescribed target or a small set of objects –.Corridor clearing instead requires selecting which of many movable obstacles to rearrange.Source: 3) Physics-Informed Planning · p. 1

B. Our Method:

  • PushAround jointly chooses obstacles and pushing modes, combining W-clearance connectivity, frontier-gap ranking, constrained mode generation, and physics-evaluated transitions.Its modes specify contacts, directions, and forces, while execution feedback updates connectivity and can trigger replanning.Source: B. Our Method · pp. 1–2
  • The paper presents a unified framework for physics-verified collaborative path clearing and reports empirical gains in feasibility, efficiency, and scalability over evaluated baselines, with robustness to execution-side physics mismatch.The reported scope includes simulation and hardware experiments.Source: Figure 1 · p. 1, B. Our Method · p. 2, Figure 2 · p. 2

II. PROBLEM DESCRIPTION

The problem is set in a bounded planar workspace with immovable structures, movable rigid obstacles, and a cooperative robot team. The team must rearrange obstacles so a vehicle of width W has a collision-free route, using pushing modes feasible under modeled contact and actuation constraints.

A. Workspace and Robots

  • The workspace contains immovable structures and movable rigid polygons with mass, inertia, frictional parameters, and pose; N rigid-body robots operate cooperatively.The free-space definition follows from the workspace and occupied obstacle and robot regions.Source: A. Workspace and Robots · p. 2

B. External Vehicle and Clearance Goal

  • The robots must rearrange obstacles so the external vehicle, enclosed by a radius-W/2 disk, can travel from its start to goal with W-clearance.The clearance condition certifies a collision-free centerline path for any vehicle footprint contained in that disk.Source: B. External Vehicle and Clearance Goal · p. 2

C. Collaborative Pushing Modes

  • A collaborative pushing mode assigns ordered contact points to robots and stacks their planar contact forces in the obstacle body frame.Admissible forces obey robot pushing limits, robot–object friction, and unilateral contact; feasible modes also require reachable contacts and feasible pre-contact configurations.Source: C. Collaborative Pushing Modes · p. 2

D. Problem Statement

The planning objective is a hybrid schedule of obstacle pushes that yields a W-feasible vehicle path. PushAround couples obstacle choice and pushing-mode decisions, using W-clearance connectivity and simulation-informed costs while acknowledging that finite sampling does not guarantee optimality.

D. Problem Statement

  • The goal is a hybrid schedule of obstacle, direction, and pushing-mode choices that reconfigures obstacles until the external vehicle has a W-feasible path.The objective couples obstacle selection, mode generation, and switching, adding robot-team contacts and forces to NAMO-style rearrangements,.Source: D. Problem Statement · pp. 2–3
  • Finite sampling means PIHS does not guarantee an optimal schedule; its clearance duration excludes vehicle traversal, while manipulation cost is simulation-estimated.The constraints enforce valid pushing transitions, and vehicle traversal enters through the terminal W-clearance condition.Source: D. Problem Statement · p. 3

III. PROPOSED SOLUTION

  • PushAround identifies and prioritizes blocking gaps, generates physically feasible collaborative pushing modes, and integrates them in simulation-in-the-loop search and online execution.Its WCCG supports repeated W-clearance connectivity queries without a grid-resolution parameter.Source: §III · p. 3, A. W–Clearance Connectivity Graph · p. 3

A. W–Clearance Connectivity Graph

  • The W-clearance connectivity graph encodes obstacle adjacencies under vehicle-width clearance, reducing route feasibility to whether a W-width corridor connects the start and goal.The graph is built from obstacle geometry for repeated connectivity queries.Source: A. W–Clearance Connectivity Graph · p. 3

1) Graph Construction:

The WCCG represents clearance-relevant boundaries and narrow gaps as a graph whose connectivity supports route-feasibility queries. When a route is blocked, frontier gaps are extracted and ranked by estimated costs to guide clearing.

1) Graph Construction:

  • The WCCG decomposes clearance-relevant boundaries into convex components or segments, creates centroid nodes, and links nearby components through bridge nodes and gap-width-annotated edges.Gaps narrower than W are marked as potential bottlenecks.Source: 1) Graph Construction · p. 3

2) Connectivity Criterion:

  • The connectivity criterion uses connected planar faces induced by the embedded WCCG, with obstacle components and bottleneck edges separating regions.A frontier-tracing procedure follows the encountered frontier loop to find a valid exit or return a blocking cycle.Source: 2) Connectivity Criterion · p. 3

B. Ranking of Frontier Gaps

  • When connectivity fails, blocking gaps on the reachable frontier are ranked by predicted downstream cost and passed to hybrid search as local clearance targets.The ranking links gap selection to the pushing module.Source: B. Ranking of Frontier Gaps · p. 3

1) Frontier Extraction and Candidate Gaps:

  • A BugPlanner query returns a separating frontier loop whose bridge–bridge edges define first-hop candidate gaps, represented by boundary points, width, and potentially movable adjacent obstacles.Each candidate gap is narrower than W.Source: 1) Frontier Extraction and Candidate… · p. 3

2) Evaluation for Immediate Cost:

  • Immediate gap cost combines robot travel to the gap with the effort required to widen it, using weighted transition, direct-pushing, and recursive-pushing terms.The weights λt and λp are positive.Source: 2) Evaluation for Immediate Cost · p. 3

3) Long-term Cost w.r.t. Goal:

The planner estimates downstream costs by virtually crossing frontier gaps and prioritizes promising gap sequences, while pushing strategies pair a selected obstacle and direction with a feasible mode checked by rollout or approximation.

3) Long-term Cost w.r.t. Goal:

  • Gap-lookahead virtually crosses gaps, recomputes frontiers, and ranks predicted cost-to-connect in ascending order so promising gaps are expanded first.Its bounded-width, bounded-depth A*-style presearch estimates a bottleneck sequence without moving obstacles; a goal-distance heuristic prioritizes gaps closer to the goal.Source: 3) Long-term Cost w.r.t. Goal · pp. 3–4
  • Recursive pushing first clears movable blockers in the swept region, then returns to the root gap-opening task.Direct pushing moves a gap-side blocker along a gap-opening direction.Source: Figure 4 · p. 4

C. Pushing Mode Generation and Evaluation

  • For each selected frontier gap, candidate strategies specify an obstacle, short-horizon pushing direction, and mode, with wrench feasibility screening contact configurations before motion validation.Forces certify feasibility rather than serving as hardware setpoints; candidate motion is checked by rollout or quick-pass approximation.Source: C. Pushing Mode Generation and… · p. 4

1) Direct and Recursive Pushing Tasks:

The planner samples direct pushes toward widening a frontier gap and recursively clears blockers when a push’s swept region is obstructed. It generates contact-and-force modes and evaluates candidate transitions through simulation or a less accurate quick-pass.

1) Direct and Recursive Pushing Tasks:

  • For direct pushing, the planner samples candidate velocities for either movable obstacle adjacent to the gap, biasing them toward gap enlargement and including angular components for local geometry.When a direct push’s swept region intersects movable blockers, recursive tasks clear outer blockers away from that region and the reference gap sequence before returning toward the root gap-opening task.Source: 1) Direct and Recursive Pushing Tasks · p. 4

2) Pushing Mode Generation:

  • A pushing mode is generated for each candidate direction and obstacle by selecting reachable contacts and testing force feasibility across direction perturbations.Contacts must have collision-free pre-contact poses; greedy replacement refines contact tuples, with bounded backtracking and a reduced-team fallback if a full-team assignment fails.Source: 2) Pushing Mode Generation · p. 4
  • The optimized contact tuple determines the forces, and admissible modes are retained for subsequent tasks through a mode cache.A full-team mode is preferred; a reduced-team mode receives a ranking penalty, and the inactive robot returns for the next task.Source: 2) Pushing Mode Generation · p. 4

3) Pushing Strategy Evaluation:

  • A candidate strategy is accepted after rollout if robots reach pre-contact poses, maintain stable contact, and move the obstacle above threshold.Joint rollout captures contact-induced interactions among bodies; quick-pass can instead approximate a transition using a cached rollout or mechanically feasible reference trajectory, subject to compatibility, reachability, and swept-clearance checks.Source: 3) Pushing Strategy Evaluation · p. 4
  • Quick-pass reduces online simulation effort by trading away prediction accuracy.Parallel simulation evaluates sampled push tasks and returns updated states for search expansion.Source: 3) Pushing Strategy Evaluation · p. 5, Figure 6 · p. 5

D. Physics-Informed Hybrid Search

PIHS searches partial clearing schedules, ranking gaps and evaluating candidate pushes to expand the search tree until a W-clear path is found. Its finite sampling and potentially non-admissible priority do not guarantee completeness or optimality.

D. Physics-Informed Hybrid Search

  • PIHS selects blocking gaps and evaluates pushing strategies using short-horizon simulation or optional quick-pass, with finite sampling providing no global optimality or completeness guarantee.The evaluated clearance cost of a partial schedule supplies its accumulated-cost term in node priority.Source: D. Physics-Informed Hybrid Search · p. 5

1) Tree and Initialization:

  • Tree nodes contain the state and partial schedule, while frontier gaps are ranked and execution cost is accumulated from the root.The algorithm initializes the queue with the initial state and an empty schedule.Source: 1) Tree and Initialization · p. 5

2) Node Selection:

  • Node selection prioritizes partial schedules using accumulated execution cost and an estimate of minimum remaining cost over unexplored gaps.The heuristic need not be admissible, so this priority provides no A* optimality guarantee.Source: 2) Node Selection · p. 5

3) Node Expansion with Parallel Simulation:

  • Expansion derives a predicted gap sequence, samples directions, optimizes modes, and evaluates candidates; successful pushes create child states and add duration plus weighted control effort to cumulative cost.Candidates include direct pushes and recursive pushes of outer blockers, and the parent is requeued for later samples.Source: 3) Node Expansion with Parallel… · p. 5

4) Termination:

  • The search terminates when a node admits a W-clear path, returning a schedule that satisfies nominal clearance and evaluated pushing transitions.Vehicle traversal follows clearing, and the returned schedule need not minimize realized clearance cost.Source: 4) Termination · p. 5

1) Execution and Online Adaptation:

Execution uses feedback to update connectivity and replan when pushes fail or invalidate the path. The paper also describes computational costs and evaluates PIHS in simulation and hardware, with representative alignment plots for two scenarios.

1) Execution and Online Adaptation:

  • During receding-horizon execution, robots reach assigned contacts and follow planned directions while feedback tracks object motion and updates the state and WCCG after each push.Failed contacts, stalled pushing, or invalidated connectivity trigger replanning from the latest observed state.Source: 1) Execution and Online Adaptation · p. 5

2) Computational Complexity:

  • Physics validation dominates node-expansion cost, which grows with evaluated candidates; parallel workers reduce rollout wall time.Mode generation uses at most N|A| single-contact substitutions per greedy sweep rather than |A|^N joint tuples, with bounded refinement and backtracking budgets.Source: 2) Computational Complexity · p. 5

IV. EXPERIMENTS

  • PIHS is evaluated in simulation and hardware for connectivity, clearing performance, scalability, and robustness to execution-side physical mismatch.The evaluation uses Python3 and PyBullet on an Intel i9-14900KF with an RTX 4080.Source: §IV · p. 5
  • Figure 7 pairs simulated path-clearing snapshots with WCCG overlays for two scenarios, showing the reachable W-clearance region expanding until the goal connects.The start face is marked in blue in the overlays.Source: Figure 7 · p. 6
  • Table I concerns WCCG connectivity validation and mean runtime, while Table II covers performance comparison and ablations on Scenario 1 over 40 randomized trials.For DFS-WCCG, P T and #Sims are reported only as lower bounds and are not comparable.Source: Table I · p. 6, Table II · p. 6, §IV · p. 6

A. Numerical Simulations

Across simulation studies, PushAround combines high clearing success with fast execution, while WCCG matches the continuous connectivity reference and targeted ablations expose the value of key search mechanisms.

1) Setup and Configuration:

  • Trials use two robots and 10–15 movable obstacles, with a success defined as reaching the goal through a W-clear path.Scenario 1 uses ten movables and 40 trials; Scenario 2 has 14 movables.Source: 1) Setup and Configuration · p. 6

2) Results:

  • Across 40 Scenario 1 trials, PushAround succeeds in 97.5%, averaging 10.3 s planning, 28.6 s execution, and 6.0 pushes per successful trial.In Scenario 2 with 14 obstacles, it plans in 11.2 s and executes in 61.3 s.Source: 2) Results · p. 6

3) WCCG Connectivity Validation:

  • WCCG matches the continuous reference on all 300 scenes and answers queries in 1.07 ms, versus 1.36 ms for CC and 243 ms for FR.CC and FR disagree in four cases, all near narrow contacts and rasterization-related.Source: 3) WCCG Connectivity Validation · p. 6

4) Ablation Studies:

  • Removing gap-lookahead or reinsertion drops success by more than ten percentage points; removing quick-pass lowers success to 90.0%.The ablations mainly change simulation-validation load rather than plan length; removing mode-cache increases simulations.Source: 4) Ablation Studies · pp. 6–7, 2) Results · p. 6

5) Comparisons:

  • 97.5% success and 38.9 s combined planning-and-execution time make PushAround the strongest evaluated Scenario 1 baseline.The comparison uses 40 randomized trials under a shared W-clearance criterion and execution simulator.Source: 5) Comparisons · p. 7

6) Scalability and Robustness Analysis:

PushAround maintains clearing success as obstacle density and team size increase, and remains effective under simulated execution-side parameter mismatch. Hardware trials demonstrate corridor clearing with state-feedback replanning.

6) Scalability and Robustness Analysis:

  • 100% success is maintained for 15–45 obstacles with two robots, and all ten trials succeed for teams of two, three, and four at 30 obstacles.At 45 obstacles, none of the evaluated baselines succeeds, while the no-recursion ablation solves 7/10 trials.Source: Figure 9 · p. 7, 6) Scalability and Robustness Analysis · p. 7
  • Under ±40% perturbations to four parameter families, PushAround achieves 97.5% success, versus 32.5% for SL-Push (sim) and 57.5% for DFS-WCCG.The planner retains nominal physics while execution varies one parameter family at a time; joint errors are untested.Source: 6) Scalability and Robustness Analysis · p. 7

1) System Description:

  • Hardware tests use two velocity-controlled UGVs and six cardboard boxes in a 5 × 6 m workspace, with optimized forces used only for feasibility evaluation.Motion-capture poses are streamed to PyBullet in real time.Source: 1) System Description · p. 7

2) Results:

  • Across two representative real-world runs, hardware Scenario 1 uses PIHS to plan a four-task schedule in 6.5 s; in Scenario 2, PushAround succeeds in 8/10 trials, averaging 5.2 pushes and 11.4 s of planning.In the illustrated run, execution takes 77.1 ± 15.9 s (mean ± standard deviation); online replanning handles deviations due to force limits, drift and wheel slip.Source: 2) Results · pp. 7–8

V. CONCLUSION

  • PushAround jointly plans obstacle selection, contacts, and forces, while future work targets obstacle-state estimation without external sensing or known masses.The conclusion reports simulation studies of density, team size, and execution-side mismatch, plus hardware path clearing with state-feedback replanning.Source: §V · p. 8

Related papers

Loading 2610.35062v1…