That said, I'm all for "smart sand" and programmable matter. IIRC, the tricky bits are in making the individual smart particles to stick to each other, and then making them behave in a coordinated fashion.
It's an interesting challenge to think about: you have a thousand, or a million, small little robots - how to get them to do something useful as a group? If the robots can barely sense their environment, can barely move on their own, can't communicate with each other except maybe their nearest neighbors - how to make them work together in a controlled fashion? Say, I have this bag of "smart sand", I pour it on a table and want it to form into a cube when I press "Enter" on my laptop - how do I translate a bulk concept like "cube shape" into instructions for a random pile of tiny robots?
Does anyone know of good papers dealing with this problem?
--
[0] - https://en.wikipedia.org/wiki/Health_impact_of_asbestos#Mech...
This was a big focus of a lot of the ALife research in the late 90s and early aughts. Cellular automata, swarming systems, etc. You can generally start with anything coming out of University of New Mexico and bounce around the citation graph of an interesting-sounding paper. You might also want to check out Dave Ackley's T2 Tile project and some of the youtube videos he has put out over the past few years. One thing he is very clear about is addressing robustness in the face of component failure (e.g. his 'Moveable Feast Machine' and 'Demon Horde' stuff is rather fun to watch as it responds to random and widespread failures.) Most of the work in this area is clearly bio-inspired, but why re-invent the wheel when you can steal from the best available examples...
Anyway at least you can model/simulate it, that would be a cool thing to design/program.
They wouldn't be aware of each other in any "smart" way but you'd want to keep the logic as low as possible on the nodes so you have less compute power to miniaturise.
Ideally, I imagine being able to point at a random pile of robots and make that pile do something, without knowing any of the IDs or health of individual cells up front.
So I wonder, is there a way to design the system in such a way that individual robots don't need to be micromanaged, but instead they self-assign to the appropriate role/place, without having full knowledge of the shared goal?
Imagine those experiments in making shapes from sand with standing audio waves, e.g. [0]. The grains of sand have no identity and no awareness. The person setting up the experiment doesn't care about what any individual grain of sand does. They just set up a pattern, encode it in a standing wave, and the sand moves to conform to it. I'm wondering if this kind of approach is possible, except with the robots moving on their own instead of being moved by air. And, as a next step, with a pattern being persisted in the pile of robots, instead of being supplied externally.
--
Nothing about what I posted assumes that. I'm just saying it's the server that would orchestrate them rather than them orchestrating each other. The server would obviously poll them for positional data (relative to neighbour), health status, etc.
> The person setting up the experiment doesn't care about what any individual grain of sand does. They just set up a pattern, encode it in a standing wave, and the sand moves to conform to it.
I didn't suggest that someone manually plots each grain either. Clearly you'd just set up a design in a CAD and then let the server define the algorithm and orchestration required.
Much like how when you manage nodes currently, you don't manually assign which node to scale up or down. You define rules and let the system manage the nodes itself.
Given the problems of miniaturisation and decentralised computing, this feels like a problem easier solved in a centralised system that then hands out instructions (and your requirements clearly stated there was a control system that you used to instruct the grains of sand when you said "press enter on my laptop").
Here's one idea I'm thinking about: flocking-like equations in "boids" simulations are local, a pure function of (the observed state of) the neighbors. In a typical implementation, they just compute velocity/acceleration vectors out of position/velocity/acceleration/class of the neighbors[0]. And the result are pretty, fluid, and uniform in steady-state flocks. But what if we added more observable state and equations to this?
Imagine each boid having a "color", a value that is a function of not just the color of the neighbors, but also of their position/velocity/acceleration/class. And then, the equations computing velocity/acceleration take this color into account too, e.g. by offsetting the result by some function of the neighbors' colors. Could we then design the f([colors]) -> v/a offset and f([everything]) -> color functions so that they end up forcing the flock into an arbitrary uniform shape? I believe we could, but I'm not sure how to define these functions for any particular shape.
(Or, in short: I'm looking for a method to turn an arbitrary picture into an error term for boids rules that makes the flock assume the shape of the picture, instead of an uniform blob.)
I'm sure there must be some pre-existing theoretical work behind finding such functions - this problem feels like a cousin of the "find a formula that draws a target picture on X/Y plot". I just don't know the right keywords to look this up.
But this is kind of the idea on the back of my head - encoding desired group behavior in a function that is common to every member of the group and is entirely local (only a function of the immediate observed environment), but that forces the system to settle in a desired configuration.
--
[0] - "class" being e.g. member of same species, a predator, or a prey.
The real problem with such research is it might work on a quadcopter with room for a chipset capable of relatively powerful real time compution (be that an off the shelf CPU or something more bespoke), but that doesn't scale down to the grain of sand level. At that point you'll want to offload as much computation overhead as you can. Which, again, brings me back to my original post.
Maybe one day in the distant future (if we haven't annihilated each other first) we'll have the technology to built smart grains of sand. But it's seems pointless theorising about something that might just as easily be deprecated by some other fantasy device by our current technological capabilities.
Anyhow, if you're after a paper on the actual calculations you'd run to convert a database of nearest neighbour coordinates into a matrix that can be used to instruct those robots, then I don't have anything directly to hand on that. When I've looked this stuff up in the past I've found most of the time it was proprietary. Maybe there is a paper I've missed. However I have seen papers doing similar work (in the sense that there is transferable logic) in a two dimensional fields, eg matrix reordering.
> Maybe one day in the distant future (if we haven't annihilated each other first) we'll have the technology to built smart grains of sand. But it's seems pointless theorising about something that might just as easily be deprecated by some other fantasy device by our current technological capabilities.
Maybe. But I feel this isn't pointless - I find myself constantly returning to this topic whenever I follow seemingly unrelated avenues of idle curiosity (e.g. "how to build self-maintaining systems", "how to do in-orbit construction" , "how to get rid of household cleaning chores", "how to build a food replicator", "ooh isn't biotech kind of fun", etc.). I think we'll eventually start building "smart matter" at some scale. Might be nanometer. Might be millimeter. Might be meter. Each of those scales has its own physics regime, but I think the concepts behind self-organization will be common. And we're already working on those ideas when studying biology at molecular and cellular level.
> When I've looked this stuff up in the past I've found most of the time it was proprietary.
Do you remember any names? Might be that some of the research is released. Or maybe my employer has access.
> However I have seen papers doing similar work (in the sense that there is transferable logic) in a two dimensional fields, eg matrix reordering.
Thanks, I'll look it up.
Maybe better would be a kind of 3D printing model, where the shape is 2D and changes over time, which leads to accretion of a 3D shape.
Even so - without feedback and monitoring you'll get errors and holes.
And you'll still have the problem that unless you're using some novel form of programmable electrostatic bonding, adhesion between bloxels will be weak.
So you won't be able to do much with your finished shape except look at it. Probably not even pick it up, in fact.
That's the thing I'm trying to work around. If bloxels are like boids in the flocking simulations, they don't care about their location - they move and change state based on the movement and state of their neighbors. In the flocking simulations, boids automatically form stable shapes and recover from disruptions, and none of them have assigned positions or even any kind of unique identifier. It's the repulsion and attraction functions - identical in every boid - that determine the steady state shape of the flock.
That said, I think there's a way for bloxels to tell where they are in their "flock". Imagine each bloxel continuously publishing a "depth" value that's computed as e.g. length of the vector \Sigma_{n}^{Neighbors}: Depth(n) x DirectionTo(n). The values would initially fluctuate, but I feel it's possible to set this up so that over short time the system will settle, with every boid's "depth" value being a correct indication of how far it is from the centre of the group. So e.g. upon activation, a pile of bloxels could wait for "depth" values to stabilize, and then each bloxel would remember its value as its designated position, and execute some different algorithm with that bit of state fixed.
Note to self: there's a bunch of free "agent-based simulation" programs I saw on the Internet the other day; such "depth" calculation should be a simple thing to simulate and verify.
Related keyword: phase-locked loops. See also: fireflies that synchronize their flashing patterns over time.
> And any kind of closed object would cause problems because bloxels would only adhere to the surface, not build up bulk inside.
Why can't they build up bulk, using each other for support?
> Maybe better would be a kind of 3D printing model, where the shape is 2D and changes over time, which leads to accretion of a 3D shape.
I'm not sure what you mean. That sounds like regular 3D printing using "dumb" matter?
> Even so - without feedback and monitoring you'll get errors and holes.
Bloxels would be active and reacting to each other - this is a feedback-full system.
> unless you're using some novel form of programmable electrostatic bonding, adhesion between bloxels will be weak
I have no good ideas here. I don't know of any programmable bonding system that isn't too energy intensive to use with current technology. AFAIK electromagnets are power hogs. Mechanical locking systems are also energy intensive, and also tricky to use (maneuvering the mating endpoints to meet, compensating torque, etc.)
And this reminds me of those audience experiments with people holding up blue and red cards and using this "vote" to successfully steer a vehicle.
In a parallel comment, I described an idea where boids first start doing nothing except publishing a "depth" value that's a function of their neighbors "depth" value, waiting for the system to settle (as detected by neighboring values not changing by more than some fixed epsilon over some fixed Δt). They could then record their individual values and continue to a second algorithm (e.g. traditional "boids"), that uses this (now fixed) "depth" value as a parameter.
This is, in general, a pattern for individual unit to discover their role in the group, without ever knowing the whole group. I just realized this sounds like things the field of "distributed consensus" deals with - I'll add that to my research list.
I remember the voting games and "Twitch plays X" events. It's kind of a different situation (external controllers voting on control input to a single actor), but there might be some parallels.