Data processing: artificial intelligence – Machine learning – Genetic algorithm and genetic programming system
Reexamination Certificate
1999-04-05
2002-11-26
Black, Thomas (Department: 2121)
Data processing: artificial intelligence
Machine learning
Genetic algorithm and genetic programming system
C706S062000
Reexamination Certificate
active
06487544
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to the field of configuring lines of complex industrial robots, especially the so-called pick and place machines, using incomplete search techniques.
2. Related Art
The invention is an improvement on U.S. Pat. No. 5,390,283 (“283”) and U.S. Pat. No. 5,864,833 (“833”), both of which are incorporated herein by reference.
Multiple head pick and place machines present a nearly intractable combinatorial problem, because there are so many layout options—what with multiple pickup nozzles, pipette modules, gripper types, feeders, trays, and so forth. It is desirable to choose the proper combination of options, so that part placement is conducted as quickly as possible, but searching all the options is impractical. Accordingly, an incomplete search of the space of layouts is undertaken.
'283 teaches creating a layout, a.k.a. configuration, for a single pick and place machine using an incomplete search technique known as a genetic algorithm (“GA”) in combination with a heuristic layout generator (“HLG”) to generate the layout. A form of GA known as CHC is preferred. The GA uses a population of chromosome strings, each containing genes that influence the HLG. The GA crosses over and mutates the population, and causes elimination of unfit individuals, in a simulation of the biological process of evolution. The HLG attempts to translate each chromosome string into an actual layout and then evaluates how good that layout or partial layout is. The quality assessment by the HLG is used in each subsequent iteration of the GA to determine which chromosome strings live or die.
The GA is a technique that generally requires a great deal of experimentation to apply to a particular problem. A chromosome string format representing a problem solution needs to be developed. Then the format must be tested by multiple applications of the GA, testing the results each time, to see if the format repeatedly results in convergence towards an improved solution. Typically several string formats must be tested prior to selection of a preferred one. It is not usually possible to predict what format will work for a given problem, especially if that problem is not simple.
'833 refines the techniques of '283 for lines of at least two pick and place machines of different types. '833 adopts a chromosome string which represents a unified layout for the entire line and then uses a GA and an HLG to find layout solutions for the line. '833's preferred embodiment shows a line of two machines of different types, a Philips FCM and a Philips ACM.
SUMMARY OF THE INVENTION
The object of the present invention is to improve the techniques of '833.
This object is achieved by modularizing the chromosome string and the HLG. In particular, the allocation of part types to machine types is carried out in a separate step from the rest of the layout generation.
REFERENCES:
patent: 4697242 (1987-09-01), Holland et al.
patent: 4821333 (1989-04-01), Gillies
patent: 4935877 (1990-06-01), Koza
patent: 5048095 (1991-09-01), Koza et al.
patent: 5136686 (1992-08-01), Koza
patent: 5148513 (1992-09-01), Koza et al.
patent: 5222192 (1993-06-01), Shaefer
patent: 5255345 (1993-10-01), Shaefer
patent: 5343554 (1994-08-01), Koza et al.
patent: 5390282 (1995-02-01), Koza et al.
patent: 5390283 (1995-02-01), Eshelman et al.
patent: 5864833 (1999-01-01), Schaffer et al.
patent: 09097246 (1997-08-01), None
patent: 10209681 (1998-07-01), None
Combinations of genetic algorithms and neural networks: a survey of the state of the art, Schaffer, J.D.; Whitley, D.; Eshelman, L.J. Combinations of Genetic Algorithms and Neural Networks, 1992., COGANN-92. International Workshop (1992) pps. 1-37.
Eshelman Larry J.
Schaffer J. David
Black Thomas
Holmes Michael B.
Koninlijke Philips Electronics N.,V.
Waxler Aaron
LandOfFree
Method for optimizing a line of pick and place machines does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for optimizing a line of pick and place machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for optimizing a line of pick and place machines will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2937815