CFP last date
22 April 2024
Call for Paper
May Edition
IJCA solicits high quality original research papers for the upcoming May edition of the journal. The last date of research paper submission is 22 April 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Decentralized and Nondeterministic Multi-Robot Area Patrolling in Adversarial Environments

by Tauhidul Alam
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 156 - Number 2
Year of Publication: 2016
Authors: Tauhidul Alam
10.5120/ijca2016912367

Tauhidul Alam . Decentralized and Nondeterministic Multi-Robot Area Patrolling in Adversarial Environments. International Journal of Computer Applications. 156, 2 ( Dec 2016), 1-8. DOI=10.5120/ijca2016912367

@article{ 10.5120/ijca2016912367,
author = { Tauhidul Alam },
title = { Decentralized and Nondeterministic Multi-Robot Area Patrolling in Adversarial Environments },
journal = { International Journal of Computer Applications },
issue_date = { Dec 2016 },
volume = { 156 },
number = { 2 },
month = { Dec },
year = { 2016 },
issn = { 0975-8887 },
pages = { 1-8 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume156/number2/26678-2016912367/ },
doi = { 10.5120/ijca2016912367 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T00:01:28.657182+05:30
%A Tauhidul Alam
%T Decentralized and Nondeterministic Multi-Robot Area Patrolling in Adversarial Environments
%J International Journal of Computer Applications
%@ 0975-8887
%V 156
%N 2
%P 1-8
%D 2016
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Multi-robot patrolling is the problem of repeatedly visiting a group of regions of interest in an environment with a group of robots to prevent intrusion. Early works have proposed deterministic patrolling algorithms which could be learned by an adversary observing them over time. More recent works provide non-deterministic patrolling schemes which only work for perimeter patrolling and require coordination and synchronization. In this paper, we investigate the problem of finding robust and scalable strategies for multi-robot patrolling under an adversarial environment. So, we present algorithms to find different decentralized strategies for a patroller in the form of Markov chains which use convex optimization to minimize the average commute time for an environment, a subset of the environment, or a specific region of an environment when we use uniform distribution over all regions for both patroller and adversary. Additionally, we use these strategies in a game theoretical setup to form a payoff matrix to obtain an optimal mixed strategy for patroller. We also propose an algorithm to find a decentralized strategy for patroller in the form of Markov chain which converges very fast as it is the optimal response from patroller against the adversary when we use non-uniform distribution over all the regions for both patroller and adversary. Our results show the scalability and applicability of our approach in different types of environments. Despite the lack of synchronization and coordination among patrollers, our approach performs competitively compared to existing methods.

References
  1. N. Agmon, S. Kraus, and G. A. Kaminka, “Multi-robot perimeter patrol in adversarial settings,” in Proc. of the Intl. Conf. on Robotics and Automation, pp. 2339–2345, 2008.
  2. N. Agmon, “On events in multi-robot patrol in adversarial environments,” in Proc. of the Intl. Conf. on Autonomous Agents and Multiagent Systems, pp. 591–598, 2010.
  3. N. Agmon, G. A. Kaminka, and S. Kraus, “Multi-robot adversarial patrolling: facing a full-knowledge opponent,” J. of Artificial Intelligence Research, vol. 42, pp. 887–916, 2011.
  4. T. Sak, J.Wainer, and S. K. Goldenstein, “Probabilistic multiagent patrolling,” in Brazilian Symp. on Artificial Intelligence, pp. 124–133, Springer, 2008.
  5. P. Paruchuri, J. P. Pearce, M. Tambe, F. Ordonez, and S. Kraus, “An efficient heuristic approach for security against multiple adversaries,” in Proc. of the Intl. Joint Conf. on Autonomous Agents and Multiagent Systems, 2007.
  6. P. Paruchuri, J. P. Pearce, J. Marecki, M. Tambe, F. Ordonez, and S. Kraus, “Playing games for security: an efficient exact algorithm for solving bayesian stackelberg games,” in Proc. of the Intl. Joint Conf. on Autonomous Agents and Multiagent Systems, pp. 895–902, 2008.
  7. A. Ghosh, S. Boyd, and A. Saberi, “Minimizing effective resistance of a graph,” SIAM Review, vol. 50, no. 1, pp. 37–66, 2008.
  8. S. Boyd, P. Diaconis, and L. Xiao, “Fastest mixing markov chain on a graph,” SIAM Review, vol. 46, no. 4, pp. 667–689, 2004.
  9. S. Boyd, “Convex optimization of graph laplacian eigenvalues,” in Proc. of the Intl. Congress of Mathematicians, vol. 3, pp. 1311–1319, 2006.
  10. T. Alam, M. Edwards, L. Bobadilla, and D. Shell, “Distributed multi-robot area patrolling in adversarial environments,” in Intl. Work. on Robotic Sensor Networks, Seattle, WA, USA, 2015.
  11. Y. Chevaleyre, F. Sempe, and G. Ramalho, “A theoretical analysis of multi-agent patrolling strategies,” in Proc. of the Intl. Joint Conf. on Autonomous Agents and Multiagent Systems, pp. 1524–1525, 2004.
  12. A. Almeida, G. Ramalho, H. Santana, P. Tedesco, T. Menezes, V. Corruble, and Y. Chevaleyre, “Recent advances on multiagent patrolling,” in Brazilian Symp. on Artificial Intelligence, pp. 474–483, Springer, 2004.
  13. M. Ahmadi and P. Stone, “A multi-robot system for continuous area sweeping tasks,” in Proc. of the Intl. Conf. on Robotics and Automation, pp. 1724–1729, 2006.
  14. Y. Elmaliach, N. Agmon, and G. A. Kaminka, “Multi-robot area patrol under frequency constraints,” Annals of Mathematics and Artificial Intelligence, vol. 57, no. 3-4, pp. 293– 320, 2009.
  15. D. Portugal and R. Rocha, “Msp algorithm: multi-robot patrolling based on territory allocation using balanced graph partitioning,” in Proc. of Symp. on Applied Computing, pp. 1271–1276, 2010.
  16. D. Portugal and R. Rocha, “A survey on multi-robot patrolling algorithms,” in Doctoral Conf. on Computing, Electrical and Industrial Systems, pp. 139–146, Springer, 2011.
  17. N. Basilico, N. Gatti, and F. Amigoni, “Leader-follower strategies for robotic patrolling in environments with arbitrary topologies,” in Proc. of the Intl. Conf. on Autonomous Agents and Multiagent Systems, pp. 57–64, 2009.
  18. N. Basilico, N. Gatti, and F. Villa, “Asynchronous multi-robot patrolling against intrusions in arbitrary topologies.,” in AAAI, 2010.
  19. N. Basilico, N. Gatti, and F. Amigoni, “Patrolling security games: Definition and algorithms for solving large instances with single patroller and single intruder,” Artificial Intelligence, vol. 184, pp. 78–123, 2012.
  20. N. Basilico and S. Carpin, “Online patrolling using hierarchical spatial representations,” in Proc. of the Intl. Conf. on Robotics and Automation, pp. 2163–2169, IEEE, 2012.
  21. Y. Vorobeychik, B. An, M. Tambe, and S. P. Singh, “Computing solutions in infinite-horizon discounted adversarial patrolling games.,” in Proc. of the Intl. Conf. on Automated Planning and Scheduling, 2014.
  22. J. Y. Yen, “Finding the k shortest loopless paths in a network,” Management Science, vol. 17, no. 11, pp. 712–716, 1971.
  23. N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, “Equation of state calculations by fast computing machines,” The J. of Chemical Physics, vol. 21, no. 6, pp. 1087–1092, 1953.
  24. W. K. Hastings, “Monte carlo sampling methods using markov chains and their applications,” Biometrika, vol. 57, no. 1, pp. 97–109, 1970.
  25. Convex Optimization in Matlab. Available at http://cvxr.com/cvx/examples/.
Index Terms

Computer Science
Information Sciences

Keywords

Patroller Adversary Markov chain Game theory Convex optimization

Powered by PhDFocusTM