US 7,584,444 B2 · System and method for external-memory graph search utilizing edge partitioning

Abstract

A method and system is provided for generator successor nodes in an external-memory search of a graph having a plurality of nodes and outgoing edges of the plurality of nodes. The method and system includes construction of an abstract representation of the graph to include a set of abstract nodes and abstract outgoing edges of the abstract set of nodes. The edges of the graph are partitioned based on the abstract representation of the graph. The partitioning includes grouping edges (or instantiated operators of a search problem) that map to the same abstract edge of the abstract representation together as isomorphic edges. Successor nodes along outgoing edges that belong to the same group are generated consecutively. By this design, partial and incremental expansion of nodes can be achieved in order to limit the number of time-consuming I/O (or other communication) operations in search algorithms that take advantage of the memory hierarchy in a computer system, such as those that use disk storage.

Claims27

Dependent claims

A method for generating successor nodes in an external-memory search of a graph having a plurality of nodes and outgoing edges of the plurality of nodes, the method comprising:

generating a plan representing actions to be taken in a physical environment to solve real world problems, the plan being at least partially represented by a graph having nodes identifying the potential actions to be taken;
constructing an abstract representation of the graph to include a set of abstract nodes and abstract edges of the graph;
partitioning the outgoing edges of the graph based on the abstract representation of the graph, the partitioning including grouping edges that map to a same abstract edge of the abstract representation together as isomorphic edges;
using only one group of isomorphic edges at a time to generate successors consecutively for a set of nodes that map to the same abstract edge;
choosing a different group of isomorphic edges once the edges in a previous group have been used to generate successors, until a goal node is found or other termination condition is met;
searching, by a computer, the graph using the abstract representation of the graph;
and
retrieving a result representing a solution to the real world problem based on the search.

5 more elements

A system for generating successor nodes in an external-memory search of a graph having a plurality of nodes and outgoing edges, the system comprising:

a plan representing actions to be taken in a physical environment to solve real world problems, the plan being at least partially represented by a graph having nodes identifying the potential actions to be taken;
a computing system having computer instructions on a computer readable medium, an internal memory and an external memory, the computer instructions programmed to:
construct an abstract representation of the graph to include a set of abstract nodes and abstract edges of the graph;
partition the edges of the graph based on the abstract representation of the graph by grouping edges that map to the same abstract edge of the abstract representation together as isomorphic edges;
and
use one or more group(s) of isomorphic edges to generate successor nodes for a set of nodes that map to the same abstract node at a time, wherein nodes within a current duplicate-detection scope are stored in internal memory, and nodes outside of the current duplicate-detection scope can, but do not have to, be stored in external memory
search the graph using the abstract representation of the graph;
and
retrieve a result representing a solution to the real world problem based on the search.

6 more elements

Dependencies are inferred from the claim text.

System and method for external-memory graph search utilizing edge partitioning

Life of this patent

System and method for external-memory graph search utilizing edge partitioning

Life of this patent

Abstract

Claims27