International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 12, No. 5, 8 Oct. 2020
Cover page and Table of Contents: PDF (size: 1205KB)
A Hybrid Approach for the Multi-sensor Patrolling Problem in an Unknown Environment with Obstacles
Full Text (PDF, 1205KB), PP.16-30
Views: 0 Downloads: 0
Author(s)
Elie Tagne Fute
1,2,*
Doris-Kholer Nyabeye Pangop
1
Emmanuel TONYE
3
Index Terms
Avoidance of obstacles, Exploration, Learning, Multi-agent system, Multi-sensors patrolling, Perception-reaction, Sensor network, Strength
Abstract
This paper introduces PREFAP, an approach to solve the multi-sensor patrolling problem in unknown environment. The multi-sensor patrolling problem consists in moving a set of sensors on a pre-set territory such that each part of this territory is visited by the sensor agents as often as possible. Eachsensor has a communicational radius and a sensory radius. indeed, optimal patrol can only be achieved if the duration between two visits of the same area of the environment is as minimal as possible. This time between two visits is called idleness. Thus, an effective patrol technique must make it possible to minimize idleness in the environment.That is why after a deep analysis of the existing resolution’s approaches, we propose a hybrid approach of resolution with three components: perception-reaction, field of strength and learning. In absence of obstacles, the perception-reaction component gives to the sensors a purely reactive behavior, as a function of their local perceptions, which permit them to move easily in their environment. The strength module enables the sensors to avoid the obstacles in the environment. As regards to the learning module, it allows the sensors to get out of blocking situations encountered during obstacle avoidance. This approach, called PREFAP, must be able to minimize idleness in different areas of the environment. The simulation results obtained show that the approach developed effectively minimizes idleness in the environment. This allows on the one hand, to have a regular patrol in the environment; on the other hand, thanks to the minimization of idleness of the areas of the environment, PREFAP will allow the sensors to quickly detect the various possible events which can occur in different areas of the environment.
Cite This Paper
Elie Tagne Fute, Doris-Khöler Nyabeye Pangop, Emmanuel Tonye, "A Hybrid Approach for the Multi-sensor Patrolling Problem in an Unknown Environment with Obstacles", International Journal of Computer Network and Information Security(IJCNIS), Vol.12, No.5, pp.16-30, 2020. DOI:10.5815/ijcnis.2020.05.02
Reference
[1]S. Sahraoui and S. Bouam, “Secure routing optimization in hierarchical cluster-based wireless sensor networks,” International Journal of Communication Networks and Infor- mation Security (IJCNIS), vol. 5, no. 3, pp. 178–185, 2013.
[2]A. CHAFIK, “Architectures de réseau de capteurs pour la surveillance de grands systèmes physiques à mobilité cyclique,” Ph.D. dissertation, UNIVERSITE DE LORRAINE, 2014.
[3]S. ZIANE, “Une approche inductive dans le routage à optimisation du délai: Application aux réseaux 802.11,” Ph.D. dissertation, Université Paris 12 Val de Marne, 2007.
[4]L. Sarzyniec, “Apprentissage par renforcement développemental pour la robotique auto- nome,” Laboratoire Lorrain de Recherche Informatique, 30 Août 2010.
[5]Y. Chevaleyre, “The patrolling problem: Theoretical and experimental results,” in Com- binatorial Optimization and Theoretical Computer Science. ISTE, 2008, pp. 161–174, https://doi.org/10.1002/9780470611098.ch6.
[6]A. Glad, “Etude de l’auto-organisation dans les algorithmes de patrouille multi-agent fon- dées sur les phéromones digitales,” Ph.D. dissertation, UNIVERSITE NANCY 2, 15 No- vembre 2011
[7]E. T. Fute, “Une approche de patrouille multi-agents pour la détection d’évènements,” Ph.D. dissertation, UNIVERSITE DE TECHNOLOGIE BELFORT-MONTBÉLIARD, 5Mars 2013.
[8]F. Lauri, A.Koukam, and J.-C. Créput, “Le problème de la patrouille multi-agent - Étude de convergencede l’évaluationdes stratégies cycliques,” Revue des Sciences et Technologies de l’Information, vol. 28, no. 6, pp. 665–687, Dec 2014, https://doi.org/10.3166/ria.28.665-687.
[9]A. Machado, G. Ramalho, J.-D. Zucker, and A. Drogoul, “Multi-agent patrolling: An empirical analysis of alternative architectures,” in Multi-Agent-Based Simulation II, Jul2003, vol. 2581, pp. 155–170, https://doi.org/10.1007/3-540-36483-8_11.
[10]F. Sempé, “Auto-organisation d’une collectivité de robots: Application à l’activité de patrouille en présence de perturbations,” Ph.D. dissertation, UNIVERSITE PIERRE ET MARIE CURIE, 2004.
[11]A. Glad, O. Buffet, O. Simonin, and F. Charpillet, “Auto-organisation dans les algorithmes de fourmis pour la patrouille multi-agent,” journées francophones planification, décision, apprentissage pour la conduite de systèmes (JFPDA’09), p. 14, Jun 2009.
[12]S. Chen, F.Wu, L.Shen, J.Chen, and S. D. Ramchurn, “Multi-agent patrolling under uncertainty and threats,” PLoS ONE, vol. 10, no. 6, Jun 2015, https://doi.org/10.1371/journal.pone.0130154.
[13]E. T. Fute, E. Tonye, A. Koukam, and F. Lauri, “Stratégie de patrouille multi-agents: Application au problèmed’exploration d’un environnement,” in In 5th IEEE Inter- national Conference: Sciences of Electronic, Technologies of Information and Tele- communications, Tunisia, Mar 2009.
[14]E. T. Fute, E.Tonye, F.Lauri, and A.Koukam, “Multi-agent patrolling: Multi- objective approach of the event detection by a mobile wireless sensors network,” International Journal of Computer Application, vol. 88, no.12, pp. 1–8, Feb 2014, https://doi.org/10.5120/15401-3845.
[15]M.-I. Popescu, H. Rivano, and O. Simonin, “Multi-robot patrolling in wireless sensor networks using bounded cycle coverage,” in 2016 IEEE 28th International Conference on Tools with Artificial Intelligence (ICTAI). San Jose, CA, USA: IEEE, Nov 2016, pp.169–176, https://doi.org/10.1109/ictai.2016.0035.
[16]A. Glad, H. N. Chu, O. Simonin, F. Sempe, A. Drogoul, and F. Charpillet, “Méthodes réactives pour le problème de la patrouille : Informations propagées vs. dépôt d’informa- tions,” in 15e Journées Francophones sur les Systèmes Multi-Agents - JFSMA’07, Institut de Recherche en Informatique de Toulouse (IRIT). Carcassonne, France:Cépaduès, Oct 2007.