The subject of present invention is method of adaptive planning of cutting patterns. Present invention belongs to category of optimization tools, which aim to improve economic effectiveness and simplify and speed-up manufacturing processes. Proposed in this present invention solution allows to arrange certain element or elements on a given material surface and define cutting device process sequence. Such operation is called cutting pattern generation. Its application fits wide range of industry to meet needs of automation in order to optimize costs and operation time of manufacturing processes. Problem of cutting pattern generation is a part of computationally complex combinatorial geometry. Optimization which lies within scope of present invention is divided into two main categories:

• one-dimensional optimization, i.e. only considering length or width of elements,

• two-dimensional optimization.

Size of optimization equals minimal number of dimensions of geometry required to present layout of elements arranged on a given surface. Present invention includes also optimization for guillotine cutting, i.e. in case where blade cuts base material each time from one edge to another. Additionally, present invention provides optimization with consideration of material specification, cutting technology and information exchange with production planning systems. These factors are treated as additional dimensions of problem to be optimized.

The aim of present invention is to find optimal, strictly speaking - suboptimal, solution to resolve nesting problem, which is similar to knapsack problem. Knapsack problem belongs to the group of the most complex algorithmic problem - there is no algorithm solving it which could be mathematically proved as optimal. Consequently, optimization used in present invention is strongly related with mechanisms for solving knapsack problem. The basic. issue is to pack given space, e.g. surface, capacity, time, with possibly the biggest amount of discrete elements at the same time with possibly the least level of unused space.

Generalized form of optimization problem is given as minimization of cumulative material losses for a given number of achieved elements. Mathematically it can be described

Subject to:

Where:

• cj - losses for j-th generated distribution of elements on material sheet,

• xj - number of base material sheets necessary to achieve desirable number of elements for given distribution,

• pij - amount of i-th element in j-th distribution,

• di - requested number of i-th element

In practical use, mathematical model can be modified what is a consequence of multidimensional reality of manufacturing processes and their processing environment.

Proposed approach for connecting heuristics which dispose elements on surface with meta-heuristics aimed to find beneficial arrangement of elements by heuristics, allows iterative adaptation of process which examine search space in order to find the best solution. Consequently, it allows to reduce probability that heuristics stop when local optimum is reached which in fact is not an optimal solution.

According to present invention the method of adaptive planning of cutting patterns on base material surface is that geometric parameters of elements to be disposed on base material surface are specified, set of heuristics which provide elements' arrangement on base material surface are configured, arrangement heuristics, elements are disposed thanks to configured heuristics, optimization of achieved cutting patterns is performed and sequence of cutting successive elements is set.

It is an object of the present invention to provide a method of adaptive planning of cutting patterns on base material which is characterized with following steps: a) geometric parameters elements are identified including dimensions, internal holes, permission or prohibition to nest other elements inside the current one, allowed orientation of elements in regards to base material,

b) arrangement heuristics are selected and configured with elements' geometric parameters, number of elements, structure of base material, dimensions of base material, data from storage facility describing availability of base material and parameters of chosen cutting technology, c) cutting patterns are generated independently by arrangement heuristics chosen in step b)and at least one generated layout is selected starting from the best one,

d) cutting pattern or patterns selected in c) are modified with meta-heuristic which generates set of modified solutions by changing sequence of disposal elements on base material surface,

e) in accordance with sequence of elements disposal on base material surface, for each modification generated in d), set of heuristics is performed which dispose elements on base material surface in order from best heuristic to the worst heuristic in accordance with patterns generated in c), f) at least one from the best results achieved in e) is modified using meta- heuristic and step e) is repeated until specified final condition is met which is either time limit for computations, or arrangement of acceptable amount of elements, or state in which no improvement is achieved in particular number of successive iterations,

g) from all achieved in e) and f) results, optimal one is chosen for which is selected optimal sequence of cutting disposed elements, h) based on results from g), machine code is generated and uploaded to cutting device.

Advantage of the present invention is that optimization of cutting patterns is performed considering only one dimension of elements. It means that there is one dimension for all elements, for example - width, but they can have different values of another dimension, for example - length. Exemplary it can be a cutting process from paper roll or canvas roll.

Another advantage of the present invention is that optimization of cutting patterns is performed considering two dimensions of elements. It means that during process of cutting patterns planning, two dimensions of element are considered. Example is cutting of elements of rectangular shape or other complex shapes.

According to one aspect of present invention, optimization of cutting layouts is performed for guillotine cutting technology. It is a specific type of technology where blade cuts each time base material and produced fragments from one edge of the material to another.

According to another embodiment of present invention, shapes of elements are classified using artificial neural network. This approach allows to assign more precisely heuristics to shapes, i.e. aimed to perform disposal optimization of elements with specific shape, for example triangular.

According to another aspect of present invention, Hamming artificial neural network is used for classification of elements' shapes. It is a 3 layers recursive network used in images classification.

It is an object of present invention to provide a method in which in step f) are used heuristics selected in step b) and are rejected those ones which generate the worst results. This approach allows to limit, in adaptive manner, usage of heuristics which produce the worst results. It is another object of present invention to provide a method in which in step g) costs of machine operation during elements cutting in base material, are minimized. Optimization is based on cutting device operation costs, both in cutting stage and idle-stage. What is more, such optimization shall conform to limits imposed by base material specification. Example is structure of wood which allows to cut only under certain angles or metal resistance to deformation in high temperature what imposes short time of laser or plasma operation within defined area of material.

Advantage of present invention is that ant colony optimization is used in order to minimize costs of cutting device operation. It is a probabilistic algorithm which searches for the best from perspective of defined aims routs in graph. Problem of searching for optimal sequence of cutting device operation is analogical to traveling salesman problem which can be successfully resolved using ant colony optimization algorithm. In another embodiment of present invention, in steps d) and f) meta- heuristic is used which belongs to category of genetic algorithms. Genetic algorithm searches in heuristic manner space of solutions in order to find optimal one. These algorithms imitate process of natural selection and therefore are appropriate for searching within wide search spaces what is the case regarding cutting pattern generation.

In yet another embodiment of present invention in steps d) and f) simulated annealing meta-heuristic is used. Simulated annealing optimization is a equivalent of physical annealing process used in metallurgy. Solution of optimization problem corresponds to state of physical object during annealing which is based on cooling and heating. In this manner, state corresponds to sequence according to which heuristics arrange elements on a surface.

Other advantage of present invention is that in steps d) and f) particle swarm optimization meta-heuristic is used. It is a stochastic optimization model which simulates adaptation of particles swarm to environment, for example insects, birds. In accordance with present invention, particle position corresponds to sequence, i.e. order in which elements are disposed on a surface of material by heuristics. The aim is to find optimal sequence, that is, particle with the nest position in a swarm.

According to another aspect of present invention more than one meta- heuristics are used in step d) and step f). In such a case each meta-heuristic makes independent computation on input solutions provided by arrangement heuristics.

An object of present invention is presented in exemplary embodiment in following picture, on which fig. 1 shows exemplary industrial system based on invention.

In presented exemplary embodiment of present invention it is assumed that:

• Cutting patterns are prepared for laser CNC devices which are destined to cut sheet metal,

• Elements to be cut are of irregular shapes,

• Optimization of elements disposal on base material surface is performed considering two dimensions of elements,

• There is possibility to use additional shape classifier which is based on Hamming artificial neural network,

• It is allowed to nest smaller elements inside bigger when it is possible, under condition that inner holes of bigger elements have enough space to nest smaller elements,

• Elements are read from DXF files,

• Application which is an implementation of present invention uses its own representation of elements which conforms to Object Oriented Programming methodology and parser which transforms DXF files to that representation; neither representation nor parser is within scope of present invention, • Parser verifies correctness of DXF files by checking, inter alia, general syntax errors, figures closure, double or multiple lines it assures elimination of errors during optimization process,

• Process of elements arrangement, nesting, is configured with following parameters:

o Allowed distance between elements, which depends on thickness of base material and specification of used cutting device, i.e. diameter of cutting beam and produced temperature,

o Allowed distance from edges of base material,

o Minimal length of cut, allowed by the cutting device, o Dimensions of available base material sheets and theirs quantity, o Requested number of elements to be cut,

• In scope of single nesting process, different heuristics are used which arrange elements on surface in order to find the best pattern, · Process which determines cutting path, i.e. sequence of cutting elements from base material, is configured with unit costs of device operation while cutting and traverses in idle state, and also allowed temperature of base material which does not cause its deformation,

• Based on results, two alternative types of files are generated, i.e. G- Code and STEP-NC.

Figure fig. 1 shows schema of exemplary embodiment of present invention. User 100 can work in local or remote manner. User interface 101 in this exemplary instance of present invention is implemented as an application which is accessed through a web browser. Other elements in this exemplary instance of present invention are located on remote application server. Optimizer manager 102 is responsible for supervision and coordination of operation of all elements which compose exemplary instance of present invention and also for communication with the user, cutting devices 107 in order to load of G-Code or STEP-NC, and module which plan and coordinate production 108 - it shall be noticed that this module are out of scope of presented invention. DXF engine module 103 is responsible for δ

DXF files parsing and base on them, generating of object oriented representation of each element. Optimizer engine module 104 provides optimization of cutting patterns considering nesting of elements and sequence of their cutting. Shape classifier module 105 is responsible for assignment of elements' shape to certain category, and for this purpose it utilizes Hemming artificial neural network. Usage of shape classifier is optional. Machine code generator module 106 generates code which is interpreted by cutting device. In this exemplary embodiment of invention it is G-Code or STEP-NC. First of all, DXF files which contain projects of elements are parsed and verified in module 103. It is possible to use different elements which come from different DXF file and use them all in a single cutting pattern. Object oriented representation of these elements are provided to module 102. Module 102 configures module 104 with parameters which are geometric parameters of element, quantitative data about number of elements to be cut, information about available formats, thickness and endurance limits of used base material, cutting technology parameters, identifiers of heuristics which dispose elements on surface and which are going to be used. Presented exemplary embodiment of present invention provides optional shape qualification mechanisms realized by Hamming artificial neural network realized as module 105. Shape qualification is meant to assign shapes to certain category, e.g. triangular shapes, elliptic shapes, long and thin shapes. Qualification is performed for raster images created for elements to be cut. Such qualification generates additional data which are utilized by module 102 during selection of heuristics which arrange elements on base material surface. First step to be performed by module 104 is to generate preliminary cutting layouts. In presented exemplary implementation of present invention, set of heuristics which arrange elements on a surface is composed, amongst others, of several types of no-fit polygon, heuristics which create groups from several elements which shapes are similar to regular shapes, e.g. triangular, rectangular, and arrange those groups accordingly in row and columns on surface of base material - e.g. clustering bottom-left nesting heuristics, heuristics oriented to maximize usage of space between elements with other elements. However, heuristics are not a subject of present invention thus are not described herein in details. In this exemplary implementation of present invention, sequence according to which elements are provided to heuristics inputs, can be random or determined by size of elements in ascending or descending order. Module 102 selects several best layouts, i.e. the ones which provides the least material losses. Layouts can differ in number of disposed elements or it can be requested to arrange certain number of elements and heuristics which do not fulfill this requirement are rejected outright. Subsequently module 102 requests from module 104 to modify those layouts. For this purpose, in this exemplary embodiment of present invention, meta-heuristic is used which is a genetic algorithm tailored to present invention needs. This meta-heuristic proceeds with following order:

• the best patterns selected by module 102 and created by module 104 are coded as chromosomes; in this exemplary implementation of present invention, coded is only a sequence in which elements where placed by heuristics on a surface; coding must be performed in a way which allows to dispose maximal number of elements within given optimization process,

• Modifications of coded patterns are generated with the use of mutation genetic operator; optionally it is allowed to use crossover operator and - also optionally - another mutation,

· Arrangement heuristics are performed for each permutation of dispose sequence that is result of previous step; heuristics dispose elements on a surface in accordance with sequences which are results of modification; optionally, in this exemplary embodiment of present invention, only subset of the best heuristics can be used; in case when certain heuristic allows to dispose additional elements and there are still some not nested elements they are also arranged,

• Fitness function is computed for achieved results; such function in this embodiment of invention is a ratio of area used by elements taking into account also space which cannot be utilized to arrange additional elements - for example too small spaces between elements to fit other elements - to area of base material; it may happen that for some layouts, number of elements will differ;

• The best fitted patterns are mutated again and optionally crossbred and mutated again, arrangement heuristics are performed on results of genetic operator or operators usage, fitness functions are computed - until time limit for computation is reached or steady-state is reached, i.e. lack of improvement in next iterations.

Sequence of moves of cutting device is generated for the best pattern, i.e. optimal sequence of cutting of arranged elements. In this exemplary implementation of present invention ant colony optimization is used, which in turn is configured taking into account unit costs of device operation while cutting and traverses in idle state in such a way so as to minimize overall costs of machine operation. What is more, in scope of generated sequence considered are both base material specification and cutting technology in order to avoid risk of material deformation due to exposure to high temperature. Based on results from previous step, module 106 generates machine code to be loaded onto cutting device; in this exemplary embodiment of present invention code can be of G-Code or STEP-NC type. At the end, module 108 receives information about base material leftovers which eventually can be utilized later.