Difference between revisions of "Pursuit Evasion"
(8 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
− | A Sensor | + | A Robotic Sensor Network (RSN) is a network of devices equipped with sensing, communication, actuation (e.g.: mobility) and computation capabilities. Many RSN automation tasks, such as surveillance and tracking, can be modeled as pursuit-evasion games. In a pursuit-evasion game, one or more pursuers try to capture an evader who, in turn, tries to avoid capture. This project will develop a theory of pursuit-evasion games taking place in complex environments among complex systems. |
==Motivation== | ==Motivation== | ||
− | Pursuit strategies to be developed as a part of this project will provide robust solutions for a number of | + | Pursuit strategies to be developed as a part of this project will provide robust solutions for a number of tasks in emergency response, search and rescue, energy and environmental monitoring, and health care automation. In particular, their utility will be demonstrated on a prototype system for monitoring the elderly. More broadly, the results of this project will participate in the formation of the next generation of automation technologies by advancing the state-of-the-art in distributed sensing and decision making. |
==Goals== | ==Goals== | ||
− | Pursuit-evasion games among complex systems are computationally hard in their most general form. Hence, we focus on instances that model | + | Pursuit-evasion games among complex systems are computationally hard in their most general form. Hence, we focus on instances that model RSN automation tasks. Specifically, this project involves |
# the investigation of the effect of information available to the players on the outcome of pursuit-evasion games, | # the investigation of the effect of information available to the players on the outcome of pursuit-evasion games, | ||
# the development of distributed pursuit strategies which efficiently reason about various forms of uncertainty, and | # the development of distributed pursuit strategies which efficiently reason about various forms of uncertainty, and | ||
Line 17: | Line 17: | ||
==Contributions== | ==Contributions== | ||
− | Our | + | We have recently published a [http://www-users.cs.umn.edu/~isler/pub/pe-survey.pdf survey paper] on search and pursuit-evasion in robotics and a [http://www.cs.umn.edu/sites/cs.umn.edu/files/tech_reports/15-013.pdf toolkit] based on our recent work. |
+ | Our contributions so far can be summarized as follows: | ||
* We started with a game that takes place on a graph. The players have only local visibility. We show that two pursuers can capture the evader on any graph (with high probability). We also present an algorithm which recognizes graphs on which a single pursuer suffices. [http://www.cs.rpi.edu/%7Eisler/new/pub/pubs/isler04sidma.pdf] | * We started with a game that takes place on a graph. The players have only local visibility. We show that two pursuers can capture the evader on any graph (with high probability). We also present an algorithm which recognizes graphs on which a single pursuer suffices. [http://www.cs.rpi.edu/%7Eisler/new/pub/pubs/isler04sidma.pdf] | ||
Line 24: | Line 25: | ||
* We have also studied a pursuit-evasion game where the players' motions are restricted to a roadmap. [http://www.cs.rpi.edu/%7Eisler/new/pub/pubs/isler-rss05.pdf] | * We have also studied a pursuit-evasion game where the players' motions are restricted to a roadmap. [http://www.cs.rpi.edu/%7Eisler/new/pub/pubs/isler-rss05.pdf] | ||
− | + | Our recent contributions can be summarized as follows: | |
+ | * Robotic Routers - The task of a network of robotic routers maintaining the connectivity of a mobile user with a base station is formulated as a pursuit-evasion game, in which the user is an adversary trying to break connection. The resulting robotic router strategy guarantees connectivity to any user (adversarial or otherwise) for the maximum duration of time possible. | ||
+ | :* O. Tekdas, W. Yang, and V. Isler. '''Robotic Routers: Algorithms and Implementation.''' ''Int. Journal of Robotics Research'', 2009. Note: Accepted. | ||
+ | ::[http://www.cs.umn.edu/~isler/pub/ijrr2008RoboticRouters.pdf pdf] [http://www-users.cs.umn.edu/~isler/pub/Year/2009.complete.html#tekdas09routers bibTeX] | ||
+ | |||
+ | * Lion and Man game - In the original Lion-and-Man game, a lion tries to catch a man (with equal maximum speed) while the man simultaneously tries to avoid capture. We study variants of this game relevant to applications where mobile robots have limited sensing capabilities. | ||
+ | :* First, we showed that the lion's pursuit strategy applies to simply-connected polygonal environments. | ||
+ | :: V. Isler, S. Kannan, and S. Khanna. '''Randomized Pursuit-Evasion in a Polygonal Environment.''' ''IEEE Transactions on Robotics'', 5(21):864--875, 2005. | ||
+ | :: [http://www.cs.umn.edu/~isler/pub/randpe-tro.pdf pdf] [http://www-users.cs.umn.edu/~isler/pub/Year/2005.complete.html#isler05tro bibTeX] | ||
+ | :* Then, we restricted the lion (pursuer) to have bearing-only sensing information about the man (evader) and presented a pursuit strategy that takes the lion to within a step-size distance of the man. It appears that exact capture is unlikely. | ||
+ | :: N. Karnad and V. Isler. '''Bearing-Only Pursuit.''' ''In Proc. IEEE Int. Conf. on Robotics and Automation'', 2008. Note: To appear. | ||
+ | :: [http://www.cs.umn.edu/~isler/pub/icra08pe.pdf pdf] [http://www-users.cs.umn.edu/~isler/pub/Year/2008.complete.html#karnad08icra bibTeX] | ||
+ | :* Next, we introduced a circular obstacle into the lion-and-man game played in a simply-connected polygon. The game was formulated as an optimal control problem, where the obstacle is expressed as a terminal condition. We derived optimal trajectories for the lion and the man, and, presented a decision algorithm that takes any initial condition as input and declares which player wins as the output (along with the winning strategy). | ||
+ | :: N. Karnad and V. Isler. '''Lion and Man Game in the Presence of a Circular Obstacle.''' ''In IEEE International Conference on Intelligent Robots and Systems (IROS)'', 2009. Note: To Appear. | ||
+ | :: [http://www.cs.umn.edu/~isler/pub/iros09pe.pdf pdf] [http://www-users.cs.umn.edu/~isler/pub/Year/2009.complete.html#nikhil09iros bibTeX] | ||
+ | :* Our most recent result shows that three pursuers can capture the evader in any polygon (possibly with holes) if they can see it at all times. | ||
+ | :: [http://www.cs.umn.edu/~isler/pub/ijcai11.pdf pdf][http://rsn.cs.umn.edu/index.php?title=All_Publications#bhadauria11ijcai bib]. The remaining question is then: when do two pursuers suffice? [http://arxiv.org/abs/1401.2960 Here] is a sufficient condition. | ||
+ | |||
+ | * We also studied the effect of reducing the pursuer's sensing range for a pursuit-evasion game played on a graph. | ||
+ | :: V. Isler and N. Karnad. '''The Role of Information in the Cop-Robber Game.''' ''Theoretical Computer Science'', 3(399):179--190, 2008. Note: Accepted to the Special Issue on Graph Searching. | ||
+ | :: [http://www.cs.umn.edu/~isler/pub/tcs07.pdf pdf] [http://www-users.cs.umn.edu/~isler/pub/Year/2008.complete.html#karnad08tcs bibTeX] | ||
==Videos== | ==Videos== | ||
Line 38: | Line 59: | ||
{{#ev:youtube|lRrac8Pi1bg}} | {{#ev:youtube|lRrac8Pi1bg}} | ||
</div> | </div> | ||
+ | |||
+ | == Publications on pursuit-evasion games == | ||
+ | |||
+ | <bibliography src="All_Publications" keywords="pursuit-evasion" /> | ||
+ | |||
---- | ---- | ||
This work is supported by the NSF grant [http://www.nsf.gov/awardsearch/showAward.do?AwardNumber=0634823 Pursuit-Evasion Games with Complex Systems in Complex Environments] | This work is supported by the NSF grant [http://www.nsf.gov/awardsearch/showAward.do?AwardNumber=0634823 Pursuit-Evasion Games with Complex Systems in Complex Environments] |
Latest revision as of 14:32, November 22, 2015
A Robotic Sensor Network (RSN) is a network of devices equipped with sensing, communication, actuation (e.g.: mobility) and computation capabilities. Many RSN automation tasks, such as surveillance and tracking, can be modeled as pursuit-evasion games. In a pursuit-evasion game, one or more pursuers try to capture an evader who, in turn, tries to avoid capture. This project will develop a theory of pursuit-evasion games taking place in complex environments among complex systems.
Motivation
Pursuit strategies to be developed as a part of this project will provide robust solutions for a number of tasks in emergency response, search and rescue, energy and environmental monitoring, and health care automation. In particular, their utility will be demonstrated on a prototype system for monitoring the elderly. More broadly, the results of this project will participate in the formation of the next generation of automation technologies by advancing the state-of-the-art in distributed sensing and decision making.
Goals
Pursuit-evasion games among complex systems are computationally hard in their most general form. Hence, we focus on instances that model RSN automation tasks. Specifically, this project involves
- the investigation of the effect of information available to the players on the outcome of pursuit-evasion games,
- the development of distributed pursuit strategies which efficiently reason about various forms of uncertainty, and
- the adaptation of these results to solve two ubiquitous sensor-actuator network automation tasks (tracking and surveillance) in a robust fashion.
Contributions
We have recently published a survey paper on search and pursuit-evasion in robotics and a toolkit based on our recent work. Our contributions so far can be summarized as follows:
- We started with a game that takes place on a graph. The players have only local visibility. We show that two pursuers can capture the evader on any graph (with high probability). We also present an algorithm which recognizes graphs on which a single pursuer suffices. [1]
- Next, we studied a version where the game takes place in a simply-connected polygon. The pursuers have only line-of-sight visibility. We showed that a single pursuer can locate the evader (which can be arbitrarily faster than the pursuer) in any simply connected polygon with high probability. This game is known as the "visibility based pursuit-evasion game". If the pursuers are as fast as the evader, we show that they can in fact capture the evader. [2] (An applet that demonstrates this strategy)
- We are currently working on designing pursuit-evasion strategies for more general systems. Recently, we have extended the pursuit strategy for finding the evader in a polygon to the case where the pursuer's motion is subject to polyhedral kinematic constraints. [3]
- We have also studied a pursuit-evasion game where the players' motions are restricted to a roadmap. [4]
Our recent contributions can be summarized as follows:
- Robotic Routers - The task of a network of robotic routers maintaining the connectivity of a mobile user with a base station is formulated as a pursuit-evasion game, in which the user is an adversary trying to break connection. The resulting robotic router strategy guarantees connectivity to any user (adversarial or otherwise) for the maximum duration of time possible.
- O. Tekdas, W. Yang, and V. Isler. Robotic Routers: Algorithms and Implementation. Int. Journal of Robotics Research, 2009. Note: Accepted.
- Lion and Man game - In the original Lion-and-Man game, a lion tries to catch a man (with equal maximum speed) while the man simultaneously tries to avoid capture. We study variants of this game relevant to applications where mobile robots have limited sensing capabilities.
- First, we showed that the lion's pursuit strategy applies to simply-connected polygonal environments.
- V. Isler, S. Kannan, and S. Khanna. Randomized Pursuit-Evasion in a Polygonal Environment. IEEE Transactions on Robotics, 5(21):864--875, 2005.
- pdf bibTeX
- Then, we restricted the lion (pursuer) to have bearing-only sensing information about the man (evader) and presented a pursuit strategy that takes the lion to within a step-size distance of the man. It appears that exact capture is unlikely.
- N. Karnad and V. Isler. Bearing-Only Pursuit. In Proc. IEEE Int. Conf. on Robotics and Automation, 2008. Note: To appear.
- pdf bibTeX
- Next, we introduced a circular obstacle into the lion-and-man game played in a simply-connected polygon. The game was formulated as an optimal control problem, where the obstacle is expressed as a terminal condition. We derived optimal trajectories for the lion and the man, and, presented a decision algorithm that takes any initial condition as input and declares which player wins as the output (along with the winning strategy).
- N. Karnad and V. Isler. Lion and Man Game in the Presence of a Circular Obstacle. In IEEE International Conference on Intelligent Robots and Systems (IROS), 2009. Note: To Appear.
- pdf bibTeX
- Our most recent result shows that three pursuers can capture the evader in any polygon (possibly with holes) if they can see it at all times.
- We also studied the effect of reducing the pursuer's sensing range for a pursuit-evasion game played on a graph.
Videos
- The role of information in pursuit evasion: Graph theoretic models, Applied Algebraic Topology Seminar, IMA, June 2009. Video available through IMA
- Pursuit-Evasion outreach: demonstration of a greedy pursuit strategy in an educational setting.
- Turn-based pursuit evasion with localization: mobile robots query a vision system to obtain their coordinates.
Publications on pursuit-evasion games
2016 | |
23 | U. Ruiz, V. Isler Capturing an Omnidirectional Evader in Convex Environments Using a Differential Drive Robot IEEE Robotics and Automation Letters, 1(2): 1007-1013, 2016. |
22 | N. Noori, A. Renzaglia, J. V. Hook, V. Isler Constrained Probabilistic Search for a One-Dimensional Random Walker IEEE Transactions on Robotics, 32(2): 261-274, 2016. |
21 | N. Noori, A. Beveridge, V. Isler Pursuit-Evasion: A Toolkit to Make Applications More Accessible Tutorial IEEE Robotics Automation Magazine, PP(99): 1-1, 2016. |
2015 | |
20 | Ubaldo Ruiz, Volkan Isler Capturing an Omnidirectional Evader in Convex Environments using a Differential Drive Robot CoRR, abs/1508.06333, 2015. |
2014 | |
19 | N. Noori, V. Isler Lion and Man Game on Polyhedral Surfaces with Boundary In IEEE Conference on Intelligent Robots and Systems (IROS), 2014. pdf,.bib |
18 | J. Vander Hook, V. Isler Pursuit and Evasion with Uncertain Bearing Measurements In Proc. 2014 Canadian Conference on Computational Geometry, 2014. pdf,.bib |
17 | N. Noori, V. Isler Lion and Man Game on Convex Terrains In Workshop on the Algorithmic Foundations of Robotics (WAFR), 2014. pdf,.bib |
2012 | |
16 | D. Bhadauria, K. Klein, V. Isler, S. Suri Capturing an Evader in Polygonal Environments with Obstacles: The Full Visibility Case International Journal of Robotics Research, 2012. pdf,.bib |
15 | N. Noori, V. Isler Lion and Man with Visibility in Monotone Polygons In Workshop on the Algorithmic Foundations of Robotics (WAFR), 2012. pdf,.bib |
2011 | |
14 | T. Chung, G. Hollinger, V. Isler Search and pursuit-evasion in mobile robotics Autonomous Robots(3), 2011. pdf,prelim.version,.bib |
13 | D. Bhadauria, V. Isler Capturing an Evader in a Polygonal Environment with Obstacles In 22nd International Joint Conference on Artificial Intelligence, 2011. pdf,.bib |
2010 | |
12 | O. Tekdas, W. Yang, V. Isler Robotic Routers: Algorithms and Implementation Int. Journal of Robotics Research, 29(1), 2010. pdf,.bib |
2009 | |
11 | N. Karnad, V. Isler Lion and Man Game in the Presence of a Circular Obstacle In IEEE International Conference on Intelligent Robots and Systems (IROS), 2009. pdf,.bib |
2008 | |
10 | V. Isler, N. Karnad The Role of Information in the Cop-Robber Game Theoretical Computer Science, 3(399): 179--190, 2008. pdf,.bib |
9 | N. Karnad, V. Isler Bearing-Only Pursuit In Proc. IEEE Int. Conf. on Robotics and Automation, 2008. pdf,.bib |
2006 | |
8 | V. Isler, S. Kannan, S. Khanna Randomized Pursuit-Evasion with Local Visibility SIAM Journal on Discrete Mathematics, 1(20): 26--41, 2006. pdf,.bib |
2005 | |
7 | C. Belta, V. Isler, G. J. Pappas Discrete Abstractions for Robot Motion Planning and Control in Polygonal Environments IEEE Transactions on Robotics, 5(21): 864--875, 2005. pdf,.bib |
6 | V. Isler, S. Kannan, S. Khanna Randomized Pursuit-Evasion in a Polygonal Environment IEEE Transactions on Robotics, 5(21): 864--875, 2005. pdf,.bib |
5 | V. Isler, D. Sun, S. Sastry Roadmap Based Pursuit-Evasion and Collision Avoidance In Robotics: Science and Systems, 2005. pdf,.bib |
2004 | |
4 | V. Isler, S. Kannan, S. Khanna Randomized Pursuit-Evasion with Limited Visibility In ACM-SIAM Symposium on Discrete Algorithms, 2004. pdf,.bib |
3 | V. Isler, K. Daniilidis, G.J. Pappas, C. Belta Hybrid Control for Visibility-Based Pursuit-Evasion Games In IEEE/RSJ International Conference on Intelligent Robots and Systems, 2004. pdf,.bib |
2 | V. Isler, S. Kannan, S. Khanna Locating and Capturing an Evader in a Polygonal Environment In Sixth International Workshop on the Algorithmic Foundations of Robotics, 2004. pdf,.bib |
1 | V. Isler Algorithms for Distributed and Mobile Sensing PhD Thesis, Department of Computer and Information Science, University of Pennsylvania, 2004. pdf,.bib |
This work is supported by the NSF grant Pursuit-Evasion Games with Complex Systems in Complex Environments