Patent ID: 8086595

Claim:
An on-line combinatorial search method implemented in a computer control system for utilizing a state-space planner for planning of operations for multi-step production processes in a manufacturing system having a plurality of machines, wherein the state-space planner considers possible combinations of actions, searching for one that correctly transforms an initial state of an object of a plurality of objects into a specified desired final state, wherein each of the combination of actions the state-space planner considers is called a search node, with each search node containing a series of actions to be performed on the object of the plurality of objects, the method comprising: performing, while the manufacturing system is on-line, multiple state-space search operations in a search space having a plurality of the search nodes to find individual solutions to multiple interacting individual problems, wherein at least some of the search nodes include children nodes, and actions of the search nodes and children nodes represent potential solutions to the existing interacting individual problems to be solved, and wherein the performed multiple state-space search operations include: searching for a solution to a first individual problem, from among the plurality of existing individual problems required to be solved for operation of the manufacturing system, wherein the solution to the first individual problem results in a plan for the first individual problem; suspending searching for the solution to the first individual problem when the solution is found; storing the solution to the first individual problem when the solution is found; searching for a solution to a second individual problem, from among the plurality of individual problems, wherein the solution to the second individual problem results in a plan for the second individual problem and wherein the solution for the second individual problem is consistent with the solution of the first individual problem such that the solution to the first individual problem and the solution to the second individual problem do not interfere with each other; determining the solution to the second individual problem cannot be obtained; backtracking to the first individual problem; discarding the entire solution to the first individual problem; searching for an alternative solution to the first individual problem; finding the alternative solution to the first individual problem; re-searching for the second individual problem; repeating the searching, suspending, storing, determining, backtracking, discarding, finding, and re-searching steps for the remaining problems; returning a final solution for all the individual problems; and linking, while the manufacturing system is on-line, the solutions found by the multiple state-space search operations for the solved multiple individual problems together as an overall solution.