Abstract
In search theory, the goal of the Optimal Search Path (OSP) problem is to find a finite length path maximizing the probability that a searcher detects a lost wanderer on a graph. We propose to bound the probability of finding the wanderer in the remaining search time by relaxing the problem into a stochastic game of cop and robber from graph theory. We discuss the validity of this bound and demonstrate its effectiveness on a constraint programming model of the problem. Experimental results show how our novel bound compares favorably to the DMEAN bound from the literature, a state-of-the-art bound based on a relaxation of the OSP into a longest path problem.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Trummel, K., Weisinger, J.: The complexity of the optimal searcher path problem. Operations Research 34(2), 324–327 (1986)
Stewart, T.: Search for a moving target when the searcher motion is restricted. Computers and Operations Research 6(3), 129–140 (1979)
Stone, L.: Theory of Optimal Search. Academic Press, New York (2004)
Netsch, R.: The USCG search and rescue optimal planning system (SAROPS) via the commercial/joint mapping tool kit (c/jmtk). In: Proceedings of the 24th Annual ESRI User Conference, vol. 9, August 2004
Abi-Zeid, I., Frost, J.: A decision support system for canadian search and rescue operations. European Journal of Operational Research 162(3), 636–653 (2005)
Washburn, A.R.: Branch and bound methods for a search problem. Naval Research Logistics 45(3), 243–257 (1998)
Lau, H., Huang, S., Dissanayake, G.: Discounted MEAN bound for the optimal searcher path problem with non-uniform travel times. European Journal of Operational Research 190(2), 383–397 (2008)
Morin, M., Lamontagne, L., Abi-Zeid, I., Lang, P., Maupin, P.: The optimal searcher path problem with a visibility criterion in discrete time and space. In: Proceedings of the 12th International Conference on Information Fusion, pp. 2217–2224 (2009)
Sato, H., Royset, J.O.: Path optimization for the resource-constrained searcher. Naval Research Logistics, 422–440 (2010)
Morin, M., Papillon, A.-P., Abi-Zeid, I., Laviolette, F., Quimper, C.-G.: Constraint programming for path planning with uncertainty. In: Milano, M. (ed.) CP 2012. LNCS, vol. 7514, pp. 988–1003. Springer, Heidelberg (2012)
Nowakowski, R., Winkler, P.: Vertex-to-vertex pursuit in a graph. Discrete Mathematics 43(2), 235–239 (1983)
Quilliot, A.: Problème de jeux, de point fixe, de connectivité et de représentation sur des graphes, des ensembles ordonnés et des hypergraphes. Ph.D thesis, Université de Paris VI (1983)
Bonato, A., Nowakowski, R.: The game of cops and robbers on graphs. American Mathematical Soc. (2011)
Fomin, F.V., Thilikos, D.M.: An annotated bibliography on guaranteed graph searching. Theoretical Computer Science 399(3), 236–245 (2008)
Beldiceanu, N., Demassey, S.: Global constraint catalog (2014). http://sofdem.github.io/gccat/ (accessed 2015–04)
Martins, G.H.: A new branch-and-bound procedure for computing optimal search paths. Master’s thesis, Naval Postgraduate School (1993)
Kehagias, A., Mitsche, D., Prałat, P.: Cops and invisible robbers: The cost of drunkenness. Theoretical Computer Science 481, 100–120 (2013)
Kehagias, A., Prałat, P.: Some remarks on cops and drunk robbers. Theoretical Computer Science 463, 133–147 (2012)
Komarov, N., Winkler, P.: Capturing the Drunk Robber on a Graph. arXiv preprint arXiv:1305.4559 (2013)
Bäuerle, N., Rieder, U.: Markov Decision Processes with Applications to Finance. Springer (2011)
Puterman, M.L.: Markov decision processes: discrete stochastic dynamic programming, vol. 414. John Wiley & Sons (2009)
Barto, A.G., Sutton, R.S.: Reinforcement learning: An introduction. MIT press (1998)
Laburthe, F., Jussien, N.: Choco solver documentation. École de Mines de Nantes (2012)
O’Madadhain, J., Fisher, D., Nelson, T., White, S., Boey, Y.B.: The JUNG (Java universal network/graph) framework (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Simard, F., Morin, M., Quimper, CG., Laviolette, F., Desharnais, J. (2015). Bounding an Optimal Search Path with a Game of Cop and Robber on Graphs. In: Pesant, G. (eds) Principles and Practice of Constraint Programming. CP 2015. Lecture Notes in Computer Science(), vol 9255. Springer, Cham. https://doi.org/10.1007/978-3-319-23219-5_29
Download citation
DOI: https://doi.org/10.1007/978-3-319-23219-5_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23218-8
Online ISBN: 978-3-319-23219-5
eBook Packages: Computer ScienceComputer Science (R0)