Another look at search-based drama management

ABSTRACT

A drama manager (DM) is a system that monitors an interactive experience, such as a computer game, and intervenes to keep the global experience in line with the author's goals without decreasing a player's interactive agency. In declarative optimization-based drama management (DODM), an author declaratively specifies desired properties of the experience; the DM intervenes in a way that optimizes the specified metric. The initial DODM approach used online search to optimize an experience-quality function. Later work questioned both online search as a technical approach and the experience-quality optimization framework. Recent work on targeted trajectory distribution Markov decision processes (TTD-MDPs) replaced the experience-quality metric with a metric and associated algorithm based on targeting experience distributions. We show that, though apparently quite different on the surface, the original optimization formulation and TTD-MDPs are actually variants of the same underlying search algorithm, and that offline cached search, as is done by the TTD-MDP algorithm, allows the original search-based systems to achieve similar results to TTD-MDPs. Furthermore, we argue that the original idea of optimizing an experience-quality function does not destroy interactive agency, as had previously been argued, and that in fact it can capture that goal directly.

REFERENCES

• 1: Joseph Bates, Virtual reality, art, and entertainment, Presence: Teleoperators and Virtual Environments, v.1 n.1, p.133-138, Winter 1992
• 2: Sooraj Bhat , David L. Roberts , Mark J. Nelson , Charles L. Isbell , Michael Mateas, A globally optimal algorithm for TTD-MDPs, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329367]
• 3: Andrew S. Cantino , David L. Roberts , Charles L. Isbell, Autonomous nondeterministic tour guides: improving quality of experience with TTD-MDPs, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329152]
• 4: B. Magerko. Story representation and interactive drama. In Proceedings of AIIDE, 2005.
• 5: M. J. Nelson and M. Mateas. Search-based drama management in the interactive fiction Anchorhead. In Proceedings of AIIDE, 2005.
• 6: Mark Riedl , C. J. Saretto , R. Michael Young, Managing interaction between users and agents in a multi-agent storytelling environment, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860694]
• 7: D. L. Roberts, S. Bhat, K. St. Clair, and C. L. Isbell. Authorial idioms for target distributions in TTD-MDPs. In Proceedings of AAAI, 2007.
• 8: D. L. Roberts, M. J. Nelson, C. L. Isbell, M. Mateas, and M. L. Littman. Targeting specific distributions of trajectories in MDPs. In Proceedings of AAAI, 2006.
• 9: Peter William Weyhrauch , Joseph Bates, Guiding interactive drama, Carnegie Mellon University, Pittsburgh, PA, 1997
• 10: R. M. Young, M. O. Riedl, M. Branly, A. Jhala, R. J. Martin, and C. J. Saretto. An architecture for integrating plan-based behavior generation with interactive game environments. Journal of Game Development, 1(1), 2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms, Design, Management, Theory