Introduction
In biological systems, hormones diffuse to create gradients that coordinate growth and repair. In the fields of amorphous computing and modular robotics, researchers aim to mimic this behavior using digital gradients. Typically, this is achieved by having nodes broadcast a "hop count" to their neighbors to establish a distance-based coordinate system. However, standard broadcast methods face two significant hurdles: communication inefficiency and the "ghost gradient" problem. In dynamic networks, if a link to the source is severed, nodes may continue passing stale hop-count values indefinitely—a phenomenon similar to the "count-to-infinity" problem in networking. This paper introduces a highly efficient, distributed algorithm that addresses these issues by extending classic loop-free routing techniques.
Methodology: Distributed DAG Formation
The core of the proposed approach is an asynchronous, agent-based algorithm that maintains a Directed Acyclic Graph (DAG) over the network. Unlike continuous broadcasting, agents in this system only send messages when their local state or the network topology changes, significantly reducing communication overhead.
Key technical features include:
- State-Based Updates: Communication is triggered only by state changes, ensuring the system remains quiet when stable.
- Delete Propagation: To eliminate "ghost gradients," the algorithm includes a mechanism to propagate "delete" messages. A small timing delay (typically 3 time-steps) is introduced during gradient spreading. This allows faster-moving delete messages to "catch up" and clear stale information before new gradients propagate.
- Pose Propagation: The algorithm can carry 3D pose data, allowing each module to use feed-forward kinematics to calculate its own coordinates relative to the source module as the gradient spreads.
Performance and Scalability
The algorithm was evaluated using various synthetic topologies, including string graphs, single-cycle graphs, and fully connected grids, as well as simulations of modular robotic systems like ATRON and M-TRAN. The results demonstrate that the algorithm is both robust and highly scalable.
Key findings include:
- Linear Scalability: Both the number of messages and the time-steps required to establish a gradient scale linearly with the number of edges and vertices in the graph.
- Low Communication Overhead: In most tested configurations, the average message count per connector remained below two, proving the efficiency of the state-based update model.
- Robustness to Asynchronicity: The algorithm functioned correctly across different activation schemes, confirming its suitability for truly decentralized, asynchronous environments.
Conclusion and Future Work
By structuring hormone gradients as DAGs and implementing a strategic propagation delay, this research provides a robust solution for global coordination in dynamic modular systems. While the current "delay constant" is a heuristic that has proven effective in simulations, future work will focus on analytical proofs of convergence and methods to determine optimal delay parameters for irregular or high-noise environments.
Summary updated