Monte Carlo Action Programming

Lenz BelznerarXiv 2017 · arXiv

Abstract

Monte Carlo Action Programming (MCAP) is a framework that integrates high-level behavioral blueprints with Monte Carlo Tree Search (MCTS). By using nondeterministic programs to prune the search space, MCAP enables autonomous agents to navigate massive, probabilistic environments that typically overwhelm standard planning algorithms.

1. Introduction

Autonomous systems, such as rescue robots or game-playing AI, frequently operate in "wild" environments characterized by astronomical state spaces and high branching factors. Current approaches generally fall into two categories: online planning (e.g., MCTS) and action programming (e.g., Golog). While MCTS simulates many futures to find optimal moves, it often gets "lost" in complex environments by exploring irrelevant paths. Conversely, action programming provides high-level guidance but often requires exhaustive search or exact logical models, making it brittle in uncertain domains.

Monte Carlo Action Programming (MCAP) addresses this gap by providing a "heuristic sketch"—a high-level program that guides the agent without hard-coding every move, allowing for optimization via real-time simulations.

The core innovation of MCAP is the use of a nondeterministic program that acts as a constraint on the MCTS search tree. Instead of a rigid script, an MCAP program is a "sketch" (e.g., "Either move to position X OR extinguish a fire"), leaving the final choice to the agent's search process.

The four stages of the Monte Carlo Tree Search (MCTS) process.

MCAP uses MCTS to "interpret" the program. During the Expansion phase (see Figure 1), the algorithm only considers actions permitted by the current state of the MCAP program. This is formalized through a "potential program" function (pot), which takes a state and a program to return valid next actions and the remaining program "tail." This effectively masks the search tree, hiding irrelevant or suboptimal actions from the planner.

Algorithm 1: The general MCTS approach.

Furthermore, MCAP replaces standard mean-average updates with Bellman-style updates during the Backpropagation (or Backup) phase (see Figure 2, line 6). This approach is more effective for sequential decision-making in probabilistic environments.

3. Experimental Evaluation: The Rescue Domain

The framework was evaluated in a simulated Rescue Domain, featuring a graph of 20 positions with 30% connectivity and a state space exceeding $10^{19}$ states. The environment is highly dynamic: positions catch fire, victims must be transported to safe zones, and robots have limited capacity. Uncertainty is introduced via probabilistic action success ($p=0.05$ failure rate) and random fire dynamics, creating a massive branching factor of $2 \cdot 2^{17}$ per action.

4. Results and Key Insights

Experiments comparing plain MCTS against MCAP revealed several key advantages:

  • Heuristic Pruning: Even loose program sketches drastically improved performance. By excluding obviously poor choices, MCTS could focus its computational budget (1,000 playouts) on deeper, more promising paths.
  • Robustness and Recovery: MCAP demonstrated significant resilience to "unexpected events" (e.g., victims falling out of robot arms). Because it remains a search-based planner, it re-evaluates the program from the new state to find a recovery path.
  • Efficiency and Adaptability: MCAP achieved higher victim safety ratios and adapted faster to mid-run changes in reward functions compared to the baseline.

5. Conclusion and Future Work

MCAP offers a model-agnostic approach to action programming, requiring only a generative simulator rather than a formal logical description. However, current limitations include the need for manual program specification and a focus on discrete domains. Future research will explore extending MCAP to continuous domains and using representation learning to automatically "learn the sketch" from experience, further reducing the burden on human designers.

Summary updated

Abstract

This paper proposes Monte Carlo Action Programming, a programming language framework for autonomous systems that act in large probabilistic state spaces with high branching factors. It comprises formal syntax and semantics of a nondeterministic action programming language. The language is interpreted stochastically via Monte Carlo Tree Search. Effectiveness of the approach is shown empirically.
BibTeX
@misc{belzner2017monte,
  author = {Lenz Belzner},
  title = {{Monte Carlo Action Programming}},
  year = {2017},
  eprint = {1702.08441},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1702.08441},
}
Figure