Name
Abstract | ||
|---|---|---|
Searching a random graph is known to be computationally complex. The classic example for the single agent case is the traveling salesman problem. In this paper, we generalize to the multi-agent case where n autonomous agents must cooperate to visit all the nodes of a random graph in an efficient manner. We impose a limitation on the agent's ability to communicate with each other. A satisficing game approach is ideally suited to this problem since it accommodates multiple solutions for each player and provides the opportunity for negotiation. We demonstrate performance of this approach on both deterministic and random graphs with up to 100 nodes. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1109/ICSMC.2005.1571132 | Systems, Man and Cybernetics, 2005 IEEE International Conference |
Keywords | Field | DocType |
game theory,graph theory,multi-agent systems,tree searching,agent cooperation,autonomous agents,computational complexity,cooperative graph search,deterministic graphs,multiagent system,random graphs,satisficing game approach,traveling salesman problem,Satisficing,coordination,multi-agent,negotiation | Graph theory,Satisficing,Autonomous agent,Random graph,Computer science,Multi-agent system,Travelling salesman problem,Game theory,Artificial intelligence,Machine learning,Negotiation | Conference |
Volume | ISSN | ISBN |
1 | 1062-922X | 0-7803-9298-1 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jared C. Hill | 1 | 28 | 3.68 |
| Matthew S. Nokleby | 2 | 116 | 17.37 |
| James K. Archibald | 3 | 632 | 161.01 |
| Richard L. Frost | 4 | 55 | 8.14 |
| Wynn C. Stirling | 5 | 108 | 21.00 |