Adaptive AI Engine for RTS Games

Discussing the theory and practice

Representation in case-based reasoning

Posted by Ogail on December 1, 2009

  • Case representation techniques:
    • Feature vector representation (propositional).
      • Represents case as vector of attribute-value pairs.
      • A category is extensionally represented as a collection of cases called exemplars.
      • Here retrieval is the process of explaining the (similarity) relation between a new case and an exemplar.
    • Structured representation (relational).
      • Using frame based formalism where relations appear between frames (as in OO).
      • Cases, from this perspective, are clusters of relations between the kinds of elementary objects that comprise them.
      • Notion of similarity between two cases is linked to the concepts of subsumption and anti-unification of terms.
        • Object oriented representation.
    • Textual representation (semi-structured).
      • Imposes only a weak structure on the cases.
      • A case decomposes the text that constitutes a case into information entities (IEs). An IE is a word or a phrase contained in the text that is relevant to determine the reusability of the episode captured in the case.
      • The set of cases that form the case base is organized in the form of a case retrieval net (CRN), which is a directed graph with nodes representing cases and their IEs. These nodes are linked according to their similarity. Hence knowledge about similarity is encoded into the strength of the links between the nodes in the CRN.
  • More sophisticated approaches make use of hierarchical representations or generalized cases.
  • A case is a “contextualized piece of knowledge representing an experience that teaches a lesson fundamental to achieving the goals of the reasoner”.
  • Kolodner proposed case representation:
    • Describe situation and its goal.
    • Describe solution (often includes how solution was derived).
    • Result of carrying solution out (the state of the world after applying solution).
    • Explanations of results.
    • Lessons that can be learned from the experience.
      • In failures, we can include why this solution have not worked as well as expected.
  • Distance-based similarity metrics are easy to apply to feature vectors, while techniques related to Information Retrieval (IR) can easily be applied to textual representations. Frame-based cases often require knowledge-intensive indexing and matching algorithms.
  • Kolodner does not try to comment on the form that a case should take but rather focuses on the kinds of things that should be represented in a case so that it can be productively used for reasoning.
  • Advanced approaches:
    • Hierarchal case representation:
      • Case itself is divided into a hierarchy that represents relations between constrains.
    • Generalized cases
  • In planning, a problem is typically described by an initial state and a goal state. A solution is a totally or partially ordered sequence of actions. In principle, a planning case contains such a problem description and its related plan.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: