A mechanism is provided for identifying a set of top-m clusters from a set of top-k plans. A planning problem and an integer value k indicating a number of top plans to be identified are received. A set of top-k plans are generated with at most size k, where the set of top-k plans is with respect to a given measure of plan quality. Each plan in the set of top-k plans is clustered based on a similarity between plans such that each cluster contains similar plans and each plan is grouped only into one cluster thereby forming the set of top-m clusters. A representative plan from each top-m cluster is presented to the user.
Please help me write a proper abstract based on the patent claims. CLAIM: 1-11. (canceled) 12. A computer program product comprising a computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a computing device, causes the computing device to: receive a planning problem and an integer value k indicating a number of top plans to be identified; generate a set of top-k plans with at most size k, wherein the set of top-k plans is with respect to a given measure of plan quality; cluster each plan in the set of top-k plans based on a similarity between plans such that each cluster contains similar plans and each plan is grouped only into one cluster thereby forming the set of top-m clusters; and present a representative plan from each top-m cluster to the user. 13. The computer program product of claim 12, wherein the integer value k is at least one of a fixed integer or a function indicating a percentage of an optimal plan other identified plans must be within. 14. The computer program product of claim 12, wherein the computer readable program generates the top-k plans by causing the computing device to: responsive to receiving a planning problem, add all initial state predicates to a reachable ground predicate set; responsive to finding a subset of the reachable ground predicate set that satisfies the precondition of one of the actions, add a new operator to a set of operators, add positive effects of the new operator to the reachable ground predicate set, and set an operator cost equal to action cost; responsive to a failure to find a subset of the reachable ground predicate set that satisfies the precondition of one of the actions, add a node corresponding to an initial state to a state graph; responsive to finding an operator that does not have a corresponding edge in the state graph, add a node corresponding to the state produced by the operator to the state graph, add an edge corresponding to the operator to the state graph, and set a cost of the edge equal to the operator cost; responsive to a failure to find an operator that does not have a corresponding edge in the state graph, add a new node to the state graph thereby forming a goal node, and connect every node corresponding to a goal state to the goal node with an edge of zero cost; apply Eppstein's algorithm to find k shortest paths in the state graph from the node corresponding to the initial state to the goal node; and construct the set of top-k plans by traversing each path from the initial state to the goal state and adding an instance of the action for each operator corresponding to an edge in the path. 15. The computer program product of claim 12, wherein the computer readable program generates the top-k plans by causing the computing device to: responsive to receiving a top-k planning problem, create a new state graph consisting of one node corresponding to an initial state, add the initial state node to an unvisited list, and set a distance score of the initial node to zero; select and remove a node with a lowest heuristic score, computed based on distance score, from the unvisited list, and add the selected node to a closed list; responsive to finding a new operator that may be applied to the state of the selected node: compute a new distance score of the state produced by the operator as the sum of the score of the selected node and the cost of the action; responsive to determining that there is not a node corresponding to the produced state on unvisited list, add a node to the state graph corresponding to the produced state to the unvisited list, assign the new distance score as the nodes distance score, and add a link to the state graph that connects the selected state node and the produced state node corresponding to the action; and responsive to determining that there is a node corresponding to the produced state on unvisited list, update the score of the produced node using the new score and add a link to the state graph that connects the selected state node and the produced state node corresponding to the action; responsive to the unvisited list being empty and responsive to the goal state being reached, or responsive to the unvisited list failing to be empty, the state graph being expanded by preset percentage, and responsive to the goal state being reached, use the state graph to construct k shortest paths from the initial state to any goal state using Eppstein's k shortest paths algorithm; responsive to a failure to identify k shortest paths, repeat the process until k-shortest paths are identified; and responsive to k shortest paths being found, for each found path, construct a plan by traversing the path from the initial state to the goal state, and add an instance of the action for each action corresponding to an edge in the path. 16. The computer program product of claim 12, wherein the computer readable program clusters each plan of the set of top-k plans by causing the computing device to: iterate over the top-k plans starting with a highest-quality plan; responsive to the existence of at least one cluster, determine a similarity to a representative plan of the at least one existing cluster; responsive to the plan being similar to the representative plan in the at least one cluster, add the plan to the at least one cluster; responsive to the plan failing to be similar to the representative plan in the at least one cluster, create a new cluster and add the plan to the new cluster such that the plan becomes the new cluster's representative plan; and responsive to the non-existence of the at least one cluster, create a new cluster and add the plan to the new cluster such that the plan becomes the new cluster's representative plan. 17. The computer program product of claim 16, wherein the computer readable program determines the similarity to the representative plan of the at least one existing cluster by causing the computing device to: compare the plans in the set of top-k plans as a comparison of a sequence of strings, wherein the comparison only considers a state transition sequence of each plan; view each state of a plan as a “token” in a string and the sequence of states as the string; using the sequence of states, determine a relationship between states to determine whether two plans in the set of top-k plans belong to a same cluster; and compute a similarity score as a minimum transformation cost required to convert one string to another string. 18. The computer program product of claim 12, wherein the computer readable program clusters each plan of the set of top-k plans by causing the computing device to: iterate over the top-k plans starting with a highest-quality plan; responsive to the existence of at least one cluster, determine a similarity to a plan in the at least one existing cluster, responsive to the plan being similar to an existing plan in the at least one cluster, add the plan to the at least one cluster; responsive to the plan failing to be similar to any existing plan in the at least one cluster, create a new cluster and add the plan to the new cluster such that the plan becomes the new cluster's representative plan; and responsive to the non-existence of the at least one cluster, create a new cluster and add the plan to the new cluster such that the plan becomes the new cluster's representative plan. 19. The computer program product of claim 12, wherein the computer readable program clusters each plan of the set of top-k plans by causing the computing device to: iterate over the top-k plans starting with a highest-quality plan; responsive to the existence of at least one cluster, determinea similarity, on average, to all the plans in the at least one existing cluster, responsive to the plan being similar, on average, to an existing plan in the at least one cluster, add the plan to the at least one cluster; responsive to the plan failing to be similar, on average, to any existing plan in the at least one cluster, create a new cluster and add the plan to the new cluster such that the plan becomes the new cluster's representative plan; and responsive to the non-existence of the at least one cluster, create a new cluster and add the plan to the new cluster such that the plan becomes the new cluster's representative plan. 20. An apparatus comprising: a processor, and a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to: receive a planning problem and an integer value k indicating a number of top plans to be identified; generate a set of top-k plans with at most size k, wherein the set of top-k plans is with respect to a given measure of plan quality; cluster each plan in the set of top-k plans based on a similarity between plans such that each cluster contains similar plans and each plan is grouped only into one cluster thereby forming the set of top-m clusters; and present a representative plan from each top-m cluster to the user. 21. The apparatus of claim 20, wherein the planning problem includes a finite set of facts, an initial state, a finite set of action operators, and a goal condition. 22. The apparatus of claim 20, wherein the integer value k is at least one of a fixed integer or a function indicating a percentage of an optimal plan other identified plans must be within. 23. The apparatus of claim 20, wherein the plan quality is measured by a cost of the plan and wherein each action in the plan is associated with an action cost. 24. The apparatus of claim 20, wherein the instructions generate the top-k plans by causing the processor to: responsive to receiving a planning problem, add all initial state predicates to a reachable ground predicate set; responsive to finding a subset of the reachable ground predicate set that satisfies the precondition of one of the actions, add a new operator to a set of operators, add positive effects of the new operator to the reachable ground predicate set, and set an operator cost equal to action cost; responsive to a failure to find a subset of the reachable ground predicate set that satisfies the precondition of one of the actions, add a node corresponding to an initial state to a state graph; responsive to finding an operator that does not have a corresponding edge in the state graph, add a node corresponding to the state produced by the operator to the state graph, add an edge corresponding to the operator to the state graph, and set a cost of the edge equal to the operator cost; responsive to a failure to find an operator that does not have a corresponding edge in the state graph, add a new node to the state graph thereby forming a goal node, and connect every node corresponding to a goal state to the goal node with an edge of zero cost; apply Eppstein's algorithm to find k shortest paths in the state graph from the node corresponding to the initial state to the goal node; and construct the set of top-k plans by traversing each path from the initial state to the goal state and adding an instance of the action for each operator corresponding to an edge in the path. 25. The apparatus of claim 20, wherein the instructions generate the top-k plans by causing the processor to: responsive to receiving a top-k planning problem, create a new state graph consisting of one node corresponding to an initial state, add the initial state node to an unvisited list, and set a distance score of the initial node to zero; select and remove a node with a lowest heuristic score, computed based on distance score, from the unvisited list, and add the selected node to a closed list; responsive to finding a new operator that may be applied to the state of the selected node: compute a new distance score of the state produced by the operator as the sum of the score of the selected node and the cost of the action; responsive to determining that there is not a node corresponding to the produced state on unvisited list, add a node to the state graph corresponding to the produced state to the unvisited list, assign the new distance score as the nodes distance score, and add a link to the state graph that connects the selected state node and the produced state node corresponding to the action; and responsive to determining that there is a node corresponding to the produced state on unvisited list, update the score of the produced node using the new score and add a link to the state graph that connects the selected state node and the produced state node corresponding to the action; responsive to the unvisited list being empty and responsive to the goal state being reached, or responsive to the unvisited list failing to be empty, the state graph being expanded by preset percentage, and responsive to the goal state being reached, use the state graph to construct k shortest paths from the initial state to any goal state using Eppstein's k shortest paths algorithm; responsive to a failure to identify k shortest paths, repeat the process until k-shortest paths are identified; and responsive to k shortest paths being found, for each found path, construct a plan by traversing the path from the initial state to the goal state, and add an instance of the action for each action corresponding to an edge in the path. 26. The apparatus of claim 20, wherein the instructions cluster each plan of the set of top-k plans by causing the processor to: iterate over the top-k plans starting with a highest-quality plan; responsive to the existence of at least one cluster, determine a similarity to a representative plan of the at least one existing cluster; responsive to the plan being similar to the representative plan in the at least one cluster, add the plan to the at least one cluster; responsive to the plan failing to be similar to the representative plan in the at least one cluster, create a new cluster and add the plan to the new cluster such that the plan becomes the new cluster's representative plan; and responsive to the non-existence of the at least one cluster, create a new cluster and add the plan to the new cluster such that the plan becomes the new cluster's representative plan. 27. The apparatus of claim 26, wherein the instructions determine the similarity to the representative plan of the at least one existing cluster by causing the processor to: compare the plans in the set of top-k plans as a comparison of a sequence of strings, wherein the comparison only considers a state transition sequence of each plan; view each state of a plan as a “token” in a string and the sequence of states as the string; using the sequence of states, determine a relationship between states to determine whether two plans in the set of top-k plans belong to a same cluster, and compute a similarity score as a minimum transformation cost required to convert one string to another string. 28. The apparatus of claim 20, wherein the instructions cluster each plan of the set of top-k plans by causing the processor to: iterate over the top-k plans starting with a highest-quality plan; responsive to the existence of at least one cluster, determine a similarity to a plan in the at least one existing cluster; responsive to the plan being similar to an existing plan in the at least one cluster, add the plan to the at least one cluster; responsive to the plan failing to be similar to any existing plan in the at least one cluster, create a new cluster and add the plan to the new cluster such that the plan becomes the new cluster's representative plan; and responsive to the non-existence of the at least one cluster, create a new cluster and add the plan to the new cluster such that the plan becomes the new cluster's representative plan. 29. The apparatus of claim 20, wherein the instructions cluster each plan of the set of top-k plans by causing the processor to: iterate over the top-k plans starting with a highest-quality plan; responsive to the existence of at least one cluster, determinea similarity, on average, to all the plans in the at least one existing cluster, responsive to the plan being similar, on average, to an existing plan in the at least one cluster, add the plan to the at least one cluster; responsive to the plan failing to be similar, on average, to any existing plan in the at least one cluster, create a new cluster and add the plan to the new cluster such that the plan becomes the new cluster's representative plan; and responsive to the non-existence of the at least one cluster, create a new cluster and add the plan to the new cluster such that the plan becomes the new cluster's representative plan. 30. The apparatus of claim 20, where the planning problem is obtained by translating inputs to a hypotheses generation problem, a trace, and a state transition model. 31. The computer program product of claim 12, where the planning problem is obtained by translating inputs to a hypotheses generation problem, a trace, and a state transition model.