System and method for parallel edge partitioning in and/or graph search

Patent metadata

Field	Value
Publication number	US-10410144-B2
Application number	US-201113273714-A
Country	US
Kind code	B2
Filing date	Oct 14, 2011
Priority date	Oct 14, 2011
Publication date	Sep 10, 2019
Grant date	Sep 10, 2019

Abstract

A method and system for searching a graph in parallel which constructs an abstract representation of an AND/OR graph using state-space abstraction. The abstract representation of the graph includes one or more abstract nodes having duplicate detection scopes and one or more abstract edges having operator groups adjusted for AND node outcomes. The duplicate detection scopes of the abstract nodes are partitioned into smaller duplicate detection scopes using edge partitioning, wherein the abstract edges are used to define the smaller duplicate detection scopes. Nodes in the current search layer are expanded by a processing unit using the adjusted operator groups of outgoing abstract edges of the abstract nodes mapped into by the nodes, wherein the nodes expanded in parallel use adjusted operator groups associated with abstract edges having disjoint duplicate detection scopes. The method progresses to the next search layer once all the adjusted operator groups in the current search layer have been used for node expansions.

First claim

What is claimed is:

1. A printing system, comprising:
a plurality of feeders;
a plurality of print engines;
a plurality of output trays;
memory; and
one or more electronic processing devices programmed to:
construct from an AND/OR graph in an original state space, an abstract representation of the AND/OR graph in an abstract state space, by use of state-space abstraction, which includes a many-to-one mapping process;
partition duplicate detection scopes by edge partitioning including consideration of alternative outcomes;
expand nodes in a current search layer using outcome adjusted operator groups;
chain together multiple successor OR nodes to a same AND node;
update f-costs, wherein the updating of f-costs includes updating f-costs on ancestor nodes to reflect f-costs of successor nodes, and wherein the f-costs include an edge cost or operator cost and a node cost;
progress to a next search layer once all the outcome adjusted operator groups of a present search layer are used;
repeat at least some of the foregoing steps until a termination condition is reached, and
finding a shortest path from a feeder of the plurality of feeders to an output tray of the plurality of output trays by:
treating the nodes as printing system states, and
treating edges of the AND/OR graph as relations between printing system states;

wherein the printing system is configured to output a print job on the found shortest path from the feeder of the plurality of feeders to the output tray of the plurality of output trays.

2. The printing system according to claim 1 wherein operators of the outcome adjusted operator groups are all applicable to nodes that map to a source of an abstract edge.

3. The printing system according to claim 1 wherein there exists at least one outcome such that a successor node resulting from applying operators, map to a same abstract state that is a destination of an abstract edge.

4. The printing system of claim 1 , wherein the searching of the AND/OR graph addresses non-deterministic planning problems.

5. The printing system of claim 1 , wherein the searching of the AND/OR graph automatically synthesizes workflows and action sequences in business process management.

6. A method to improve performance of non-deterministic planners, said method comprising:
constructing, from an AND/OR graph in an original state space, an abstract representation of the AND/OR graph in an abstract state space, using state-space abstraction which includes a many-to-one mapping process, wherein the abstract representation of the AND/OR graph includes one or more abstract nodes having duplicate detection scopes and one or more abstract edges having outcome-adjusted operator groups which are operator groups adjusted for AND node outcomes, wherein operators in the outcome-adjusted operator groups are annotated with a set of outcomes leading to a destination abstract state, and wherein the operators of the outcome-adjusted operator groups are all applied to nodes that map to a source of a same abstract edge;
partitioning the duplicate detection scopes of the abstract nodes into smaller duplicate detection scopes using edge partitioning, wherein the abstract edges are used to define the smaller duplicate detection scopes;
expanding nodes in a current search layer using the outcome-adjusted operator groups of outgoing abstract edges of the abstract nodes mapped into by the nodes, wherein the nodes expanded in parallel use the outcome-adjusted operator groups associated with abstract edges having disjoint duplicate detection scopes, and wherein during node expansion, only those outcomes that are associated with the operator for a particular abstract state are considered to generate OR successors of an AND search node; and,
progressing to a next search layer once all the outcome-adjusted operator groups in the current search layer have been used for node expansions;
wherein the AND/OR graph is a search graph for a planning problem in which nodes of the AND/OR graph correspond to planning states and edges correspond to transitions between system states, and wherein a source state, an action and resulting outcome are all taken into consideration in the planning problem;
wherein the steps of the method are performed using at least two processors; and
wherein the planning problem is parallelized on the at least two processors.

7. The method of claim 6 , wherein the abstract nodes are comprised of OR and AND nodes of the AND/OR graph, wherein the OR nodes of the AND/OR graph and the AND nodes with successor nodes chained together map to the abstract nodes under a state-space projection function.

8. The method of claim 7 , wherein a first abstract node of the abstract nodes is a successor of a second abstract node of the abstract nodes if a first node of the AND/OR graph is a successor of a second node of the AND/OR graph which is an OR node, the first node maps to the first abstract node under the state-space projection function, and the second node maps to the second abstract node under the state-space projection function; and
wherein a first abstract node of the abstract nodes is a successor of a second abstract node of the abstract nodes if a first node of the AND/OR graph is a successor of a second node of the AND/OR graph which is an AND node, and the first node is chained to all successors of the second node, the first node and nodes chained to the first node map to the first abstract node under the state-space projection function, and the second node maps to the second abstract node under the state-space projection function.

9. The method of claim 6 , wherein the duplicate-detection scope for an abstract edge is comprised of nodes and of the AND/OR graph mapping to a destination of the abstract edge, and the immediate successors of any AND nodes are grouped.

10. The method of claim 6 , wherein the edge partitioning includes using an operator-grouping procedure to divide a set of applicable operators O y for an abstract node y into operator groups, one for each successor of y, wherein an operator group O y,y′ is a subset of the applicable operators O y that consists of all operators and operators adjusted for AND outcomes that are associated with the abstract edge (y, y′).

11. The method of claim 6 , wherein the expanding includes generating successor nodes through incremental node expansion.

12. The method of claim 6 , wherein an OR node represents a choice of actions, and an AND represents a non-deterministic state and the successor nodes to the AND node represent possible outcomes.

13. The method of claim 12 , wherein the AND/OR graph represents business plans and possible contingencies.

14. The method of claim 6 , wherein the at least two processors comprises at least four processors.

15. The method of claim 6 , wherein:
the AND/OR graph represents business plans and possible contingencies;
an OR node represents a choice of actions; and
an AND represents a non-deterministic state and the successor nodes to the AND node represent possible outcomes.

16. A printing system, comprising:
a plurality of feeders;
a plurality of print engines;
memory; and
one or more electronic processing devices programmed to:
construct from an AND/OR graph an abstract representation of the AND/OR graph in an original state space, using state-space abstraction which includes a many-to-one mapping process, wherein the abstract representation of the AND/OR graph includes one or more abstract nodes having duplicate detection scopes and one or more abstract edges having outcome-adjusted operator groups which

Assignees

• Zhou Rong
• Do Minh Binh
• Schmidt Tim C
• Uckun Serdar
• Palo Alto Res Ct Inc

Inventors

• Zhou Rong
• Do Minh Binh
• Schmidt Tim C
• Uckun Serdar

Classifications

• G06Q10/04 Primary

  Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" (market predictions or forecasting for commercial activities G06Q30/0202) · CPC title