Automated generation of machining sequences

When I was an undergraduate student I took a course on Machining. I did not enjoy to study the details of how various machine tools are built or how they work, but I had a lot of fun creating machining sequences, which required ingenuity. The regular visits to the machine shop were also fun. After all, it’s not everyday that one gets to see an object taking shape right before one’s eyes :-)

The instructor would give us a certain mechanical part and ask us to come up with a machining sequence for it. If you are not acquainted with machinist’s jargon, here’s a definition:

Definition: a machining sequence is a sequence of machining operations (such as turning, drilling, milling, boring, broaching, etc) that remove material from, say, an aluminium block in order to obtain a desired object (such as a piston or a cylinder for a car engine).

Note that machining is about removing material, i.e., it’s a subtractive technology. By contrast, rapid prototyping is an additive technology.

Let us consider an example. Suppose I give you the following 3D model:

What machining sequence would you propose? Here’s my proposal:

1. Start with a crude block of aluminium.
2. Given the object’s rotational symmetry about the longitudinal axis, use the lathe to shape the cylindrical / conical parts. Use the lathe also to drill the central hole along the longitudinal axis.
3. Note that the surface of the central hole is not smooth. It has “teeth”. I would say that a combined lathe / broach would allow one to obtain the “teeth”.
4. Drill 6 holes at the base.
5. Use a milling machine to remove material at the base, in between the 6 holes.

Here’s a sketchy illustration of the machining sequence I proposed, where a machine tool is assigned to various sections of the object being fabricated:

I am not an experienced machinist, and I make no claims that the machining sequence I have just proposed is any good. If you have ideas, feel free to share.

Suppose you have a 3D model of some object you would like to fabricate via machining. An experienced machinist is able to visualize the object and devise a machining sequence. Could a computer be taught to do the same?

Problem: develop algorithms that, given a 3D model of some object, automatically generate machining sequences. These algorithms should determine which machining operations to use, and in which order.

The machining sequence to be carried out is a function of the geometry and the topology of the object to be fabricated. Hence, algorithms that automatically generate machining sequences would have to “understand” the geometry and the topology of the given 3D model. This suggests that ideas from Computational Geometry and Computational Topology could perhaps be applied in this particular problem. For example, if the object to be fabricated has cylindrical holes in it, then it’s likely that one should use a drill or a lathe. These holes are a geometrical / topological property of the object. How can a computer be taught to understand them?

Furthermore, there probably is more than one possible machining sequence to fabricate the desired object from the same crude block of metal. If there are many possible machining sequences, then one can start thinking of optimality. Some possible optimality criteria would be to minimize the total number of operations, or to minimize the total fabrication time, for example. Can you think of other criteria? Given one optimality criterion, one can then try to find the “best” machining sequence.

I wonder if Machine Learning could help, too. Give the same 3D model to an experienced machinist and to the software system we’re developing. Both devise machining sequences. The human will probably beat the computer. Feed the computer with the machining sequence devised by the human. Repeat this procedure many times. Iterate until one has obtained a skilled “machining expert system“. The ingenuity and creativity required to transform crude blocks of metal into beautifully machined parts would be emulated by algorithms. I make no claims that this would be easy to implement ;-)

I looked for work on this area. I found a few patents [1]-[5], and a bunch of technical papers [6]-[12] dedicated to this problem. Interestingly, most patents I found on this topic were filed by Japanese. This should come as no surprise. After all, the Japanese are notoriously good at optimizing manufacturing processes.

This post is admittedly vague. I propose a problem, but I do not present any sketch of a solution. Basically, I wanted to share my thoughts in order to invite constructive discussion. Any ideas?

__________

References

[1] Hajimu Kishi, Masaki Seki, Kunio Tanaka, Teruyuki Matsumura, Automatic machining process determination method in an automatic programming system, U.S. patent #4723203. Filed: 1985 / Issued: 1988.

[2] Koichi Asakura, Machine tool with tool selection and work sequence determination, U.S. patent #4739488. Filed: 1985 / Issued: 1988.

[3] Yasushi Fukaya, Yuto Mizukami, Method for determining a machining method in numerical control information generating apparatus, U.S. patent #5107414. Filed: 1989 / Issued: 1992.

[4] Kotaro Watanabe, CAD/CAM unit data generating apparatus and process, U.S. patent #5297022. Filed: 1992 / Issued: 1994.

[5] Takashi Takegahara, Shigetoshi Takagi, Koji Suzuki, Machining sequence determining method and apparatus for wire-cut electric discharge machining and computer readable medium storing a machining sequence determining program, U.S. patent #6445972. Filed: 1999 / Issued: 2002.

[6] In-Ho Kim, Jung-Soo Oh and Kyu-Kab Cho, Computer aided setup planning for machining processes, Computers & Industrial Engineering, 18th International Conference on Computers and Industrial Engineering, Vol. 31, Issues 3-4, pp. 613-617, December 1996.

[7] Z. Gu, Y.F. Zhang, A.Y.C. Nee, Identification of important features for machining operations sequence generation, International Journal of Production Research, Vol. 35, Issue 8, pp. 2285-2308, August 1997.

[8] Majid Tolouei-Rad, An efficient algorithm for automatic machining sequence planning in milling operations, International Journal of Production Research, Vol. 41, Issue 17, pp. 4115-4131, November 2003.

[9] W.D. Li, S. K. Ong, A.Y.C. Nee, Optimization of process plans using a constraint-based tabu search approach, International Journal of Production Research, Vol. 42, Issue 10, pp. 1955-1985, May 2004.

[10] D. Kingsly Jeba Singh, C. Jebaraj, Feature-based design for process planning of machining processes with optimization using genetic algorithms, International Journal of Production Research, Vol. 43, Issue 18, pp. 3855-3887, September 2005.

[11] L. Wang, N. Cai, H.-Y. Feng, Z. Liu, Enriched machining feature-based reasoning for generic machining process sequencing, International Journal of Production Research, Vol. 44, Issue 8, pp 1479-1501, April 2006.

[12] Rezo Aliyev, A strategy for selection of the optimal machining sequence in high speed milling process, International Journal of Computer Applications in Technology, Vol. 27, Issue 1, pp. 72-82, September 2006.

The Binary Marble Adding Machine

Matthias Wandel built a rudimentary digital computer out of wood. The ingenious Binary Marble Adding Machine is, basically, a 6-bit adder that runs on gravity and uses mechanical flip-flops for memory storage.

[ schematic courtesy of Matthias Wandel ]

Here’s a demo video:

More info on the lovely Marble Adding Machine:

• More on the binary marble adding machine

• Plans for the marble adding machine

• How the marble flip-flop works

Other interesting creations of Matthias Wandel:

• Wooden Machines

• Marble Machines

(hat tip: Rick Regan)

The virtual Apollo Guidance Computer

I remember on the trip home on Apollo 11 it suddenly struck me that that tiny pea, pretty and blue, was the Earth. I put up my thumb and shut one eye, and my thumb blotted out the planet Earth. I didn’t feel like a giant. I felt very, very small.

– Neil Armstrong [1]

On this day 40 years ago, the Apollo 11′s Eagle lunar module landed on the Moon. As Neil Armstrong and Buzz Aldrin became the first humans to walk on the lunar surface, Michael Collins orbited the Moon inside the Columbia command module, experiencing “an aloneness unknown to man before”, as aviator Charles Lindbergh put it [2].

[ photo courtesy of NASA ]

The Apollo program was an enormous technical achievement. I shall forever be amazed at how the engineers who worked on this program managed to accomplish so much with the technology they had available at the time. The rocket engine was a relatively recent technology back then, the transistor had been invented in 1947, the integrated circuit had been invented in 1958, and the microprocessor had not even been invented yet. In particular, the Apollo Guidance Computer (AGC) was a wonderful work of ingenuity: it was the world’s first modern real-time embedded system, and it led to the development of fly-by-wire systems.

To commemorate the 40th anniversary of the Apollo 11 mission, the command module code (Comanche054) and the lunar module code (Luminary099) have been transcribed from scanned images by the Virtual AGC and AGS project! [3] The code can be found here.

For example, take a look at the following modules: ascent guidance, Kalman filter, master ignition routine. Yes, programming the AGC seems to have been a spartan endeavor! ;-) If you happen to dislike vintage assembly programming languages, take a look at the yaAGC code, which is written in C.

__________

References

[1] The Greening of the Astronauts, Time Magazine, December 11, 1972.

[2] Robin McKie, How Michael Collins became the forgotten astronaut of Apollo 11, The Observer, July 18, 2009.

[3] Nathaniel Manista, Apollo 11 mission’s 40th Anniversary: One large step for open source code…, The official Google Code blog, July 20, 2009.

Colored Water Figures

Fotoopa is a photographer from Belgium who has shot amazing high speed photos of dancing and splashing colored water drops. Here’s an example of a droplet captured in mid-splash in vivid detail:

[ photo courtesy of fotoopa ]

Apart from the standard photographic equipment (camera, lenses, multiple flashes), fotoopa uses some high-tech hardware more commonly found on a physics research lab: lasers, LEDs, homemade electronics, power amplifiers, microcontrollers, FPGAs. It’s very, very impressive indeed.

The Connection Machine

One day when I was having lunch with Richard Feynman, I mentioned to him that I was planning to start a company to build a parallel computer with a million processors. His reaction was unequivocal, “That is positively the dopiest idea I ever heard.” For Richard a crazy idea was an opportunity to either prove it wrong or prove it right. Either way, he was interested.

– Danny Hillis [1]

When Danny Hillis (b. 1956) was a graduate student at MIT‘s Artificial Intelligence (AI) lab in the early 1980s, he built a massively parallel supercomputer which he named the Connection Machine. At the time, computers were still somewhat ENIAC-like: sequential, single-processor machines. By contrast, the Connection Machine had over 65,000 processors! The Connection Machine was the topic of Danny Hillis’ PhD thesis [2], supervised by Prof. Gerald Jay Sussman.

[ Connection Machine 2 ]

Danny Hillis‘ motivation to build such a parallel computer stemmed from his desire to explore new paradigms of computation outside the traditional von Neumann architecture. Hillis believed that Computer Science needed fresh ideas, and he turned to Physics as a source of inspiration [3].

Although the Connection Machine was initially intended for applications in Artificial Intelligence, later versions of it (CM-2, CM-5) were used with remarkable success in Computational Physics (e.g., Lattice QCD).

In 1983 Danny Hillis co-founded a company named Thinking Machines Corporation (TMC)  in order to exploit possible commercial applications of the Connection Machine paradigm. Competition from established supercomputer firms forced TMC into bankruptcy in 1993.

__________

References:

[1] Danny Hillis, Richard Feynman and the Connection Machine.

[2] Danny Hillis, The Connection Machine, PhD thesis, Department of Electrical Engineering and Computer Science (EECS), MIT, 1988.

[3] Danny Hillis, New Computer Architectures and their relationship to Physics, International Journal of Theoretical Physics, Vol 21, Nos. 3/4, 1982.

__________

Related:

• Applied Minds think remarkably (June 2005)

• A Morning With Danny Hillis (June 2004)

• If tomorrow comes (2004)

• QCD on the Connection Machine (1995)

• The Rise and Fall of Thinking Machines (Sept. 1995)