Producing clustered top-k plans

Patent metadata

Field	Value
Publication number	US-9740978-B2
Application number	US-201414525790-A
Country	US
Kind code	B2
Filing date	Oct 28, 2014
Priority date	Oct 28, 2014
Publication date	Aug 22, 2017
Grant date	Aug 22, 2017

Abstract

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.

First claim

What is claimed is:

1. A computer program product comprising a non-transitory 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 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;
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, 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;
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-rn cluster to the user, wherein the representative plan is a minimum cost plan in the top-m cluster.

2. The computer program product 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.

3. The computer program product of claim 1 , 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 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, 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 the goal node, and connect every node corresponding to a goal state to the goal node with an edge of zero cost;
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.

4. The computer program product of claim 1 , 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 the 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 new 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 new 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 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, use 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, 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.

5. The computer program product of claim 1 , 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.

6. The computer program product of claim 5 , 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.

7. The computer program product of claim 1 , 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 represen

Assignees

• IBM

Inventors

• Hassanzadeh Oktie
• Riabov Anton V
• Sohrabi Araghi Shirin
• Udrea Octavian

Classifications

• G06N5/022 Primary

  Knowledge engineering; Knowledge acquisition · CPC title

• G06F17/30598

  Physics · mapped topic

• G06N99/005

  Physics · mapped topic

• G06F16/285

  Clustering or classification · CPC title

• G06N20/00 Primary

  Machine learning · CPC title