Notes taken by Shashank Singh Andrea Richa: Programmable Matter: Models and Problems This talk is inspired by, but not about biological systems. Many tiny synthetic elements (called particles) can move and bond. There are two types: active (e.g., finite automata) and passive (e.g., dna). Programable Matter (PM) is a general framework for looking at self-organizing systems, where we pro- gram identical individuals to achieve desired global structure or function. Typically, elements on latch to each other to change structure, move, etc. Why study self-organizing behavior? It is flexible for problem solving and occurs widely in nature. Examples from robotics include kilobot swarms, nubots, modular robots, prismatic cubes, and M-blocks (Seth Goldstein at mit). Major potential applications include monitoring environmental/structural conditions (e.g. for weather, oil pipelines, bridges, health) Basic problems for programmable matter include forming a predetermined shape and coating a surface. We study a model based on regular tilings in R 2 . We assume particles start in a connected formation (since they move by disconnecting and reconnecting with others). Algorithms on basic model: Inspiration from amoebas (amoebot). On a hexagonal grid, agents can identify their edges, but not orientation, ids, n, etc., They can only count to a constant (i.e., Stone Age model). Particles expand and contract to move. We allow an agent to expand to a neighborng cell and contract if it chooses. They can push the tail of another agent. Some problems and initial results: consider covering a surface. We cant actually cover the whole surface (which is basically infinite), but want to maximize coverage. Particles start in an arbitrary configuration. Our algorithm: particles that touch surface dont move. Need to bring down other floating particles. Make spannign tree from floating particles towards surface. Then move root towards the surface (with all agents in the tree moving in parallel). [video of simulated particles covering surface with this algorithm] What if we have more particles than surface? Make multiple layers. How do we know when to form a new layer? Alternate moving spanning trees left and right. We have some proofs of what different types of programmable matter can do, but don’t discuss them here. Another important problem is form a given shape starting from a given seed particle. We use a similar snake-like, layered algorithm. [videos of particles forming simulated hexagon, rectangle of fixed sidelength ratio, and triangle] Results are unknown for nonconvex shapes or shapes with holes. The algorightm is “work optimal”, but inherently sequential. An important open problem is parallelizing this. Note that PM needs a seed particle (it can’t do leader election, even with randomness). Other problems: bridging/filling gaps, parallellizing algorithms, etc.? More general model: abstract from tiling of R 2 , using graph where nodes are agents and edges represent visibility (defined per context) and move destinations. AMOEBOT is a particular case where visibility is defined as cells at distance 2. The model needs a primitive motion step. Particles may need more space to move to stay in a static state. What are interesting questions for a general model? How much memory is needed? What can we do with constant memory? How do various oracles fit in (e.g. information about a constant size neighborhood, constant-size message broadcasting, or leadership selection). Questions? Well, an observation: most distributed algorithms want to elect leaders. Why? It’s much easier to coordinate with leader. But biological systems often dont have leaders. Often, a temporary leader is sufficient. Many fundamental distributed problems provably need a leader. Biological systems often use an external stimulus (e.g. finding food) to identify a leader. Chris Reid: Cellular Decision-making: How an Amoeboid Or- ganism Solves the Two-armed Bandit Problem Mostly empirical work about slime molds (SMs). [Some videos of slime mold growth.] SM is able to do intelligent behaviours. One big organism/cell with many coupled oscillators/pulses. When food is introduced, the local oscillator increases frequency and passes this on to nearby oscillators. This softens the local cell wall, and so SM grows in that direction. [video of SM solving shortest path problem in a maze] SM can anticipate periodic events. After periodic negative feedback, for some time, SM acts as if in anticipation of negative feedback. The mechanism for this is unknown. What else can SM do? When growing and moving in search of food, it performs an exploration- exploitation (speed-accuracy) tradeoff: do I keep looking or settle for what I’ve found (e.g. finding parking). In Machine Learning, the analogous problem is the two-armed bandit. How much time should you spend trying both levers before deciding on one? Experiment setup: SM starts in the middle with 2 possible paths along which to grow/move: left and right. Each path has some food sources, with more one side than on the other. Initially, SM grows evenly along both paths. Eventually, it should choose to grow only along the path with more food. How and when does it choose to do so, based on the food distribution? We look at the difference between left-right arm lengths. For 4 food on left vs. 8 food on right, SM quickly chooses 8. Similarly for 8 vs. 16. So SM uses relative preferences. For 11 vs. 16, SM takes longer to choose. What about different food qualities? SM can still do this. How? Bayesian Analysis: We studied 8 plausible models/strategies, including moving proportional to food, alternating growth direction, etc. A relative success model (taking into account both food amount and quality) best explains data. Tobias Langner: Towards more realistic ANTS Parameters: n (# ants) and D (distance from nest to food). Easy to show Ω(D + D 2 /n) lower bound on search time. Previous work assumed ants (ants nearby treasure search) were Turing machines without communication. We model ants as finite state machines and allow some communication. Model: Ants walk horizontally or vertically on a grid. Designated nest cell and food cell. Ants want to start at nest and find food quickly. Can talk to ants in same cell (finite message size). Each ant is a finite automaton, with structure independent of n. How many ants are needed to find the food? For asynchronous models, 4 ants suffice, using triangle search algorithm: there are 1 “explorer” ant, 3 “guides” ants. Explorer walks in triangle and guides move outward to the next larger triangle when explorer meets them. For synchronous models, 3 ants suffice, using a diamond algorithm: there are an “explorer” ant, a “guide” ant, and a “nest” ant. The nest ant stays still on the nest. The explorer goes in and out of the nest in a cross shape, turning around whenever it meets the guide. The guide walks in diamond shape, turning whenever it meets the explorer. We can show that 1 or 2 ants is insufficient. With randomization, we can do the asynchronous case with 3 ants (though this takes expected Ω(2 D ) time). Diamond search can parallelize well.