Search and pursuit-evasion in mobile robotics

Adler, M., Räcke, H., Sivadasan, N., Sohler, C., & Vöcking, B. (2003). Randomized pursuit-evasion in graphs. Combinatorics, Probability & Computing, 12(3), 225–244.

Aigner, M., & Fromme, M. (1984). A game of cops and robbers. Discrete Applied Mathematics, 8(1), 1–12.

Alexander, S., Bishop, R., & Ghrist, R. (2006). Pursuit and evasion in non-convex domains of arbitrary dimensions. In Proc. robotics: science and systems conference.

Alexander, S., Bishop, R., & Ghrist, R. (2009). Capture pursuit games on unbounded domains. L’Enseignement Mathématique, 55, 103–125.

Alonso, L., Goldstein, A. S., & Reingold, E. M. (1992). Lion and man: upper and lower bounds. INFORMS Journal on Computing, 4(4), 447.

Alspach, B. (2004). Searching and sweeping graphs: a brief survey. Matematiche, 59, 5–37.

Assaf, D., & Zamir, S. (1985). Optimal sequential search: a Bayesian approach. Annals of Statistics, 13(3), 1213–1221.

Barrière, L., Fraigniaud, P., Santoro, N., & Thilikos, D. (2003). Searching is not jumping, graph-theoretic concepts in computer. Science, 2880, 34–45.

Başar, T., & Olsder, G. J. (1999). Dynamic noncooperative game theory. Philadelphia: Society for Industrial Mathematics.

Benkoski, S. J., Monticino, M. G., & Weisinger, J. R. (1991). A survey of the search theory literature. Naval Research Logistics, 38(4), 469–494.

Bhadauria, D., & Isler, V. (2011). Capturing an evader in a polygonal environment with obstacles. In Proc. international joint conference on artificial intelligence.

Bhattacharya, S., & Hutchinson, S. (2010). On the existence of Nash equilibrium for a visibility based pursuit evasion game. The International Journal of Robotics Research, 29(7), 831–839.

Bienstock, D., & Seymour, P. D. (1991). Monotonicity in graph searching. Journal of Algorithms, 12(2), 239–245.

Bopardikar, S. D., Bullo, F., & Hespanha, J. P. (2007). Sensing limitations in the Lion and Man problem. In Proc. American control conference (pp. 5958–5963).

Borie, R., Tovey, C., & Koenig, S. (2009). Algorithms and complexity results for pursuit-evasion problems. In Proc. international joint conference on artificial intelligence (pp. 59–66).

Bourgault, F., Furukawa, T., & Durrant-Whyte, H. F. (2003). Coordinated decentralized search for a lost target in a Bayesian world. In Proc. IEEE/RSJ international conference on intelligent robots and systems (pp. 48–53).

Bourgault, F., Furukawa, T., & Durrant-Whyte, H. F. (2006). Optimal search for a lost target in a Bayesian world. Field and Service Robotics, 24, 209–222.

Chew, M. C. (1967). A sequential search procedure. Annals of Mathematical Statistics, 38(2), 494–502.

Chew, M. C., & Milton, C. (1973). Optimal stopping in a discrete search problem. Operations Research, 21(3), 741–747.

Dambreville, F., & Cadre, J. P. L. (2002). Search game for a moving target with dynamically generated informations. In Proc. international conference on information fusion (pp. 243–250).

Dobbie, J. M. (1968). A survey of search theory. Operations Research, 16(3), 525–537.

Dobbie, J. M. (1973). Some search problems with false contacts. Operations Research, 21(4), 907–925.

Eagle, J. N., & Yee, J. R. (1990). An optimal branch-and-bound procedure for the constrained path, moving target search problem. Operations Research, 38(1), 110–114.

Eaton, J., & Zadeh, L. (1962). Optimal pursuit strategies in discrete-state probabilistic systems. Journal of Basic Engineering, 84, 23–28.

Fomin, F. V., & Thilikos, D. M. (2008). An annotated bibliography on guaranteed graph searching. Theoretical Computer Science, 399(3), 236–245.

Gerkey, B., Thrun, S., & Gordon, G. (2005). Parallel stochastic hill-climbing with small teams. In Proc. international NRL workshop on multi-robot systems.

Goldstein, A. S., & Reingold, E. M. (1995). The complexity of pursuit on a graph. Theoretical Computer Science, 143(1), 93–112.

Goodrich, M., Morse, B., Gerhardt, D., Cooper, J., Quigley, M., Adams, J., & Humphrey, C. (2008). Supporting wilderness search using a camera-equipped UAV. Journal of Field Robotics, 25(1–2), 89–110.

Guibas, L., Latombe, J., LaValle, S., Lin, D., & Motwani, R. (1999). Visibility-based pursuit-evasion in a polygonal environment. International Journal of Computational Geometry and Applications, 9(5), 471–494.

Hespanha, J., Prandini, M., & Sastry, S. (2000). Probabilistic pursuit-evasion games: a one-step Nash approach. In Proc. IEEE conference on decision and control (pp. 2272–2277).

Hohzaki, R. (2007). Discrete search allocation game with false contacts. Naval Research Logistics, 54(1), 46–58.

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.

Hollinger, G., Kehagias, A., & Singh, S. (2010a). GSST: anytime guaranteed search. Autonomous Robots, 29(1), 99–118.

Hollinger, G., Kehagias, A., & Singh, S. (2010b). Improving the efficiency of clearing with multi-agent teams. The International Journal of Robotics Research, 29(8), 1088–1105.

Isler, V., & Karnad, N. (2008). The role of information in the cop-robber game. Theoretical Computer Science, 3(399), 179–190 Special issue on graph searching.

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

Isler, V., Kannan, S., & Khanna, S. (2006). Randomized pursuit-evasion with local visibility. SIAM Journal on Discrete Mathematics, 1(20), 26–41.

Jankovic, V. (1978). About a man and lions. Matematički Vesnik, 2, 359–361.

Kadane, J. (1971). Optimal whereabouts search. Operations Research, 19(4), 894–904.

Kalbaugh, D. (1992). Optimal search among false contacts. SIAM Journal on Applied Mathematics, 52(6), 1722–1750.

Karnad, N., & Isler, V. (2008). Bearing-only pursuit. In Proc. IEEE international conference on robotics and automation (pp. 2665–2670).

Katsilieris, F., Lindhé, M., Dimarogonas, D., Ögren, P., & Johansson, K. (2010). Demonstration of multi-robot search and secure. In Proc. ICRA workshop on search and pursuit/evasion.

Kimeldorf, G., & Smith, F. (1979). Binomial searching for a random number of multinomially hidden objects. Management Science, 25(11), 1115–1126.

Kolling, A., & Carpin, S. (2010). Pursuit-evasion on trees by robot teams. IEEE Transactions on Robotics, 26(1), 32–47.

Kolling, A., Kleiner, A., Lewis, M., & Sycara, K. (2010). Pursuit-evasion in 2.5D based on team-visibility. In Proc. IEEE/RSJ international conference on intelligent robots and systems (pp. 4610–4616).

Kolling, A., Kleiner, A., Lewis, M., & Sycara, K. (2011). Computing and executing strategies for moving target search. In Proc. IEEE international conference on robotics and automation (pp. 4246–423).

Koopman, B. O. (1956a). The theory of search. Part I. Kinematic bases. Operations Research, 4(5), 324–346.

Koopman, B. O. (1956b). The theory of search. Part II. Target detection. Operations Research, 4(5), 503–531.

Koopman, B. O. (1957). The theory of search. Part III. The optimum distribution of searching effort. Operations Research, 5(5), 613–626.

Koopman, B. O. (1979). Search and its optimization. The American Mathematical Monthly, 86(7), 527–540.

Kopparty, S., & Ravishankar, C. V. (2005). A framework for pursuit evasion games in Rn. Information Processing Letters, 96(3), 114–122.

Kress, M., Lin, K. Y., & Szechtman, R. (2008). Optimal discrete search with imperfect specificity. Mathematical Methods of Operations Research, 68(3), 539–549.

LaPaugh, A. S. (1993). Recontamination does not help to search a graph. Journal of the Association for Computing Machinery, 40(2), 224–245.

Lau, H., Huang, S., & Dissanayake, G. (2005). Optimal search for multiple targets in a built environment. In Proc. IEEE/RSJ international conference on intelligent robots and systems (pp. 3740–3745).

Lau, H., Huang, S., & Dissanayake, G. (2006). Probabilistic search for a moving target in an indoor environment. In Proc. IEEE/RSJ international conference on intelligent robots and systems (pp. 3393–3398).

LaValle, S. M. (2006). Planning algorithms. Cambridge: Cambridge University Press.

LaValle, S., Lin, D., Guibas, L., Latombe, J., & Motwani, R. (1997). Finding an unpredictable target in a workspace with obstacles. In Proc. IEEE international conference on robotics and automation (pp. 737–742).

Lazebnik, S. (2001). Visibility-based pursuit-evasion in three-dimensional environments. Technical report, CVR-TR-2001-01, Beckman Institute, University of Illinois at Urbana-Champaign.

Lenstra, J. K., & Kan, A. H. G. R. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(2), 221–227.

Littlewood, J. E. (1953). A mathematician’s miscellany. London: Methuen & Co.

McCue, B. (1990). U-boats in the bay of Biscay: an essay in operations analysis. National Defense University Press.

Megiddo, N., Hakimi, S., Garey, M., Johnson, D., & Papadimitriou, C. (1988). The complexity of searching a graph. Journal of the Association for Computing Machinery, 35(1), 18–44.

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.

Nowakowski, R., & Winkler, P. (1983). Vertex-to-vertex pursuit in a graph. Discrete Mathematics, 43(2–3), 235–239.

Ong, S. C. W., Png, S. W., Hsu, D., & Lee, W. S. (2010). Planning under uncertainty for robotic tasks with mixed observability. The International Journal of Robotics Research, 29(8), 1053–1068.

Park, S.-M., Lee, J.-H., & Chwa, K.-Y. (2001). Visibility-based pursuit-evasion in a polygonal region by a searcher. In Proc. international colloquium on automata, languages and programming (pp. 456–468).

Parsons, T. (1976). Pursuit-evasion in a graph. In Y. Alavi & D. Lick (Eds.), Theory and applications of graphs (pp. 426–441). Berlin: Springer.

Ross, S. M. (1969). A problem in optimal search and stop. Operations Research, 17(6), 984–992.

Roy, N., Gordon, G., & Thrun, S. (2005). Finding approximate POMDP solutions through belief compression. The Journal of Artificial Intelligence Research, 23, 1–40.

Sato, H., & Royset, J. O. (2010). Path optimization for the resource-constrained searcher. Naval Research Logistics, 57(5), 422–440.

Sgall, J. (2001). Solution of David Gale’s lion and man problem. Theoretical Computer Science, 259(1–2), 663–670.

Stone, L. D. (1989a). Theory of optimal search (2nd edn.). San Diego: Academic Press.

Stone, L. D. (1989b). What’s happened in search theory since the 1975 Lanchester prize? Operations Research, 37(3), 501–506.

Tisdale, J., Kim, Z., & Hedrick, J. K. (2009). Autonomous path planning and estimation using UAVs. IEEE Robotics & Automation Magazine, 16(2), 35–42.

Toth, P., & Vigo, D. (2002). The vehicle routing problem. Philadelphia: Society for Industrial Mathematics.

Trummel, K. E., & Weisinger, J. R. (1986). The complexity of the optimal searcher path problem. Operations Research, 34(2), 324–327.

Vidal, R., Shakernia, O., Kim, H. J., Shim, D. H., & Sastry, S. (2002). Probabilistic pursuit-evasion games: theory, implementation, and experimental evaluation. IEEE transactions on robotics and automation, 18(5), 662–669.

Vieira, M., Govindan, R., & Sukhatme, G. S. (2009). Scalable and practical pursuit-evasion with networked robots. Journal of Intelligent Service Robotics, 2(4), 247–263.

Wagner, D. H. (1999). Naval operations analysis. Annapolis: United States Naval Institute.

Washburn, A. R. (1983). Search for a moving target: the FAB algorithm. Operations Research, 31(4), 739–751.

Washburn, A. R. (1998). Branch and bound methods for a search problem. Naval Research Logistics, 45(3), 243–257.

Washburn, A. R. (2002). Search and detection. Topics in operations research series (4th edn.) INFORMS.

Wegener, I. (1985). Optimal search with positive switch cost is NP-hard. Information Processing Letters, 21(1), 49–52.

Wong, E.-M., Bourgault, F., & Furukawa, T. (2005). Multi-vehicle Bayesian search for multiple lost targets. In Proc. IEEE international conference on robotics and automation (pp. 3169–3174).