×

Clearing an orthogonal polygon to find the evaders. (English) Zbl 1464.68403

Summary: In a multi-robot system, a number of autonomous robots would sense, communicate, and decide to move within a given domain to achieve a common goal. In the pursuit-evasion problem, a polygonal region is given and a robot called a pursuer tries to find some mobile targets called evaders. The goal of this problem is to design a motion strategy for the pursuer such that it can detect all the evaders. In this paper, we consider a new variant of the pursuit-evasion problem in which the robots (pursuers) each moves back and forth along an orthogonal line segment inside a simple orthogonal polygon \(P\). We assume that \(P\) includes unpredictable, moving evaders that have bounded speed. We propose the first motion-planning algorithm for a group of robots, assuming that they move along the pre-located line segments with a constant speed to detect all the evaders with bounded speed. Also, we prove an upper bound for the length of the paths that all pursuers move in the proposed algorithm.

MSC:

68T40 Artificial intelligence for robotics
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Parsons, T. D., Pursuit-evasion in a graph, (Theory and Applications of Graphs (1978), Springer), 426-441 · Zbl 0379.05026
[2] LaValle, S. M.; Lin, D.; Guibas, L. J.; Latombe, J.-C.; Motwani, R., Finding an unpredictable target in a workspace with obstacles, (Robotics and Automation, 1997. Proceedings., 1997 IEEE International Conference on, vol. 1 (1997), IEEE), 737-742
[3] Katz, M. J.; Morgenstern, G., Guarding orthogonal art galleries with sliding cameras, Int. J. Comput. Geom. Appl., 21, 02, 241-250 (2011) · Zbl 1216.65028
[4] Durocher, S.; Mehrabi, S., Guarding orthogonal art galleries using sliding cameras: algorithmic and hardness results, (Mathematical Foundations of Computer Science 2013 (2013), Springer), 314-324 · Zbl 1400.68247
[5] de Berg, M.; Durocher, S.; Mehrabi, S., Guarding monotone art galleries with sliding cameras in linear time, (Combinatorial Optimization and Applications (2014), Springer), 113-125 · Zbl 1358.68308
[6] Suzuki, I.; Yamashita, M., Searching for a mobile intruder in a polygonal region, SIAM J. Comput., 21, 5, 863-888 (1992) · Zbl 0757.68098
[7] Durham, J. W.; Franchi, A.; Bullo, F., Distributed pursuit-evasion without mapping or global localization via local frontiers, Auton. Robots, 32, 1, 81-95 (2012)
[8] O’rourke, J., Art Gallery Theorems and Algorithms, vol. 57 (1987), Oxford University Press: Oxford University Press Oxford · Zbl 0653.52001
[9] Urrutia, J., Art gallery and illumination problems, (Handbook of Computational Geometry, vol. 1 (1) (2000)), 973-1027 · Zbl 0941.68138
[10] Hoffmann, F., On the Rectilinear Art Gallery Problem (1990), Springer · Zbl 0765.68208
[11] Schuchardt, D.; Hecker, H.-D., Two np-hard art-gallery problems for ortho-polygons, Math. Log. Q., 41, 2, 261-267 (1995) · Zbl 0827.68115
[12] Lee, D.-T.; Lin, A. K., Computational complexity of art gallery problems, IEEE Trans. Inf. Theory, 32, 2, 276-282 (1986) · Zbl 0593.68035
[13] Motwani, R.; Raghunathan, A.; Saran, H., Covering orthogonal polygons with star polygons: the perfect graph approach, (Proceedings of the Fourth Annual Symposium on Computational Geometry (1988), ACM), 211-223
[14] Worman, C.; Keil, J. M., Polygon decomposition and the orthogonal art gallery problem, Int. J. Comput. Geom. Appl., 17, 02, 105-138 (2007) · Zbl 1144.65015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.