Patent ID: 7584444

Claim:
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.