Sokoban Random Walk: From Environment Reshaping to Trapping Crossover

This paper demonstrates that a Sokoban random walker's ability to push obstacles eliminates the classic percolation transition by inducing a dynamical crossover at a critical density, shifting the system from self-trapping to pre-existing trapping mechanisms and placing it within the Balagurov-Vaks-Donsker-Varadhan universality class characterized by stretched-exponential relaxation.

The Gist

Imagine a game of Sokoban, the classic puzzle where you push boxes around a warehouse to get them into specific spots. Now, imagine a tiny, confused robot (our "walker") lost in a giant, dark warehouse filled with randomly scattered boxes.

In the old, classic version of this story (called the "Ant in a Labyrinth"), the robot is helpless. If it bumps into a box, it stops. If the boxes are too crowded, the robot gets stuck in a dead end and can never escape to the infinite warehouse. Scientists used to think there was a "tipping point" (a specific density of boxes) where the robot would suddenly go from being able to wander forever to being permanently trapped.

But this paper tells a different story.

The Super-Strong Robot

In this new study, the robot isn't helpless. It has a superpower: it can push one box out of the way. It can't move the whole warehouse, but it can nudge a single obstacle if the space behind it is empty.

You might think, "Great! If it can push boxes, it should be better at escaping, right?"

Surprisingly, the opposite happens. Even though the robot can push, it actually gets trapped faster and more easily than the helpless robot. The ability to push boxes changes the game so completely that the "tipping point" for escaping disappears entirely. No matter how few boxes are in the room, the robot eventually gets stuck.

How Does It Get Stuck? (The Two Ways)

The researchers discovered that the robot gets trapped in two very different ways, depending on how crowded the room is. They call this a "crossover," like a fork in the road.

1. The "Self-Made Cage" (Low Density)
Imagine the room is mostly empty, with just a few scattered boxes.

• What happens: The robot wanders around, pushing boxes here and there. Because it keeps pushing, it accidentally rearranges the boxes into a circle around itself.
• The Analogy: It's like a person walking through a field of wildflowers, stepping on them and trampling them down. Eventually, they trample a perfect circle of flowers around themselves, creating a fence they can't climb over. They built their own prison!
• The Result: The robot gets trapped in a cage it created itself.

2. The "Pre-Existing Cage" (High Density)
Now imagine the room is packed tight with boxes.

• What happens: The robot tries to push, but there are so many boxes that it can't move far before it runs into a wall of them that was already there.
• The Analogy: It's like being stuck in a crowded elevator. You can't push anyone out of the way because everyone is already packed tight. The trap wasn't made by you; the trap was already there when you walked in.
• The Result: The robot gets trapped by the original arrangement of the boxes.

The Magic Number (0.55)

The researchers found a specific "magic number" for how full the room is: 55%.

• Above 55% full: The robot is trapped by the initial crowd (Pre-existing).
• Below 55% full: The robot is trapped by its own pushing actions (Self-made).

At exactly 55%, the average size of the "cage" the robot gets stuck in is at its largest. As the room gets emptier (below 55%), the cages actually get smaller because the robot has fewer boxes to push around to build a big fence.

The "Survival" Math

The paper also looked at the math of how long the robot survives before getting stuck.

• In the old "helpless" model, the chance of survival drops off in a specific way.
• In this "pushing" model, the chance of survival drops off in a stretched-exponential way.
• Simple Analogy: Imagine a balloon deflating. In the old model, it deflates at a steady, predictable rate. In this new model, the balloon deflates slowly at first, then suddenly gets stuck, then slowly leaks again. The math describing this "leak" is surprisingly similar to a famous theory about particles getting trapped in random forests, but the details of how it happens are unique to our pushing robot.

Why This Matters (According to the Paper)

The paper concludes that this "pushing" ability creates a smooth transition between these two trapping styles, rather than a sharp "on/off" switch for escaping.

They suggest this isn't just a video game theory. It applies to real-world things like:

• Robots: A robot navigating a room full of movable furniture.
• Biology: Immune cells moving through tissue, pushing aside other cells to make a path, only to accidentally trap themselves in a pocket of tissue.

The key takeaway is simple: Sometimes, having the power to change your environment is exactly what causes you to get stuck. By trying to clear a path, the robot ends up building a cage around itself.

Technical Summary

Technical Summary: Sokoban Random Walk – From Environment Reshaping to Trapping Crossover

Problem Statement
The paper investigates the transport dynamics of a random walker (the "Sokoban walker") moving through a disordered medium with obstacle density $\rho$. Unlike the classic "Ant in a labyrinth" model (de Gennes), where obstacles are static and a percolation transition allows escape to infinity below a critical density, the Sokoban walker possesses a limited ability to push surrounding obstacles. The central problem is to understand how this active, environment-modifying capability alters the long-time transport properties, specifically the survival probability and the existence of percolation. Previous work indicated that even limited pushing eliminates the percolation transition in two dimensions, but the underlying physical mechanisms and the nature of the resulting localization were not fully characterized.

Methodology
The authors employ a combination of rigorous large-deviation theory and extensive numerical simulations:

1. Model Definition: The system is defined on a $d$-dimensional square lattice with obstacle density $\rho$. The walker attempts to move to a neighboring site; if occupied, it pushes the obstacle one step further, provided the site beyond is vacant. This introduces kinetically constrained dynamics where motion depends on local configurations.
2. Theoretical Analysis (1D): In one dimension, the authors construct a renewal framework to calculate the conditional survival probability $Q(n|L_1, L_2)$, where $L_1$ and $L_2$ are the distances to the second obstacles on either side. By averaging over the distribution of these distances and applying a saddle-point approximation in the large-$n$ limit, they derive the unconditional survival probability $S(n)$.
3. Generalization (NP-Sokoban): The analysis is extended to a generalized model where the walker can push up to $N_P$ obstacles. Large-deviation calculations are performed in the joint limit $N_P \to \infty$ and $n \to \infty$ with a fixed ratio $\omega = n/N_P^3$.
4. Numerical Simulations (2D): Due to the analytical complexity in two dimensions, the authors rely on numerical simulations to study the survival probability $S(n)$ and the average trap size $\langle A_T \rangle$. They rescale time by the average trapping time $\langle n_T \rangle$ to identify universal scaling behaviors.

Key Contributions and Results

• Loss of Percolation and Universality Class: The study confirms that the ability to push obstacles eliminates the classical percolation transition. Instead, the system belongs to the Balagurov-Vaks-Donsker-Varadhan (BVDV) universality class.
• Stretched-Exponential Relaxation: The survival probability $S(n)$ (the probability the walker has not been trapped by time $n$) exhibits stretched-exponential decay at late times:
  • 1D: $S(n) \sim \exp(-c n^{1/3})$.
  • 2D: $S(n) \sim \exp(-c n^{1/2})$.
    These exponents ($1/3$ and $1/2$) match the BVDV formula for reactive trapping (where a walker is absorbed upon first contact with an obstacle). However, the pre-factors and the specific constants differ, reflecting the distinct mechanism of "caging" (confinement by a self-formed cage) versus "reactive trapping."
• Dynamical Crossover: Using the average trap size $\langle A_T \rangle$ as a proxy, the authors identify a non-monotonic dependence on density $\rho$. A dynamical crossover occurs at a characteristic density $\rho^* \approx 0.55$:
  • High Density ($\rho > \rho^*$): Trapping is dominated by pre-existing traps formed by the initial random arrangement of obstacles. As density decreases, the available void space increases, leading to larger trap sizes.
  • Low Density ($\rho < \rho^*$): A self-trapping mechanism emerges. Despite the availability of large voids, the walker's pushing dynamics allow it to actively reorganize a local cluster of obstacles into a confining cage. As density decreases further, fewer manipulable obstacles are available to form these cages, causing the average trap size to decrease.
• Robustness: The stretched-exponential exponents and the existence of the crossover are robust against variations in the microscopic pushing rules (e.g., varying the number of pushable obstacles $N_P$). The long-time behavior is determined by rare events involving large voids not shaped by the walker, making the results independent of specific pushing strengths as long as the ability remains limited.

Significance and Claims
The paper claims to uncover a distinct transport regime where the interplay between tracer motion and environment reshaping leads to dynamical localization, replacing the classical percolation transition. The primary significance lies in:

1. Mechanistic Insight: It clarifies that the loss of percolation is not merely a suppression of connectivity but a result of a smooth crossover between two qualitatively different trapping mechanisms (pre-existing vs. self-formed).
2. Universality: The findings suggest that the BVDV universality class and the specific crossover behavior are generic features of systems with limited environment-modifying capabilities, independent of specific microscopic details.
3. Experimental Relevance: The authors note that these theoretical predictions are amenable to experimental verification in systems such as active colloids or bristle robots, where caging can be operationally defined by the saturation of visited grid cells or the plateau in time-averaged mean-squared displacement.

The work provides fundamental insights into transport in dynamically reshaped environments, highlighting how finite energy or force constraints on a tracer can fundamentally alter macroscopic transport properties.