Posts Tagged ‘problem solving’

Real-Time Case-Based Reasoning for Interactive Digital Entertainment

(Click image to view the video – it’s near the bottom of the new page.)

User-generated content is everywhere: photos, videos, news, blogs, art, music, and every other type of digital media on the Social Web. Games are no exception. From strategy games to immersive virtual worlds, game players are increasingly engaged in creating and sharing nearly all aspects of the gaming experience: maps, quests, artifacts, avatars, clothing, even games themselves. Yet, there is one aspect of computer games that is not created and shared by game players: the AI. Building sophisticated personalities, behaviors, and strategies requires expertise in both AI and programming, and remains outside the purview of the end user.

To understand why authoring Game AI is hard, we need to understand how it works. AI can take digital entertainment beyond scripted interactions into the arena of truly interactive systems that are responsive, adaptive, and intelligent. I will discuss examples of AI techniques for character-level AI (in embedded NPCs, for example) and game-level AI (in the drama manager, for example). These types of AI enhance the player experience in different ways. The techniques are complicated and are usually implemented by expert game designers.

I propose an alternative approach to designing Game AI: Real-Time CBR. This approach extends CBR to real-time systems that operate asynchronously during game play, planning, adapting, and learning in an online manner. Originally developed for robotic control, Real-Time CBR can be used for interactive games ranging from multiplayer strategy games to interactive believable avatars in virtual worlds.

As with any CBR technique, Real-Time CBR integrates problem solving with learning. This property can be used to address the authoring problem. I will show the first Web 2.0 application that allows average users to create AIs and challenge their friends to play them—without programming. I conclude with some thoughts about the role of CBR in AI-based Interactive Digital Entertainment.

Keynote talk at the Eighteenth Conference on Pattern Recognition and Artificial Intelligence (RFIA-12), Lyon, France, February 5, 2012.
Slides and video here: rfia2012.liris.cnrs.fr/doku.php?id=pub:ram
 
Keynote talk at the Eleventh Scandinavian Conference on Artificial Intelligence (SCAI-11), Trondheim, Norway, May 25, 2011.
 
Keynote talk at the 2010 International Conference on Case-Based Reasoning (ICCBR-10), Alessandria, Italy, July 22, 2010.
 
GVU Brown Bag talk, October 14, 2010. Watch the talk here: www.gvu.gatech.edu/node/4320 
 
Try it yourself:
Learn more about the algorithms:
View the talk:
www.sais.se/blog/?p=57

View the slides:

User-Generated AI for Interactive Digital Entertainment

CMU Seminar

User-generated content is everywhere: photos, videos, news, blogs, art, music, and every other type of digital media on the Social Web. Games are no exception. From strategy games to immersive virtual worlds, game players are increasingly engaged in creating and sharing nearly all aspects of the gaming experience: maps, quests, artifacts, avatars, clothing, even games themselves. Yet, there is one aspect of computer games that is not created and shared by game players: the AI. Building sophisticated personalities, behaviors, and strategies requires expertise in both AI and programming, and remains outside the purview of the end user.

To understand why Game AI is hard, we need to understand how it works. AI can take digital entertainment beyond scripted interactions into the arena of truly interactive systems that are responsive, adaptive, and intelligent. I discuss examples of AI techniques for character-level AI (in embedded NPCs, for example) and game-level AI (in the drama manager, for example). These types of AI enhance the player experience in different ways. The techniques are complicated and are usually implemented by expert game designers.

I argue that User-Generated AI is the next big frontier in the rapidly growing Social Gaming area. From Sims to Risk to World of Warcraft, end users want to create, modify, and share not only the appearance but the “minds” of their characters. I present my recent research on intelligent technologies to assist Game AI authors, and show the first Web 2.0 application that allows average users to create AIs and challenge their friends to play them—without programming. I conclude with some thoughts about the future of AI-based Interactive Digital Entertainment.

CMU Robotics & Intelligence Seminar, September 28, 2009
Carnegie-Mellon University, Pittsburgh, PA.
MIT Media Lab Colloquium, January 25, 2010
Massachusetts Institute of Technology, Cambridge, MA.
Stanford Media X Philips Seminar, February 1, 2010
Stanford University, Stanford, CA.
Pixar Research Seminar, February 2, 2010

Try it yourself:
Learn more about the algorithms:
View the talk:
www.sais.se/blog/?p=57

View the slides:

Drama Management and Player Modeling for Interactive Fiction Games

A growing research community is working towards employing drama management components in story-based games. These components gently guide the story towards a narrative arc that improves the player’s gaming experience. In this paper we evaluate a novel drama management approach deployed in an interactive fiction game called Anchorhead. This approach uses player’s feedback as the basis for guiding the personalization of the interaction.

The results indicate that adding our Case-based Drama manaGer (C-DraGer) to the game guides the players through the interaction and provides a better overall player experience. Unlike previous approaches to drama management, this paper focuses on exhibiting the success of our approach by evaluating results using human players in a real game implementation. Based on this work, we report several insights on drama management which were possible only due to an evaluation with real players.

Read the paper:

Drama Management and Player Modeling for Interactive Fiction Games

by Manu Sharma, Santi Ontañón, Manish Mehta, Ashwin Ram

Computational Intelligence, 26(2):183-211, 2010.
www.cc.gatech.edu/faculty/ashwin/papers/er-09-10.pdf
www3.interscience.wiley.com/journal/123387570/abstract

An Ensemble Learning and Problem Solving Architecture for Airspace Management

In this paper we describe the application of a novel learning and problem solving architecture to the domain of airspace management, where multiple requests for the use of airspace need to be reconciled and managed automatically. The key feature of our “Generalized Integrated Learning Architecture” (GILA) is a set of integrated learning and reasoning (ILR) systems coordinated by a central meta-reasoning executive (MRE). Each ILR learns independently from the same training example and contributes to problem-solving in concert with other ILRs as directed by the MRE. Formal evaluations show that our system performs as well as or better than humans after learning from the same training data. Further, GILA outperforms any individual ILR run in isolation, thus demonstrating the power of the ensemble architecture for learning and problem solving.

Read the paper:

An Ensemble Learning and Problem Solving Architecture for Airspace Management

by XS Zhang et al.

International Conference on Innovative Applications of Artificial Intelligence (IAAI-09), Pasadena, CA, July 2009
www.cc.gatech.edu/faculty/ashwin/papers/er-09-03.pdf

Goal-Driven Learning in the GILA Integrated Intelligence Architecture

Goal Driven Learning (GDL) focuses on systems that determine by themselves what has to be learned and how to learn it. Typically GDL systems use meta-reasoning capabilities over a base reasoner, identifying learning goals and devising strategies. In this paper we present a novel GDL technique to deal with complex AI systems where the meta-reasoning module has to analyze the reasoning trace of multiple components with potentially different learning paradigms. Our approach works by distributing the generation of learning strategies among the different modules instead of centralizing it in the meta-reasoner. We implemented our technique in the GILA system, that works in the airspace task orders domain, showing an increase in performance.

Read the paper:

Goal-Driven Learning in the GILA Integrated Intelligence Architecture

by Jai Radhakrishnan, Santi Ontañón, Ashwin Ram

International Joint Conference on Artificial Intelligence (IJCAI-09), Pasadena, CA, July 2009
www.cc.gatech.edu/faculty/ashwin/papers/er-09-02.pdf

Argumentation-Based Information Exchange in Prediction Markets

We investigate how argumentation processes among a group of agents may affect the outcome of group judgments. In particular we focus on prediction markets (also called information markets). We investigate how the existence of social networks (that allow agents to argue with one another to improve their individual predictions) effect on group judgments.

Social networks allow agents to exchange information about the group judgment by arguing about the most likely choice based on their individual experience. We develop an argumentation-based deliberation process by which the agents acquire new and relevant information. Finally, we experimentally assess how different social network connectivity affect group judgment.

Read the paper:

Argumentation-based Information Exchange in Prediction Markets

by Santi Ontañón and Enric Plaza

in ArgMAS 2008, pp. 181 – 196
www.cc.gatech.edu/faculty/ashwin/papers/er-08-12.pdf

Case-Based Reasoning for Gas Turbine Diagnostics

General Electric used case-based reasoning for gas turbine diagnostics at their monitoring and diagnostics center in Atlanta, GA. This application had requirements that included accuracy, maintainability, modularity, parameterization, robustness, and integration of the system into an existing infrastructure. The CBR system has a modular “plug and play” architecture to facilitate experimentation and optimization. It was integrated into the production environment in 2004. The CBR system is currently in a trial deployment where diagnoses made by the system are created along with the previous process of using human-generated diagnosis.

Case-Based Reasoning for Gas Turbine Diagnostics

by Mark Devaney, Bill Cheetham

18th International FLAIRS Conference (FLAIRS-05), Clearwater, FL, May 2005
www.cc.gatech.edu/faculty/ashwin/papers/er-05-05.pdf

Plan Recognition in Large-Scale Multi-Agent Tactical Domains

This research addresses the task of representing and recognizing events in a tactical domain from large-scale spatio-temporal data under conditions of limited observability and high noise with real-time response constraints.  These assumptions differ from those traditionally made in  plan recognition and produce a problem that combines aspects of plan recognition, pattern recognition and object tracking. This research provides evidence that parsimonious qualitative representations used to represent pair-wise interactions among agents can be combined to identify large-scale group behaviors that form the basis of increasingly complex patterns of activity.

A comprehensive software application was constructed to demonstrate the claims of the thesis by evaluating performance on a real-world problem involving the recognition of a tactical maneuver in actual US Army training battles.  Evaluations were conducted and performance evaluated by both novices and active military subject matter experts.

Plan Recognition in Large-Scale Multi-Agent Tactical Domains

by Mark Devaney

PhD Thesis, College of Computing, Georgia Institute of Technology, Atlanta, GA, 2003
www.cc.gatech.edu/faculty/ashwin/papers/git-cc-03-01.ps.zip

IRIA: The Information Research Intelligent Assistant

The explosion of information in the modern environment demands the ability to collect, organize, manage, and search large amounts of information across a wide variety of real-world applications. The primary tools available for such tasks are large-scale database systems and keyword-based document search techniques. However, such tools are rapidly proving inadequate: traditional database systems do not enable ready access to relevant knowledge, prompting a market of add-ons and existing search techniques are insufficiently precise or selective to support such tasks, leading to consumer exasperation. In the end users are left unsatisfied, confronted with a sea of unorganized and unhelpful data. A new approach is needed.

The Information Research Intelligent Assistant (IRIA) is an integrated information retrieval architecture that addresses this problem. IRIA enables a user or workgroup to build a personalized map of the relevant information available in a database, intranet, or internet, and the ability to find, add, and use information quickly and easily. An IRIA-based intelligent information management system acts as an autonomous assistant to a user working on a task, working unobtrusively in the background to learn both the user’s interests and the resources available to satisfy those interests. This approach enables “reminding engines” which monitor a user’s work to proactively find and recommend useful information as well as “workgroup memories” which learn from a user’s behavior to build a comprehensive knowledge map of a particular area of interest.

In empirical tests, IRIA has demonstrated the ability to monitor a user’s progress on a task (specifically, web search) and proactively find and recommend information relevant to that task based on the context and history of the user’s interactions with the system. IRIA further demonstrated that it could provide collaborative facilities to the workgroup and that it could learn and improve its knowledge map over time.

Read the paper:

IRIA: The Information Research Intelligent Assistant

by Anthony Francis, Mark Devaney, Ashwin Ram

International Conference on Artificial Intelligence (ICAI-00), Las Vegas, Nevada
www.dresan.com/research/publications/icai-2000.html

Context-Sensitive Asynchronous Memory

Retrieving useful answers from large knowledge bases given under-specified questions is an important problem in the construction of general intelligent agents. The core of this problem is how to get the information an agent needs when it doesn’t know how to ask the right question and doesn’t have the time to exhaustively search all available information.

Context-sensitive asynchronous memory is a model of memory retrieval that solves this problem. The context-sensitive asynchronous memory approach exploits feedback from the task and environment to guide and constrain memory search by interleaving memory retrieval and problem solving. To achieve this behavior, a context-sensitive asynchronous memory uses an asynchronous retrieval system to manage a context- sensitive search process operating over a content-addressable knowledge base. Solutions based on this approach provide useful answers to vague questions efficiently, based on information naturally available during the performance of a task.

The core claims of this approach are:
•  Claim 1: An efficient, domain-independent solution to the problem of retrieving useful answers from large knowledge bases given under-specified queries is to interleave memory retrieval with task performance and use feedback from the task or environment to guide the search of memory.
•  Claim 2: Interleaving memory retrieval with and exploiting feedback from task performance can be achieved in a domain-independent way using a context- sensitive, asynchronous memory retrieval process.
•  Claim 3: A rich, reified, grounded semantic network representation enables context-sensitive memory retrieval processes to retrieve useful information in a domain-independent way for a wide variety of tasks.
•  Claim 4: To effectively use a context-sensitive asynchronous memory to retrieve useful answers, a task must be able to work in parallel with a memory process, communicate with it, provide feedback to it, and must possess integration mechanisms to incorporate asynchronous retrievals provided by the memory.

The context-sensitive asynchronous memory approach is applicable to tasks and domains which exhibit the following criteria: problems are difficult to solve, questions are difficult to formulate, a large knowledge base is available yet contains only a small selection of relevant information, and, most importantly, the environment is regular, in that solutions in the knowledge base occur in patterns and relationships similar to those found in situations in which the solutions are likely to be applicable in the future. This approach is domain independent: it is applicable to a wide variety of tasks and problems from simple search applications to complex cognitive agents.

To exploit context-sensitive asynchronous memory, reasoners need certain properties. Experience-based agency is an agent architecture which provides an outline of how to construct complete intelligent agents which use a context-sensitive asynchronous memory to support a reasoning system performing a real task. The experience-based agent architecture combines a context-sensitive asynchronous memory retrieval process with a global store of experience used by all agent processes, a global working memory to provide a uniform way to collect feedback, and a global task controller which orchestrates reasoning and memory. The experience-based agent architecture also provides principles for constructing integration mechanisms that enable reasoning tasks to work with the context-sensitive asynchronous memory.

Furthermore, to help determine when these approaches should be used, this research also contributes theoretical analyses that predict the classes of tasks and situations in which the context-sensitive asynchronous memory and experience-based agent approaches will provide the greatest benefit.

To evaluate the approach, the experience-based agent architecture has been implemented in the Nicole system. Nicole is a large Common Lisp program providing global long-term and working memory stores represented as a rich, reified, grounded semantic network, a context-sensitive asynchronous memory process based on a novel model of context-directed spreading activation, a control system for orchestrating reasoning and memory, and a task language to implement reasoning tasks. Nicole enables the context-sensitive asynchronous memory approach to be applied to real problems, including information retrieval in Nicole-IRIA, a information management application that uses context to recommend useful information (Francis et al. 2000), planning in Nicole-MPA, a case-based least-commitment planner that adapts multiple plans (Ram & Francis 1995) and language understanding in ISAAC (Moorman 1997), a story understanding system which uses Nicole’s retrieval system as part of its creative understanding process. Nicole and her children thus provide a testbed to evaluate the context-sensitive asynchronous memory approach.

Experiments with Nicole support the claims of the approach. Experiments with Nicole-IRIA demonstrate that a context-sensitive asynchronous memory can use feedback from browsing to improve the quality of memory retrieval, while experiments with Nicole-MPA demonstrate how information derived from reasoning can improve the quantity of retrieval. The use of Nicole’s memory in the ISAAC system demonstrates the generality of the context-sensitive asynchronous memory approach. Other experiments with Nicole-MPA demonstrate the importance of representation as a source of power for context-sensitive asynchronous memory, and further demonstrate that the core features of the experience-based agent architecture are crucial sources of power necessary to enable a reasoning task to work with and exploit a context-sensitive asynchronous memory.

In sum, these evaluations demonstrate that the context-sensitive asynchronous memory approach is a general approach to memory retrieval which can provide concrete benefits to real problems.

Read the thesis:

Context-Sensitive Asynchronous Memory

by Anthony Francis

PhD Thesis, College of Computing, Georgia Institute of Technology, Atlanta, GA, 2000
www.cc.gatech.edu/faculty/ashwin/papers/git-cc-00-01.pdf