Method and apparatus for determining viability of path expansions
First Claim
1. For a path search that identifies a path between source and target states in a space, a method of determining viability of an expansion of a path from a first state to a second state, wherein the second state is a dimensional state, the method comprising:
- a) computing a first cost function that expresses a cost of the path to reach the second state, wherein the first cost function is defined over the second state;
b) determining whether the first cost function expresses a better cost over any portion of the second state than a second cost function, wherein the second cost function expresses the best cost of paths that have reached the second state during the path search;
wherein the expansion is a viable one if the first cost function expresses a better cost over at least a portion of the second state than the second cost function, wherein said portion of said second state is less than said second state.
1 Assignment
0 Petitions
Accused Products
Abstract
For a path search that identifies a path between source and target states in a space, some embodiments of the invention provide a method for determining viability of an expansion of a path from a first state to a second dimensional state. The method computes a first cost function that expresses the cost of the path to reach the second state. The first cost function is defined over the second state. The method then determines whether the first cost function expresses a better cost over any portion of the second state than a second cost function that expresses the best cost of paths that have reached the second state during the path search. The expansion is a viable one if the first cost function expresses a better cost over at least a portion of the second state than the second cost function.
-
Citations
15 Claims
-
1. For a path search that identifies a path between source and target states in a space, a method of determining viability of an expansion of a path from a first state to a second state, wherein the second state is a dimensional state, the method comprising:
-
a) computing a first cost function that expresses a cost of the path to reach the second state, wherein the first cost function is defined over the second state;
b) determining whether the first cost function expresses a better cost over any portion of the second state than a second cost function, wherein the second cost function expresses the best cost of paths that have reached the second state during the path search;
wherein the expansion is a viable one if the first cost function expresses a better cost over at least a portion of the second state than the second cost function, wherein said portion of said second state is less than said second state. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A computer readable medium that stores a computer program having executable code, the computer program for a method of determining viability of an expansion of a path from a first state to a second state in a space, wherein the second state is a dimensional state, the computer program comprises sets of instructions for:
-
a) computing a first cost function that expresses a cost of the path to reach the second state, wherein the first cost function is defined over the second state;
b) determining whether the first cost function expresses a better cost over any portion of the second state than a second cost function, wherein the second cost function expresses the best cost of paths that have reached the second state during the path search;
wherein the expansion is a viable one if the first cost function expresses a better cost over at least a portion of the second state than the second cost function, wherein said portion of said second state is less than said second state. - View Dependent Claims (10, 11, 12, 13, 14, 15)
-
Specification