Next-generation autonomous mobile robots (AMRs)—including smart retail shopping carts, mobile clinical pushchairs, and airport luggage trolleys—must route continuously through human-shared public spaces. Unlike isolated industrial warehouses, public service environments present unique multi-agent challenges: space is constrained by orthogonal shelving fixtures, corridors are frequently single-file, and human pedestrians move stochastically with browsing and loitering behaviors.
This research proposes Distributed Dynamic Route Optimization (D²RO) powered by Socially-Weighted Distributed Graph Optimization (SW-DGO). Rather than treating navigation as isolated reactive avoidance or purely local search, SW-DGO establishes a time-varying graph-cost field $C_i(u, v, t)$ shared across peer agents and solved via incremental D* Lite heuristic graph repair over V2V mesh telemetry.
4 Core Research Motivations & Technical Bottlenecks
- The ORCA / APF Trap (Local Potential Minima): Near $90^\circ$ shelf corners, end-caps, and U-bays, continuous collision avoidance algorithms (ORCA, APF) suffer from canceling force vectors ($\|\mathbf{F}_{\text{net}}\| \to 0$), stalling agents near pedestrians.
- The $A^*$ Flaw (Social Blindness): Static shortest-path planners treat pedestrians as non-existent or point obstacles, commanding carts to drive straight through crowds and causing severe personal space violations ($d < 0.8\text{ m}$).
- Symmetrical Live-Locks in Single-File Corridors: In narrow passages (e.g., $2.1\text{ m}$ supermarket grocery aisles), physical clearances prevent two carts from passing side-by-side. Opposing carts entering simultaneously produce permanent live-locks with reactive planners.
- Information Isolation & Delayed Backtracking: Decoupled agents with myopic local sensing ($R_s = 7.2\text{ m}$) do not learn of downstream aisle blockages until reaching the congested mouth, causing severe makespan inflation.
Mathematical Formulation
SW-DGO formalizes a four-term edge traversal cost function subject to a directional corridor reservation constraint:
\[C_i(u, v, t) = w_D \cdot C_{\text{geom}}(u, v) + w_M \cdot C_{\text{mesh}}(u, v, t) + w_H \cdot C_{\text{social}}(v, t) + w_S \cdot C_{\text{kinematic}}(i, v, t) \quad \text{subject to } e \notin \mathcal{E}_i^{\text{reserved}}(t)\]Cost Components & Parameters
- $w_D = 1.0$ (Intrinsic Geometry $C_{\text{geom}}$): Baseline Euclidean physical distance $\|p_u - p_v\|_2$.
- $w_M = 1.5$ (V2V Mesh Telemetry $C_{\text{mesh}}$): Time-decayed event-driven congestion alerts broadcast over an ad-hoc mesh ($\text{TTL} = 3$), extending effective perception horizons beyond local sensors.
- $w_H = 2.0$ (Continuous Asymmetric Proxemics $C_{\text{social}}$): Integrates Hall's Proxemics via an asymmetric Gaussian potential field aligned with pedestrian heading ($\sigma_{\text{front}} = 1.35\text{ m}$, $\sigma_{\text{side}} = 0.90\text{ m}$, $\sigma_{\text{rear}} = 0.60\text{ m}$).
- $w_S = 1.2$ (Kinematic Clearance Envelope $C_{\text{kinematic}}$): Prices proximity to fixed shelf geometry ($0.54\text{ m}$ buffer) and peer vehicles ($1.08\text{ m}$ anti-tailgating gap).
- Directional Bottleneck Reservation Protocol ($\mathcal{L}_e$): Resolves single-file corridor contention via directional lock tuples. Opposing agents observe an infinite edge cost $C_{\text{mutex}} = \infty$ and execute a cost-projected diversion through parallel aisles or Turnout Alcoves ($V_{\text{alcove}}$).
Multi-Domain Simulation Topologies
The framework is validated across three distinct public service environments:
- Retail Supermarket ($36 \times 24\text{ m}$): Fixture-dense parallel grocery aisles ($W_{\text{aisle}} = 2.1\text{ m}$), transverse promenades (Action Alley), cashier registers, and front depots.
- Clinical Hospital: Features an emergency priority hierarchy ($R_{\text{lock}} = \infty$ for trauma pushchairs) and designated Turnout Alcoves ($V_{\text{alcove}}$) where routine vehicles pull aside.
- Airport Departure Terminal: Open concourses with dense passenger clusters, security screening pinch points, and boarding gate piers (Gates A1–A4, B1–B4).
Empirical Benchmark & Key Findings
Across 4,650 kinodynamic Monte Carlo trials in 11 experiments:
- Proxemic Compliance: SW-DGO eliminates intimate-space exposure, reducing median exposure to 0.00 person-seconds (vs. 6.40 for $A^*$ and 10.18 for APF).
- Anticipatory Rerouting: V2V mesh telemetry advances rerouting lead time by 11.10 seconds ($p = 3.8 \times 10^{-9}$) and reduces backtracking distance from $2.73\text{ m}$ to $1.08\text{ m}$.
- Corridor Bottleneck Resolution: Directional reservations raise single-file aisle mission success from 36.0% to 88.0% ($p = 1.7 \times 10^{-4}$).
- Microsecond Compute Overhead: Incremental $D^*$ Lite graph repair executes in microsecond scale (median $< 0.01\text{ ms}$, p95 $< 0.20\text{ ms}$), well under 1% of the 50 ms control budget.
- Cross-Domain Generalization: The unchanged planner achieves **99.0%** success in retail supermarkets, **100.0%** in clinical hospitals, and **95.0%** in airport terminals.
Interactive Simulator & Research Assets
- SW-DGO Live Research Site
- Interactive WebAssembly Simulator (Runs the exact Python planner compiled via Pyodide)
- GitHub Repository (Open-source Python package `d2ro`, test suites, and 4,650-trial raw datasets)