iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://link.springer.com/doi/10.1007/s10514-011-9246-z
Tracking an omnidirectional evader with a differential drive robot | Autonomous Robots Skip to main content
Springer Nature Link
Log in

Tracking an omnidirectional evader with a differential drive robot

  • Published:
Autonomous Robots Aims and scope Submit manuscript

Abstract

In this paper we consider the surveillance problem of tracking a moving evader by a nonholonomic mobile pursuer. We deal specifically with the situation in which the only constraint on the evader’s velocity is a bound on speed (i.e., the evader is able to move omnidirectionally), and the pursuer is a nonholonomic, differential drive system having bounded speed.

We formulate our problem as a game. Given the evader’s maximum speed, we determine a lower bound for the required pursuer speed to track the evader. This bound allows us to determine at the beginning of the game whether or not the pursuer can follow the evader based on the initial system configuration. We then develop the system model, and obtain optimal motion strategies for both players, which allow us to establish the long term solution for the game. We present an implementation of the system model, and motion strategies, and also present simulation results of the pursuit-evasion game.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Balkcom, D. J., & Mason, M. T. (2002). Time optimal trajectories for bounded velocity differential drive vehicles. The International Journal of Robotics Research, 21(3), 219–232.

    Article  Google Scholar 

  • Bandyopadhyay, T., Li, Y., Ang, M. H., & Hsu, D. (2006). A Greedy Strategy for Tracking a Locally Predictable Target among Obstacles. In Proc. IEEE int. conf. on robotics and automation.

    Google Scholar 

  • Başar, T., & Olsder, G. (1982). Dynamic noncooperative game theory. San Diego: Academic Press.

    MATH  Google Scholar 

  • Becker, C., González-Baños, H., Latombe, J.-C., & Tomasi, C. (1995). An intelligent observer. In Int. symposium on experimental robotics.

    Google Scholar 

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

    Article  Google Scholar 

  • Bronshtein, I., & Semendiaev, K. (1988). Manual de matemáticas para ingenieros y estudiantes. Moscow: Mir.

    Google Scholar 

  • Chung, T. H. (2008). On probabilistic search decisions under searcher motion constraints. In WAFR (pp. 501–516).

    Google Scholar 

  • Fabiani, P., & Latombe, J.-C. (1999). Tracking a partially predictable object with uncertainty and visibility constraints: a game-theoretic approach. In IJCAI.

    Google Scholar 

  • González, H. H., Lee, C.-Y., & Latombe, J.-C. (2002). Real-time combinatorial tracking of a target moving unpredictably among obstacles. In Proc. IEEE int. conf. on robotics and automation.

    Google Scholar 

  • Guibas, L., Latombe, J.-C., LaValle, S. M., Lin, D., & Motwani, R. (1997). Visibility-based pursuit-evasion in a polygonal environment. In Proc. 5th workshop on algorithms and data structures.

    Google Scholar 

  • Hájek, O. (1965). Pursuit games. New York: Academic Press.

    Google Scholar 

  • Hespanha, J., Prandini, M., & Sastry, S. (2000). Probabilistic pursuit-evasion games: a one-step nash approach. In Proc. conference on decision and control.

    Google Scholar 

  • 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.

    Article  Google Scholar 

  • Isaacs, R. (1965). Differential games. New York: Wiley.

    MATH  Google Scholar 

  • Isler, V., Kannan, S., & Khanna, S. (2005). Randomized pursuit-evasion in a polygonal environment. IEEE Transactions on Robotics, 5(21), 864–875.

    Google Scholar 

  • Jung, B., & Sukhatme, G. (2002). Tracking targets using multiple robots: the effect of environment occlusion. Journal Autonomous Robots, 12, 191–205.

    Article  Google Scholar 

  • Latombe, J.-C. (1991). Robot motion planning. Dordrecht: Kluwer Academic.

    Book  Google Scholar 

  • Laumond, J. P. (Ed.) (1998). Lectures notes in control and information sciences: Vol. 229. Robot motion planning and control. Berlin: Springer.

    Google Scholar 

  • Laumond, J. P., Jacobs, P. E., Taix, M., & Murray, R. M. (1994). A motion planner for nonholonomic mobile robots. IEEE Transactions on Robotics and Automation, 10(5), 577–593.

    Article  Google Scholar 

  • 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 Proc. IEEE int. conf. on robotics and automation.

    Google Scholar 

  • Li, Z., & Canny, J. (1990). Motion of two rigid bodies with rolling constraint. IEEE Transactions on Robotics and Automation, 6, 62–72.

    Article  Google Scholar 

  • Murray, R. M., & Sastry, S. (1993). Nonholonomic motion planning: Steering using sinusoids. IEEE Transactions on Robotics and Automation, 38(5), 700–716.

    MathSciNet  MATH  Google Scholar 

  • Murrieta-Cid, R., Muñoz, L., Alencastre, M., Sarmiento, A., Kloder, S., Hutchinson, S., Lamiraux, F., & Laumond, J.-P. (2005a). Maintaining visibility of a moving holonomic target with a non-holonomic robot. In Proc. IEEE/RSJ international conference on intelligent robots and systems 2005, Edmonton, Canada, August (pp. 2028–2034).

    Google Scholar 

  • Murrieta-Cid, R., Tovar, B., & Hutchinson, S. (2005b). A sampling-based motion planning approach to maintain visibility of unpredictable targets. Journal Autonomous Robots, 19(3), 285–300.

    Article  Google Scholar 

  • Murrieta-Cid, R., Muppirala, T., Sarmiento, A., Bhattacharya, S., & Hutchinson, S. (2007). Surveillance strategies for a pursuer with finite sensor range. The International Journal of Robotics Research, 26(3), 233–253.

    Article  Google Scholar 

  • 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.

    Google Scholar 

  • Parker, L. (2002). Algorithms for multi-robot observation of multiple targets. Journal Autonomous Robots, 12, 231–255.

    Article  MATH  Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Article  Google Scholar 

  • Schwartz, J. T., & Sharir, M. (1987). On the Piano movers’ problem: I. The case if a two-dimensional rigid polygon body moving amidst polygonal barriers. Communications on Pure and Applied Mathematics, 36, 345–398.

    Article  MathSciNet  Google Scholar 

  • Sussmann, H. J., & Liu, W. (1991). Limits of highly oscillatory controls and the approximation of general paths by admissible trajectories (Tech. Rep. SYSCON-91-02). Rutgers Center for Systems and Control, February.

  • Suzuki, I., & Yamashita, M. (1992). Searching for a mobile intruder in a polygonal region. SIAM Journal on Computing, 21(5), 863–888.

    Article  MathSciNet  MATH  Google Scholar 

  • Tekdas, O., & Isler, V. (2008). Robotic Routers. In Proc. IEEE int. conf. on robotics and automation.

    Google Scholar 

  • Tovar, B., & LaValle, S. M. (2008). Visibility-based pursuit-evasion with bounded speed. The International Journal of Robotics Research, 27(11–12), 1350–1360.

    Article  Google Scholar 

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

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Centro de Investigación en Matemáticas, CIMAT, Guanajuato, México

    Rafael Murrieta-Cid, Ubaldo Ruiz & Jose Luis Marroquin

  2. LAAS-CNRS, University of Toulouse, Toulouse, France

    Jean-Paul Laumond

  3. Electrical and Computer Engineering, University of Illinois, Urbana, IL, USA

    Seth Hutchinson

Authors
  1. Rafael Murrieta-Cid
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ubaldo Ruiz
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jose Luis Marroquin
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jean-Paul Laumond
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Seth Hutchinson
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rafael Murrieta-Cid.

Additional information

A preliminary version of portions of this work appeared in Murrieta-Cid et al., Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems 2005.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Murrieta-Cid, R., Ruiz, U., Marroquin, J.L. et al. Tracking an omnidirectional evader with a differential drive robot. Auton Robot 31, 345–366 (2011). https://doi.org/10.1007/s10514-011-9246-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10514-011-9246-z

Keywords

Search

Navigation