Building with Moving LEGOs: How Robots Rearrange Themselves

Imagine you have a giant bucket of LEGO bricks, but there is a catch: the bricks can move themselves.

These "smart bricks" are what scientists call modular robots, which are like high-tech building blocks that can rearrange their own bodies to turn from a bridge into a tower.

The Friction Problem

For a long time, the math behind these robots was a bit too perfect. It assumed the blocks could slide past each other without any friction or "bumps" getting in the way.

But in the real world, robots have tiny pegs and holes to help them click together. These features can cause a "squeezing" problem, which is like trying to slide a dresser through a hallway that is exactly the same width as the dresser—you’re going to get stuck on the doorframe.

The MIT–NASA Discovery

Researchers from MIT and NASA just solved this puzzle. They proved that if you give a robot just a little bit of "wiggle room," it can build almost anything.

The Loose-Sliding Constraint

They discovered that for a robot to move, it needs a loose-sliding constraint of $k=2$ . This is like saying a car needs a two-lane road to drive through even if the car only takes up one lane.

MIT–NASA

Team

Notably, the constraints on the moves in our model are strictly stronger than in the pivoting-cube model as well. Thus our universality results can be seen as strengthenings of past work to better apply to real-world robotics.

The Building Strategy

By using a clever "3D printing" method, the team showed they could move $n$ number of modules into any shape.

The Diagonal Plane Sweep

The strategy uses a Diagonal Plane Sweep, which is like a giant, invisible squeegee moving across a room at a tilt to push blocks into their perfect spots one by one.

Two Ways to Win

The study found two big, efficient paths to building any shape.

Method 1

If you have $O(n)$ extra "scaffolding" blocks—which act like temporary training wheels—you can build any shape you want.

Method 2

If the shape doesn't have any tiny, one-inch-wide holes (a rule they call External Feature Size of at least 2), the robots can build it without any extra help at all!

Remarkable Efficiency

This math is incredibly efficient. It takes $O(n^2)$ moves, which is the fastest way possible to get the job done.

Best of all, the movement is monotonic, which is like a professional mover carrying a box straight from the truck to the right shelf without ever putting it down or moving it twice.

Limits and Reality Checks

The "Wiggle Room" Limit
Scientists found that if the "wiggle room" gets too big (like $k=3$ ), the robots actually get stuck and can’t finish the job.

While this is a huge leap for NASA's space-building robots, there are still limits. The robots currently need a lot of empty space around them to work, and they can't quite build shapes with super-skinny, microscopic gaps yet.

Key Takeaway: By introducing a small, realistic amount of wiggle room ( $k=2$ ), researchers have created a powerful and provably efficient model that allows modular robots to reconfigure themselves into almost any shape, bringing theory much closer to real-world application.

Reference: "Reconfiguration Algorithms for Cubic Modular Robots with Realistic Movement Constraints", MIT–NASA Space Robots Team (Josh Brunner, et al.). arXiv:2405.15724v1 [cs.CG] 24 May 2024.