Solving the Famous Alpha 1.0 Puzzle

The goal is the separate the two bars from each other. You might have seen a puzzle like this before. The example was constructed by Boris Yamrom, GE Corporate Research & Development Center, and posted as a research benchmark by Nancy Amato at Texas A&M University. It has been cited in many places as a one of the most challenging motion planning examples.

In 2001, it was solved by using a balanced bidirectional RRT, developed by James Kuffner and Steve LaValle. There are no special heuristics or parameters that were tuned specifically for this problem. On a current PC (circa 2003), it consistently takes a few minutes to solve. As of June 2003, we know of only two other algorithms that have been able to solve this example. One is by Kineo, a French company that develops motion planning software. This planner is also based on RRTs. The other is by Pekka Isto, who was a Ph.D. student from the Helsinki University of Technology in Finland.

MPEG Animation: [5.1MB]

The animation was made by James Kuffner.

Return to RRT Gallery page
Return to main RRT page

Web page maintained by Steve LaValle