Abstract
Multi-agent systems can be used to perform patrolling tasks in various domains. In this work, we compare the results obtained by new negotiation based approaches with previous ones. By splitting the nodes of the world graph, the negotiator agents reduce the path they have to walk and the number of nodes to patrol, making it easier to maintain a low average idleness in world nodes. Auctions are the negotiation mechanisms used to split the nodes of the world, the agents bid on nodes based in their utility function. Empirical evaluation has shown the effectiveness of this distributed approach, as the results obtained are substantially better than those previously achieved by negotiator agents. The agent types presented in this work are more scalable and reactive since they can perform patrolling in worlds of all sizes and topology types. Besides, they are more stable as indicated by the low standard deviation obtained in node idleness.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Machado, A., Ramalho, G., Zucker, J., Drogoul, A.: Multi-Agent Patrolling: an Empirical Analysis of Alternative Architectures. In: Multiagnet Based Simulation, Bolona, Itália (2002)
Almeida, A., Ramalho, G., Santana, H., Tedesco, P., Menezes, T., Corruble, V., Chevaleyre, Y.: Recent Advances on Multiagent Patrolling. In: The 17th Brazilian Symposium on Artificial Intelligence, pp. 474–483. Springer, Heidelberg (2004)
Chevaleyre, Y., Sempé, F.: A theoretical analysis of multi-agent patrolling strategies. In: Poster at the International Conference on Autonomous Agents and Multi-Agents Systems, AAMAS (2004)
Santana, H., Ramalho, G., Corruble, V., Ratitch, B.: Multi-agent Patrolling with Reinforcement Learning. In: International Conference on Autonomous Agents and Multi-agents Systems (2004)
Faratin, P., Sierra, C., Jennings, N.: Negotiation Decisions Functions for Autonomous Agents (1998)
Faratin, P., Sierra, C., Jennings, N.: Using Similarity Criteria to Make Issue Trade-Offs in Automated Negotiations. Artificial Intelligence Journal (2002)
Manber, U.: Introduction to Algoritms - A Creative Approach, pp. 208–211. Addison-Wesley, Tucson (1989)
Helvig, C., Robins, G., Zelikovsky, A.: Moving Target TSP and Related Problems. In: Proceedings of the 6th Annual European Symposium on Algorithms, pp. 453–464 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Menezes, T., Tedesco, P., Ramalho, G. (2006). Negotiator Agents for the Patrolling Task. In: Sichman, J.S., Coelho, H., Rezende, S.O. (eds) Advances in Artificial Intelligence - IBERAMIA-SBIA 2006. IBERAMIA SBIA 2006 2006. Lecture Notes in Computer Science(), vol 4140. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11874850_9
Download citation
DOI: https://doi.org/10.1007/11874850_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-45462-5
Online ISBN: 978-3-540-45464-9
eBook Packages: Computer ScienceComputer Science (R0)