Patent ID: 7451132
Filing Date: 2008-11-11
Classification: G06Q,Y10S

Abstract:
1. A combinatorial search method for on-line state-space planning of operations for multi-step production processes, wherein the method is performed by a planner residing within a computer control system having a memory storage, wherein the planner considers various possible combinations and sequences of actions to transform an object from one state into the specified desired final state described in at least one job request, wherein each combination of actions the planner considers is called a search node, with each node containing a plan representing a series of actions on a single object and also containing the predicted state of the object with those actions applied either forward or backward, wherein the state of the object consists of the set of attributes of the object, the method comprising: generating an initial search node for an object, wherein said internal search node contains an empty production plan and a current object state, wherein said current object state corresponds to either the raw material of the production line if forward planning is utilized or the finished product if backward planning is utilized; inserting said generated initial search node into a data structure that holds candidate search nodes; selecting one of said candidate search nodes in said data structure to extend further; removing said selected candidate search node from said data structure; determining if the object state in said selected candidate search node conforms to a goal object state, or whether actions should be added to said selected search node's plan, wherein said goal object state comprises either a specified desired final finished state of the object if forward planning is utilized or the starting state of the object if backward planning is utilized; considering all actions compatible with said current object state, wherein actions are modeled in part as transformations of attributes of an object; generating at least one new search node, wherein each said new search node contains a production plan including one of said actions and a predicted object state corresponding to applying said one of said actions; inserting said at least one new search node into said data structure; repeating selecting a new candidate search node, determining if the object state in said selected candidate search node conforms to a goal object state, and considering all actions compatible with said current object state until the state of said object for at least one child node candidate plan corresponds to said goal object state; returning said child node candidate production plan that corresponds to said goal object state to the control system for implementation of multi-step production for said object; and storing said returned child node candidate production plan in the memory storage of the computer system.