Abstract
The Internet contains a vast array of sources that provide identical or similar services. When an agent needs to solve a problem, it may split the problem into “subproblems” and find an agent to solve each of the subproblems. Later, it may combine the results of these subproblems to solve the original problem. In this case, the agent is faced with the task of determining to which agents to assign the subproblems. We call this the agent selection problem (ASP for short). Solving ASP is complex because it must take into account several different parameters. For instance, different agents might take different amounts of time to process a request. Different agents might provide varying “qualities” of answers. Network latencies associated with different agents might vary. In this paper, we first formalize the agent selection problem and show that it is NP-hard. We then propose a generic cost function that is general enough to take into account the costs of (i) network and server loads, (ii) source computations, and (iii) internal mediator costs. We then develop exact and heuristic based algorithms to solve the agent selection problem.
Original language | English (US) |
---|---|
Title of host publication | KI 2001 |
Subtitle of host publication | Advances in Artificial Intelligence - Joint German/Austrian Conference on AI, Proceedings |
Editors | Franz Baader, Gerhard Brewka, Thomas Eiter |
Publisher | Springer Verlag |
Pages | 2-17 |
Number of pages | 16 |
ISBN (Print) | 9783540454229 |
DOIs | |
State | Published - 2001 |
Externally published | Yes |
Event | Joint 24th German Conference on Artificial Intelligence and 9th Austrian Conference on Artificial Intelligence, KI 2001 - Vienna, Austria Duration: Sep 19 2001 → Sep 21 2001 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 2174 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | Joint 24th German Conference on Artificial Intelligence and 9th Austrian Conference on Artificial Intelligence, KI 2001 |
---|---|
Country/Territory | Austria |
City | Vienna |
Period | 9/19/01 → 9/21/01 |
Funding
This work was supported by the Army Research Lab under contract number DAAL0197K0135, the Army Research Office under grant number DAAD190010484, by DARPA/RL contract number F306029910552 and by National Science Foundation grant CCR-98-96232.
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science