Аннотация.

В работе предлагается алгоритм стохастического патрулирования на основе метода потенциалов, обеспечивающий непредсказуемость движения роботов. Предложенный алгоритм является распределенным и функционирует без единого центра управления. Роботы не обмениваются спланированными маршрутами движения по сети, а только текущими координатами. Эти свойства защищают систему от вмешательства извне. В работе также исследуется падение эффективности патрулирования при отсутствии, слабой и прерывистой связи.

Ключевые слова:

патрулирование, метод потенциалов, коллективное поведение

Стр. 70-73.

Полная версия статьи в формате pdf. 

E. А. Shvets

"Studying the dependence of the efficiency of collective stochastic patrolling on the connectivity and reliability of mesh network"

Abstract. In the paper we propose an algorithm for stochastic patrolling using social potential fields method. It provides irregular and hard-to-predict behavior of robots. Proposed algorithm is fully distributed and operates without a single center of command; robots use the network to only exchange the information about their current coordinates, but not about the plans for their future movement. These properties of the system protect it from the outside intrusion. The paper also examines how efficiency of the patrolling drops under the conditions of lossy, low-range networks and full absence of network.

Keywords: patrolling, social potential fields, swarm intelligence

REFERENCES

1. Kitano Hiroaki. Robocup rescue: A grand challenge for multi-agent systems. MultiAgent Systems, 2000.
2. Machado Aydano, et al. Multi-agent movement coordination in patrolling. First Workshop on Agents in Computer Games, at the 3rd International Conference on Computers and Games (CG’02)
3. Portugal D., Rocha R. P. Multi-robot patrolling algorithms: examining performance and scalability, Advanced Robotics 27.5. 2013, pp. 325–336.
4. Chu H., Glad A., Simonin O. Swarm approaches for the patrolling problem, information propagation vs. pheromone evaporation, Proceedings of the 19th IEEE International Conference on Tools with Artificial Intelligence - Volume 01. 2007, pp. 442 – 449.
5. Elmaliach Yehuda, Noa Agmon, Gal A. Kaminka.  Multi-robot area patrol under frequency constraints. Annals of Mathematics and Artificial Intelligence 57.3-4. 2009, pp. 293-320.
6. Portugal David, Rui Rocha. Msp algorithm: multirobot patrolling based on territory allocation using balanced graph partitioning. Proceedings of the 2010 ACM Symposium on Applied Computing. ACM, 2010.
7. Santana H., Corruble V., Ratitch B. Multiagent patrolling with reinforcement learning, Proceedings of the Third International Joint Conference on 97Autonomous Agents and Multiagent Systems-Volume 3. IEEE Computer Society, 2004, pp. 1122 – 1129.
8. Menezes T., Tedesco P., Ramalho G. Negotiator agents for the patrolling task, Advances in Artificial Intelligence IBERAMIA-SBIA 2006, Springer Berlin Heidelberg, 2006, pp. 48 – 57.
9. Reif J., Wang H. (1999), Social potential fields: A distributed behavioral control for autonomous robots, Robotics and Autonomous Systems, Volume 27, Issue 3, p. 171-194.
10. Ge S., Cui Y. Dynamic motion planning for mobile robots using potential field method, Autonomous Robots Volume 13, Issue 3, 2002, pp. 207 – 222.
11. Shvets E. Stochastic multi-agent patrolling using social potential fields. 29th EUROPEAN Conference on Modelling and Simulation. 2015.
12. Rubin F. The Lee path connection algorithm, Computers, IEEE Transactions on 100.9, 1974, pp. 907 – 914.