Bounded sub-optimal problem solving

A data structure is described that comprises a balanced binary tree and a binary heap, which may be utilized for combinatorial searching algorithms. For instance, solutions for performing a task, such as a print job or the like, are associated with nodes that are utilized to generate the data structure. Each node is associated with a quality indicator that describes a most optimal solution that may be reached through the node when traversing the binary tree. The binary heap is generated from a subset of the nodes in the tree, wherein each node in the subset has a quality indicator value that is within a predefined range of a best known solution quality. The binary heap is sorted according to a search effort indicator value for each node, where nodes that are more easily reached in the tree are placed higher in the heap to facilitate rapid identification.

CROSS REFERENCE TO RELATED PATENTS AND APPLICATIONS

The following patents/applications, the disclosures of each being totally incorporated herein by reference are mentioned:

U.S. application Ser. No. 11/364,685, filed Feb. 28, 2006, entitled “SYSTEM AND METHOD FOR MANUFACTURING SYSTEM DESIGN AND SHOP SCHEDULING USING NETWORK FLOW MODELING”, by Hindi, et al.;

BACKGROUND

In machine control system design, it is important to utilize resources to their maximum capacities in order to optimize system throughput and/or minimize cost associated with such optimization. In the case of printers, photocopiers, and the like, conventional control mechanisms are limited in the manner in which they process information, perform jobs or tasks, plan such jobs or tasks, etc. For instance, where multiple tasks are to be performed for a job, a specific ordering of tasks may be preferable to the exclusion of one or more other orderings, and such a solution may be considered optimal for execution by a machine. In the case of a print platform, for example, an optimal ordering of pages to be printed, print associated tasks, or the like can be desirable in order to mitigate resource waste and improve printer throughput.

Conventional systems and methods for planning employ various search algorithms, including an A* search algorithm, which typically operates to facilitate finding a path from a given starting state to a desired goal state. An A* search algorithm is an example of a “best-first” search algorithm because it utilizes a heuristic estimate to rank a given node according to an estimate of an optimal route passing through the node to the desired node. The search algorithm may then determine an order in which to evaluate nodes according to their respective estimated values. However, A* algorithms explore all nodes that cannot be proven to be worse than the optimal, which can be time consuming and computationally expensive. This in turn can occupy resources (e.g., memory, processing power, etc.) and lead to processing delays. Accordingly, an unmet need exists in the art for systems and/or methods that facilitate improved processing efficiency for search algorithms and associated data structures.

BRIEF DESCRIPTION

In accordance with various aspects described herein, systems and methods are described that relate to generating, maintaining, and searching a data structure comprising a balanced binary tree and a binary heap. For example, a method of storing and accessing data in a coordinated data structure comprises generating a balanced binary tree data structure comprising a set of nodes arranged in order of decreasing quality indicator values, and generating a binary heap data structure comprising a subset of the set of nodes arranged in order of increasing search effort indicator value associated with the subset of nodes.

According to another aspect, a system that facilitates identifying a solution for a print job comprises a data structure generator that generates a balanced binary tree data structure and a binary heap data structure, a solver that searches the balanced binary tree data structure and the binary heap data structure to identify an optimal solution, and a search queue in which the balanced binary tree data structure and the binary heap data structure are stored for evaluation.

Yet another aspect relates to a system comprising one or more components that execute instructions for performing a process, and a data structure generator that generates a data structure comprising a binary tree and a binary heap using a plurality of nodes representing respective actions for performing the process, wherein each node is associated with a quality indicator representative of the quality of a best solution under the node and a search effort indicator representative of an amount of search effort related to reaching the best solution under the node. The system further comprises a solver that searches the binary heap to identify an action within a predetermined quality range of a best known action and places the identified node in a search queue for evaluation, wherein the data structure generator removes the node associated with the selected action from the binary tree and the binary heap to update the data structure and the solver iteratively searches the binary heap to select a next optimal action upon each successive update of the data structure.

DETAILED DESCRIPTION

In accordance with various aspects described herein, a coordinated data structure comprising a balanced binary tree and a binary heap may be cross-correlated during execution of a combinatorial search algorithm to permit rapid identification of a feasible search result of bounded suboptimality. It is to be understood that features presented herein may comprise and/or be employed in a variety of environments, including but not limited to a computing system, an industrial control system, a manufacturing execution system, computer game opponent controller, biological sequence alignment system, logistics software, an electronic imaging environment, as well as a xerographic environment, whereby one or more xerographic components are utilized to perform a xerographic procedure or function. Although the subject concepts are described largely in conjunction with a print platform, such as a printer or a copier, it will be appreciated that such concepts may be employed in conjunction with numerous other technologies and/or search algorithms. According to other aspects, such methods may be employed in conjunction with gaming applications, routing and motion planning applications, etc. Indeed, the subject innovation may be employed in any and all applications where a best-first search protocol and related data structure are utilized.

With reference toFIG. 1, a system100is illustrated that facilitates performing a combinatorial search using a combined data structure comprising a binary tree and a binary heap. The system100comprises a solver102(e.g., a processor or the like) that may evaluate a plurality of nodes to determine an optimal solution possibility. For instance, each node (N) (e.g., representing a unique solution possibility) may have two values associated with it. For example, a quality indicator value (QV) describing a best solution under the node may be associated with the node, and a search effort indicator value (SEV) that indicates a level of effort required to reach the best solution under the node may additionally be associated with the node. A search queue104may comprise a data structure106that may be used by the solver102. Nodes in the data structure106are depicted as N1through Nn, where n is an integer, and each is associated with its respective QV and SEV indicator values. It will be appreciated that the system100may be executed in and/or comprised by a computer108.

In accordance with various aspects, the data structure106facilitates finding a node with a least amount of effort among a subset of all nodes comprising nodes within a predetermined quality factor of a best node (e.g., an optimal node for expansion when searching for a solution to a job request or the like). In this sense, an “optimal” node need not be the solution with the highest quality indicator value (although the optimal may have the highest quality indicator value of the set of all nodes), but rather may be a node with a “high-enough” quality indicator value (e.g., within a predetermined quality factor of the best solution) that is also associated with a minimum amount of search effort. Thus, the selected node may be somewhat “sub-optimal” in quality but may be selected over a more optimal node because it is easier to search among its descendants and find a feasible solution.

According to an example, each node may represent a unique action in a job plan solution for a machine, such as a printer or the like. Reaching a node representing the completion of the job would then correspond to having found a sequence of actions that accomplishes the job. This plan would be represented by a path along the nodes leading from the root node to the terminal node. The solver102may determine that it wants to evaluate all job plans within 5% efficiency of an optimal one. For instance, an optimal next node (N) may be given a unity quality value. The most easily reached node having at least 95% efficiency may then be removed from the binary tree114and the binary heap116of the data structure106and expanded (e.g., child nodes may be generated for the selected node), and the process may be reiterated. On a next pass, a next node meeting the predefined criteria may be selected, removed from the data structure106, and expanded by the search algorithm110to facilitate generating complete solutions to a print job or the like. It will be appreciated that the foregoing example is not limited to an efficiency threshold of 95%, but rather may employ any suitable or desired efficiency threshold. Moreover, quality may be a function of one or more factors or parameters, including but not limited to: job processing time; job execution time; a number of actions involved in completing a given job solution; a number or quantity of resources involved in executing a given job solution; or any other suitable parameter that may result in a given job solution or action being preferred over another job solution or action. Search effort may be a function of many factors, such as the number of intervening nodes to a solution, the accuracy of heuristic quality estimates, or other factors.

The search queue104and its data structure106may comprise, for instance, the binary tree data structure114, which may be a balanced binary tree according to some aspects, and the binary heap structure116. The system100may additionally comprise a data structure generator112that receives input in the form of one or more jobs to be performed, one or more actions to be performed in association with the one or more jobs, or the like. The data structure generator112may then associate a plurality of job actions with respective nodes to form the data structure106. For instance, the data structure generator112may execute a set of machine-executable instructions to generate a balanced binary tree comprising a plurality of nodes, each of which is associated with a particular job action. The data structure generator112may identify nodes in the balanced binary tree114that are within the predefined efficiency or relevance range of an optimal node, and may organize identified nodes into the binary heap116according to their respective levels of search difficulty. The data structure generator112may thus facilitate selection of nodes by the solver102(e.g., a most easily searched node in the binary heap116may be selected) for evaluation and expansion by the solver102. Additionally, the data structure generator112may update the data structure106by removing a node from the binary tree114and/or the binary heap116upon selection of the node for expansion. Once the node has been expanded by the solver102, the node and its children may be reinserted into the binary tree114, and the binary tree and binary heap116may be updated to reflect any changes that are caused by the new nodes. In this manner, the system100may effectively reduce a total expanded solution space that is explored by the solver102to identify and evaluate an optimal solution.

FIG. 2is an illustration of a balanced binary tree200such as may be employed as a part of a data structure to facilitate identifying appropriate nodes among a plurality of possible nodes, in accordance with various features. The binary tree200comprises a parent node,202, which has a pair of child nodes,204Aand204B, each of which in turn has a pair of child nodes. For example, the children of204Aare labeled206Aand206B, respectively, and the children of204Bare labeled206Cand206D, respectively. Each node in the tree200is associated with an action that may be performed by a machine, such as a printer or the like, as a solution to a job request. The binary tree200may be organized in order of decreasing quality, from left to right, although other organizations will be apparent to those of skill. Each node is associated with a quality indicator value and a search effort indicator value {QV, SEV} that indicates the node's relevance as a next logical action in a potential solution to a print job and a level of difficulty associated with searching the node, respectively.

Each node in the binary tree200may comprise a pointer to its parent, to its left child, and to its right child. The binary tree200represents a first portion of a data structure, such as tree114, which is part of the data structure106described with regard toFIG. 1, in which data may be organized. Additionally, the binary tree200may be employed in conjunction with a binary heap, described below, as a pair of coordinated data structures that facilitate reducing time to access appropriate nodes to be explored by the search algorithm110. It will be understood that the binary tree200may comprise any number of nodes, which correspond to a like number of potential solutions, and is not limited to a tree size of 7 nodes as illustrated.

FIG. 3is an illustration of a binary heap300that may be utilized in conjunction with a binary tree to facilitate storing data in coordinated data structures for rapid combinatorial searching, in accordance with one or more aspects. A binary heap is a data structure that may be created using a binary tree, such as the binary tree ofFIG. 2. It will be apparent to those skilled in the art that a binary heap can be implemented using an underlying array data structure to facilitate quick access to various elements of the heap. According to an example, the binary heap300may be a min-heap where in each node is associated with less search effort than its child nodes. A node may be added to the bottom of the heap, and then compared to its parent; if the node's position in the binary tree200is less difficult to reach than its parent node's position in the binary tree200, then the node may be swapped with its parent in the binary heap300. This may be iterated until the binary heap300has a correct ordering.

It will be appreciated that the binary heap300need not include all nodes of the binary tree200described above. However, each node in the binary heap300may be a node selected from binary tree200. According to an example, a search may be performed for all nodes having a solution value that is within 10% of an optimal solution value. For instance, if a best solution for a given job sequence takes 15 seconds for execution, and if time is a criterion upon which solutions are evaluated, then nodes associated with actions that are likely to result in solutions that do not take longer than 16.5 seconds to complete may be selected for inclusion in the binary heap300.

When organizing the binary heap300, a criterion for node dependency may comprise ease of search. For example, if a search of the binary tree200for nodes within 5% of an optimal next action is performed, a total of 4 nodes will be returned (e.g., nodes202,204A,206A, and206B), and these nodes may be utilized to generate the binary heap300. Thus node206Bis shown at the top of the binary heap300because its SEV is 1, indicating a lowest relative level of search difficulty. Node206B is further down in the binary heap300because it has a higher search effort associated with it.

Accordingly, when a search is performed for a solution to a particular job or task, node204Amay be selected and removed from the binary heap300. Additionally, the corresponding node in the binary tree200(e.g., node204A) may be removed because the node contains pointer information to its parent and children (in the binary tree200) when stored in the binary heap300. That is, node204Amay comprise pointer information indicating that it is a child node of node202in the binary tree200, as well as the identity of any child nodes it has in the binary tree200. In this manner it may be easily located in the binary tree200and removed. The binary tree200may be updated for a subsequent evaluation, as may the binary heap300.

It will be appreciated that the various thresholds and/or criterion described above with regard to the preceding examples are illustrative in nature, and that any suitable threshold(s) (e.g., 1%, 5%, 7%, 15%, 50%, etc.) and/or any suitable criteria (e.g., time, energy conservation or expenditure, resource conservation or expenditure, cost reduction, etc.) may be used.

FIG. 4illustrates a combined data structure comprising a binary tree portion and a binary heap portion, such as is described above. A plurality of nodes is depicted, and arrows in the figure correspond to active pointers from one node to another. A first node401has five pieces of information associated with it (e.g., in addition to the QV and SEV information described above). For instance, node401has a node data field402associated with it, wherein the node data comprises information related to the identity of the node, actions associated with the node (e.g., which may form part of a solution), and any other suitable information that may facilitate the various methods described herein. Additionally, node401has an array index value404that indicates its position in the array432(e.g., the binary heap). In this case, node401has an array pointer value of 0 because it is associated with a lowest amount of search effort and is thus first in the array, which is initiated at 0 (although such arrays may be initiated at 1 or some other suitable value, as is known). Node401also has three pointer fields: a pointer406to its left child node, a pointer408to its right child node, and a pointer410to its parent node. Since node401is the root node in the tree portion of the data structure400, it has no parent, and therefore its parent pointer410is null, as indicated by the hash line through the null pointer.

Similarly, node403has a node data field412, an array index or pointer414, left and right child node pointers416and420, respectively, and a parent pointer418. In like fashion, Node405comprises a node data field422, an array pointer424, left and right child node pointers426and430, respectively, and a parent pointer428. In this simplified example, only three nodes are shown, and thus nodes403and405exhibit null child node pointers. However, it will be appreciated that the systems and methods presented in this document are not limited in the number of nodes that may be employed in the data structure(s) described herein. Additionally, it will be noted that node405has a null array pointer430because it is not included in the array, which is the result of node405not being selected for inclusion in the array. This occurrence is caused by node405having a quality indicator value that is outside a predetermined acceptable range for inclusion in the array432, such as is described above with regard to preceding figures.

The binary heap array structure432comprises nodes arranged according to their respective search effort values. As depicted, a first position434holds a pointer to node401indicating that it is the most easily searched node in the array. Position434has a pointer to node401in order to permit rapid location of it in the binary tree portion of the data structure (e.g., at node401). Similarly, location436has a pointer to a location in the tree portion, at node412. In this manner, nodes may be rapidly removed from the data structure400for expansion when evaluating potential job solution paths.

With regard toFIGS. 5-6, methods are described that facilitate generating and/or updating a data structure comprising both a balanced binary tree and a binary heap to facilitate combinatorial searching algorithm execution. The methods are represented as flow diagrams depicting a series of acts. However, it will be appreciated that, in accordance with various aspects of the described innovation, one or more acts may occur in an order different than the depicted order, as well as concurrently with one or more other acts. Moreover, it is to be understood that a given method may comprise fewer than all depicted acts, in accordance with some aspects.

FIG. 5is an illustration of a method500for generating a coordinated data structure comprising a binary tree and a binary heap to facilitate combinatorial searching of a plurality of nodes, in accordance with one or more features described herein. According to the method, a quality indicator may be assigned to a node, wherein the quality indicator describes a quality of an action or plurality of actions associated with the node, at502. For instance, in the context of a machine, such as a printer, the quality of a given action may be associated with the rapidity with which the action facilitates performance of a print job, a number of actions associated with job completion, a number or quantity of resources consumed in completing the action, or some other parameter associated with action and/or solution efficiency, etc.

At504, a search effort indicator may be assigned to the node. For instance, the search effort indicator may estimate number of nodes in a path to a goal node, accuracy of evaluation information, or the like. At506, the node may be inserted into a data structure, which may comprise a binary tree with nodes arranged according to their respective qualities, as well as a binary heap with nodes arranged according to their associated relative degrees of search effort.

FIG. 6is an illustration of a method600for searching a data structure comprising both a balanced binary tree and a binary heap in order to identify and/or evaluate an optimal solution for a job request. At602, the binary tree may be initialized. At604, the binary heap (or array) may be initialized, where the binary heap is generated as a function of the binary tree. According to an example, the binary tree may be searched to identify all nodes within a predefined threshold range of a target value that is associated with an action to be performed in a job solution, or plan. For instance, if a target value is 100% efficiency, and the predefined threshold range is 30%, then all nodes associated with actions that are at least 70% as efficient as the best known next action may be identified in the tree and placed in the binary heap in order of their respective levels of search difficulty with lower search effort levels given priority in the heap. At606, a node may be selected from the binary heap for expansion, whereby the node removed from the binary tree and the binary heap and is added to a search tree that delineates possible job solution routes.

At608, a determination may be made regarding whether consideration of the selected node results in a terminal condition. For example, this may occur when the node's action results in the completion of the desired print job, etc (e.g., no further actions need be searched). If such is the case, then the node does not require expansion and the method may terminate. However, if a terminal condition is not detected, then at610, child nodes may be generated for the selected node, where the generated child nodes represent elaborations or extensions of the parent's partial solution. At612, the new child nodes may be inserted into the binary tree. Inserted child nodes may, for example, represent a single action or a plurality of actions associated with performing a print job or the like. The addition of the generated child nodes may change the structure of the binary tree with regard to relative quality indicator values and the like, and may thus result in an update of the binary tree. At612, the binary heap or array may also be updated to account for changes in solution quality thresholds or search difficulty that may have arisen due to the insertion of the new nodes. The method may then revert to606, where a subsequent node may be selected for expansion. In this manner, a vast number of potential actions may be searched, evaluated, and serialized in order to generate a viable solution to a job request, while mitigating time expenditure associated with evaluation of non-viable or too-distant solution paths.

FIG. 7illustrates a system700comprising a plurality of components, such as may be employed in a universal production printer with a color print sheet buffer or a tightly-integrated parallel printer (TIPP) system, which represents an environment in which the various features described herein may be employed. The system700comprises a paper source702, which may comprise one or more sheets of paper, and which is operatively associated with a color engine704and a crossover708. Paper from the paper source702may follow one of two paths. For instance, paper may be routed from the paper source702to the color print engine704, and on to a color print buffer706, before entering the crossover708. Additionally or alternatively, paper may be routed directly from the paper source702to the crossover708(e.g., bypassing the color engine704and the color print buffer706).

Paper that has been routed directly from the paper source702to the crossover708may be passed to a black-and-white print engine710, then through a merger712that merges black-and-white and color pages, before proceeding on to a finisher714that finishes the document for presentation to a user. Prior to insertion by crossover708, paper may be stored temporarily in a sheet buffer716. Paper that has been routed through the color print engine704and the color print buffer706may be passed through the crossover708into a sheet buffer718for temporary storage until such time as the color-printed page is merged by merger712with other black-and-white pages. It will be appreciated that according to other examples, a page may pass through all components of the system700and may have both color portions and black-and-white portions. The actions associated with a job performed by system700may be organized into a series of events that define one or more solutions to the job, which may be associated with respective nodes in the data structure(s) described above.