Real-Time Navigation in Classical Platform Games via Skill Reuse

Michael Dann, Fabio Zambetta, John ThangarajahIJCAI 2017 · DOI

TL;DR

This paper introduces Synoptic Vision Planning (SVP), a novel approach for real-time navigation in platform games that leverages transferable "skills" and a "god's eye view" to plan complex paths without needing a perfect forward model of the game. SVP significantly outperforms traditional search-based agents in challenging, procedurally generated levels, demonstrating its potential for agents that can adapt to new environments quickly.

What Problem Does This Paper Address?

Classical platform games often require agents to navigate complex environments, collect items, and reach specific goals. Traditional AI approaches for these games typically rely on low-level forward search, which is computationally expensive and requires a precise understanding of the game's physics and how the environment will change with each action (a "forward model"). This makes it difficult for agents to plan effectively in real-time, especially in games with procedurally generated levels where every playthrough is unique. Furthermore, these methods often struggle with medium-term navigation tasks, like reaching a distant item that requires a series of coordinated movements. Human players, in contrast, seem to tackle these problems by abstracting actions into higher-level "skills" and using a broad overview of the level to plan. This paper aims to bridge this gap by developing an AI agent that can mimic this human-like planning strategy.

Methods

The core of SVP lies in its ability to learn and reuse transferable skills. Instead of learning task-specific skills, SVP focuses on learning fundamental "basis" behaviors (like running and jumping) and a general estimator for the likelihood of these skills succeeding.

  1. Skill Learning (Local Movement Policy): The agent first learns a policy for local movement. This is achieved by defining a grid of "tiles" over the game's spatial dimensions and training a Q-learning agent to navigate to random target tiles within a certain neighborhood. This learned policy represents a fundamental skill for moving within the game world.
  2. Success Probability Estimation: After learning the local movement policy, the agent trains a probabilistic estimator. This estimator learns to predict the probability that a learned skill (like moving from one tile to another) will succeed within a given time limit, without needing a perfect forward model. This is trained on a variety of conditions to generalize well.
  3. Synoptic Vision Planning: When faced with a navigation task, SVP uses a "god's eye view" (synoptic vision) to project potential paths. It leverages the learned success probability estimator to assign a likelihood to each step in a potential path. Dijkstra's algorithm is then used to find the path with the highest overall probability of success, treating log-likelihoods as path costs.
  4. Replanning: Since plans are probabilistic, SVP incorporates a replanning mechanism. It replans only if a step is deemed failed, either by the target waypoint falling out of local movement range or if the current likelihood of success drops significantly below the initial estimate.

Datasets

The paper uses Infinite Mario, a procedurally generated version of Super Mario Bros., for both training and evaluation. The authors specifically modified the level generator to create maze-like tasks that are challenging for AI agents. No new datasets were introduced.

Key Insights and Ideas

  • Transferable Skills are Key: The paper argues that learning general, transferable "basis" skills, rather than task-specific skills, is crucial for agents to adapt to new problems without extensive retraining.
  • Probabilistic Planning over Deterministic Models: SVP demonstrates that a probabilistic approach to predicting skill success, combined with a "god's eye view," can be more effective than relying on precise, deterministic forward models, especially in complex and unknown environments.
  • Reversing the Traditional Order: Unlike many hierarchical learning approaches that identify subgoals first, SVP derives plans by first learning skills and their capabilities, with subgoals (waypoints) emerging as a consequence of the planning process.
  • The Power of Abstraction: By abstracting actions into skills and using a high-level view, SVP can derive complex plans in real-time, mirroring how human players might approach similar challenges.

Key Results

  • Superior Performance: Both "basis skill" and "flexi skill" versions of SVP significantly outperformed the A* benchmark agent in Infinite Mario, achieving much higher success rates over time.
  • Basis Skill Advantage: Surprisingly, the "basis skill" agent, which learned more constrained local movements, achieved a higher overall success rate (97.1%) than the more versatile "flexi skill" agent (90.0%) when combined with the SVP planner. This suggests that simpler, more predictable skills can be more effectively leveraged by the planner.
  • Effective Replanning: The replanning threshold was found to be critical. A low threshold (k=0.2 for the basis skill agent) allowed the agent to recover from failures, while a high threshold (k=1.0, continual replanning) was detrimental, leading to frequent plan switching and lack of progress.
  • Real-time Capability: SVP was able to derive complex plans in real-time, enabling it to solve navigation tasks that were too demanding for the A* agent within the game's tight time constraints.

Limitations and Future Work

  • Synoptic View Dependency: SVP critically relies on the availability of a "god's eye" or synoptic view of the environment. This limits its applicability to domains where such a view is not readily available.
  • Grid-Based Assumption: The current SVP formulation is best suited for grid-based environments like classical 2D platformers. Applying it to less structured environments presents challenges, such as handling partially blocked tiles.
  • Future Work: The authors plan to address the challenges of applying SVP to less structured environments and extend it to more complex domains. They also suggest exploring more sophisticated approaches for constructing hypothetical initiation states for planning.

Summary updated

BibTeX
@inproceedings{dann2017real,
  author = {Michael Dann and Fabio Zambetta and John Thangarajah},
  title = {{Real-Time Navigation in Classical Platform Games via Skill Reuse}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/219},
}
Figure