An object-oriented shape nesting expert system on two-dimensional highly irregular resources

The objective of the automatic nesting problem is to find an arrangement for cutting irregularly shaped pieces that most efficiently, automatically and quickly utilizes an available resource. The available resource, in this case, is highly irregular with not only irregular boundaries but also defective areas. In the solution of this problem, three subproblems must be considered: irregular resource/piece representation, search/match methods and localization of the search space. We propose an object-oriented representational scheme which describes pieces and resources in multiple ways. This object-oriented representational scheme can directly depict physical objects and mental concepts in a coherent manner, making it much easier to embed an expert's knowledge into a system. We also present a novel hybrid search algorithm, an abstract heuristic search in combination with a best-first search using limited backtracking. The solution is then further enhanced by incorporating feedback techniques. A new way of localizing the search space called recursive look ahead is also introduced. This technique is a domain-dependent approach that sub-divides the world based on the locations of defects. This recursive look ahead procedure is a novel variant of the sub-goal technique. Several other inference procedures, such as intersection and overlap detection, rotation, cut and try procedures are also proposed. This system has been developed and the preliminary result is satisfactory. The testing has been performed by comparing the system against a human expert. The average yield difference had been within five percent.