Execution Monitoring as Meta-Games for General Game-Playing Robots

David Rajaratnam, Michael ThielscherIJCAI 2015

General Game Playing (GGP) represents a pinnacle of artificial intelligence, where systems are designed to understand and play novel games based solely on their formal rules. While GGP has seen significant success in virtual domains, transitioning these capabilities to physical robotics introduces a host of real-world challenges. In the physical world, actions are not always deterministic: robots may drop pieces, sensors may fail, and human opponents may commit errors or even cheat.

The Challenge of Physical Execution

Traditionally, "execution monitoring"—the process of detecting and recovering from such real-world failures—is handled by separate, often hard-coded modules. This approach limits the "generality" that GGP aims to achieve. This paper, presented at IJCAI 2015, proposes a novel framework that treats execution monitoring itself as a "meta-game."

System architecture showing the interaction between the operator, game controller, and the GGP players (Arbiter and Robot).

The Meta-Game Framework

The authors introduce a method for the automatic construction of meta-games. By embedding a source game's rules ($\Sigma_G$) into a broader Game Description Language (GDL) framework, they create a "meta-game" ($\Sigma_{meta}$) that accounts for physical realities.

The framework consists of three primary layers:

  1. Source Game ($\Sigma_G$): The original rules of the game (e.g., Chess or Tic-Tac-Toe).
  2. Environment Model ($\Sigma_{env}$): This layer describes the physical world, including potential "illegal" or accidental transitions, such as a piece toppling over or being placed incorrectly.
  3. Execution Monitoring Strategy ($\Sigma_{em}$): This defines the role of the Arbiter.

The Arbiter is a specialized player within the GDL description. Under normal play, the Arbiter remains passive (noop). However, if the game state becomes "abnormal" due to a physical failure, the Arbiter takes control. Using standard GGP search and planning, the Arbiter determines the necessary sequence of actions to restore the game to a valid state.

Implementation and Case Studies

The framework's effectiveness was demonstrated through physical implementations, most notably using the game Breakthrough. In this setup, a robot arm plays against a human using tin cans on a 4x4 grid.

Physical setup of the Breakthrough game using a robot arm and tin cans (a), alongside the digital representation of the board state (b).

In addition to Breakthrough, the authors used Connect Four to illustrate more complex recovery scenarios. For instance, if a disc is dropped into the wrong column, the Arbiter must plan a multi-step process to clear the column and recreate the intended state.

Key Insights

  • Arbiter as a GGP Player: By framing monitoring as a game, any off-the-shelf GGP engine can serve as an execution monitor. The monitor "wins" by successfully restoring the board state.
  • Axiomatic Embedding: The paper provides a formal method to rewrite any GDL game into a meta-game, ensuring the result remains a "well-formed" game compatible with standard GGP tools.
  • Generality: This approach is game-independent. The same transformation logic can be applied to any game described in GDL, providing the robot with a built-in, game-specific execution monitor.

Limitations and Future Directions

While promising, the current model assumes perfect observability—the Arbiter sees every state change immediately. Future work suggests utilizing GDL-II to handle partial observability, where a robot might only detect an error several turns after it occurred. Additionally, the increased state space of the meta-game introduces computational overhead, which may require optimization for more complex games.

Summary updated

BibTeX
@inproceedings{rajaratnam2015execution,
  author = {David Rajaratnam and Michael Thielscher},
  title = {{Execution Monitoring as Meta-Games for General Game-Playing Robots}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure