A mechanism is provided for identifying a set of top-in 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 t
A mechanism is provided for identifying a set of top-in 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.
대표청구항▼
1. A method, in a data processing system, for identifying a set of top-m clusters from a set of top-k plans, the method comprising: receiving, by a processor in the data processing system, a planning problem for testing and treatment of a patient in a hospital and an integer value k indicating a num
1. A method, in a data processing system, for identifying a set of top-m clusters from a set of top-k plans, the method comprising: receiving, by a processor in the data processing system, a planning problem for testing and treatment of a patient in a hospital and an integer value k indicating a number of top plans to be identified for the planning problem;generating, by the processor, the 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, wherein the plan quality is measured by a cost of a plan, wherein each action in the plan is associated with an action cost encompassed in the cost of the plan, and wherein generating the set of top-k plans with at most k is performed by applying Eppstein's shortest paths algorithm to find k shortest paths in a state graph from a node corresponding to an initial state to a goal node;clustering, by the processor, 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; andpresenting, by the processor, a representative plan from each top-m cluster to the user, wherein the representative plan is a minimum cost plan in the top-m cluster. 2. The method of claim 1, wherein the planning problem includes a finite set of facts, an initial state, a finite set of action operators, and a goal condition. 3. The method of claim 1, 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. 4. The method of claim 1, 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. 5. The method of claim 1, wherein the top-k plans are generated by the method comprising: responsive to receiving a planning problem, adding, by the processor, 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, adding, by the processor, a new operator to a set of operators, adding, by the processor, positive effects of the new operator to the reachable ground predicate set, and setting, by the processor, 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, adding, by the processor, the node corresponding to the initial state to the state graph;responsive to finding an operator that does not have a corresponding edge in the state graph, adding, by the processor, a node corresponding to the state produced by the operator to the state graph, adding, by the processor, an edge corresponding to the operator to the state graph, and setting, by the processor, 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, adding, by the processor, a new node to the state graph thereby forming the goal node, and connecting, by the processor, every node corresponding to a goal state to the goal node with an edge of zero cost; andconstructing, by the processor, 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. 6. The method of claim 1, wherein the top-k plans are generated by the method comprising: responsive to receiving a top-k planning problem, creating, by the processor, a new state graph consisting of one node corresponding to the initial state, adding, by the processor, the initial state node to an unvisited list, and setting, by the processor, a distance score of the initial node to zero;selecting and removing, by the processor, a node with a lowest heuristic score, computed based on distance score, from the unvisited list, and adding, by the processor, the selected node to a closed list;responsive to finding a new operator that may be applied to the state of the selected node: computing, by the processor, 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, adding, by the processor, a node to the new state graph corresponding to the produced state to the unvisited list, assigning, by the processor, the new distance score as the nodes distance score, and adding, by the processor, a link to the new state graph that connects the selected state node and the produced state node corresponding to the action; andresponsive to determining that there is a node corresponding to the produced state on unvisited list, updating, by the processor, the score of the produced node using the new score and adding, by the processor, a link to the new 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 new state graph being expanded by preset percentage, and responsive to the goal state being reached, using, by the processor, the new state graph to construct the 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, repeating, by the processor, the process until k-shortest paths are identified; andresponsive to k shortest paths being found, for each found path, constructing, by the processor, a plan by traversing the path from the initial state to the goal state, and adding, by the processor, an instance of the action for each action corresponding to an edge in the path. 7. The method of claim 1, wherein clustering each plan of the set of top-k plans is performed by the method comprising: iterating, by the processor, over the top-k plans starting with a highest-quality plan;responsive to the existence of at least one cluster, determining, by the processor, 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, adding, by the processor, 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, creating, by the processor, a new cluster and adding, by the processor, the plan to the new cluster such that the plan becomes the new cluster's representative plan; andresponsive to the non-existence of the at least one cluster, creating, by the processor, a new cluster and adding, by the processor, the plan to the new cluster such that the plan becomes the new cluster's representative plan. 8. The method of claim 7, wherein determining the similarity to the representative plan of the at least one existing cluster is performed by the method comprising: comparing, by the processor, 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;viewing, by the processor, each state of a plan as a “token” in a string and the sequence of states as the string;using the sequence of states, determining, by the processor, a relationship between states to determine whether two plans in the set of top-k plans belong to a same cluster; andcomputing, by the processor, a similarity score as a minimum transformation cost required to convert one string to another string. 9. The method of claim 1, wherein clustering each plan of the set of top-k plans is performed by the method comprising: iterating, by the processor, over the top-k plans starting with a highest-quality plan;responsive to the existence of at least one cluster, determining, by the processor, 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, adding, by the processor, 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, creating, by the processor, a new cluster and adding, by the processor, the plan to the new cluster such that the plan becomes the new cluster's representative plan; andresponsive to the non-existence of the at least one cluster, creating, by the processor, a new cluster and adding, by the processor, the plan to the new cluster such that the plan becomes the new cluster's representative plan. 10. The method of claim 1, wherein clustering each plan of the set of top-k plans is performed by the method comprising: iterating, by the processor, over the top-k plans starting with a highest-quality plan;responsive to the existence of at least one cluster, determining, by the processor, a 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, adding, by the processor, 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, creating, by the processor, a new cluster and adding, by the processor, the plan to the new cluster such that the plan becomes the new cluster's representative plan; andresponsive to the non-existence of the at least one cluster, creating, by the processor, a new cluster and adding, by the processor, the plan to the new cluster such that the plan becomes the new cluster's representative plan. 11. The method of claim 1, where the planning problem is obtained by translating inputs to a hypotheses generation problem, a trace, and a state transition model.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (4)
Tran My (Albuquerque NM), Aircraft survivability system state management.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.