Probabilistic Search and Pursuit Evasion on a Graph
DOI:
https://doi.org/10.14738/tmlai.33.1313Keywords:
Machine Learning, Mechatronics, Pursuit Evasion, POMDP, Reinforcement Learning, Graph SearchAbstract
This paper presents an approach to locate an adversarial, mobile evader in an indoor environment using motion planning of mobile pursuers. The approach presented in this paper uses motion planning of mobile robots to search a target in a graph and clear the workspace. The algorithm used is Partially Observable Markov Decision Process (POMDP), a probabilistic search method to clear the indoor workspace in a pursuit evasion domain. In this paper, the indoor environment is assumed to be known beforehand and the mobile evader to be adversarial with no motion model given. The workspace is first discretized and then converted to a graph, whose nodes represent the rooms and corridors and edges represent connection between them. The task of pursuer is to clear the whole graph with no contaminated node left in minimum possible steps. Such path planning problems are NP-hard and the problem scales exponentially with increased number of pursuers and complex graph.References
(1) T. D. Parsons, “Pursuit-Evasion in a Graph,” vol. 642, 1978.
(2) T. H. Chung, G. a. Hollinger, and V. Isler, “Search and pursuit-evasion in mobile robotics A survey,” Auton. Robots, vol. 31, no. 4, pp. 299–316, 2011.
(3) R. Nowakowski and P. Winkler, “Vertex-to-vertex pursuit in a graph,” Discrete Math., vol. 43, no. 2–3, pp. 235–239, 1983.
(4) M. Aigner and M. Fromme, “A game of cops and robbers,” Discret. Appl. Math., vol. 8, no. 1, pp. 1–12, 1984.
(5) V. Isler, S. Kannan, and S. Khanna, “Randomized Pursuit-Evasion with Local Visibility,” SIAM J. Discret. Math., vol. 20, no. 1, pp. 26–41, 2006.
(6) N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson, and C. H. Papadimitriou, “The complexity of searching a graph,” 22nd Annu. Symp. Found. Comput. Sci. (sfcs 1981), vol. 35, no. 1, pp. 18–44, 1981.
(7) D. Bienstock and P. Seymour, “Monotonicity in graph searching,” J. Algorithms, vol. 12, no. 2, pp. 239–245, 1991.
(8) A. S. LaPaugh, “Recontamination does not help to search a graph,” J. ACM, vol. 40, no. 2, pp. 224–245, Apr. 1993.
(9) A. Kehagias and S. Singh, “A Graph Search Algorithm for Indoor Pursuit / Evasion,” no. July, pp. 1305–1317, 2008.
(10) V. Isler, S. Kannan, and S. Khanna, “Randomized Pursuit evasion in a polygonal environment,” IEEE Trans. Robot., no. Wafr, 2005.
(11) D. (department of C. S. and E. of M. Bhadauria and V. (Department of C. S. and E. of M. Isler, “Capturing an Evader in a Polygonal Environment with Obstacles,” no. June, pp. 16–26, 2011.
(12) B. P. Gerkey, “Visibility-based Pursuit-evasion with Limited Field of View,” The International Journal of Robotics Research, vol. 25, no. 4. pp. 299–315, 2006.
(13) L. J. Guibas, J. L. Steven, M. L. David, and L. Rajeev, “A Visibility-Based Pursuit-Evasion Problem,” pp. 1–29.
(14) 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 & Applications, vol. 09, no. 04n05. pp. 471–493, 1999.
(15) L. Guibas, J.-C. Latombe, S. Lavalle, D. Lin, and R. Motwani, “Visibility-based pursuit-evasion in a polygonal environment,” Algorithms Data Struct., pp. 17–30, 1997.
(16) G. Hollinger, A. Kehagias, and S. Singh, “GSST: Anytime guaranteed search,” Auton. Robots, vol. 29, no. 1, pp. 99–118, 2010.
(17) M. (Department of E. E. U. Yamashita, E. D. D. C. A. C. Umemoto, Hideki (System Engineering Section, I. (Department of E. E. and C. S. of W. Suzuki, and T. (School of C. S. F. U. Kameda, “Searching for Mobile
Intruders in a Polygonal Region by a Group of Mobile Searchers.”
(18) S. C. W. Ong, Shao Wei Png, D. Hsu, and Wee Sun Lee, “Planning under Uncertainty for Robotic Tasks with Mixed Observability,” Int. J. Rob. Res., vol. 29, no. 8, pp. 1053–1068, 2010.
(19) J. H. Eaton and L. A. Zadeh, “Optimal Pursuit Strategies in Discrete-State Probabilistic Systems,” J. Basic Eng., vol. 84, no. 1, p. 23, Mar. 1962.
(20) N. Roy, G. Gordon, and S. Thrun, “Finding approximate POMDP solutions through belief compression,” J. Artif. Intell. Res., vol. 23, pp. 1–40, 2005.
(21) K. P. Murphy, “A survey of POMDP solution techniques,” Environment, vol. 2, no. September, p. X3, 2000.
(22) A. Barto, “Reinforcement learning: An introduction,” 1998.
