A New Model for Ant Trail Formation and its Convergence Properties
summary
A flow-based pheromone model on directed graphs is defined with decay, node leakage and forward/backward unit flows and a linear decision rule; for two parallel s–d paths it proves convergence to the minimum leakage path when incoming flows are constant and all edges on that path start positive, and to the shortest path when leakage is zero and incoming flow grows (linear or exponential). Bidirectional flow is necessary and the linear decision rule is uniquely guaranteed to converge; simulations on random graphs match the theorems.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:36Computation in Nature
- 3:02Turtle Ant Cephalotes Goniodontus
- 3:52Turtle Ants: A Surprising Observation
- 5:12Model Overview
- 6:09Model: Pheromone Update
- 6:46Model: Leakage and Flow Division
- 10:04Model: Example (Pheromone Update)
- 11:35Model: Example (Flow update)
- 13:02Model: Related Work
- 16:35Constant Incoming flow
- 19:33Increasing Incoming flow
- 21:53Bidirectional Flow is necessary
- 22:44Non-linear decision rules
- 24:52Conflict between leakage, change in flow and non...!
- 31:36Takeaways
related talks
48mDistributed Learning Dynamics Convergence in Routing Games
01h 07mMarrying Graph Convergence and Cascade Models
41mRerouting Flows when Links Fail
39mBroadcasting on Directed Acyclic Graphs
35mClosed-Loop Control of Network Processes
01h 09mElectrical Flows Primitive and Fast Graph Algorithms
49mAn Algorithmic Theory of Brain Networks
21mThe Evolution of Traffic Routing in a Streaming World