Research

Self-Reconfiguration Algorithm for Modular Robots

Project Details

Abstract

Large modular-robot lattices often stall when many units must traverse the same narrow passageways. We formulate this congestion as a unit-capacity maximum-flow problem on a grid graph and introduce a Dynamic Bridge strategy that repurposes idle modules into temporary “porous” links, widening critical cut-sets while preserving overall connectivity. The framework implements both manual and NetworkX-accelerated Edmonds–Karp solvers, supports complete 2-D and 3-D lattice models, and records every reconfiguration step as high-resolution visualizations. It also constructs a virtual full grid, evaluates every empty cell as a potential bridge, ranks candidates by marginal gain in max-flow, and schedules relocations only when a depth-first connectivity test ensures the remaining structure stays intact. Development proceeds through six phases: (1) grid construction and module labelling, (2) baseline flow analysis and bottleneck detection, (3) strategic bridge planning with path-safe module selection, (4) incremental bridge construction, followed by planned phases for (5) dynamic routing and (6) large-scale simulation-based validation. At each phase the system exports annotated figures—including initial lattices, bottleneck heat-maps, bridge candidates, movement sequences, and final flow overlays—providing a transparent audit trail for debugging and presentation.
By blending search-based path-planning insights from MAPF research with porous self-reconfiguration concepts such as RePoSt and ASAPs, this work establishes a practical foundation for quantitatively improving throughput and scaling toward massively parallel 3-D self-reconfiguration.
 
2024-2025-URE-ece-kalaoun-pic-res.jpg