Visibility and Pursuit-Evasion
Visibility problems arise in many fields, including robotics,
computer graphics, security, architecture, computer vision, virtual
reality, and wireless communications. The key component is to
determine whether pairs of points can "see" each other, or are
blocked by an obstacle. A variety of visibilty algorithms have been
studied, mainly in the area of computational geometry;
see this
book by Ghosh.
We have worked on many visibility problems for over two decades.
Most of the work has to do with pursuit-evasion (or hide-and-seek)
problems, in which one or more robots with cameras must
systematically search a complicated environment for a moving target
that is trying to elude discovery.
Our first paper on the subject a
complete algorithm that computes how a robot with a panoramic camera
should precisely move to correctly solve the problem. Most of the
papers here address finding or tracking of moving targets in
complicated environments. These papers involve keeping tracking of
information states that represent the status of the pursuit, and are
encdoded as a single bit associated with connected component of the
environment that is not currently visible. The highest level of
generality appears in this paper,
in which the bits are extended to a vectors of upper and lower
bounds on the numbers of various classes of targets.
Papers on Visibility and Pursuit-Evasion
Equivalent environments and covering spaces for robots. V. Weinstein and S. M. LaValle. In M. Farber and J. Gonzalez, editors, Topology, Geometry and AI. EMS Series in Industrial and Applied Mathematics, 2024. In press, [pdf].
Visibility-inspired models of touch sensors for navigation. K. Tiwari, B. Sakcak, P. Routray, Manivannan M., and S. M. LaValle. In IEEE/RSJ International Conference on Intelligent Robots and Systems, 2022. [pdf].
A visibility-based approach to computing nondeterministic bouncing strategies. A. Q. Nilles, Y. Ren, I. Becerra, and S. M. LaValle. In Proc. Workshop on the Algorithmic Foundations of Robotics, 2018. [pdf].
Navigation among visually connected sets of partially distinguishable landmarks. L. Erickson and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2012. [pdf].
Optimal gap navigation for a disc robot. R. Lopez-Padilla, R. Murrieta-Cid, and S. M. LaValle. In Proc. Workshop on the Algorithmic Foundations of Robotics, 2012. [pdf].
Shadow information spaces: Combinatorial filters for tracking targets. J. Yu and S. M. LaValle. IEEE Transactions on Robotics, 28(2):440-456, 2012. [pdf].
How many landmark colors are needed to avoid confusion in a polygon?. L. Erickson and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2011. [pdf].
An art gallery approach to ensuring that landmarks are distinguishable. L. Erickson and S. M. LaValle. In Proceedings Robotics: Science and Systems, 2011. [pdf].
Mapping and pursuit-evasion strategies for a simple wall-following robot. M. Katsev, A. Yershova, B. Tovar, R. Ghrist, and S. M. LaValle. IEEE Transactions on Robotics, 27(1):113-128, 2011. [pdf].
Sensor lattices: A preimage-based approach to comparing sensors. S. M. LaValle. September 2011. Department of Computer Science, University of Illinois, [pdf].
Probabilistic shadow information spaces. J. Yu and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2010. [pdf].
Filtering and planning in information spaces. S. M. LaValle. Technical report, Department of Computer Science, University of Illinois, October 2009. [pdf].
Clearing a polygon with two 1-searchers. B. Simov, G. Slutzki, and S. M. LaValle. International Journal of Computational Geometry and Applications, 19(1), 2009. [pdf].
Sensor beams, obstacles, and possible paths. B. Tovar, F. Cohen, and S. M. LaValle. In Proceedings Workshop on Algorithmic Foundations of Robotics (WAFR), 2008. [pdf].
Rendezvous without coordinates. J. Yu, D. Liberzon, and S. M. LaValle. In Proceedings IEEE Conference Decision and Control, pages 1803-1808, 2008. [pdf].
Tracking hidden agents through shadow information spaces. J. Yu and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, 2008. [pdf].
Using a robot to learn geometric information from permutations of landmarks. B. Tovar, L. Freda, and S. M. LaValle. In Contemporary Mathematics, volume 438, pages 33-45. American Mathematical Society, 2007. [pdf].
Distance-optimal navigation in an unknown environment without sensing distances. B. Tovar, R Murrieta-Cid, and S. M. LaValle. IEEE Transactions on Robotics, 23(3):506-518, June 2007. [pdf].
Learning combinatorial information from alignments of landmarks. L. Freda, B. Tovar, and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, 2007. [pdf].
Mapping and navigation from permutations of landmarks. B. Tovar, L. Freda, and S. M. LaValle. Technical report, Department of Computer Science, University of Illinois, June 2006. [pdf].
Visibility-based pursuit-evasion with bounded speed. B. Tovar and S. M. LaValle. In Proceedings Workshop on Algorithmic Foundations of Robotics, 2006. [pdf].
Chapter 12: Planning Under Sensing Uncertainty, Planning Algorithms. S. M. LaValle. Cambridge University Press, Cambridge, U.K., 2006. [pdf] [Entire Book].
Information spaces for mobile robots. B. Tovar, A. Yershova, J. M. O'Kane, and S. M. LaValle. In Proceedings International Workshop on Robot Motion and Control (RoMoCo 2005), 2005. [pdf].
Bitbots: Simple robots solving complex tasks. A. Yershova, B. Tovar, R. Ghrist, and S. M. LaValle. In Proceedings AAAI National Conference on Artificial Intelligence, 2005. [pdf].
Pursuit-evasion in an unknown environment using gap navigation trees. L. Guilamo, B. Tovar, and S. M. LaValle. In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2004. [pdf].
Visibility-based pursuit-evasion in an unknown planar environment. S. Sachs, S. Rajko, and S. M. LaValle. International Journal of Robotics Research, 23(1):3-26, January 2004. [pdf].
Gap navigation trees: A minimal representation for visibility-based tasks. B. Tovar, L. Guilamo, and S. M. LaValle. In M. Erdmann, D. Hsu, M. Overmars, and A. F. van der Stappen, editors, Algorithmic Foundations of Robotics, VI. Springer-Verlag, Berlin, 2005. [pdf].
Locally-optimal navigation in multiply-connected environments without geometric maps. B. Tovar, S. M. LaValle, and R. Murrieta-Cid. In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003. [pdf].
Optimal navigation and object finding without geometric maps or localization. B. Tovar, S. M. LaValle, and R. Murrieta-Cid. In Proceedings IEEE International Conference on Robotics and Automation, pages 464-470, 2003. [pdf].
An algorithm for searching a polygonal region with a flashlight. S. M. LaValle, B. Simov, and G. Slutzki. International Journal of Computational Geometry and Applications, 12(1-2):87-113, 2002. [pdf].
A complete pursuit-evasion algorithm for two pursuers using beam detection. B. Simov, S. M. LaValle, and G. Slutzki. In Proceedings IEEE International Conference on Robotics and Automation, pages 618-623, 2002. [pdf].
Visibility-based pursuit-evasion: The case of curved environments. S. M. LaValle and J. Hinrichsen. IEEE Transactions on Robotics and Automation, 17(2):196-201, April 2001. [pdf].
A pursuit-evasion bug algorithm. S. Rajko and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, pages 1954-1960, 2001. [pdf].
Robot motion planning: A game-theoretic foundation. S. M. LaValle. Algorithmica, 26(3):430-465, 2000. [pdf].
An algorithm for searching a polygonal region with a flashlight. S. M. LaValle, B. Simov, and G. Slutzki. In Proceedings ACM Annual Symposium on Computational Geometry, 2000. [pdf].
Pursuit-evasion using beam detection. B. Simov, G. Slutzki, and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, 2000. [pdf].
Visibility-based pursuit-evasion in a polygonal environment. L. J. Guibas, J.-C. Latombe, S. M. LaValle, D. Lin, and R. Motwani. International Journal of Computational Geometry and Applications, 9(5):471-494, 1999. [pdf].
Visibility-based pursuit-evasion: An extension to curved environments. S. M. LaValle and J. Hinrichsen. In Proceedings IEEE International Conference on Robotics and Automation, pages 1677-1682, 1999. [pdf].
Visibility-based pursuit-evasion in a polygonal environment. L. J. Guibas, J.-C. Latombe, S. M. LaValle, D. Lin, and R. Motwani. In F. Dehne, A. Rau-Chaplin, J.-R. Sack, and R. Tamassia, editors, WADS '97 Algorithms and Data Structures (Lecture Notes in Computer Science, 1272), pages 17-30. Springer-Verlag, Berlin, 1997. [pdf].
Motion strategies for maintaining visibility of a moving target. S. M. LaValle, H. H. Gonz\'alez-Ba\ nos, C. Becker, and J.-C. Latombe. In Proceedings IEEE International Conference on Robotics and Automation, pages 731-736, 1997. [pdf].
Finding an unpredictable target in a workspace with obstacles. S. M. LaValle, D. Lin, L. J. Guibas, J.-C. Latombe, and R. Motwani. In Proceedings IEEE International Conference on Robotics and Automation, pages 737-742, 1997. [pdf].