Producing Clustered Top-K Plans

Patent metadata

Field	Value
Publication number	US-2016117602-A1
Application number	US-201514745899-A
Country	US
Kind code	A1
Filing date	Jun 22, 2015
Priority date	Oct 28, 2014
Publication date	Apr 28, 2016
Grant date	—

Abstract

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.

First claim

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 and an integer value k indicating a number of top plans to be identified; 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; 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; and presenting, by the processor, a representative plan from each top-m cluster to the user.

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, 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, 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 a goal node, and connecting, by the processor, every node corresponding to a goal state to the goal node with an edge of zero cost; applying, by the processor, 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 constructing, 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 an 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 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 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, updating, by the processor, the score of the produced node using the new score and adding, by the processor, 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, using, by the processor, 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, repeating, by the processor, the process until k-shortest paths are identified; and responsive 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; and responsive 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; and computing, 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

Assignees

• IBM

Inventors

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

Classifications

• G06N99/005 Primary

  Physics · mapped topic

• G06F17/30598

  Physics · mapped topic

• G06F16/285

  Clustering or classification · CPC title

• G06N20/00 Primary

  Machine learning · CPC title

• G06N5/022 Primary

  Knowledge engineering; Knowledge acquisition · CPC title