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

Resumo Técnico: Emergência e Coexistência de Movimento Periódico e Não Estruturado em Caminhadas Aleatórias de Evitação de Futuro

Definição do Problema
Este estudo investiga a dinâmica de trajetórias interagentes em redes, focando especificamente em uma classe de sistemas denominados "Caminhadas Aleatórias de Evitação de Futuro Mútua" (MFARWs - Mutual Future-Avoiding Random Walks). Diferente das caminhadas aleatórias de autoevitação tradicionais, onde agentes evitam seu próprio passado, as MFARWs envolvem caminhantes estocasticamente impulsionados que evitam as trajetórias futuras planejadas uns dos outros. Esta dinâmica é motivada por modelos conceituais de mobilidade compartilhada, como frotas de transporte sob demanda (ride-pooling), onde os veículos competem por solicitações com base em seus planos de rota futuros. O problema central abordado é se tais sistemas, governados por regras simétricas e acoplamento não linear, exibem espontaneamente "estados quimera" — um fenômeno onde uma população de unidades idênticas se divide em subpopulações coerentes (periódicas/estruturadas) e não coerentes (não estruturadas).

Metodologia
Os autores utilizam simulações numéricas usando o pacote Python ridepy para modelar frotas de $B$ veículos em seis topologias de rede distintas: grafos estrela, linha, anel, árvore de Cayley, grade e roda.

• Dinâmica: As solicitações (pares origem-destino) chegam via um processo de Poisson. Os veículos são atribuídos a solicitações com base em dois algoritmos de despacho:
  1. Heurística de Não Desvio (NDH - No-Detour-Heuristic): Atribui solicitações para minimizar o tempo de entrega sem aumentar os tempos de viagem dos passageiros existentes.
  2. Distância Mínima da Frota (MFD - Minimal-Fleet-Distance): Realiza uma avaliação de força bruta para minimizar a distância total adicionada ao sistema, sujeito a restrições de tempo de espera e atraso.
• Análise: O estudo utiliza gráficos de recorrência ponderados por valor para visualizar e quantificar a periodicidade. Diferente das matrizes de recorrência binárias, este método mapeia valores de trajetória para identificar nós recorrentes. A periodicidade é quantificada usando o comprimento médio da linha diagonal ($L$) de gráficos de recorrência, normalizado pelo comprimento médio da rota para definir uma "fração de periodicidade da rota" ($F$).
• Abordagem Analítica: Para o grafo anel (ciclo), os autores derivam uma aproximação de campo médio para prever o surgimento da estrutura. Isso envolve o cálculo da probabilidade ($P_c$) de um veículo mudar de direção quando uma nova solicitação é inserida, baseando-se na competição entre o comprimento da rota atual e o tempo de espera por rotas alternativas.

Principais Resultados

1. Emergência de Estados Quimera: As simulações demonstram que as MFARWs geram espontaneamente uma coexistência de rotas periódicas e não estruturadas. Em configurações de rede específicas (notadamente redes de 1 dimensão como linhas e ciclos, e o grafo roda), um subconjunto de veículos desenvolve trajetórias periódicas estáveis (visitando a mesma sequência de nós), enquanto outros permanecem não estruturados. Isso representa um estado quimera em dinâmicas de caminho não oscilatórias.
2. Dependência de Rede e Carga: A emergência da periodicidade é altamente dependente da topologia da rede e da carga de solicitações normalizada ($x$).
   • Redes de alta dimensão (árvore de Cayley, grafo estrela) permanecem não estruturadas em todas as cargas.
   • Redes de 1 dimensão (linha, ciclo) exibem uma transição de fase nítida de comportamento não estruturado para periódico em cargas intermediárias.
   • Redes mistas (grade, roda) mostram comportamentos variados dependendo do despachante; por exemplo, o despachante MFD em uma grade não produziu rotas globalmente periódicas no intervalo testado, enquanto o despachante NDH o fez.
3. Especificidades do Despachante: O despachante MFD tende a criar rotas periódicas que são significativamente mais longas que as não estruturadas, pois prioriza a maximização da ociosidade para minimizar a distância total. O despachante NDH distribui as solicitações de forma mais equilibrada, mas ainda assim suporta a emergência de periodicidade sob condições específicas.
4. Modelagem Preditiva: O modelo de caminhada de Caixeiro Viajante (TSP) estocástico foi encontrado para prever padrões de uso de links ($R^2 \approx 0,92-0,96$) melhor do que caminhadas simples de caminho mais curto ou centralidade de intermediação de arestas (edge betweenness centrality), sugerindo que mesmo trajetórias únicas exibem comportamento periódico intermitente em altas cargas.
5. Mecanismo de Transição de Fase: A aproximação analítica para o grafo anel revela que a transição de fase é impulsionada por um mecanismo de acoplamento auto-amplificador. Rotas mais longas têm menor probabilidade de mudar de direção quando novas solicitações são adicionadas, causando sua estabilização em loops periódicos. Por outro lado, rotas mais curtas acumulam reversões, permanecendo não estruturadas. Isso se alinha à teoria quimera, onde entradas incoerentes estabilizam a parte síncrona do conjunto.

Significância e Alegações
O artigo afirma fornecer o primeiro exemplo de comportamento do tipo Quimera em dinâmicas de caminho não oscilatórias em redes. Os autores argumentam que essa emergência auto-organizada de rotas coexistentes, periódicas e não estruturadas oferece uma base teórica para compreender a estabilidade natural de sistemas de transporte mistos. Especificamente, os resultados implicam um regime onde serviços de transporte sob demanda flexíveis (rotas não estruturadas) e transporte público baseado em linhas (rotas periódicas) podem coexistir naturalmente sem coordenação externa, impulsionados puramente pelas dinâmicas internas do sistema e pela densidade de demanda. O estudo recontextualiza o debate sobre mobilidade compartilhada não meramente como uma competição com o transporte público, mas como um potencial sistema complementar onde ambos os modos emergem espontaneamente a partir da mesma demanda subjacente e restrições de roteamento.