Unlucky Explorer: A Complete non-Overlapping Map Exploration

Mohammad Sina Kiarostami, Saleh Khalaj Monfared, Mohammad Reza Daneshvaramoli, Negar Yousefian, Mahsa Massoud, Aku Visuri, Simo Hosio, Dara Rahmati, Saeid GorginWsse 2021 · DOI

TL;DR

This paper introduces "Maze Dash," a novel exploration puzzle requiring agents to visit every cell in a 2D grid without revisiting any. They propose and evaluate a modified Monte Carlo Tree Search (MCTS) algorithm, demonstrating its effectiveness on small to medium-sized grids compared to SAT solvers, while identifying simulation cost as a bottleneck for larger grids.

What Problem Does This Paper Address?

The paper tackles the challenge of "exploration" in Artificial Intelligence, specifically within the context of computer games. Exploration problems involve an agent navigating an unknown environment to discover its layout. This work focuses on a specific variant: "non-overlapping exploration," where an agent must visit every cell in a 2D grid exactly once. This is framed as a variation of the Hamiltonian Path problem, a well-known NP-complete problem. The authors highlight the real-world relevance of such problems, particularly in robotics, where efficient and complete exploration with constraints like minimizing turns is crucial.

Methods

The core of the paper's methodology lies in adapting and evaluating algorithms for the Maze Dash puzzle.

  • Monte Carlo Tree Search (MCTS): The authors employ a standard MCTS framework, which involves four steps: Selection, Expansion, Simulation, and Backpropagation. They introduce modifications to the Expansion and Selection steps to prune the search tree more effectively. Specifically, they block terminal states with inadequate values and nodes whose children have all been blocked.
  • SAT Solver: A Satisfiability (SAT) solver is used as a baseline and comparison method. The problem's constraints are translated into boolean logic, which the SAT solver then attempts to satisfy.
  • Backtracking: A simple backtracking algorithm is implemented as a naive approach and a benchmark for worst-case scenarios.

A key methodological contribution is the generation of solvable test cases. Since existing benchmarks were insufficient, the authors developed a technique to create random grids with obstacles, ensuring they are solvable by the backtracking approach.

Datasets

The paper does not use pre-existing datasets. Instead, it introduces a new benchmark generation methodology for the Maze Dash game. This involves creating random 2D grids with obstacles. The generation process ensures that the generated test cases are solvable, and the number of obstacles can be varied. These auto-generated test cases are then used to evaluate the performance of the proposed algorithms.

Key Insights and Ideas

  • Maze Dash as a Hamiltonian Path Variant: Framing the non-overlapping exploration as a Hamiltonian Path problem provides a clear theoretical basis and allows for the application of established AI techniques.
  • MCTS Optimization for Pruning: Modifying the MCTS expansion and selection steps to prune unproductive branches significantly improves efficiency, especially in scenarios where early failure detection is possible.
  • Simulation Cost Bottleneck: The paper identifies the simulation step in MCTS as the primary bottleneck for larger grid sizes. This is due to the need to explore many potential paths to determine their value, leading to a high computational cost (estimated as O(I × N⁴)).
  • Real-world Relevance of Turn Minimization: The constraint of minimizing turns in exploration is highlighted as a critical factor for practical applications like robotics, where turning incurs additional costs.

Key Results

The paper presents a comparative evaluation of SAT, Backtracking, and a modified MCTS on auto-generated Maze Dash test cases.

  • SAT: Accurately solves test cases but its execution time increases exponentially as the number of obstacles decreases.
  • Backtracking: Used as a baseline for solvability and worst-case performance; it is not competitive in terms of speed.
  • MCTS:
    • Small and Medium Grids: MCTS outperforms SAT in terms of execution time for small and medium-sized grids.
  • Large Grids: MCTS struggles with large grids due to the high simulation cost, eventually failing to complete within reasonable timeframes.
  • Memory: MCTS generally uses less memory than SAT for comparable grid sizes.

Limitations and Future Work

  • MCTS Scalability: The primary limitation identified is the scalability of the MCTS approach to large grid sizes, primarily due to the computational cost of the simulation step.
  • Future Work: The authors propose two future research directions:
  • Relaxed Exploration: Investigating exploration problems where previously visited cells are not strictly forbidden (i.e., the non-overlapping constraint is relaxed).
  • Turn Minimization: Focusing on exploration problems that prioritize minimizing the number of turns, which has direct applications in areas like 2D robotic soccer.

Summary updated

BibTeX
@inproceedings{kiarostami2021unlucky,
  author = {Mohammad Sina Kiarostami and Saleh Khalaj Monfared and Mohammad Reza Daneshvaramoli and Negar Yousefian and Mahsa Massoud and Aku Visuri and Simo Hosio and Dara Rahmati and Saeid Gorgin},
  title = {{Unlucky Explorer: A Complete non-Overlapping Map Exploration}},
  booktitle = {Wsse},
  year = {2021},
  doi = {10.1145/3488838.3488864},
}
Figure