M-Unit EigenAnt: An Ant Algorithm to Find the M Best Solutions


  • Sameena Shah Indian Institute of Technology Delhi
  • Jayadeva Jayadeva Indian Institute of Technology Delhi
  • Ravi Kothari IBM India Research Laboratory
  • Suresh Chandra Indian Institute of Technology Delhi


In this paper, we shed light on how powerful congestion control based on local interactions may be obtained. We show how ants can use repellent pheromones and incorporate the effect of crowding to avoid traffic congestion on the optimal path. Based on these interactions, we propose an ant algorithm, the M-unit EigenAnt algorithm, that leads to the selection of the M shortest paths. The ratio of selection of each of these paths is also optimal and regulated by an optimal amount of pheromone on each of them. To the best of our knowledge, the M-unit EigenAnt algorithm is the first antalgorithm that explicitly ensures the selection of the M shortest paths and regulates the amount of pheromone on them such that it is asymptotically optimal. In fact, it is in contrast with most ant algorithms that aim to discover just a single best path. We provide its convergence analysis and show that the steady state distribution of pheromone aligns with the eigenvectors of the cost matrix, and thus is related to its measure of quality. We also provide analysis to show that this property ensues even when the food is moved or path lengths change during foraging. We show that this behavior is robust in the presence of fluctuations and quickly reflects the change in the M optimal solutions. This makes it suitable for not only distributed applications butalso dynamic ones as well. Finally, we provide simulation results for the convergence to the optimal solution under different initial biases, dynamism in lengths of paths, and discovery of new paths.




How to Cite

Shah, S., Jayadeva, J., Kothari, R., & Chandra, S. (2011). M-Unit EigenAnt: An Ant Algorithm to Find the M Best Solutions. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 732-737. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/7877



AAAI Technical Track: Multiagent Systems