Drawbot: much better TSP solving

Optimization is the name of the game when attempting to solve the Travelling Salesman Problem (TSP). I’ve figured out most of what Lin/Kernighan is saying and then implemented it to run as fast as I can get it to go. Here’s the progress since the last picture I posted.
Here’s one of the Seattle skyline for the Seattle Maker Fair

It helps if you back up and squint. No really, it’s like pointilism paintings. Ever heard of the Group of Seven? Like that.

Here’s the results of the Drawbot working on the above image done by the TSP solver last night.

It ran for three hours and then failed when the laptop went into sleep mode while I was at the VHS. The mess in the top left is because I tried to draw the picture twice – once it failed when the stepper motor got warm and caused the bobbin to slip off the shaft. In a future version of the drawbot I’d like to try bicycle chain and sprockets instead of bobbins and thread.

Got any suggestions for pictures I should draw? Post ’em below!

In the News

Drawbot presentation slides

In April of 2012 Dan made a presentation at the Vancouver Hack Space about the Makelangelo polargraph drawbot. Dan talked about his history building machines, what he is working on, and what the future holds. Click on each image for a more detailed explanation.


Drawbot: Overview

The Makelangelo is a great way to start learning about robotics. It has two motors mounted at the top of a wall. The motors have bobbins wound with string. The strings are connected to a plotter, a tool that holds a pen. To draw lines the computer can control the motors, which pulls the strings and moves the pen.

But how does that actually work?

I’ll start with the motors, then the measurements, and then the math. After that you’ll have all the theory and we can start talking about what the Arduino computer does.


When you give power to a normal electric motor it spins as fast as it can. A lot of robotics involves stepper motors. They have a special design so that they only move one step each time they are told to, and only in the direction they are told to. I use NEMA17 stepper motors that have 400 steps per turn, or about 0.9 degrees per step. NEMA17 is a particular size. I have seen NEMA sizes from 8 all the way up to 34.


Inverse Kinematics

I know how much string is reeled in or out at each step because I know the number of steps per turn and I know the circumference of the bobbin.

STEPS = 200;
DIAMETER = 0.9;  // cm

I can use Pythagorus’ theorem to find the lengths of the strings because I have The distance between the motors (M1M2) and I know the position of the plotter (P) . If all of this was on a grid then I could say

function IK(P) {
  A = Px - M1x;  // same as V-M1 in the picture
  B = Py - M1y;  // same as P-V in the picture
  M1P = square_root(A*A+B*B);
  A = Px - M2x;  // same as V-M2 in the picture
  // B is the same
  M2P = square_root(A*A+B*B);

  return M1P,M2P;

In robotics this is known as Inverse Kinematics – when you know where you want to be and you calculate how to move the motors/muscles/etc in order to get there.

Forward Kinematics

There’s also Forward Kinematics, when you know how far the robot moved and you need to find out where the thing has gone to. For that I use the law of cosines.

function FK() {
  A = length( P-M1 );
  B = length( M1-M2 );
  C = length( P-M2 );
  Theta = arccos( ( A*A + B*B - C*C ) / ( 2*A*B ) );
  Px = cos( Theta ) * A*A + M1;
  Py = sin( Theta ) * A*A + M1;

So: If you can calculate the length of string at any point then you can find the difference – we can find the moment the string length needs to change while it is moving.

Linear Interpolation

Let’s pretend I’m moving M (me) from point H (here) to point T (there) in one second. At any moment I can describe my position as

M = ( T - H ) * S + H

At the start of the second S=0 and M=T. at the middle S=0.5 and M is halfway between here and there. At S=1 M=T (I have arrived there).

Putting it all together

If we combine this we get something like

function DrawLineTo(T) {
  start = IK( H );
  tstart = millis();
  loop {
    S = ( millis() - tstart ) * 0.001;
    now = IK( ( T - H ) * S + H );

  } while( S < 1 ); } function ChangeStringLengths( now, &start ) { if( now.MIP > start.MIP + TPS ) {  M1.Unwind();  start.M1P+=TPS;  }
  if( now.MIP < start.MIP - TPS ) { M1.WindUp(); start.M1P-=TPS; } if( now.M2P > start.M2P + TPS ) {  M2.Unwind();  start.M2P+=TPS;  }
  if( now.M2P < start.M2P - TPS ) {  M2.WindUp();  start.M2P-=TPS;  }

The rest, as they say, is details. Stepper motors can only turn so fast; the type of plotter used might change things; sometimes the now IK is more than two TPS from the current TPS; and so on.

I use a very similar technique for drawing arcs, or parts of circles. The only difference is that now I’m moving on a curve instead of a straight line.

Arduino code

Download the arduino code here. Almost all of the code has one job: to prevent user error. The rest is comments to explain my specific implementation.

Wait! What about the halftones?

Halftone() uses the line drawing code to fill in a square with a zigzag pattern. I tell halftone how big the square is, how thick the zigzag line is, and how much to fill in. It does the rest!

Can you put all these parts in a kit for me?

I’ve used timing belt and pulleys instead for greater precision, and written software to make it super easy to run.

Thanks for reading!

If you have any comments or questions about the robot, please feel free to post them below and I’ll be happy to answer.