×

Discounted MEAN bound for the optimal searcher path problem with non-uniform travel times. (English) Zbl 1146.90368

Summary: We consider an extension of the optimal searcher path problem (OSP), where a searcher moving through a discretised environment may now need to spend a non-uniform amount of time travelling from one region to another before being able to search it for the presence of a moving target. In constraining not only where but when the search of each cell can take place, the problem more appropriately models the search of environments which cannot be easily partitioned into equally sized cells. An existing OSP bounding method in literature, the MEAN bound, is generalised to provide bounds for solving the new problem in a branch and bound framework. The main contribution of this paper is an enhancement, discounted MEAN (DMEAN), which greatly tightens the bound for the new and existing problems alike with almost no additional computation. We test the new algorithm against existing OSP bounding methods and show it leads to faster solution times for moving target search problems.

MSC:

90B20 Traffic problems in operations research
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Brown, S. S., Optimal search for a moving target in discrete time and space, Operations Research, 28, 1275-1289 (1980) · Zbl 0447.90046
[2] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (1990), The MIT Press: The MIT Press Cambridge, MA · Zbl 1158.68538
[3] Dambreville, F.; Le Cadre, J.-P., Detection of a Markovian target with optimization of the search efforts under generalized linear constraints, Naval Research Logistics, 49/2, 117-142 (2002) · Zbl 0992.90036
[4] DasGupta, B.; Hespanha, J. P.; Riehl, J.; Sontag, E., Honey-pot constrained searching with local sensory information, Journal of Nonlinear Analysis: Hybrid Systems and Applications, 65/1, 1773-1793 (2006) · Zbl 1138.90402
[5] Dell, R. F.; Eagle, J. N.; Martins, G. H.A.; Santos, A. G., Using multiple searchers in constrained-path, moving-target search problems, Naval Research Logistics, 43, 463-480 (1996) · Zbl 0846.90060
[6] Eagle, J. N.; Yee, J. R., An optimal branch and bound procedure for the constrained path, moving target search problem, Operations Research, 38/1, 110-114 (1990) · Zbl 0719.90042
[7] Hohzaki, R.; Iida, K., Optimal strategy of route and look for the path constrained search problem with reward criterion, European Journal of Operational Research, 100, 236-249 (1997) · Zbl 0947.90594
[8] Kierstead, D. P.; DelBalzo, D. R., A genetic algorithm applied to planning search paths in complicated environments, Military Operations Research 8/2, 45-59 (2003)
[9] Lau, H., Huang, S., Dissanayake, G., 2005. Optimal search for multiple targets in a built environment. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS’05), Edmonton, Canada, pp. 3740-3745.; Lau, H., Huang, S., Dissanayake, G., 2005. Optimal search for multiple targets in a built environment. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS’05), Edmonton, Canada, pp. 3740-3745.
[10] Lau, H., Huang, S., Dissanayake, G., 2006. Probabilistic search for a moving target in an indoor environment. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS’06), Beijing, China, pp. 3393-3398.; Lau, H., Huang, S., Dissanayake, G., 2006. Probabilistic search for a moving target in an indoor environment. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS’06), Beijing, China, pp. 3393-3398.
[11] Lau, H., Huang, S., Dissanayake, G., 2007. Multi-agent search with interim positive information. To appear in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS’07), San Diego, USA.; Lau, H., Huang, S., Dissanayake, G., 2007. Multi-agent search with interim positive information. To appear in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS’07), San Diego, USA.
[12] Lössner, U.; Wegener, I., Discrete sequential search with positive switch cost, Mathematics of Operations Research 7/3, 426-440 (1982) · Zbl 0498.90047
[13] Martins, G., 1993. A new branch-and-bound procedure for computing optimal search paths. Master’s Thesis, Naval Postgraduate School.; Martins, G., 1993. A new branch-and-bound procedure for computing optimal search paths. Master’s Thesis, Naval Postgraduate School.
[14] Moors, M., Schulz, D., Improved Markov models for indoor surveillance. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS’06), Beijing, China, pp. 3393-3398.; Moors, M., Schulz, D., Improved Markov models for indoor surveillance. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS’06), Beijing, China, pp. 3393-3398.
[15] Stewart, T. J., Search for a moving target when searcher motion is restricted, Computers and Operations Research, 6, 129-140 (1979)
[16] Thomas, L. C.; Eagle, J. N., Criteria and approximate methods for path-constrained moving-target search problems, Naval Research Logistics, 42, 27-38 (1995) · Zbl 0822.90149
[17] Trummel, K. E.; Weisinger, J. R., The complexity of the optimal searcher path problem, Operations Research, 34/2, 324-327 (1986) · Zbl 0615.90072
[18] Washburn, A.R., 1995. Branch and bound methods for search problems. Technical Report, NPS-OR-95-003, Naval Postgraduate School, Monterey, CA (April).; Washburn, A.R., 1995. Branch and bound methods for search problems. Technical Report, NPS-OR-95-003, Naval Postgraduate School, Monterey, CA (April).
[19] Washburn, A. R., Branch and bound methods for a search problem, Naval Research Logistics, 45, 243-257 (1998) · Zbl 0927.90058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.