String Art Robot Is An Autorouter In Reverse

In the depths of Etsy and Pinterest is a fascinating, if tedious, artform. String art, the process of nailing pins in a board and wrapping thread around the perimeter to create shapes and shading, The most popular project in this vein is something like putting the outline of a heart, in string, in the shape of your home state. Something like that, at least.

While this artform involves about as much effort as pallet wood furniture, there is an interesting computational aspect of it: you can create images with string art, and doing this is a very, very hard problem to solve with an algorithm. Researchers at TU Wien have brought out the best that string art has to offer. They’ve programmed an industrial robot to create portraits out of string.

The experimental setup for this is about as simple as it gets. It’s a circular frame studded with 256 hooks around the perimeter. An industrial robot arm takes a few kilometers of thread winds a piece of string around one of these hooks, then travels to another hook. Repeat that thousands and thousands of times, and you get a portrait of Ada Lovelace or Albert Einstein.

The wire wrapped backplane of a DEC PDP-11. This was assembled by a robot that was programmed with an autorouter. It’s also string art.

The real trick here is the algorithm that takes an image and translates it into the paths the string will take. This is an NP-hard problem, but it is a surprisingly well-studied problem. The first autorouters — the things you should never trust to route traces between the packages on your PCB — we created for wire wrapped computers. Here, computers would find the shortest path between whatever pins had to be connected together. There were, of course, limitations: pins could only have so many connections on them thanks to the nature of wire wrapping, and you couldn’t have one gigantic mass of wires for a parallel bus. The first autorouters were string art algorithms, only in reverse.

You can take a look at the complete publication here.

You’ll also find prior art (tee-hee) in our own pages. Here is an artist doing it by hand, and here’s a machine to do it for you if you’re lazy. We’ve even seen further work on the underlying algorithm on Hackaday.io.

13 thoughts on “String Art Robot Is An Autorouter In Reverse

  1. “The first autorouters — the things you should never trust to route traces between the packages on your PCB — we created for wire wrapped computers.”

    Sounds kind of useless then? Untrustworthy tools.

  2. “The real trick here is the algorithm that takes an image and translates it into the paths the string will take. This is an NP-hard problem, but it is a surprisingly well-studied problem.”

    What is the upper bound on the complexity of the problem? NP-hard provides lower bound that it is at least as hard as the hardest problem in NP. Saying NP-hard would mean the problem is probably not in NP but that is currently unknown. If it’s a well studied problem, then of course there is some upper limit, I’m justing wondering how hard this problem really is computationally speaking.

    1. Each line depends on the one before it. You can compute what the optimal path is for the next line segment, but it is harder to calculate the optimal path for the next 10, or 100 lines. With 256 pegs, there are 256x possibilities with each step.

      So if you create a string art with 1000 strings on a board with 256 pegs, you have 256^100 combinations.

      256^1000 =

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.