Cooperative graph search by a system of autonomous agents

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 man...

Full description

Saved in:
Bibliographic Details
Main Authors: Hill, J.C., Nokleby, M.S., Archibald, J.K., Frost, R.L., Stirling, W.C.
Format: Conference Proceeding
Language:English
Subjects:
Air traffic control
Autonomous agents
coordination
Decision making
Design methodology
Game theory
Manufacturing automation
multi-agent
Multiagent systems
negotiation
Reconnaissance
Satisficing
Traveling salesman problems
Utility theory
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1062-922X
2577-1655
DOI:10.1109/ICSMC.2005.1571132