Maintaining strong mutual visibility of an evader moving over the reduced visibility graph
Tóm tắt
In this paper, we address the problem of determining whether a mobile robot, called the pursuer, is able to maintain strong mutual visibility (a visibility notion between regions over a convex partition of the environment) of an antagonist agent, called the evader. We frame the problem as a non cooperative game. We consider the case in which the pursuer and the evader move at bounded speed, traveling in a known polygonal environment with or without holes, and in which there are no restrictions as to the distance that might separate the agents. Unlike our previous efforts (Murrieta-Cid et al. in Int J Robot Res 26:233–253, 2007), we give special attention to the combinatorial problem that arises when searching for a solution through visiting several locations in an environment with obstacles. In this paper we take a step further, namely, we assume an antagonistic evader who moves continuously and unpredictably, but with a constraint over its set of admissible motion policies, as the evader moves in the shortest-path roadmap, also called the reduced visibility graph (RVG). The pursuer does not know which among the possible paths over the RVG the evader will choose, but the pursuer is free to move within all the environment. We provide a constructive method to solve the decision problem of determining whether or not the pursuer is able to maintain strong mutual visibility of the evader. This method is based on an algorithm that computes the safe areas (areas that keep evader surveillance) at all times. We prove decidability of this problem, and provide a complexity measure to this evader surveillance game; both contributions hold for any general polygonal environment that might or not contain holes. All our algorithms have been implemented and we show simulation results.
Tài liệu tham khảo
Bandyopadhyay, T., Li, Y., Ang, M.H., & Hsu, D. (2006). A greedy strategy for tracking a locally predictable target among obstacles. In Proceedings of IEEE International Conference on Robotics and Automation.
Bandyopadhyay, T., Ang, M.H., & Hsu, D. (2007). Motion planning for 3-D target tracking among obstacles. In International Symposium on Robotics Research.
Barrière, L., Flocchini, P., Fraigniaud, P., & Santoro, N. (2002). Capture of an intruder by mobile agents. In Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures (pp. 200–209). Winnipeg, Manitoba.
Başar, T., & Olsder, G. (1982). Dynamic noncooperative game theory. London: Academic Press.
Becerra, I., Murrieta-Cid, R., & Monroy, R. (2010). Evader surveillance under incomplete information. In IEEE International Conference on Robotics and Automation.
Becker, C., González-Baños, H., Latombe, J.-C., & Tomasi, C. (1995). An intelligent observer. In International Symposium on Experimental Robotics.
Bhattacharya, S., & Hutchinson, S. (2009). On the existence of nash equilibrium for a two player pursuit-evasion game with visibility constraints. In International Journal on Robotics Research.
Bhattacharya, S., & Hutchinson, S. (2011). A Cell decomposition approach to visibility-based pursuit evasion among obstacles. The International Journal of Robotics Research, 30(14), 1709–1727.
Chung, T.H. (2008). On probabilistic search decisions under searcher motion constraints. In WAFR 2008 (pp. 501–516).
Chung, T., Hollinger, G., & Isler, V. (2011). Search and pursuit-evasion in mobile robotics: A survey. Autonomous Robots, 31(4), 299–316.
Cormen, T. H., Stein, C., Rivest, R. L., & Leiserson, C. E. (2001). Introduction to algorithms. Groveport: McGraw-Hill Higher Education.
Efrat, A., Gonzalez-Baños, H.H., Kobourov, S.G., & Palaniappan, L. (2003). Optimal motion strategies to track and capture a predictable target. In Proceedings of IEEE International Conference on Robotics and Automation (pp. 411–423). Taipei, Taiwan.
Fabiani, P., & Latombe, J.-C. (1999). Tracking a partially predictable object with uncertainty and visibility constraints: A game-theoretic approach. In IJCAI.
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability. New York: W. H. Freeman and Company.
González, H.H. et al. (2002). Real-time combinatorial tracking of a target moving unpredictably among obstacles. In Proceedings of IEEE International Conference on Robotics and Automation.
Guibas, L., Latombe, J.-C., LaValle, S. M., Lin, D., & Motwani, R. (1999). Visibility-based pursuit-evasion in a polygonal environment. International Journal of Computational Geometry and Applications, 9(5), 471–494.
Hájek, O. (1965). Pursuit games. New York: Academic Press.
Hespanha, J., Prandini, M., & Sastry, S. (2000). Probabilistic pursuit-evasion games: A one-step Nash approach. In Proceedings of Conference on Decision and Control.
Hollinger, G., Singh, S., Djugash, J., & Kehagias, A. (2009). Efficient multi-robot search for a moving target. The International Journal of Robotics Research, 28(2), 201–219.
Isaacs, R. (1965). Differential games. New York: Wiley.
Isler, V., Kannan, S., & Khanna, S. (2005). Randomized pursuit-evasion in a polygonal environment. IEEE Transactions on Robotics, 5(21), 864–875.
Jung, B., & Sukhatme, G. (2002). Tracking targets using multiple robots: The effect of environment occlusion. Journal Autonomous Robots, 12, 191–205.
Latombe, J.-C. (1991). Robot motion planning. New York: Kluwer Academic Publishers.
LaValle, S.M., González-Baños, H.H., Becker, C., & Latombe, J.-C. (1997) Motion strategies for maintaining visibility of a moving target. In Proceedings of IEEE International Conference on Robotics and Automation.
LaValle, S. M. (2006). Planning algorithms. Cambridge: Cambridge University Press.
Merz, A.W. (1971). The homicidal chauffeur a differential game. PhD. Thesis. Stanford University.
Murrieta-Cid, R., Sarmiento, A., & Hutchinson, S. (2003). On the existence of a strategy to maintain a moving target within the sensing range of an observer reacting with delay. In Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems.
Murrieta-Cid, R., Tovar, B., & Hutchinson, S. (2005). A sampling-based motion planning approach to maintain visibility of unpredictable targets. Journal Autonomous Robots, 19(3), 285–300.
Murrieta-Cid, R., Muppirala, T., Sarmiento, A., Bhattacharya, S., & Hutchinson, S. (2007). Surveillance strategies for a pursuer with finite sensor range. International Journal of Robotics Research, 26(3), 233–253.
Murrieta-Cid, R., Monroy, R., Hutchinson, S., & Laumond, J.-P. (2008). A complexity result for the pursuit-evasion game of maintaining visibility of a moving evader. In IEEE International Conference on Robotics and Automation.
O’Rourke, J. (2000). Computational geometry in C. Cambridge: Cambridge University Press.
O’Rourke, J. (1987). Art gallery theorems and algorithms. Oxford: Oxford University Press.
O’Kane, J.M. (2008). On the value of ignorance: Balancing tracking and privacy using a two-bit sensor. In Proceedings of International Workshop on the Algorithmic Foundations of Robotics.
Parker, L. (2002). Algorithms for multi-robot observation of multiple targets. Journal Autonomous Robots, 12, 231–255.
Parsons, T. D. (1976). Pursuit-evasion in a graph. In Y. Alani & D. R. Lick (Eds.), Theory and application of graphs (pp. 426–441). Berlin: Springer.
Pocchiola, M., & Vegter, G. (1996). The visibility complex. In International Journal of Computational Geometry and Applications.
Rappoport, A. (1966). Two-person game theory. Dover: Courier Corporation.
Sachs, S., Rajko, S., & LaValle, S. M. (2004). Visibility-based pursuit-evasion in an unknown planar environment. International Journal on Robotics Research, 23(1), 3–26.
Shermer, T.C. (1992). Recent results in art galleries. In Proceedings of the IEEE (vol. 80, no. 9).
Stump, E., Michael, N., Kumar, V., & Isler, V. (2011). Visibility-based deployment of robot formations for communication maintenance. In IEEE International Conference on Robotics and Automation 2011.
Suzuki, I., & Yamashita, M. (1992). Searching for a mobile intruder in a polygonal region. SIAM Journal on Computing, 21(5), 863–888.
Takeuti, G., & Zaring, W. M. (1971). Introduction to axiomatic set theory. New York: Springer.
Tekdas, O., Yang, W., & Isler, V. (2010). Robotic routers: Algorithms and implementation. The International Journal of Robotics Research, 29(1), 110–126.
Tovar, B., & LaValle, S. M. (2008). Visibility-based pursuit—evasion with bounded speed. The International Journal of Robotics Research, 27(11–12), 1350–1360.
Vidal, R., et al. (2002). Probabilistic pursuit-evasion games: Theory, implementation, and experimental evaluation. IEEE Transactions on Robotics and Automation, 18(5), 662–669.