The trace-reinforced ants process does not find shortest paths

In this paper, we study a probabilistic reinforcement-learning model for ants searching for the shortest path(s) from their nest to a food source, represented here by two vertices of a finite graph. In this model, the ants each take a random walk on the graph, starting from the nest vertex, until they reach the food vertex, and then reinforce the weight of the set of crossed edges. We show that if the graph is a finite tree, in which the set of leaves is identified with a single food vertex, and the root with the nest vertex, and if there is an edge between the nest and the food, then almost surely the proportion of ants that end up taking this last edge tends to 1. On the other hand we show on three other examples that in general ants do not always choose the shortest path. Our techniques use stochastic approximation methods, as well as couplings with urn processes.