Source: http://www.google.com/patents/US6336107?dq=%22virtual+interaction+configuration%22
Timestamp: 2014-10-26 07:25:18
Document Index: 676515662

Matched Legal Cases: ['art. 4', 'art. 5', 'art. 23', 'art. 26', 'art. 33', 'art. 37']

Patent US6336107 - Method and system of automatic arrangement of composing elements - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentspast positions of a plurality of composing elements indicated by various past arrangement examples are given to each potential function corresponding to one composing element, and parameter values of the potential functions corresponding to the composing elements are automatically set on condition that...http://www.google.com/patents/US6336107?utm_source=gb-gplus-sharePatent US6336107 - Method and system of automatic arrangement of composing elementsAdvanced Patent SearchPublication numberUS6336107 B1Publication typeGrantApplication numberUS 09/124,890Publication dateJan 1, 2002Filing dateJul 30, 1998Priority dateJul 31, 1997Fee statusLapsedPublication number09124890, 124890, US 6336107 B1, US 6336107B1, US-B1-6336107, US6336107 B1, US6336107B1InventorsTomohiro Uchida, Natsuki Oka, Hiroyuki YoshimuraOriginal AssigneeMatsushita Electric Industrial Co., LtdExport CitationBiBTeX, EndNote, RefManPatent Citations (8), Non-Patent Citations (2), Referenced by (6), Classifications (5), Legal Events (6) External Links: USPTO, USPTO Assignment, EspacenetMethod and system of automatic arrangement of composing elementsUS 6336107 B1Abstract past positions of a plurality of composing elements indicated by various past arrangement examples are given to each potential function corresponding to one composing element, and parameter values of the potential functions corresponding to the composing elements are automatically set on condition that a past total potential energy obtained by solving the potential functions is minimized. Thereafter, the parameter values are given to the potential functions in which a position of any composing element is not determined, and particular positions of the composing elements are determined on condition that a total potential energy obtained by solving the potential functions is minimized. Because each potential function corresponding to one composing element has an attraction term indicating the attraction between the composing element and the other composing elements and an attraction-repulsion term indicating the setting of the composing element at a position spaced at moderate distances from the other composing elements, the particular positions of the composing elements are set in an optimum arrangement. Accordingly, the optimum arrangement of the composing elements can be automatically obtained without extracting any arrangement knowledge from a skilled person.
What is claimed is: 1. A method for automatically arranging a plurality of particular electric parts of an electric device at an optimum arrangement on a printed circuit board,
by using a plurality of past examples respectively indicating a past arrangement of a set of electric parts of the electric device, each past example of electric parts being composed of position information indicating positions of the set of electric parts and attribute information indicating attributes of the set of electric parts, also by using information indicative of a potential function including one or more parameters for indicating a potential energy of each electric part of the set of electric parts, the plurality of past examples and the information indicative of the potential function being stored in a storing unit, the method comprising the steps of: selecting a plurality of particular past examples corresponding to the plurality of particular electric parts from the past examples stored in the storing unit; automatically determining values of the one or more parameters of the potential function according to the particular past examples for each particular electric part; differentiating each of the potential functions to obtain a force exerted on each particular electric part to be arranged on the printed circuit board; changing, under calculation, a position of each particular electric part to be arranged on the printed circuit board according to the force so as to decrease a total potential energy obtained by summing up the potential energies of the particular electric parts, each potential energy of one particular electric part being obtained by determining a position of the particular electric part in one potential function; determining a particular arrangement of the particular electric parts placed at the changed positions as the optimum arrangement; and outputting information indicating the determined optimum arrangement through an outputting device. 2. An automatic arrangement method according to claim 1 in which the step of automatically determining values of one or more parameters includes the step of:
determining the values of the parameters for each particular electric part on condition that a sum of a plurality of potential energies obtained by setting positions of the particular electric parts indicated by the particular past examples to the potential functions is minimized. 3. An automatic arrangement method according to claim 1 in which the step of automatically determining values of one or more parameters includes the step of:
equalizing the values of the parameters for a first particular electric part with those for a second particular electric part in cases where one attribute of the first particular electric part is the same as that of the second particular electric part. 4. An automatic arrangement method according to claim 1 in which the step of automatically determining values of one or more parameters includes the step of:
equalizing the values of the parameters for a first particular electric part with those for a second particular electric part in cases where one attribute of the first particular electric part is similar to that of the second particular electric part. 5. A method for automatically arranging a plurality of particular electric parts of an electric device at an optimum arrangement on a printed circuit board,
by using a plurality of past examples respectively indicating a past arrangement of a set of electric parts of the electronic device, each past example being composed of past position information indicating past positions of the set of electric parts, past attribute information indicating attributes of the set of electric parts and past connection information indicating a direct connection of each electric part with other electric parts or another electric part, also by using a prototype of a total potential function indicating a total potential energy of the set of electric parts, the plurality of past examples and the information indicative of the potential function being stored in a storing unit, the method comprising the steps of: inputting particular part information of the plurality of particular electric parts, the particular part information including particular attribute information, indicating attributes of the particular electric parts, and particular connection information, indicating a direct connection of each particular electric part with at least one other particular electric part; selecting a plurality of particular past examples corresponding to the particular electric parts from the past examples stored in the storing unit, the particular past examples including particular past position information of the particular electric parts, particular past attribute information of the particular electric parts and particular past connection information of the particular electric parts; producing a total past potential function corresponding to the particular electric parts from the prototype of the total potential function according to the particular past attribute information and the particular past connection information; setting values of one or more parameters included in the total past potential function as a set of parameter values; calculating a total past potential energy of the particular electric parts from the total past potential function by giving both of: one set of parameter values to the total past potential function to determine an equation of the total past potential function; and particular past positions of the particular electric parts indicated by the particular past position information to the equation of the total past potential function to solve the equation each time the set of parameter values is set while changing the parameter values; determining a particular set of parameter values on condition that the total past potential energy calculated according to the particular set of parameter values is minimized; producing the total potential function corresponding to the particular electric parts from the prototype of the total potential function according to the particular attribute information and the particular connection information; giving the particular set of parameter values to the total potential function to determine a particular equation of the total potential function; determining a particular set of positions of the particular electric parts on condition that a particular total potential energy of the particular obtained from the particular equation of the total potential function is minimized by giving the particular set of positions to the particular equation of the total potential function; adopting a particular arrangement of the particular electric parts determined by the particular set of positions of the particular electric parts as the optimum arrangement of the particular electric parts; and outputting the adopted optimum arrangement through an outputting device. 6. An automatic arrangement method according to claim 5 in which the step of setting values of one or more parameters comprises the step of:
calculating the values of the parameters on condition that a past potential energy obtained by solving the total past potential function is minimized by giving the values of the parameters and past positions of the particular electric parts indicated by the particular past position information of the particular past examples to the total past potential function. 7. An automatic arrangement method according to claim 6 in which the step of producing a total past potential function comprises the steps of:
producing a past potential function corresponding to each particular electric part from the prototype of the total potential function according to the particular past attribute information and the particular past connection information of the particular past examples, a potential energy of each particular electric part being obtained by solving the past potential function corresponding to the particular electric part; and summing up the past potential functions corresponding to the particular electric parts to obtain the total past potential function, and the step of calculating the values of the parameters comprises the step of: calculating values of one or more parameters of each past potential function on condition that a sum of a plurality of past potential energies obtained by solving the past potential functions is minimized by giving the values of the parameters and past positions of the particular electric parts indicated by the particular past position information of the particular past examples to each past potential function. 8. An automatic arrangement method according to claim 5 in which the step of producing the total potential function comprises the steps of:
producing a potential function corresponding to each particular electric part from the prototype of the total potential function according to the particular attribute information and the particular connection information of the part information, a potential energy of each particular electric part being obtained by solving the potential function corresponding to the particular electric part; and summing up the potential functions corresponding to the particular electric parts to obtain the total potential function, and the step of setting values of one or more parameters comprises the steps of: classifying the potential functions into a plurality of groups of potential functions, a plurality of particular electric parts corresponding to a plurality of potential functions in the same group having the same attribute indicated by the particular attribute information of the particular electric parts; and setting values of one or more parameters used in each potential function on condition that the parameter values of one potential function of one group are the same as those of another potential function of the same group. 9. An automatic arrangement method according to claim 5 in which the step of producing the total potential function comprises the steps of:
producing a potential function corresponding to each particular electric part from the prototype of the total potential function according to the particular attribute information and the particular connection information of the part information, a potential energy of each particular electric part being obtained by solving the potential function corresponding to the particular electric part; and summing up the potential functions corresponding to the particular electric parts to obtain the total potential function, and the step of setting values of one or more parameters comprises the steps of: classifying the potential functions into a plurality of groups of potential functions, a plurality of particular electric parts corresponding to a plurality of potential functions in the same group having a plurality of attributes indicated by the particular attribute information of the particular electric parts, the attributes of the potential functions being similar to each other; and setting values of one or more parameters used in each potential function on condition that the parameter values of one potential function of one group are the same as those of another potential function of the same group. 10. An automatic arrangement method according to claim 5 in which the step of determining a particular set of positions comprises the steps of:
setting a position Ri(t−Δt) of each particular electric part at a time t−Δt, the symbol Δt denoting a minute time; setting a position Ri(t) of each particular electric part at a time t; giving the positions Ri(t) of the particular electric parts to the particular equation of the total potential function; solving the particular equation of the total potential function to calculate a potential energy Ei(t) of each particular electric part at a time t; calculating a position Ri(t+Δt) of each particular electric part at a time t+Δt according to an equation Ri(t+Δt)=2*Ri(t)−Ri(t−Δt)−1/m*□iEtot*(Δt)2,
the symbol □i denoting a nabla, and the symbol Etot denoting a total energy of the particular electric parts; and repeating the calculation of the positions of the particular electric parts to obtain the particular set of positions Ri(T) at a particular time T, a value of □iEtot being almost zero. 11. An automatic arrangement method according to claim 10 in which the particular part information includes initial position information indicating a plurality of initial positions Ri(0), Ri(−Δt) of the particular electric parts.
adding an attraction term to the prototype of the total potential function to express an attraction between one electric part E1 and the other electric parts E2 for each electric part E1, the total potential energy of the electric parts indicated by the attraction term decreasing as each of the electric parts E2 becomes close to the electric part E1; and adding a repulsion-attraction term to the prototype of the total potential function to express a repulsion between each electric part E1 and the other electric parts E2 not to overlap the electric part E1 with the electric parts E2 and an attraction between each electric part E1 and the other electric parts E2 not to arrange the electric parts E2 far from the electric part E1, the total potential energy of the electric parts indicated by the repulsion-attraction term decreasing as the electric parts E2 approach positions spaced at moderate distances from the electric part E1. 13. An automatic arrangement system for automatically arranging a plurality of particular electric parts of an electric device at an optimum arrangement on a printed circuit board, the system comprising:
past example storing means for storing a plurality of past examples respectively indicating a past arrangement of a set of electric parts of the electric device, each past example being composed of past position information indicating past positions of the set of electric parts, past attribute information indicating attributes of the set of electric parts and past connection information indicating a direct connection of each electric part with other electric parts or another electric part; total potential function storing means for storing a prototype of a total potential function indicating a total potential energy of the set of electric parts; element information receiving means for receiving particular part information of the plurality of particular electric parts, the particular part information being composed of particular attribute information indicating attributes of the particular electric parts and particular connection information indicating a direct connection of each particular electric part with other particular electric parts or another particular electric part; past example selecting means for selecting a plurality of particular past examples corresponding to the particular electric parts from the past examples, the particular past examples being composed of particular past position information of the particular electric parts, particular past attribute information of the particular electric parts and particular past connection information of the particular electric parts; parameter value determining means for producing a total past potential function corresponding to the particular electric parts from the prototype of the total potential function according to the particular past attribute information and the particular past connection information of the particular past examples, setting values of one or more parameters included in the total past potential function as a set of parameter values each time the parameter values are changed, determining an equation of the total past potential function by giving one set of parameter values to the total past potential function, calculating a total past potential energy of the particular electric parts from the equation of the total past potential function by giving particular past positions of the particular electric parts indicated by the particular past position information to the equation of the total past potential function each time the parameter values are changed, and determining a particular set of parameter values on condition that the total past potential energy calculated according to the particular set of parameter values is minimized; and optimum arrangement determining means for producing the total potential function corresponding to the particular electric parts from the prototype of the total potential function according to the particular attribute information and the particular connection information of the particular part information, giving the particular set of parameter values to the total potential function to determine a particular equation of the total potential function, determining a particular set of positions of the particular electric parts on condition that a particular total potential energy of the particular electric parts obtained from the particular equation of the total potential function is minimized by giving the particular set of positions to the particular equation of the total potential function, adopting a particular arrangement of the particular electric parts determined by the particular set of positions of the particular electric parts as the optimum arrangement of the particular electric parts, and outputting the adopted optimum arrangement through an outputting device. 14. An automatic arrangement system according to claim 13 in which the parameter value determining means includes:
parameter value setting means for calculating the values of the parameters on condition that a past potential energy obtained by solving the total past potential function is minimized by giving the values of the parameters and past positions of the particular electric parts indicated by the particular past position information of the particular past examples to the total past potential function. 15. An automatic arrangement system according to claim 13 in which the parameter value determining means includes:
parameter value setting means for producing a past potential function corresponding to each particular electric part from the prototype of the total potential function according to the particular past attribute information and the particular past connection information of the particular past examples and setting values of one or more parameters used in one past potential function for each particular electric part, a particular set of parameter values being determined by the parameter value determining means for each particular electric part on condition that a sum of a plurality of past potential energies obtained by solving the past potential functions is minimized in cases where the particular set of parameter values and past positions of the particular electric parts indicated by the particular past position information of the particular past examples are given to each past potential function. 16. An automatic arrangement system according to claim 13 in which the prototype of the total potential function stored in the total potential function storing means has an attraction term and a repulsion-attraction term, an attraction between one electric part E1 and the other electric parts E2 being expressed by the attraction term for each electric part E1, the total potential energy of the electric parts indicated by the attraction term decreasing as each of the electric parts E2 becomes close to the electric part E1, a repulsion between each electric part E1 and the other electric parts E2 not to overlap the electric part E1 with the electric parts E2 and an attraction between each electric part E1 and the other electric parts E2 not to arrange the electric parts E2 far from the electric part E1 being expressed by the repulsion-attraction term, and the total potential energy of the electric parts indicated by the repulsion-attraction term decreasing as the electric parts E2 approach positions spaced at moderate distances from the electric part E1.
automatically determining values of one or more parameters included in a potential function according to a past arrangement example for each electric part, the parameters indicating a potential energy of each electric part to be arranged on the printed circuit board; differentiating each potential function to obtain a force exerted on each electric part to be arranged on the printed circuit board; changing a position of each electric part to be arranged on the printed circuit board according to the force so as to decrease a total potential energy of the electric parts; and determining a particular arrangement of the electric parts placed at the changed positions as the optimum arrangement. 18. A method for automatically arranging a plurality of electric parts providing circuitry of an electric device at an optimum arrangement on a printed circuit board, comprising the steps of:
determining an arranging order of the plurality of electric parts in a first classifier system according to attributes of the electric parts and one or more connection conditions among the electric parts; determining an arranging position determining method for each electric part in the arranging order in a second classifier system according to the attributes and the connection conditions; determining an arranged position of each electric part in an arrangement area or an area surrounding the arrangement area on the printed circuit board according to the arranging position determining method determined for each electric part in the arranging order; judging in a third classifier system whether or not the change of the arranged position of each electric part is required according to the attributes and the arranged positions of the electric parts and the connection conditions among the electric parts in the arranging order; detecting a position changing method for one electric part in the third classifier system in cases where it is judged that the change of the arranged position of each electric part is required; changing the arranged position of one electric part according to the position changing method for each electric part, in cases where it is judged that the change of the arranged position is required, to determine the arranged positions of the electric parts as the optimum arrangement in the arrangement area; and outputting information indicting the determined optimum arrangement through an outputting device. 19. An automatic arrangement method according to claim 18 in which the step of determining an arranging order includes the steps of:
setting one or more attributes in a condition part of the first classifier system as a first condition rule of a first rule for each first rule; setting an arrangement priority degree in an action part of the first classifier system as a first action rule of one first rule for each first rule; activating one first rule corresponding to one first condition rule, in which the attributes agreeing with those of one electric part are set, for each electric part; detecting one arrangement priority degree set in the first action rule of the activated first rule for each electric part; and determining the arranging order of the electric parts according to the arrangement priority degrees of the electric parts. 20. An automatic arrangement method according to claim 19 in which the step of determining an arranging order further includes the step of:
changing each of the first rules respectively composed of one first condition rule and one first action rule in the first classifier system according to a genetic algorithm. 21. An automatic arrangement method according to claim 19 in which the step of determining an arranging order further includes the steps of:
producing an initial condition rule and an initial action rule of each first rule according to past arrangement examples of the electric parts; setting the initial condition rule as one first condition rule of one first rule for each first rule; setting the initial action rule as one first action rule of one first rule for each first rule; and changing each of the first rules in the first classifier system according to a genetic algorithm. 22. An automatic arrangement method according to claim 18 in which the step of determining an arranging position determining method includes the steps of:
setting one or more attributes in a condition part of the second classifier system as a second condition rule of a second rule for each second rule; setting one arranging position determining method in an action part of the second classifier system as a second action rule of one second rule for each second rule; activating one second rule corresponding to one second condition rule, in which the attributes agreeing with those of one electric part are set, for each electric part; and detecting one arranging position determining method set in the second action rule of the activated second rule for each electric part. 23. An automatic arrangement method according to claim 22 in which the step of determining an arranging position determining method further includes the step of:
changing each of the second rules respectively composed of one second condition rule and one second action rule in the second classifier system according to a genetic algorithm. 24. An automatic arrangement method according to claim 22 in which the step of determining an arranging position determining method further includes the steps of:
producing an initial condition rule and an initial action rule of each second rule according to past arrangement examples of the electric parts; setting the initial condition rule as one second condition rule of one second rule for each second rule; setting the initial action rule as one second action rule of one second rule for each second rule; and changing each of the second rules in the second classifier system according to a genetic algorithm. 25. An automatic arrangement method according to claim 18 in which the step of judging in a third classifier system includes the steps of:
setting an arrangement condition in a condition part of the third classifier system as a third condition rule of a third rule for each third rule; setting one judgement about a position change and one position changing method in an action part of the third classifier system as a third action rule of one third rule for each third rule; preparing a particular arrangement condition of one electric part according to the attributes and arranged position of the electric part and the arrangement area for each electric part; activating one third rule corresponding to one third condition rule, in which the arrangement condition agreeing with one particular arrangement condition of one electric part is set, for each electric part; and detecting one judgement about a position change and one position changing method set in the third action rule of the activated third rule for each electric part. 26. An automatic arrangement method according to claim 25 in which the step of judging in a third classifier system further includes the step of:
changing each of the third rules respectively composed of one third condition rule and one third action rule in the third classifier system according to a genetic algorithm. 27. An automatic arrangement method according to claim 25 in which the step of judging in a third classifier system further includes the steps of:
producing an initial condition rule and an initial action rule of each third rule according to past arrangement examples of the electric parts; setting the initial condition rule as one third condition rule of one third rule for each third rule; setting the initial action rule as one third action rule of one third rule for each third rule; and changing each of the third rules in the third classifier system according to a genetic algorithm. 28. An automatic arrangement method according to claim 18 in which the step of determining an arranging order includes the steps of:
setting one or more attributes in a condition part of the first classifier system as a first condition rule of a first rule for each first rule; setting an arrangement priority degree in an action part of the first classifier system as a first action rule of one first rule for each first rule; setting a fitness value to each first rule of the first classifier system; activating one or more first rules corresponding to one or more first condition rules, in which the attributes agreeing with those of one electric part are set, for each electric part; selecting a particular first rule from the activated first rules at a selection probability proportional to the fitness value of the particular first rule for each electric part; detecting one arrangement priority degree set in the first action rule of the particular first rule for each electric part; and determining the arranging order of the electric parts according to the arrangement priority degrees of the electric parts. 29. An automatic arrangement method according to claim 28 in which the step of determining an arranging order further includes the step of:
adjusting each of the fitness values set to the first rules in the first classifier system according to a reinforcement learning. 30. An automatic arrangement method according to claim 28 in which the step of determining an arranging order includes the steps of:
producing an initial fitness value of each first rule according to past arrangement examples of the electric parts; setting the initial fitness value as one fitness value of one first rule for each first rule; and adjusting each of the fitness values in the first classifier system according to a reinforcement learning. 31. An automatic arrangement method according to claim 28 in which the step of determining an arranging order further includes the steps of:
changing each of the first rules respectively composed of one first condition rule and one first action rule in the first classifier system according to a genetic algorithm; and adjusting each of the fitness values set to the first rules in the first classifier system according to a reinforcement learning. 32. An automatic arrangement method according to claim 18 in which the step of determining an arranging position determining method includes the steps of:
setting one or more attributes in a condition part of the second classifier system as a second condition rule of a second rule for each second rule; setting one arranging position determining method in an action part of the second classifier system as a second action rule of one second rule for each second rule; setting a fitness value to each second rule of the second classifier system; activating one or more second rules corresponding to one or more second condition rules, in which the attributes agreeing with those of one electric part are set, for each electric part; selecting a particular second rule from the activated second rules at a selection probability proportional to the fitness value of the particular second rule for each electric part; and detecting one arranging position determining method set in the second action rule of the particular second rule for each electric part. 33. An automatic arrangement method according to claim 32 in which the step of determining an arranging position determining method further includes the steps of:
producing an initial fitness value of each second rule according to past arrangement examples of the electric parts; setting the initial fitness value as one fitness value of one second rule for each second rule; and adjusting each of the fitness values in the second classifier system according to a reinforcement learning. 34. An automatic arrangement method according to claim 32 in which the step of determining an arranging position determining method further includes the step of:
adjusting each of the fitness values set to the second rules in the second classifier system according to a reinforcement learning. 35. An automatic arrangement method according to claim 32 in which the step of determining an arranging position determining method further includes the steps of:
changing each of the second rules respectively composed of one second condition rule and one second action rule in the second classifier system according to a genetic algorithm; and adjusting each of the fitness values set to the second rules in the second classifier system according to a reinforcement learning. 36. An automatic arrangement method according to claim 18 in which the step of judging in a third classifier system includes the steps of:
setting an arrangement condition in a condition part of the third classifier system as a third condition rule of a third rule for each third rule; setting one judgement about a position change and one position changing method in an action part of the third classifier system as a third action rule of one third rule for each third rule; setting a fitness value to each third rule of the third classifier system; preparing a particular arrangement condition of one electric part according to the attributes and arranged position of the electric part and the arrangement area for each electric part; activating one or more third rules corresponding to one or more third condition rules, in which the arrangement condition agreeing with one particular arrangement condition of one electric part is set, for each electric part; selecting a particular third rule from the activated third rules at a selection probability proportional to the fitness value of the particular third rule for each electric part; and detecting one judgement about a position change and one position changing method set in the third action rule of the particular third rule for each electric part. 37. An automatic arrangement method according to claim 36 in which the step of judging in a third classifier system includes the steps of:
producing an initial fitness value of each third rule according to past arrangement examples of the electric parts; setting the initial fitness value as one fitness value of one third rule for each third rule; and adjusting each of the fitness values in the third classifier system according to a reinforcement learning. 38. An automatic arrangement method according to claim 36 in which the step of judging in a third classifier system further includes the step of:
adjusting each of the fitness values set to the third rules in the third classifier system according to a reinforcement learning. 39. An automatic arrangement method according to claim 36 in which the step of judging in a third classifier system further includes the steps of:
changing each of the third rules respectively composed of one third condition rule and one third action rule in the third classifier system according to a genetic algorithm; and adjusting each of the fitness values set to the third rules in the third classifier system according to a reinforcement learning. 40. An automatic arrangement method according to claim 18 in which the step of changing the arranged position includes the steps of:
producing an evaluation value according to the arranged positions of the electric parts and the arrangement area; judging that the arranged positions of the electric parts are set in an optimum arrangement in cases where the evaluation value is equal to or lower than a reference value; judging that the arranged positions of the electric parts are not set in an optimum arrangement in cases where the evaluation value is higher than the reference value; revising the first, second and third classifying systems according to a genetic algorithm or a reinforcement learning to produce a revised evaluation value equal to or lower than the reference value. 41. An automatic arrangement system for automatically arranging a plurality of electric parts providing circuitry of an electric device at an optimum arrangement on a printed circuit board, the system comprising:
element information receiving means for receiving element information indicating the plurality of electric parts; electric part storing means for storing one or more attributes of each electric part received by the element information receiving means; electric part arranging order determining means, having a first classifier system, for determining an arranging order of the received electric parts in the first classifier system according to the attributes of the electric parts; arranging position determining means, having a second classifier system, for determining an arranging position determining method for each electric part in the arranging order of the electric parts in the second classifier system according to the attributes and determining an arranged position of each electric part in an arrangement area or an area surrounding the arrangement area on the printed circuit board according to the arranging position determining method; arranged position change judging means, having a third classifier system, for judging in the third classifier system whether or not the change of the arranged position of each electric part is required according to the attributes and the arranged positions of the electric parts and producing a position changing method for one electric part in the third classifier system in cases where it is judged that the change of the arranged position of each electric part is required; electric part arranging means for changing the arranged position of one electric part according to the position changing method, in cases where it is judged in the third classifier system that the change of the arranged position of each electric part is required, to determine the arranged positions of the electric parts as the optimum arrangement in the arrangement area; and outputting means for outputting information indicating the determined optimum arrangement through an outputting device. 42. An automatic arrangement system according to claim 41 in which the first classifier system of the electric part arranging order determining means comprises a plurality of first rules respectively corresponding to one electric part, wherein each first rule of one electric part comprises:
a first condition rule for indicating a group of one or more attributes of the electric part, a plurality of particular first rules of a plurality of particular first condition rules, which indicate a plurality of groups of attributes of the electric parts received by the part information receiving means, being activated; and a first action rule for indicating an arrangement priority degree of the electric part, the arranging order of the electric parts being determined according to the arrangement priority degrees indicated by a plurality of particular first action rules of the particular first rules. 43. An automatic arrangement system according to claim 42, further comprising:
first learning means for performing the learning of the first classifier system to change each of the first rules according to a genetic algorithm. 44. An automatic arrangement system according to claim 42, further comprising:
initial rule producing means for producing an initial condition rule and an initial action rule of each first rule according to past arrangement examples of the electric parts, setting the initial condition rule as one first condition rule of one first rule for each first rule, setting the initial action rule as one first action rule of one first rule for each first rule; and learning means for performing the learning of the first classifier system to change each of the first rules in the first classifier system according to a genetic algorithm. 45. An automatic arrangement system according to claim 41 in which the second classifier system of the arranging position determining means comprises a plurality of second rules respectively corresponding to one electric part, wherein each second rule of one electric part comprises:
a second condition rule for indicating a group of one or more attributes of the electric part, a particular second rule of a particular second condition rule, which indicates a particular group of attributes of one electric part, being activated for each electric part in the arranging order of the electric parts; and a second action rule for indicating one arranging position determining method applied for the electric part, the arranging position determining method indicated by a particular second action rule of one activated particular second rule being determined for each electric part in the arranging order of the electric parts. 46. An automatic arrangement system according to claim 45, further comprising:
learning means for performing the learning of the second classifier system to change each of the second rules according to a genetic algorithm. 47. An automatic arrangement system according to claim 45, further comprising:
initial rule producing means for producing an initial condition rule and an initial action rule of each second rule according to past arrangement examples of the electric parts, setting the initial condition rule as one second condition rule of one second rule for each second rule, setting the initial action rule as one second action rule of one second rule for each second rule; and learning means for performing the learning of the second classifier system to change each of the second rules in the second classifier system according to a genetic algorithm. 48. An automatic arrangement system according to claim 41 in which the third classifier system of the arranged position change judging means comprises a plurality of third rules respectively corresponding to one electric part, wherein each third rule of one electric part comprises:
a third condition rule for indicating an arrangement condition of the electric part, a particular third rule of a particular third condition rule, which indicates a particular arrangement condition of one electric part, being activated for each electric part in the arranging order of the electric parts; and a third action rule for indicating one judgement about a position change and one position changing method applied for the electric part, a position change of one electric part being judged according to the judgement about a position change indicated by a particular third action rule of one activated particular third rule, and the position changing method indicated by the particular third action rule being produced for each electric part in the arranging order of the electric parts. 49. An automatic arrangement system according to claim 48, further comprising:
learning means for performing the learning of the third classifier system to change each of the third rules according to a genetic algorithm. 50. An automatic arrangement system according to claim 48, further comprising:
initial rule producing means for producing an initial condition rule and an initial action rule of each third rule according to past arrangement examples of the electric parts, setting the initial condition rule as one third condition rule of one third rule for each third rule, setting the initial action rule as one third action rule of one third rule for each third rule; and learning means for performing the learning of the third classifier system to change each of the third rules in the third classifier system according to a genetic algorithm. 51. An automatic arrangement system according to claim 41, further comprising:
evaluation value calculating means for calculating an evaluation value from the arranged positions of the electric parts determined by the electric part arranging means and the arrangement area; control means for judging whether or not the learning of the first, second and third classifier systems is required according to the evaluation value calculated by the evaluation value calculating means; and learning means for revising the first, second and third classifier systems according to a genetic algorithm or a reinforcement learning. 52. An automatic arrangement system according to claim 41 in which the first classifier system of the electric part arranging order determining means comprises a plurality of first rules respectively corresponding to one electric part, wherein each first rule of one electric part comprises:
a first condition rule for indicating a group of one or more attributes of the electric part, one or more first rules of one or more first condition rules, which indicate the same group of attributes of each electric part received by the part information receiving means, being activated; a first action rule for indicating an arrangement priority degree of the electric part, one or more arrangement priority degrees of one or more first action rules of the activated first rules being selected for each electric part; and a fitness value for indicating the fitness of the electric part, a particular first rule being selected from the activated first rules at a selection probability proportional to the fitness value of the particular first rule for each electric part, and the arranging order of the electric parts being determined according to the arrangement priority degrees indicated by a plurality of particular first action rules of the particular first rules. 53. An automatic arrangement system according to claim 52 further comprising:
first learning means for performing the learning of the first classifier system to adjust each of the fitness values of the first rules according to a reinforcement learning. 54. An automatic arrangement system according to claim 41 in which the second classifier system of the arranging position determining means comprises a plurality of second rules respectively corresponding to one electric part, wherein each second rule of one electric part comprises:
a second condition rule for indicating a group of one or more attributes of the electric part, one or more second rules of one or more second condition rules, which indicate the same particular group of attributes of one electric part, being activated for each electric part in the arranging order of the electric parts; a second action rule for indicating one arranging position determining method applied for the electric part; and a fitness value for indicating the fitness of the electric part, a particular second rule being selected from the activated second rules at a selection probability proportional to the fitness value of the particular second rule for each electric part, and the arranging position determining method indicated by a particular second action rule of the particular second rule being determined for each electric part in the arranging order of the electric parts. 55. An automatic arrangement system according to claim 54 further comprising:
second learning means for performing the learning of the second classifier system to adjust each of the fitness values of the second rules according to a reinforcement learning. 56. An automatic arrangement system according to claim 41 in which the third classifier system of the arranged position change judging means comprises a plurality of third rules respectively corresponding to one electric part, wherein each third rule of one electric part comprises:
a third condition rule for indicating an arrangement condition of the electric part, one or more third rules of one or more third condition rules, which indicate the same particular arrangement condition of one electric part, being activated for each electric part in the arranging order of the electric parts; and a third action rule for indicating one judgement about a position change and one position changing method applied for the electric part; and a fitness value for indicating the fitness of the electric part, a particular third rule being selected from the activated third rules at a selection probability proportional to the fitness value of the particular third rule for each electric part, a position change of one electric part being judged according to the judgement about a position change indicated by a particular third action rule of the activated particular third rule, and the position changing method indicated by the particular third action rule being produced for each electric part in the arranging order of the electric parts. 57. An automatic arrangement system according to claim 56 further comprising: learning means for performing the learning of the third classifier system to adjust each of the fitness values of the third rules according to a reinforcement learning.
determining an arranging order of the plurality of electric parts in a first classifier system according to attributes of the electric pars and one or more connection conditions among the electric parts; determining an arranging position determining method for each electric part in the arranging order in a second classifier system according to the attributes and the connection conditions; determining an arranged position of each electric part in an arrangement area or an area surrounding the arrangement area on the printed circuit board according to the arranging position determining method determined for each electric part in the arranging order; judging in a third classifier system whether or not the change of the arranged position of each electric part is required according to the attributes and the arranged positions of the electric parts and the connection conditions among the electric parts in the arranging order; detecting a position changing method for one electric part in the third classifier system in cases where it is judged that the change of the arranged position of each electric part is required; and changing the arranged position of one electric part according to the position changing method for each electric part, in cases where it is judged that the change of the arranged position is required, to determine the arranged positions of the electric parts as the optimum arrangement in the arrangement area. 59. A method for automatically arranging a plurality of particular composing elements at an optimum arrangement in an enclosed field, comprising the steps of:
preparing a plurality of past examples in a storing unit, the past examples respectively indicating a past arrangement of a set of composing elements, each past example of composing elements being composed of position information indicating positions of the set of composing elements and attribute information indicating attributes of the set of composing elements; also preparing in the storing unit information indicative of a potential function including one or more parameters for indicating a potential energy of each composing element of the set of composing elements; selecting a plurality of particular past examples corresponding to a plurality of particular composing elements from the past examples stored in the storing unit; automatically determining values of the one or more parameters of the potential function according to the particular past examples for each particular composing element; differentiating each of the potential functions to obtain a force exerted on each particular composing element to be arranged in the enclosed field; changing, under calculation, a position of each particular composing element to be arranged in the enclosed field according to the force so as to decrease a total potential energy obtained by summing up the potential energies of the particular composing elements, each potential energy of one particular composing element being obtained by determining a position of the particular composing element in one potential function; determining a particular arrangement of the particular composing elements placed at the changed positions as the optimum arrangement; and outputting the determined optimum arrangement through an outputting device. 60. A method for automatically arranging a plurality of particular composing elements at an optimum arrangement in an enclosed field, comprising the steps of:
preparing a plurality of past examples in a storing unit, the past examples respectively indicating a past arrangement of a set of composing elements, each past example being composed of past position information indicating past positions of the set of composing elements, past attribute information indicating attributes of the set of composing elements and past connection information indicating a direct connection of each composing element with other composing elements or another composing element; also preparing in the storing unit a prototype of a total potential function indicating a total potential energy of the set of composing elements; inputting particular element information of the plurality of particular composing elements, the particular element information including particular attribute information, indicating attributes of the particular composing elements, and particular connection information, indicating a direct connection of each particular composing element with at least one other particular composing element; selecting a plurality of particular past examples corresponding to the particular composing elements from the past examples stored in the storing unit, the particular past examples including particular past position information of the particular composing elements, particular past attribute information of the particular composing elements and particular past connection information of the particular composing elements; producing a total past potential function corresponding to the particular composing elements from the prototype of the total potential function according to the particular past attribute information and the particular past connection information; setting values of one or more parameters included in the total past potential function as a set of parameter values; calculating a total past potential energy of the particular composing elements from the total past potential function by giving both of: one set of parameter values to the total past potential function to determine an equation of the total past potential function; and particular past positions of the particular composing elements indicated by the particular past position information to the equation of the total past potential function to solve the equation each time the set of parameter values is set while changing the parameter values; determining a particular set of parameter values on condition that the total past potential energy calculated according to the particular set of parameter values is minimized; producing the total potential function corresponding to the particular composing elements from the prototype of the total potential function according to the particular attribute information and the particular connection information; giving the particular set of parameter values to the total potential function to determine a particular equation of the total potential function; determining a particular set of positions of the particular composing elements on condition that a particular total potential energy of the particular composing elements obtained from the particular equation of the total potential function is minimized by giving the particular set of positions to the particular equation of the total potential function; adopting a particular arrangement of the particular composing elements determined by the particular set of positions of the particular composing elements as the optimum arrangement of the particular composing elements; and outputting the adopted optimum arrangement through an outputting device.
2.1. PREVIOUSLY PROPOSED ART As an example of the automatic parts arrangement system, an automatic parts arrangement system (H. Yoshimura, S. Miura �Approach from Artificial Intelligence to CAD of the PCB Design� the 10th Annual Conference of JSAI, 1996) is known. In this system, knowledge of composing parts arrangement is extracted from a skilled person by interviewing with the skilled person, the extracted knowledge is reflected on the automatic parts arrangement system, and a plurality of composing parts are automatically arranged on a PCB.
Also, a published unexamined Japanese Patent Application No. H5-342290 �METHOD AND DEVICE FOR ARRANGING ELEMENTS� is disclosed. In this application, attraction and repulsion occurring between elements are calculated, and the position of each element is changed for each minute time according to a sum of the attraction and the repulsion.
2.2. PROBLEMS TO BE SOLVED BY THE INVENTION However, even though a plurality of composing parts are automatically arranged on a PCB while reflecting knowledge extracted from a skilled person on the automatic parts arrangement system, there is a problem that the arrangement of the composing parts satisfying the skilled person cannot be always obtained. That is, the skilled person has knowledge unconsciously used as well as knowledge consciously used, the knowledge consciously used cannot be extracted by interviewing with the skilled person, so that the knowledge extracted from the skilled person are not sufficient to appropriately arrange the composing parts on the PCB. In particular, because a density of wirings on the PCB and a density of parts attached on the printing substrate have been recently heightened, there is little space between the composing parts on the PCB, it is required that the skilled person performs the trial and error operation many times to appropriately arrange the composing parts on the PCB. Therefore, the knowledge of the skilled person has been more complicated, so that the extraction of the knowledge from the skilled person becomes more difficult. As a result, the composing parts cannot be appropriately arranged on the PCB in a conventional automatic arrangement system according to a conventional automatic arrangement method performed by extracting the knowledge of the parts arrangement from the skilled person.
SUMMARY OF THE INVENTION An object of the present invention is to provide, with due consideration to the drawbacks of such a conventional automatic arrangement method and a conventional automatic arrangement system, an automatic arrangement method and an automatic arrangement system in which positions of a plurality of composing elements are automatically set in an optimum (or appropriate) arrangement without extracting knowledge of element arrangement from a skilled person.
FIG. 3 shows the relationship between the distance rij and a potential energy Eij of the electronic part Pifor each electronic part Pj; FIG. 4 is a block diagram of a computer system for performing the automatic arrangement method according to the first embodiment;
DETAILED DESCRIPTION OF THE EMBODIMENTS Preferred embodiments of an automatic arrangement method and an automatic arrangement system according to the present invention are described with -reference to the drawings.
(First Embodiment) FIG. 1 is a block diagram of an automatic arrangement system according to a first embodiment of the present invention.
In a step S102, a prototype of a total potential function Etot composed of a plurality of prototypes of potential functions Ei corresponding to a plurality of electronic parts Pi is stored in the storing unit 12 to calculate a total potential energy Etot which is obtained by determining a plurality of potential functions Ei corresponding to the electronic parts Pi from the prototypes of potential functions Ei, calculating a plurality of potential energies Ei corresponding to the electronic parts Pi by solving the potential functions Ei and summing the potential energies Ei. The prototype of functions Etot and Ei are expressed as follows. E tot = ∑ i  E   i ( 1 ) E   i = 1 / 2 * α i * ∑ j ≠ i  ( Net ij * r ij ) + 1 / 2 * β i * ∑ j ≠ i  { ( γ i / r ij ) 12 - ( γ i / r ij ) 6 } ( 2 ) Each prototype of the potential function corresponds to one electronic part Pi, the symbol rij denotes a distance between the center of the electronic part Pi and the center of another electronic part Pj connected with the electronic part Pi, and the symbols αi, βi and γi denote parameters for the electronic part Pi.
A position (or coordinates) of each electronic part Pi at a time t is expressed by a position vector Ri(t). A Taylor expansion is performed around the time t for position vectors Ri(t�Δt) of each electronic part Pi at a time t+Δt and a time t−Δt, and the terms higher than the third order are omitted in Taylor-expanded position vectors Ri(t�Δt) because Δt is sufficiently small. Therefore, a following equation
Ri(t�Δt)=Ri(t)�dRi(t)/dt*Δt+�*d2Ri(t)/dt2*(Δt)2 is obtained for each electronic part Pi. The symbol Δt denotes a minute time, the symbol d/dt denotes a differentiation by time, and the symbol d2/dt2 denotes a quadratic differentiation by time. Therefore,
Ri(t+Δt)+Ri(t−Δt)=2*Ri(t)+d2Ri(t)/dt2*(Δt)2 is obtained for each electronic part Pi. Therefore, the position Ri(t+Δt) of the electronic part Pi at the time t+Δt is expressed as follows.
Ri(t+Δt)=2*Ri(t)−Ri(t−Δt)+d2Ri(t)/dt2*(Δt)2 A vector Fi of force exerting on the electronic part Pi placed in a position Ri(t)=(xi,yi,zi,t) of the potential field at the time t is expressed as follows. Fi =  m * d 2  R i  ( t ) / d   t 2 =  - ∇ i  E tot The symbol m denotes a weight of the electronic part Pi, and the symbol ∇i denotes a nabla (δ/δx,δ/δy,δ/δz). Therefore, the above equation is rewritten as follows.
Ri(t+Δt)=2*Ri(t)−Ri(t−Δt)−1/m*∇iEtot*(Δt)2 Therefore, after the positions Ri(t) and Ri(t−Δt) of the electronic part Pi at the time t and the time t−Δt are determined, the position Ri(t+Δt) of the electronic part Pi at the time t+Δt can be determined by differentiating the potential energy Etot of the electronic part Pi. In other words, because the positional vectors Ri(0) of the particular electronic parts Pi are input as an initial arrangement of the particular electronic parts in the step S103 and the initial potential energies Ei(xi,yi,zi,0) of the particular electronic parts Pi can be calculated, a positional vector Ri(Δt) of each particular electronic part Pi is expressed as follows.
Ri(Δt)=Ri(0)−1/m*∇iEtot*(Δt)2 Here, Ri(O)=Ri(−Δt) is assumed. Therefore, the positional vector Ri(t) of each particular electronic part Pi at an arbitrary time t=Np*Δt (Np is the position changing number expressed by a positive integer) can be determined. It is preferred that positions of the particular electronic parts Pi at the time Δt be input to the receiving unit 13 as the positional vectors Ri(−Δt).
(Second Embodiment) In this embodiment, positions of a plurality of composing elements are set in an optimum arrangement according to the concept of a classifier system using a genetic algorithm and a reinforcement learning. Therefore, the concept of a classifier system, the concept of the genetic algorithm and the concept of the reinforcement learning are described prior to the description of a second embodiment.
A classifier system is one type of adaptive computing system proposed by John Holland. As shown in FIG. 5A, the classifier system fundamentally comprises a set of classifiers and a list of messages attached to the set of classifiers. Each classifier is composed of a condition part and an action part. In cases where the classifier system is expressed by words used in a production system, the classifier corresponds to a rule, and the message list corresponds to a working memory for temporarily storing an input condition (or an input message). Information indicating fitness (or strength) is normally attached to each classifier (or rule) of the classifier system. In the classifier system, a coded input condition (for example, �1110�) is compared with each of codes (or coded messages such as �11**�, 0011�, �01**� and �**11�, the symbol �*� denotes an arbitrary binary digit) of the classifiers in the condition part prepared in advance. In cases where the coded input condition agrees with the code �11**� of a particular classifier (No.1), the particular classifier (or particular rule) is activated, and the code �0011� of the action part of the particular classifier is output. Thereafter, a result of the action of the action part is evaluated. In cases where an evaluation value is enhanced more than a reference value, a fitness value is renewed. To renew the fitness value, a reinforcement learning is often used.
Also, in the classifier system, each rule (or each classifier) is generally changed according to a genetic algorithm. A classifier system using the genetic algorithm is disclosed in U.S. Pat. No. 4,881,178 and a literature (E. Kitano, �Genetic Algorithm�, 1993). A learning method of the classifier system using the genetic algorithm disclosed in the above U.S.P and literature is roughly described.
(1) The fitness value of one rule (or one classifier), which is activated because an input condition (or an input message) agrees with a message of the condition part of the rule, is reduced by a value proportional to the fitness value. For example, as shown in FIG. 5C, because an input condition �1110� agrees with a message �11**� of the condition part of the rule No.1, the rule is activated, the fitness value 100 of the rule is reduced by a value 100*Ctax proportional to a tax Ctax=0.1.
(2) A value, which is reduced from a fitness value in a current step, is added to a fitness value of a rule adopted (or activated) in a step just before the current step. For example, as shown in FIG. 5D, in cases where the rule No.1 is activated in a preceding step, a message �0011� of the action part of the rule No.1 is output, the rule No.2 and the rule No.4 are activated in a current step because a message �0011� of the condition part of the rule No.2 and a message �**11� of the condition part of the rule No.4 respectively agree with the message �0011�, the fitness of the rule No.2 and the fitness of the rule No.4 are respectively reduced by a value 100*Cbid proportional to a bid Cbid=0.1, and the reduced value of the rule No.2 and the reduced value 10 of the rule No.4 are added to the value 90 of the fitness of the rule No.1.
In the step S210, the rules of the first, second and third classifier systems are changed according to the genetic algorithm, and the fitness values of the rules are adjusted according to the reinforcement learning, and the changed rules and the adjusted fitness values are stored in the memory 63. For example, as shown in FIG. 10B, in cases where the first rule R11 �13112210� defined as the combination of the first condition rule Rc11 �1311221� and the first action rule Ra11 �0� and the first rule R14 �15111*21� defined as the combination of the first condition rule Rc14 �15111*2� and the first action rule Ra14 �1� are changed by performing the crossover for the first rules R11 and R14 with each other, a crossing position is determined for each of the first rules R11 and R14, and the first rules R11 and R14 are crossed with each other to produce a changed first rule R11 �13111*21� and a changed first rule R14 �15112210�. Therefore, a changed first condition rule Rc11 �13111*2�, a changed first action rule Ra11 �1�, a changed first condition rule Rc14 �1511221�, and a changed first action rule Ra14 �0� are obtained.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4881178May 7, 1987Nov 14, 1989The Regents Of The University Of MichiganMethod of controlling a classifier systemUS4935877 *May 20, 1988Jun 19, 1990Koza John RNon-linear genetic algorithms for solving problemsUS5140530 *Mar 28, 1989Aug 18, 1992Honeywell Inc.Genetic algorithm synthesis of neural networksUS5343554 *May 11, 1992Aug 30, 1994John R. KozaNon-linear genetic process for data encoding and for solving problems using automatically defined functionsUS5434796 *Jun 30, 1993Jul 18, 1995Daylight Chemical Information Systems, Inc.Method and apparatus for designing molecules with desired properties by evolving successive populationsUS5867397 *Feb 20, 1996Feb 2, 1999John R. KozaMethod and apparatus for automated design of complex structures using genetic programmingUS5897628 *Sep 10, 1996Apr 27, 1999Sony CorporationCircuit designing method and circuit designing deviceJPH05342290A Title not available* Cited by examinerNon-Patent CitationsReference1"Approach from Artificial Intelligence to CAD of the Printed Circuit Board Design" by Yoshimura et al; The 10th Annual Conference of JSAI, 1996; pp., 1-15 (w/partial English translation).2"Genetic Algorithm" by Akihiro Kitano; first version published Jun. 3, 1993 (w/partial English translation).Referenced byCiting PatentFiling datePublication dateApplicantTitleUS7089173 *Mar 30, 2001Aug 8, 2006Altera CorporationHardware opencore evaluationUS7127436 *Mar 18, 2002Oct 24, 2006Motorola, Inc.Gene expression programming algorithmUS7676355Mar 10, 2006Mar 9, 2010Altera CorporationMethod and apparatus for providing protected intellectual propertyUS8200472Jan 20, 2010Jun 12, 2012Altera CorporationMethod and apparatus for providing protected intellectual propertyUS8566616Sep 10, 2004Oct 22, 2013Altera CorporationMethod and apparatus for protecting designs in SRAM-based programmable logic devices and the likeUS8612772Jul 20, 2006Dec 17, 2013Altera CorporationSecurity core using soft key* Cited by examinerClassifications U.S. Classification706/13, 706/12International ClassificationG06F17/50Cooperative ClassificationG06F17/5072European ClassificationG06F17/50L1Legal EventsDateCodeEventDescriptionFeb 18, 2014FPExpired due to failure to pay maintenance feeEffective date: 20140101Jan 1, 2014LAPSLapse for failure to pay maintenance feesAug 9, 2013REMIMaintenance fee reminder mailedJun 3, 2009FPAYFee paymentYear of fee payment: 8Jun 7, 2005FPAYFee paymentYear of fee payment: 4Jul 30, 1998ASAssignmentOwner name: MATSUSHITA ELECTRIC INDUSTRIAL CO., LTD., JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:UCHIDA, TOMOHIRO;OKA, NATSUKI;YOSHIMURA, HIROYUKI;REEL/FRAME:009362/0659Effective date: 19980724RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google