[en] In this paper, the multi pursuer version of the pursuit evasion problem in polygonal environments is addressed. This problem is NP-hard, and therefore we seek good enough, but not optimal solutions. By modeling the problem as a Boolean Control Network, we can efficiently keep track of which regions are cleared, and which are not, while the input nodes of the network are used to represent the motion of the pursuers. The environment is partitioned into a set of convex regions, where each region correspond to a set of nodes in the network. The method is implemented in ANSI C, and efficiently solves complex environments containing multiple loops and requiring so-called recontamination. The provided examples demonstrate the effectiveness of the method in terms of computational time.
Disciplines :
Ingénierie, informatique & technologie: Multidisciplinaire, généralités & autres
Auteur, co-auteur :
THUNBERG, Johan ; University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB)
Ogren, P.
Hu, X.
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
A boolean control network approach to pursuit evasion problems in polygonal environments
Date de publication/diffusion :
2011
Nom de la manifestation :
2011 IEEE International Conference on Robotics and Automation (ICRA)
Lieu de la manifestation :
Shangai, Chine
Date de la manifestation :
9-13 May 2011
Titre de l'ouvrage principal :
Proceedings of the 2011 IEEE International Conference on Robotics and Automation (ICRA)
D. Cheng. Input-state approach to Boolean networks. IEEE Transactions on Neural Networks, 20(3):512-521, 2009.
D. Cheng and H. Qi. Controllability and observability of Boolean control networks. Automatica, 45(7):1659-1667, 2009.
B.P. Gerkey, S. Thrun, and G. Gordon. Visibility-based pursuit-evasion with limited field of view. The International Journal of Robotics Research, 25(4):299, 2006.
L.J. Guibas, J.C. Latombe, S.M. LaValle, D. Lin, and R. Motwani. A visibility-based pursuit-evasion problem. International Journal of Computational Geometry and Applications, 1999.
A.G. Hamilton. Logic for mathematicians. Cambridge Univ Pr, 1988.
G. Hollinger, S. Singh, and A. Kehagias. Efficient, Guaranteed Search with Mult-Agent Teams. 2009 Robotics: Science and Systems Conference, RSS, 2009.
V. Isler, S. Kannan, and S. Khanna. Randomized pursuit-evasion in a polygonal environment. IEEE Transactions on Robotics, 21(5):875-884, 2005.
A. Kolling and S. Carpin. The GRAPH-CLEAR problem: definition, theoretical properties and its connections to multirobot aided surveillance. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 1003-1008, 2007.
R. Murrieta-Cid, R. Monroy, S. Hutchinson, and J.P. Laumond. A complexity result for the pursuit-evasion game of maintaining visibility of a moving evader. In Robotics and Automation, 2008. ICRA 2008. IEEE International Conference on, pages 2657-2664. IEEE, 2008.
I. Suzuki and M. Yamashita. Searching for a mobile intruder in a polygonal region. SIAM Journal on Computing, 21:863, 1992.
J. Thunberg and P. Ögren. An iterative Mixed Integer Linear Programming Approach to pursuit evasion problems in polygonal environments. In IEEE International Conference on Robotics and Automation (ICRA), pages 5498-5503. IEEE, 2010.
