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.

Are we running out of helium?

Contrary to popular belief, helium is not used only to inflate party balloons. Given that helium is inert, it is used to create nonreactive atmospheres in semiconductor fabrication and in arc welding, for instance. However, the most important industrial application of this noble gas is probably in cryogenics. Liquid helium is used to cool infrared sensors, nuclear reactors, and superconducting magnets (for example, in MRI equipment). Helium is also used for leak detection, and as a gain medium in He-Ne lasers.

Helium is the 2nd most abundant element in the universe, right after hydrogen. Helium is produced in stars by nuclear fusion:

[ source ]

On Earth, the helium-4 isotope is by far the most abundant, a byproduct of millions of years of alpha decay of uranium and thorium (note that the nucleus of helium-4 is the same as the one of an alpha particle). Helium is extracted during the refining of natural gas. If it’s not extracted during this refining process, it soars off and is forever lost.

Since nuclear fusion technology is still decades away and given that alpha decay is an extremely slow process, industrial production of helium is indeed very far from becoming a reality. We will need to keep extracting helium from natural gas reserves. The problem is that helium reserves may be depleted within the next decade [1][2]. Once that happens, where will we get the helium demanded by high-tech industries?

If helium becomes a sought-after commodity, then the same companies that extract natural gas will have an economic incentive to extract helium as well, instead of letting it escape to the atmosphere. However, helium is a non-renewable resource. Sooner or later, we will deplete the reserves that have built up over millions and millions of years.

The Sun produces colossal amounts of helium by nuclear fusion. In fact, helium is named after Helios, the Greek god who personified the Sun (helium was first found in the Sun). Harvesting helium from the Sun is impossible, however. At least directly. A possibility would be to harvest helium-3 (to serve as fuel for fusion reactors) from moon rocks [3][4][5], where it can be found due to billions of years of bombardment by the solar wind. If the idea of mining the Moon sounds insane to you, please note that Harrison Schmitt (geologist and Apollo 17 astronaut) is one of the proponents.

Is the Moon the El Dorado of helium-3? I don’t know, but I have heard rumors that India and China are developing robotic systems to harvest helium-3 from moon rocks. It seems that Space is the next frontier in the race for natural resources. What next? Will we be mining asteroids to extract platinum for fuel cells?

__________

References:

[1] Emily Jenkins, A Helium Shortage?, Wired Magazine, Aug. 2000.

[2] Laura Deakin, The coming helium shortage, Chemical Innovation, June 2001.

[3] Harrison Schmitt, Mining the Moon, Popular Mechanics, Oct. 2004.

[4] John Lasker, Race to the Moon for Nuclear Fuel, Wired Magazine, 2006.

[5] Mark Williams, Mining the Moon, Technology Review, Aug. 2007.

Dangerous Knowledge

Bring vor, was wahr ist.
Schreib so, dass es klar ist.
Und verficht’s, bis es mit dir gar ist.

– Ludwig Boltzmann

Dangerous Knowledge is a 90-minute long BBC documentary about the lives of four great thinkers: Georg Cantor (1845-1918), Ludwig Boltzmann (1844-1906), Kurt Gödel (1906-1978), and Alan Turing (1912-1954). Cantor founded Set Theory, Boltzmann founded Statistical Mechanics, Gödel’s incompleteness theorems had an immense impact on Mathematical Logic, and Turing was one of the fathers of Computer Science. Why these four scientists? What is the pattern? The answer is that all four of them committed suicide.

The documentary is a bit too sensationalist for my taste. Its message is that these four brilliant minds were driven to madness (and, ultimately, to suicide) due to the earth-shattering nature of their ideas. While one could argue that such a claim is not too far-fetched in the cases of Cantor and Boltzmann, it seems somewhat distasteful when applied to Turing. Turing did not go insane because of the depth of his revolutionary insights. Turing’s homosexuality was viewed as a security problem during the troubled times of the Cold War, and the brutal punishment which he underwent (chemical castration) was probably what led him to take his life. Gödel feared that someone was poisoning his food, and would refuse to eat unless his wife would taste his food first. When his wife was hospitalized for some time, Gödel starved himself to death. Hence, the claim that these four suicides were due to “dangerous knowledge” seems rather crude to me.

On the bright side, the claim that these four geniuses were ahead of their time sounds rather plausible. Cantor’s or Boltzmann’s ideas did not meet fierce resistance because they were technically wrong, but because they challenged the belief that the universe was perfect and orderly. No one wanted to hear about Boltzmann’s work on entropy, because entropy is, by definition, a measure of disorder. As Hilbert’s program tried to fix the inconsistencies in  the foundations of Mathematics, Gödel’s incompleteness theorems made Hilbert’s monumental mission “wir müssen wissen, wir werden wissen” seem even harder to accomplish.

In my most humble opinion the times were not yet ripe for theories that imposed limitations on human knowledge. “What about Heisenberg’s uncertainty principle?”, I hear you ask. Good point. Do note that two decades can make a world of difference. Heisenberg’s work was created when Quantum Mechanics was already out of the box. By contrast, Boltzmann had to fight the 19th Century establishment that was still deeply entrenched in the Newtonian paradigm.

If you have a couple of hours, here are the documentary’s videos:

[ part 1 | part 2]

Greg Chaitin and Sir Roger Penrose are included in this documentary, which itself makes it worth watching.