Using Meta-reasoning to Improve the Performance of Case-Based Planning

Presenters: Aaron Kahn and Jack Harris {aakahn, jackharr [at] Indiana [dot] edu}

Summary:

Real-Time Strategy (RTS) games provide a rich environment for research techniques to adapt and learn in non-deterministic rapidly changing domains. The research challenge of creating an agent that is capable of performing a task in a real-time domain can be explored more easily in these environments. The game engines used in these virtual environments provide a rich symbolic markup of units and traces of events that can be exploited in AI systems. In order to build effective agents the authors identified the importance of learning from past experiences. Case-Based Reasoning (CBR) systems are well suited for reuse of past cases/plans but lack the meta-level evaluation of their own performance.

The authors of this paper leverage the open source game engine, WARGUS (a WarCraft II open source clone) and augmented a previously developed Case Based Reasoner (Darmok) in order to test the utility of meta-reasoning techniques in real-time domains. The Darmok CBR was developed as a case abstraction, storage and retrieval system.** The Meta-Darmok system was created as an asynchronous component capable of introspecting on the utility of past plans (case base) and modifying what plans would be executed based on past successes and failures. The ability to tune the CBR system behavior increased the performance of the agents by 75% in their tests.

• Benefits
• Success based learning AND failure based learning

• Definitely unique for the RTS domain (Take that, scripting!)

• Dynamic behavior process modification

• Can kill/harvest more efficiently and effectively because the CBP process is tuned to the current dynamic game

• Downsides
• Domain specific

• If one small feature changes in the game dynamics (ie: add a hero element), system may not be able to handle the changes
• Equally problematic if trying to go from Wargus (Warcraft II) to Warcraft III

• Same problems that expert systems have

• If taught wrong the first time, bad forever (GIGO)
• Training takes a long time (manual)

• Same problems that CBP systems have

• In this case, type of Expert System à GIGO
• CB maintenance issues

• Same problems that Meta-Reasoning have

• Limited system resources (Can’t reason forever for RT Systems)

• Gave no indication of system growth if user1 played user2 repeatedly

• Even computers want a rematch…

• Where to go from here?
• Improve case storing via “better” expert users

• ie: minimize GIGO
• Begin automating expert tracing

• Automatic annotation?

• Possible model of the opponent

• Tactics can change depending on what the opponent is doing/who they are (Humans vs Orcs, Beginer vs Expert, etc)

• Expansion to other games?

Questions:

• How else could you build an AI system for RTS?
• When can meta-reasoning be worse?
• What are the benefits of a good RT agent?
• What other domains can this apply to?
• How would you automate expert knowledge acquisition and annotation?
• How would you introduce skill level into an opponent?