From: J. R. Molloy (jr@shasta.com)
Date: Thu Oct 25 2001 - 21:45:07 MDT
Stumped by Rubik's Cube? Let the Lego Robot Solve It
http://www.nytimes.com/2001/10/11/technology/circuits/11RUBI.html
LEGO bricks bring to mind rudimentary cars and houses snapped together by
children. But a 37-year-old hobbyist has added a twist, literally, to
building-block construction: he has created a Lego robot that solves Rubik's
Cube.
The hobbyist, Jonathan P. Brown, built the device from Lego's popular
MindStorms series of robot components, which include microprocessors and
motors as well as plastic bricks.
The robot, which is about 14 inches long, 4 inches wide and 8 inches high,
grasps an arbitrarily shuffled Rubik's Cube. A digital camera scans the cube's
six faces and then sends the images to an attached PC, which analyzes them and
sends the robot commands for manipulating the cube. Solving the puzzle takes
about 15 minutes.
Although simple in concept, the machine overcomes complex mechanical and
technical obstacles. "It's an exceptionally well- crafted combination of
solutions," said Michael Andersen, a software engineer in Lego's MindStorms
division.
The machine, which Mr. Brown calls the Cube Solver, is composed of more than
1,100 Lego pieces. The Lego Cam reads the Rubik's Cube's faces and relays the
data through a U.S.B. cable to the PC, which runs color-recognition software
to determine the configuration and generates the shortest string of moves to
solve the puzzle (20 moves on average).
Using an infrared transmitter, the PC communicates with two RCX
microcomputers, the programmable component of MindStorms. The RCX's control
the motors of three grippers that hold the cube and twist it to realign the
faces until every one is made up of squares of the same color.
Mr. Brown, who is from Britain, lives with his wife and 5-year-old son in
Chicago and works as a consultant on air-conditioning systems for historic
buildings. He bought his first MindStorms set, a toy designed mainly for
teenagers, at the suggestion of a friend's 10-year-old son two years ago.
Within a year he had become an expert builder, creating complex robots and
moderating forums on the Lego Web site.
When Mr. Brown spotted an unsolved Rubik's Cube in a neighbor's apartment last
year, he wondered if he could devise a robot that would solve the puzzle.
While many people have written software programs that can represent and solve
a virtual Rubik's Cube, Mr. Brown set out to build a machine that would use
such a program to solve an actual cube on its own.
Right away, he realized that the challenge would lie in building a Lego robot
precise enough to twist a cube accurately yet strong enough to do so without
deforming itself.
"The hardest part was getting the movement combined with the strength," Mr.
Brown said. "If you have enough torque to turn the faces, the Lego will bend
slightly."
A cube's joints are resistant enough to push hollow Lego bricks out of shape,
making the bricks unfit for the relatively delicate task of aligning a cube's
faces.
Mr. Brown started with the Rubik's cube itself. To make its stiff joints more
supple, he applied silicone spray. The mechanism was still too sticky, so he
wedged plastic knives between the layers of the cube and left it overnight.
Success.
He then struggled to build a robot with adequate torque, with grippers that
would keep the cube from slipping and with drive trains that could rotate the
faces precisely. The process involved lots of trial and error, and some clever
solutions. At the suggestion of another Lego enthusiast, Mr. Brown cut shims
out of the plastic insert tray from a Lego package and inserted them to keep
some screws snug.
It took him months to create a prototype of the mechanical system and to adapt
freely available software source code for solving the puzzle. At this point of
the project, a person had to type an unsolved cube's random face positions
into the PC, a project that Mr. Brown considered tedious and prone to error.
"Imagine dialing a three-dimensional, 54-digit telephone number and you get
the idea," he said.
So he set about programming color-recognition software that would read the
cube automatically and announced on a MindStorms forum that it would be ready
within a week or so. It took three months. "I thought for sure there'd be
pre-existing color-recognition software," Mr. Brown said. "But there just
isn't."
He could have used a more sophisticated camera, but he wanted an all-Lego
system. "The Lego Cam I was using is a perfectly adequate little Web cam that
was never meant for this more industrial application," Mr. Brown said. After
spending hours at the University of Chicago's science library and much of the
summer developing a program that would consistently analyze the faces, he
achieved 95 percent accuracy. By July, he had a final version of the Cube
Solver.
While observers tend to explain the contraption in terms of its technical
proficiency, Mr. Brown correlates its complexity with his own frustration
level.
"With any Lego project, you hit a wall where you get frustrated and leave the
pieces scattered all over the floor while you go away and think about it," he
said. "Then you come back and tidy up and start back in. Most projects take
about four tidies."
The Cube Solver took 20.
--- --- --- --- ---
Useless hypotheses, etc.:
consciousness, phlogiston, philosophy, vitalism, mind, free will, qualia,
analog computing, cultural relativism, GAC, Cyc, Eliza, cryonics, individual
uniqueness, ego, human values, scientific relinquishment
We move into a better future in proportion as science displaces superstition.
This archive was generated by hypermail 2.1.5 : Sat Nov 02 2002 - 08:11:40 MST