Abstract
<title>Abstract</title> <p>Multi-robot navigation in dynamic environments needs a representation compact enough for fast re-planning yet rich enough for self-organized coordination. We propose the Stigmergic Skeleton Field (SSF), coupling a medial-axis skeleton graph with an ant-colony pheromone field, plus Localized Incremental Re-skeletonization (LIR), which repairs topology only where an obstacle changes it, and position SSF against the closest related work we identify — a Voronoi-based ant colony planner for marine vehicles — with a controlled experiment separating LIR's algorithmic contribution from the effect of graph size alone, against seven baselines: static-skeleton Dijkstra, raw-grid ant colony optimization, RRT*, A*, Theta*, PRM*, and a skeleton-restricted Conflict-Based Search (CBS) for optimal small-N multi-agent planning. SSF matches the static-skeleton lower bound within 3–8% (paired Wilcoxon p<0.01 in two of three environments); LIR is up to an order of magnitude faster than full re-skeletonization at map sizes to 1000 cells per side, and two to three orders of magnitude faster than D* Lite. A coarsened-grid control shows this is partly a graph-size effect, though matching node counts roughly doubles path length, a cost the skeleton avoids. LIR also handles simultaneous obstacles and obstacle disappearance at near-linear and symmetric cost. A five-parameter sensitivity analysis shows under 10% performance variation, and per-robot planning time stays within a factor of 1.4 from 5 to 100 robots. We also execute SSF/LIR paths under continuous differential-drive control with local sensing, a step toward hardware validation, though all results remain simulation-based; we provide a ROS 2 package for future deployment.</p>