Probabilistic Strategies for Pursuit in Cluttered Environments with Multiple Robots
- 1 April 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (cat. No.01ch37164)
- No. 10504729,p. 3870-3876
Abstract
In this paper, we describe a method for coordinating multiple robots in a pursuit-evasion domain. We examine the problem of multiple robotic pursuers attempting to locate a non-adversarial mobile evader in an indoor environment. Unlike many other approaches to this problem, our method seeks to minimize expected time of capture rather than guaranteeing capture. This allows us to examine the performance of our algorithm in complex and cluttered environments where guaranteed capture is difficult or impossible with limited pursuers. We present a probabilistic formulation of the problem, discretize the environment, and define cost heuristics for use in planning. We then propose a scalable algorithm using an entropy cost heuristic that searches possible movement paths to determine coordination strategies for the robotic pursuers. We present simulated results describing the performance of our algorithm against state of the art alternatives in a complex office environment. Our algorithm successfully reduces capture time with limited pursuers in an environment beyond the scope of many other approaches.Keywords
This publication has 13 references indexed in Scilit:
- Preliminary Results in Tracking Mobile Targets Using Range Sensors from Multiple Robots2007
- Gaussian Processes for Signal Strength-Based Location Estimation2006
- Visibility-based Pursuit-evasion with Limited Field of ViewThe International Journal of Robotics Research, 2006
- A Multi-robot Strategy for Rapidly Searching a Polygonal EnvironmentLecture Notes in Computer Science, 2004
- Randomized Pursuit-Evasion in GraphsCombinatorics, Probability and Computing, 2003
- Finding an unpredictable target in a workspace with obstacles2002
- A VISIBILITY-BASED PURSUIT-EVASION PROBLEMInternational Journal of Computational Geometry & Applications, 1999
- Planning and acting in partially observable stochastic domainsArtificial Intelligence, 1998
- Pursuit-evasion in a graph1978
- Optimal Pursuit Strategies in Discrete-State Probabilistic SystemsJournal of Basic Engineering, 1962