Tracking an omnidirectional evader with a differential drive robot at a bounded variable distance

Ruiz, U. ; Marroquin, J. L. ; Murrieta-Cid, R.

International Journal of Applied Mathematics and Computer Science, Tome 24 (2014) no. 2, pp. 371-385.

Résumé

In this paper, we address the pursuit-evasion problem of tracking an Omnidirectional Agent (OA) at a bounded variable distance using a Differential Drive Robot (DDR), in an Euclidean plane without obstacles. We assume that both players have bounded speeds, and that the DDR is faster than the evader, but due to its nonholonomic constraints it cannot change its motion direction instantaneously. Only a purely kinematic problem is considered, and any effect due to dynamic constraints (e.g., acceleration bounds) is neglected. We provide a criterion for partitioning the configuration space of the problem into two regions, so that in one of them the DDR is able to control the system, in the sense that, by applying a specific strategy (also provided), the DDR can achieve any inter-agent distance (within an error bound), regardless of the actions taken by the OA. Particular applications of these results include the capture of the OA by the DDR and maintaining surveillance of the OA at a bounded variable distance.

Détail

Keywords: pursuit evasion, tracking, capturing, differential drive robot
Mots-clés : śledzenie obiektu, wychwytywanie, napęd robota

Bibliographie

[1] Başar, T. and Olsder, G. (1982). Dynamic Noncooperative Game Theory, Academic Press, New York, NY.

[2] Balkcom, D. and Mason, M. (2002). Time optimal trajectories for bounded velocity differential drive vehicles, International Journal of Robotics Research 21(3): 219–232.

[3] Bandyopadhyay, T., Li, Y., Ang, M. and Hsu, D. (2006). A greedy strategy for tracking a locally predictable target among obstacles, Proceedings of the International Conference on Robotics and Automation, ICRA 2006, Orlando, FL, USA, pp. 2342–2347.

[4] Becker, C., González-Baños, H., Latombe, J. and Tomasi, C. (1995). An intelligent observer, Proceedings of the International Symposium on Experimental Robotics, ISER 1995, Stanford, CA, USA, pp. 153–160.

[5] Bhattacharya, S. and Hutchinson, S. (2010). On the existence of Nash equilibrium for a two player pursuit-evasion game with visibility constraints, International Journal of Robotics Research 29(7): 831–839.

[6] Chung, T. (2008). On probabilistic search decisions under searcher motion constraints, Proceedings of the International Workshop on the Algorithmic Foundations of Robotics, WAFR 2008, Guanajuato, Mexico, pp. 501–516.

[7] Fabiani, P., González, H., Latombe, J. and Lin, D. (2002). Tracking an unpredictable target among occluding obstacles under localization uncertainties, Robotics and Autonomous Systems 38(1): 31–48.

[8] González, H., Lee, C. Y. and Latombe, J. C. (2002). Real-time combinatorial tracking of a target moving unpredictably among obstacles, Proceedings of the International Conference on Robotics and Automation, ICRA 2002, Washington, DC, USA, pp. 1683–1690.

[9] Guibas, L., Latombe, J., LaValle, S.M., Lin, D. and Motwani, R. (1999). A visibility-based pursuit-evasion problem, International Journal of Computational Geometry and Applications 9(4–5): 471–494.

[10] Hájek, O. (1965). Pursuit Games, Academic Press, New York, NY.

[11] Hespanha, J., Prandini, M. and Sastry, S. (2000). Probabilistic pursuit-evasion games: A one-step Nash approach, Proceedings of the 39th International Conference on Decision and Control, Los Angeles, CA, USA, pp. 2272–2277.

[12] Hollinger, G., Singh, S., Djugash, J. and Kehagias, A. (2009). Efficient multi-robot search for a moving target, International Journal of Robotics Research 28(2): 201–219.

[13] Isaacs, R. (1965). Differential Games: A Mathematical Theory With Applications to Warfare and Pursuit, Control and Optimization, Academic Press, New York, NY.

[14] Isler, V., Kannan, S. and Khanna, S. (2005). Randomized pursuit-evasion in a polygonal environment, IEEE Transactions on Robotics 21(5): 864–875.

[15] Jung, B. and Sukhatme, G. (2002). Tracking targets using multiple robots: The effect of environment occlusion, Autonomous Robots 13(3): 191–205.

[16] Kowalczuk, Z. and Czubenko, M. (2011). Intelligent decision-making system for autonomus robots, International Journal and Applied Mathematics and Computer Science 21(4): 671–684, DOI: 10.2478/v10006-011-0053-7.

[17] LaValle, S.M. (2006). Planning Algorithms, Cambridge University Press, New York, NY.

[18] LaValle, S.M., González, H., Becker, C. and Latombe, J. (1997). Motion strategies for maintaining visibility of a moving target, Proceedings of the International Conference on Robotics and Automation, ICRA 1997, Albuquerque, NM, USA, pp. 731–736.

[19] Merz, A. (1971). The Homicidal Chauffeur: A Differential Game, Ph.D. thesis, Stanford University, Stanford, CA.

[20] Murrieta-Cid, R., Monroy, R., Hutchinson, S. and Laumond, J.-P. (2008). A complexity result for the pursuit-evasion game of maintaining visibility of a moving evader, Proceedings of the International Conference on Robotics and Automation, ICRA 2008, Pasadena, CA, USA, pp. 2657–2664.

[21] Murrieta-Cid, R., Muppirala, T., Sarmiento, A., Bhattacharya, S. and Hutchinson, S. (2007). Surveillance strategies for a pursuer with finite sensor range, International Journal of Robotics Research 26(3): 233–252.

[22] Murrieta-Cid, R., Ruiz, U., Marroquin, J., Laumond, J. and Hutchinson, S. (2011). Tracking an omnidirectional evader with a differential drive robot, Autonomous Robots 31(4): 345–366.

[23] Murrieta-Cid, R., Tovar, B. and Hutchinson, S. (2005). A sampling-based motion planning approach to maintain visibility of unpredictable targets, Autonomous Robots 19(3): 285–300.

[24] O’Kane, J. (2008). On the value of ignorance: Balancing tracking and privacy using a two-bit sensor, Proceedings of the International Workshop on the Algorithmic Foundations of Robotics, WAFR 2008, Guanajuato, Mexico, pp. 235–249.

[25] Parker, L. (2002). Distributed algorithms for multi-robot observation of multiple targets, Autonomous Robots 12(3): 231–255.

[26] Prodan, I., Olaru, S., Stoica, C. and Niculescu, S.-I. (2013). Predictive control for trajectory tracking and decentralized navigation of multi-agent formations, International Journal of Applied Mathematics and Computer Science 23(1): 91–102, DOI: 10.2478/amcs-2013-0008.

[27] Ruiz, U. and Murrieta-Cid, R. (2012). A homicidal differential drive robot, Proceedings of the International Conference on Robotics and Automation, ICRA 2012, St. Paul, MN, USA, pp. 3218–3225.

[28] Ruiz, U., Murrieta-Cid, R. and Marroquin, J. (2013). Time-optimal motion strategies for capturing an omnidirectional evader using a differential drive robot, IEEE Transactions on Robotics 29(5): 1180–1196.

[29] Sachs, S., LaValle, S. and Rajko, S. (2004). Visibility-based pursuit-evasion in an unknown planar environment, International Journal of Robotics Research 23(1): 3–26.

[30] Schwartz, J.T. and Sharir, M. (1983). On the piano movers’ problem. I: The case of a two-dimensional rigid polygon body moving amidst polygonal barriers, Communications on Pure and Applied Mathematics 36(3): 345–398.

[31] Skrzypczyk, K. (2005). Control of a team of mobile robots based on non-cooperative equilibria with partial coordination, International Journal of Applied Mathematics and Computer Science 15(1): 89–97.

[32] Suzuki, I. and Yamashita, M. (1992). Searching for a mobile intruder in a polygonal region, SIAM Journal on Computing 21(5): 863–888.

[33] Tekdas, O. and Yang, W.and Isler, V. (2010). Robotic routers: Algorithms and implementation, International Journal of Robotics Research 29(1): 110–126.

[34] Tovar, B. and LaValle, S. (2008). Visibility-based pursuit-evasion with bounded speed, International Journal of Robotics Research 27(11–12): 1350–1360.

[35] Vidal, R., Shakernia, O., Jin, H., Hyunchul, D. and Sastry, S. (2002). Probabilistic pursuit-evasion games: Theory, implementation, and experimental evaluation, IEEE Transactions on Robotics and Automation 18(5): 662–669.