Dynamic multi-Agent patrolling: Robotic application for service delivery to mobile people

Dynamic multi-Agent patrolling: Robotic application for service delivery to mobile people

Jacques Saraydaryan Fabrice Jumel Olivier Simonin 

Laboratoire CITI-Inria, équipe Chroma, INSA de Lyon, Inria Grenoble Rhône-Alpes

CPE Lyon, Domaine scientifique de la Doua, 69100 Villeurbanne, France

INSA Lyon, Université de Lyon, 20 Avenue Albert Einstein, 69100 Villeurbanne, Fr.

Corresponding Author Email: 
jacques.saraydaryan@cpe.fr; fabrice.jumel@cpe.fr; olivier.simonin@insa-lyon.fr
31 August 2017
| Citation



In this paper, we address the challenge of serving people by a set of mobile robots. As people move we can define the problem as a dynamic multi-agent patrolling. We propose different metrics by considering not only the time to patrol all the people but also the equity of the service delivery. We propose and compare four algorithms, two are based on standard solutions to multi-agent patrolling and two are defined according to the mobility and idleness of the persons. We present a simulator combining a pedestrian model and a robotic model. Strategies are compared on problem settings changing the number of robots, the topology of the environment and the people dispersion. Results show the efficiency of the new approaches.


multi-agent patrolling, service robotics, simulation, populated environment

1. Introduction
2. Etat de l’art
3. Patrouille dynamique
4. Stratégies multi-robots
5. Comparaison des stratégies
6. Conclusion

Aaron E., Krizanc D., Meyerson E. (2014). DMVP: foremost waypoint coverage of timevarying graphs. CoRR, vol. abs/1407.7279. Consulté sur http://arxiv.org/abs/1407.7279

Bernardin K., Stiefelhagen R. (2008). Evaluating multiple object tracking performance: The clear mot metrics. EURASIP Journal on Image and Video Processing, vol. 2008, no 1, p. 246309. Consulté sur http://jivp.eurasipjournals.com/content/2008/1/246309

Camp T., Boleng J., Davies V. (2002). A survey of mobility models for ad hoc network research. Wireless Communications and Mobile Computing, vol. 2, no 5, p. 483-502. Consulté sur http://dblp.uni-trier.de/db/journals/wicomm/wicomm2.html#CampBD02

Chevaleyre Y. (2007). The patrolling problem: Theoretical and experimental results. In W. O. Library (Ed.), Combinatorial optimization and theoretical computer science, p. 161-174.

Elmaliach Y., Agmon N., Kaminka G. A. (2010). Multi-robot area patrol under frequency constraints. AMAI, vol. 57, no 3–4, p. 293–320.

Glad A., Buffet O., Simonin O., Charpillet F. (2009). Self-organization of patrolling-ant algorithms. In Third IEEE international conference on self-adaptive and self-organizing systems,

SASO 2009, san francisco, california, usa, september 14-18, 2009, p. 61–70. Consulté sur http://dx.doi.org/10.1109/SASO.2009.39

Gloor C., Stucki P., Nagel K. (2004). Hybrid techniques for pedestrian simulations. In P. M. A. Sloot, B. Chopard, A. G. Hoekstra (Eds.), Acri, vol. 3305, p. 581-590. Springer.

Consulté sur http://dblp.uni-trier.de/db/conf/acri/acri2004.html#GloorSN04

Gomez J. V.,Mavridis N., Garrido S. (2014). Fast marching solution for the social path planning problem. In 2014 IEEE international conference on robotics and automation, ICRA 2014, hong kong, china, may 31 - june 7, 2014, p. 1871–1876. Consulté sur http://dx.doi.org/10.1109/ICRA.2014.6907105

Helbing D., Molnár P. (1995). Social force model for pedestrian dynamics. Physical Review E, p. 4282–4286.

Lu Q., Lu G., Bai A., Zhang D., Chen X. (2013). An intelligent service system with multiple robots. In Robot competition of international joint conference on artificial intelligence (ijcai 2013).

Papadakis P., Rives P., Spalanzani A. (2014, septembre). Adaptive Spacing in Human-Robot Interactions. In IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, IROS’14,. Chicago, United States. Consulté sur https://hal.inria.fr/hal-01010224

Pasqualetti F., Franchi A., Bullo F. (2010, 12/2010). On optimal cooperative patrolling. In 49th ieee conference on decision and control, p. 7153-7158. Atlanta, GA, USA.

Portugal D., Rocha R. (2011). A survey on multi-robot patrolling algorithms. IFIP Advances in Information and Communication Technology, vol. 349, p. 139-146.

Poulet C., Corruble V., Seghrouchni A. E. F. (2012). Auction-based strategies for the opensystem patrolling task. In Proc. prima - 15th international conference on principles and practice of multi-agent systems.

Rios-Martinez J., Spalanzani A., Laugier C. (2014, septembre). From Proxemics Theory to Socially-Aware Navigation: A Survey. International Journal of Social Robotics. Consulté sur https://hal.inria.fr/hal-01067278

ROS packages for pedsim (pedestrian simulator) based on social force model of helbing et. al, https://github.com/srl-freiburg/pedsim_ros. (s. d.). Consulté sur https://github.com/srl-freiburg/pedsim_ros

Volkhardt M.,Weinrich C., Gross H.-M. (2013, Sept). Multi-modal people tracking on a mobile companion robot. In Mobile robots (ecmr), 2013 european conference on, p. 288-293.