METHODS AND APPARATUS FOR ADVERSARIAL REASONING

• US 20090063373A1
• Filed: 08/26/2008
• Published: 03/05/2009
• Est. Priority Date: 08/30/2007
• Status: Abandoned Application

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Howard, Michael D., Huang, Eric, Leung, Kenneth Y.
• Application Number:
  US12/198,437
• Publication Number:
  US 20090063373A1
• Time in Patent Office: Days
• US Class Current: 706/11
• CPC Class Codes: A63F 13/10 Control of the course of the game, e.g. start, progess, end
• CPC Class Codes: A63F 13/45 Controlling the progress of the video game
• CPC Class Codes: A63F 13/67 adaptively or by learning from player actions, e.g. skill level adjustment or by storing successful combat sequences for re-use
• CPC Class Codes: A63F 13/822 Strategy games; Role-playing games A63F13/825, A63F13/828 take precedence
• CPC Class Codes: A63F 2300/6027 using adaptive systems learning from user actions, e.g. for skill level adjustment
• CPC Class Codes: A63F 2300/807 Role playing or strategy games
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G07F 17/3272 Games involving multiple players

Abstract

Method and apparatus for an adversarial planner to create a first plan for a first agent and a second plan for a second agent, wherein the first and second plans are independent, identify conflicts between the first and second plans, and address the identified conflicts by planning a contingency branch for one of the agents that resolves the conflict in the agent'"'"'s favor, and splicing that new branch into the agent'"'"'s plan.

Claims

1. An iterative method for generating a plan using adversarial reasoning, comprising:

creating a first plan for a first agent and a second plan for a second agent, wherein the first and second plans are independent;

identifying conflicts between the first and second plans;

replanning to address one of the identified conflicts by planning a contingency branch for the first plan that resolves the conflict in favor of the first agent;

splicing the contingency branch into the first plan; and

outputting the first plan in a format to enable a user to see the first plan using a user interface.

2. The method according to claim 1, wherein the conflict includes a first action of the first plan and a second action of the second plan having overlapping time intervals wherein the effects of the first action negates preconditions for the second action.

3. The method according to claim 2, further including providing the conflicts to a user and receiving input from the user including a user selection of a conflict to be resolved next.

4. The method according to claim 2, further including applying a metric to importance rank a plurality of conflicts and selecting the most important conflict to be resolved next.

5. The method according to claim 1, wherein the step of replanning includes iteratively moving backward in time from just before the conflict and searching for a conflict resolution plan until one or more successful resolutions are found.

6. The method according to claim 5, further including outputting successful conflict resolution plans to a user and receiving a user selection of one of the conflict resolution plans to splice into the contingency plan.

7. The method according to claim 5, further including applying a metric to rank conflict resolution plans for selecting a resolution plan to splice into the contingency plan.

8. The method according to claim 1, wherein the step of splicing includes creating at a splice point a decision node that records assertions about the world that, if true, identifies a new branch as the most successful plan.

9. An article, comprising:

a storage medium comprising computer-readable instructions that enable a machine to iteratively generate a plan using adversarial reasoning by;

creating a first plan for a first agent and a second plan for a second agent, wherein the first and second plans are independent;

identifying a conflict between the first and second plans;

replanning to address the identified conflict by planning a contingency branch for the first plan that resolves the conflict in favor of the first agent;

splicing the contingency branch into the first plan; and

outputting the first plan in a format to enable a user to see the first plan using a user interface.

10. The article according to claim 9, wherein the conflict includes a first action of the first plan and a second action of the second plan having overlapping time intervals wherein the effects of the first action negates preconditions for the second action.

11. The article according to claim 10, further including instructions for providing the conflict to a user and receiving input from the user including a user selection of a conflict to be resolved next.

12. The article according to claim 10, further including instructions for applying a metric to importance rank a plurality of conflicts to enable selection of a conflict to be resolved next.

13. The article according to claim 9, wherein the step of replanning includes iteratively moving backward in time from just before the conflict and searching for a conflict resolution plan until a successful one is found.

14. The article according to claim 9, further including instructions for outputting successful conflict resolution plans to a user and receiving a user selection of one of the conflict resolution plans to splice into the contingency plan.

15. The article according to claim 9, further including instructions for applying a metric to rank conflict resolution plans for selecting a resolution plan to splice into the contingency plan.

16. The article according to claim 9, wherein the step of splicing includes creating at a splice point a decision node that records assertions about the world that, if true, identifies a new branch as the most successful plan.

17. A planner system, comprising:

a processor;

a memory coupled to the processor; and

a module for execution by the processor to create a first plan for a first agent and a second plan for a second agent, wherein the first and second plans are independent, identify a conflict between the first and second plans, replan to address the identified conflict by planning a contingency branch for the first plan that resolves the conflict in favor of the first agent, splice the contingency branch into the first plan, and output the first plan in a format to enable a user to see the first plan using a user interface.