Method for determining a sequence for drilling holes according to a pattern using global and local optimization

• US 9,703,915 B2
• Filed: 07/24/2014
• Issued: 07/11/2017
• Est. Priority Date: 07/24/2014
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Garaas, Tyler, Brand, Matthew
• Primary Examiner(s): Hill, Stanley K
• Assistant Examiner(s): Chubb, Mikayla
• Application Number:
  US14/339,877
• Publication Number:
  US 20160026747A1
• Time in Patent Office: 1,083 Days
• Field of Search: None
• CPC Class Codes: B23K 26/02 Positioning or observing the workpiece, e.g. with respect to the point of impact; Aligning, aiming or focusing the laser beam
• CPC Class Codes: B23K 26/38 by boring or cutting
• CPC Class Codes: G05B 19/4093 characterised by part programming, e.g. entry of geometrical information as taken from a technical drawing, combining this with machining and material information to obtain control information, named part programme, for the NC machine
• CPC Class Codes: G05B 19/40937 concerning programming of machining or material parameters, pocket machining
• CPC Class Codes: G05B 2219/34112 TSP traveling sales problem, SOM self organizing map for tool path
• CPC Class Codes: G05B 2219/45139 Laser drilling
• CPC Class Codes: G05B 2219/49363 Minimalize time for tool movement between different positions, holes
• CPC Class Codes: G06F 2111/06 Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
• CPC Class Codes: G06F 2119/18 Manufacturability analysis or optimisation for manufacturability
• CPC Class Codes: G06F 30/398 Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] optical proximity correction [OPC] design processes G03F1/36
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]

Abstract

A method determines a sequence for drilling holes in a workpiece according to a pattern by first partitioning the holes in the pattern into packets. A global sequence of the packets is determined by solving a global traveling salesman problem (TSP), and a local sequence of the holes in each packet is determined by solving a local TSP for each packet. Then, the local sequences of the holes are joined according to the global sequence of the packets to determine a complete sequence for drilling the holes.

Claims

1. A method for determining a sequence of drilling holes in a workpiece according to a pattern, wherein the pattern is partitioned into packets and the holes are drilled by a drilling machine, comprising:

determining a global sequence of the packets by solving a global traveling salesman problem (TSP);

determining a local sequence of the holes in each packet by solving a local TSP for each packet;

joining the local sequences of the holes according to the global sequence of the packets to determine a complete sequence of drilling the holes by a drilling machine; and

adapting the partitioning to equalize a density of the holes in each packet, wherein the steps are performed in a processor.

2. The method of claim 1, further comprising:

adapting the partitioning to make use of repetitive subpatterns of the holes.

3. The method of claim 1, wherein the global TSP is solved using a global graph, wherein vertices represent a set of candidate starting points (SPs), a set of candidate ending points (EPs), and each local TSP is solved using a local graph taking into account the SP and EP determined in from the global TSP, wherein the vertices represent the holes.

4. The method of claim 1, wherein the global TSP is solved using a global graph, wherein the vertices in the global graph represent a location of each packet, and the vertices in the local graph represent a location for a previous packet and a location for a next packet with respect to a current packet in the global sequence, and the holes.

5. The method of claim 1, wherein the global TSP and the local TSP minimize a Euclidean distance between any two sequential holes to be drilled.

6. The method of claim 1, wherein the global TSP and the local TSP minimize a time for the drilling machine to travel between any two sequential holes.

7. The method of claim 1, further comprising:

adding an instance of a particular hole to the local TSP for each time the particular hole is to be drilled and adapting a cost to account for a minimum time between redrilling the particular hole.

8. The method of claim 1, further comprising:

adding an instance of a particular packet to the global TSP for each time the particular packet is be drilled and adapting a cost of the global TSP to account for a minimum time between redrilling the particular packet.

9. The method of claim 1, solving the local TSPs using graphs, wherein vertices represent the holes, and edges represent costs that take into account a refractory period of a laser in the drilling machine.

10. The method of claim 1, solving the global TSP and the local TSPs using graphs, wherein vertices represent the holes, and edges represent costs representing a period of time passed through an inverse of a time estimation function to obtain an equivalent cost.

11. The method of claim 3, further comprising:

superimposing a grid of nodes on each packet to determine the candidate set of SPs and the candidate set of EPs in each packet for the global sequence.

12. The method of claim 1, further comprising:

adapting the partitioning to repeated patterns;

solving a single instance of the local TSPs for each repeated pattern; and

optimizing the complete sequence for drilling the holes according to a starting point and an ending point in each packet of the repeated patterns.

13. The method of claim 4, wherein the location of the packet is a geometric center.

14. The method of claim 4, wherein the location of the packet is center of mass of the packet with respect to holes.

15. The method of claim 12, wherein the optimizing uses a K-Opt local search procedure.

16. A method for determining a sequence of drilling holes in a workpiece according to a pattern, wherein the pattern is partitioned into packets and the holes are drilled by a drilling machine, comprising:

determining a global sequence of the packets by solving a global traveling salesman problem (TSP);

determining a local sequence of the holes in each packet by solving a local TSP for each packet; and

joining the local sequences of the holes according to the global sequence of the packets to determine a complete sequence of drilling the holes by a drilling machine,

wherein the global TSP is solved using a global graph, wherein the vertices in the global graph represent a location of each packet, and the vertices in the local graph represent a location for a previous packet and a location for a next packet with respect to a current packet in the global sequence, and the holes, wherein the location of the packet is center of mass of the packet with respect to holes, and wherein the steps are performed in a processor.