A Stochastic Approach to Shortcut Bridging in Programmable Matter
A Stochastic Approach to Shortcut Bridging in Programmable Matter
复制标题
可编程物质中捷径桥接的随机方法
DOI：
10.1007/978-3-319-66799-7_9
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Richa, Andrea W
中科院分区：
文献类型：
--
作者：
Andres Arroyo, Marta;Cannon, Sarah;Daymude, Joshua J;Randall, Dana;Richa, Andrea W
在自组织粒子系统中，一种可编程物质的抽象，被称为粒子的简单计算元素具有有限的记忆和通信，自组织以解决系统范围的运动，协调和配置问题。在本文中，我们考虑了一种随机、分布式、局部、异步的“捷径桥接”算法，其中粒子在间隙上自组装桥，同时平衡最小化桥的长度和成本。人们已经观察到，ecitoni属的军蚁在觅食路径上表现出类似的行为，它们通过局部相互作用动态调整桥梁以满足效率的权衡。利用马尔可夫链分析技术，我们严格地分析了我们的算法，证明了它在路径长度和桥梁成本的竞争因素之间达到了接近最优的平衡，并证明了它与蚂蚁桥的“捷径”间隙的角度类似。我们还提供了仿真结果，将我们的算法与军蚁桥接行为进行定性比较。我们的工作给出了一个合理的解释，说明如何通过计算能力有限、可以访问随机比特的简单生物（例如蚂蚁）的局部相互作用，收敛到全局最优配置。所提出的算法也证明了随机方法对可编程问题算法的鲁棒性，因为它是我们之前的压缩随机算法的一个惊人的简单扩展。
In aself-organizing particle system, an abstraction of programmable matter, simple computational elements calledparticleswith limited memory and communication self-organize to solve system-wide problems of movement, coordination, and configuration. In this paper, we consider a stochastic, distributed, local, asynchronous algorithm for “shortcut bridging”, in which particles self-assemble bridges over gaps that simultaneously balance minimizing the length and cost of the bridge. Army ants of the genusEcitonhave been observed exhibiting a similar behavior in their foraging trails, dynamically adjusting their bridges to satisfy an efficiency trade-off using local interactions. Using techniques from Markov chain analysis, we rigorously analyze our algorithm, show it achieves a near-optimal balance between the competing factors of path length and bridge cost, and prove that it exhibits a dependence on the angle of the gap being “shortcut” similar to that of the ant bridges. We also present simulation results that qualitatively compare our algorithm with the army ant bridging behavior. Our work gives a plausible explanation of how convergence to globally optimal configurations can be achieved via local interactions by simple organisms (e.g., ants) with some limited computational power and access to random bits. The proposed algorithm also demonstrates the robustness of the stochastic approach to algorithms for programmable matter, as it is a surprisingly simple extension of our previous stochastic algorithm for compression.