Abstract
The optimal search path (OSP) problem is a single-sided detection search problem where the location and the detectability of a moving object are uncertain. A solution to this \(\mathcal{NP}\)-hard problem is a path on a graph that maximizes the probability of finding an object that moves according to a known motion model. We developed constraint programming models to solve this probabilistic path planning problem for a single indivisible searcher. These models include a simple but powerful branching heuristic as well as strong filtering constraints. We present our experimentation and compare our results with existing results in the literature. The OSP problem is particularly interesting in that it generalizes to various probabilistic search problems such as intruder detection, malicious code identification, search and rescue, and surveillance.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview 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)
Stone, L.: Theory of Optimal Search. Academic Press, New York (2004)
Kranakis, E., Krizanc, D., Rajsbaum, S.: Computing with mobile agents in distributed networks. In: Rajasedaran, S., Reif, J. (eds.) Handbook of Parallel Computing: Models, Algorithms, and Applications, pp. 1–26. CRC Press (2007)
Chandramouli, R.: Web search steganalysis: Some challenges and approaches. In: Proceedings of IEEE International Symposium on Circuits and Systems, pp. 576–579 (2004)
Verkama, M.: Optimal paging - a search theory approach. In: Proceedings of the International Conference on Universal Personal Communications, pp. 956–960 (1996)
Stewart, T.: Search for a moving target when the searcher motion is restricted. Computers and Operations Research 6, 129–140 (1979)
Eagle, J.: The optimal search for a moving target when the search path is constrained. Operations Research 32(5), 1107–1115 (1984)
Eagle, J., Yee, J.: An optimal branch-and-bound procedure for the constrained path, moving target search problem. Naval Research Logistics 38(1), 110–114 (1990)
Washburn, A.: Branch and bound methods for a search problem. Naval Research Logistics 45, 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)
Martins, G.: A new branch-and-bound procedure for computing optimal search paths. Tech. rep., Naval Postgraduate School (1993)
Abi-Zeid, I., Nilo, O., Lamontagne, L.: Resource allocation algorithms for planning search and rescue operations. INFOR 49(1), 15–30 (2011)
Brown, K.M., Miguel, I.: Uncertainty and change. In: Rossi, F., Beek, P.V., Walsh, T. (eds.) Handbook of Constraint Programming, pp. 44–58. Springer (2006)
Tarim, S., Manandhar, S., Walsh, T.: Stochastic constraint programming: A scenario-based approach. Constraints 11(1), 53–80 (2006)
Brown, S.: Optimal search for a moving target in discrete time and space. Operations Research 28(6), 1275–1289 (1980)
Verfaillie, G., Jussien, N.: Constraint solving in uncertain and dynamic environments: A survey. Constraints 10, 253–281 (2005)
Nowakowski, R., Winkler, P.: Vertex-to-vertex pursuit in a graph. Discrete Mathematics 43(2-3), 235–239 (1983)
Laburthe, F., Jussien, N.: Choco Solver Documentation (2012), http://www.emn.fr/z-info/choco-solver/
O’Madadhain, J., Fisher, D., Nelson, T., White, S., Boey, Y.: Jung: Java universal network/graph framework (2010), http://jung.sourceforge.net
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Morin, M., Papillon, AP., Abi-Zeid, I., Laviolette, F., Quimper, CG. (2012). Constraint Programming for Path Planning with Uncertainty. In: Milano, M. (eds) Principles and Practice of Constraint Programming. CP 2012. Lecture Notes in Computer Science, vol 7514. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33558-7_70
Download citation
DOI: https://doi.org/10.1007/978-3-642-33558-7_70
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33557-0
Online ISBN: 978-3-642-33558-7
eBook Packages: Computer ScienceComputer Science (R0)