Display Publications by [Year] [Type] [Topic]
We consider the use of multi-agent systems to control network routing. Conventional approaches to this task are based on Ideal Shortest Path routing Algorithm (ISPA), under which at each moment each agent in the network sends all of its traffic down the path that will incur the lowest cost to that traffic. We demonstrate in computer experiments that due to the side-effects of one agent's actions on another agent's traffic, use of ISPA's can result in large global cost. In particular, in a simulation of Braess' paradox we see that adding new capacity to a network with ISPA agents can decrease overall throughput. The theory of COllective INtelligence (COIN) design concerns precisely the issue of avoiding such side-effects. We use that theory to derive an idealized routing algorithm and show that a practical machine-learning-based version of this algorithm, in which costs are only imprecisely estimated substantially outperforms the ISPA, despite having access to less information than does the ISPA. In particular, this practical COIN algorithm avoids Braess' paradox.
@inproceedings{tumer-wolpert_aaai00,
author = {K. Tumer and D. H. Wolpert},
title = {Collective Intelligence and {B}raess' Paradox},
booktitle={Proceedings of the Seventeenth National Conference on
Artificial Intelligence},
address = {Austin, TX},
pages = {104-109},
abstract = {We consider the use of multi-agent systems to control network routing. Conventional approaches to this task are based on Ideal Shortest Path routing Algorithm (ISPA), under which at each moment each agent in the network sends all of its traffic down the path that will incur the lowest cost to that traffic. We demonstrate in computer experiments that due to the side-effects of one agent's actions on another agent's traffic, use of ISPA's can result in large global cost. In particular, in a simulation of Braess' paradox we see that adding new capacity to a network with ISPA agents can <em>decrease</em> overall throughput. The theory of COllective INtelligence (COIN) design concerns precisely the issue of avoiding such side-effects. We use that theory to derive an idealized routing algorithm and show that a practical machine-learning-based version of this algorithm, in which costs are only imprecisely estimated substantially outperforms the ISPA, despite having access to less information than does the ISPA. In particular, this practical COIN algorithm avoids Braess' paradox.},
bib2html_pubtype = {Refereed Conference Papers},
bib2html_rescat = {Multiagent Systems, Collectives, Traffic and Transportation},
year = {2000}
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Apr 01, 2020 17:39:43