🌀 nonlinear sciences

Emergence and co-existence of periodic and unstructured motion in future-avoiding random walks

This paper introduces Mutual Future-Avoiding Random Walks (MFARWs) to demonstrate how shared mobility models can spontaneously exhibit Chimera states, where periodic and unstructured motion coexist through a novel self-amplifying coupling mechanism that predicts a phase transition toward stable, structured transport patterns.

Original authors: A. Schmaus, K. Stiller, N. Molkenthin

Published 2026-02-04

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: A. Schmaus, K. Stiller, N. Molkenthin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a busy city where hundreds of self-driving taxis are roaming around, waiting for passengers. Usually, we think of these taxis as chaotic: one goes here, another goes there, and they just try to get from point A to point B as quickly as possible.

This paper asks a fascinating question: What happens if these taxis are smart enough to avoid stepping on each other's future toes?

The researchers created a computer simulation where these "future-avoiding" taxis try not to block the paths they plan to take later. They discovered something surprising: even though every taxi follows the exact same rules and starts with random destinations, the fleet spontaneously splits into two very different groups.

Here is the breakdown of what they found, using some everyday analogies:

1. The "Chimera" Effect: Two Worlds in One

In mythology, a Chimera is a creature with parts of a lion, a goat, and a snake. In science, a "Chimera state" is when a group of identical things suddenly splits into two distinct behaviors at the same time.

In this simulation, the fleet of taxis did exactly that:

The "Bus" Taxis: Some taxis started driving in perfect loops. They would visit the same set of stops over and over again, like a regular city bus line.
The "Ride-Share" Taxis: Other taxis kept driving in a messy, unstructured way, going wherever the next random request took them, with no pattern.

The crazy part? They are all driving on the same streets, following the same rules, yet they naturally organized themselves into a mix of "scheduled buses" and "chaotic cabs."

2. The Traffic Jam Analogy

Why does this happen? The paper suggests it's like a game of musical chairs, but with a twist.

Imagine a ring road (a circular track). If a taxi is already driving a long way around the circle, it's hard for it to turn around and go the other way because it would have to undo a lot of its planned path. So, it keeps going in a loop.

However, if a taxi has a short trip planned, it's much easier for it to change direction or take a detour if a new request comes in. Over time, the "long loop" taxis get locked into their patterns because changing would be too costly. The "short trip" taxis stay flexible.

The system creates a self-reinforcing loop: The longer a route gets, the more likely it is to stay a long, straight loop. The shorter routes stay flexible. This causes the "Bus" taxis to get longer and longer, while the "Ride-Share" taxis stay short and chaotic.

3. The Shape of the City Matters

The researchers tested this on different "city maps" (networks):

Simple Loops and Lines: In cities that look like a circle or a straight line, the "Bus" taxis appeared very easily.
Complex Mazes: In cities that look like a star or a complex tree with many branches, the taxis stayed chaotic. They never formed the neat loops.

It seems that for these "scheduled bus" patterns to emerge naturally, the roads need to be somewhat simple and connected in a way that allows for easy looping.

4. What This Means for Real Life

The authors connect this to the real-world debate about transportation: Do on-demand ride-sharing apps (like Uber Pool) compete with public buses, or do they work together?

Their simulation suggests a third option: Natural Co-existence.
Even without a central boss telling them to do it, a system of shared rides might naturally settle into a state where some vehicles act like flexible, on-demand taxis, while others spontaneously turn into fixed-route buses. This implies that flexible and line-based transport might not be enemies, but could actually be two sides of the same coin that naturally find a stable balance.

Summary

The paper shows that if you give a group of identical, self-driving cars a rule to "avoid blocking your own future path," they will spontaneously organize into a mix of predictable, looping buses and unpredictable, wandering cabs. This happens naturally due to the math of how they interact, proving that order can emerge from chaos without anyone explicitly planning it.

Technical Summary: Emergence and Co-existence of Periodic and Unstructured Motion in Future-Avoiding Random Walks

Problem Statement
This study investigates the dynamics of interacting trajectories on networks, specifically focusing on a class of systems termed "Mutual Future-Avoiding Random Walks" (MFARWs). Unlike traditional self-avoiding random walks where agents avoid their own past, MFARWs involve stochastically driven walkers that avoid each other's planned future trajectories. This dynamic is motivated by conceptual models of shared mobility, such as on-demand ride-pooling fleets, where vehicles compete for requests based on their future route plans. The central problem addressed is whether such systems, governed by symmetric rules and non-linear coupling, spontaneously exhibit "chimera states"—a phenomenon where a population of identical units splits into coexisting coherent (periodic/structured) and non-coherent (unstructured) subpopulations.

Methodology
The authors employ numerical simulations using the ridepy Python package to model fleets of $B$ vehicles on six distinct network topologies: star, line, ring, Cayley tree, grid, and wheel graphs.

Dynamics: Requests (origin-destination pairs) arrive via a Poisson process. Vehicles are assigned requests based on two dispatcher algorithms:
1. No-Detour-Heuristic (NDH): Assigns requests to minimize delivery time without increasing existing passenger travel times.
2. Minimal-Fleet-Distance (MFD): Performs a brute-force evaluation to minimize the total added distance to the system, subject to constraints on waiting time and delay.
Analysis: The study utilizes value-weighted recurrence plots to visualize and quantify periodicity. Unlike binary recurrence matrices, this method maps trajectory values to identify recurring nodes. Periodicity is quantified using the average diagonal line length ( $L$ ) from recurrence plots, normalized by the average route length to define a "route periodicity fraction" ( $F$ ).
Analytic Approach: For the ring (cycle) graph, the authors derive a mean-field approximation to predict the onset of structure. This involves calculating the probability ( $P_c$ ) of a vehicle changing direction when a new request is inserted, based on the competition between the length of the current route and the waiting time for alternative routes.

Key Results

Emergence of Chimera States: The simulations demonstrate that MFARWs spontaneously generate a coexistence of periodic and unstructured routes. In specific network configurations (notably 1-dimensional networks like lines and cycles, and the wheel graph), a subset of vehicles develops stable, periodic trajectories (visiting the same sequence of nodes), while others remain unstructured. This represents a chimera state in non-oscillatory path dynamics.
Network and Load Dependence: The emergence of periodicity is highly dependent on network topology and normalized request load ( $x$ $x$ ).
- High-dimensional networks (Cayley tree, star graph) remain unstructured across all loads.
- 1-dimensional networks (line, cycle) exhibit a sharp phase transition from unstructured to periodic behavior at intermediate loads.
- Mixed networks (grid, wheel) show varied behaviors depending on the dispatcher; for instance, the MFD dispatcher on a grid did not produce globally periodic routes in the tested range, whereas the NDH dispatcher did.
Dispatcher Specifics: The MFD dispatcher tends to create periodic routes that are significantly longer than unstructured ones, as it prioritizes maximizing idleness to minimize total distance. The NDH dispatcher distributes requests more evenly but still supports periodic emergence under specific conditions.
Predictive Modeling: The stochastic Traveling Salesperson (TSP) walk model was found to predict link usage patterns ( $R^2 \approx 0.92-0.96$ ) better than simple shortest-path walks or edge betweenness centrality, suggesting that even single trajectories exhibit intermitted periodic behavior at high loads.
Phase Transition Mechanism: The analytic approximation for the ring graph reveals that the phase transition is driven by a self-amplifying coupling mechanism. Longer routes are less likely to change direction when new requests are added, causing them to stabilize into periodic loops. Conversely, shorter routes accumulate reversals, remaining unstructured. This aligns with chimera theory where incoherent inputs stabilize the synchronous part of the ensemble.

Significance and Claims
The paper claims to provide the first example of Chimera-style behavior in non-oscillatory path dynamics on networks. The authors argue that this self-organized emergence of coexisting periodic and unstructured routes offers a theoretical basis for understanding the natural stability of mixed transport systems. Specifically, the results imply a regime where flexible, on-demand pooling services (unstructured routes) and line-based public transport (periodic routes) can coexist naturally without external coordination, driven purely by the system's internal dynamics and request density. The study reframes the debate on shared mobility not merely as a competition with public transport, but as a potential complementary system where both modes emerge spontaneously from the same underlying demand and routing constraints.