Принцип максимума энтропии в теории поиска

Aleksandr N. Prokaev

doi:10.21638/11701/spbu10.2023.103

Authors

Aleksandr N. Prokaev St. Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences, Hi Tech Research and Development Office, 39, 14-ya liniya V. O., St. Petersburg, 199178, Russian Federation https://orcid.org/0000-0002-9843-0417

DOI:

https://doi.org/10.21638/11701/spbu10.2023.103

Abstract

The paper considers the relationship between search theory and information theory. The traditional problem of search theory is to develop a search plan for a physical object in the sea or on land. The search plan has to develop the distribution of available search resources in such a way that the probability of detection the search object is to be maximum. The optimal solution is traditionally considered as so-called "uniformly optimal search plan", which provides a uniform distribution of the posterior probability of the location of the object as the search is conducted. At the same time, optimality simultaneously according to the criteria of maximum detection probability and equality of a posteriori probability is possible only for the exponential detection function, which is used most often in search theory. For other kinds of detection functions, the optimal solutions according to the specified criteria do not match. In this paper, the approach to this problem is considered on the basis of the maximum entropy principle. For a situation of discrete distribution, it is shown that, within the framework of information theory, the search problem has a simpler solution that does not depend on the kind of the detection function.

Keywords:

information theory, search theory, uniformly optimal search plan, detection function, maximum entropy principle

Downloads

Download data is not yet available.

References

Литература

Ackoff R. L., Sasieni M. W. Fundamentals of operations research. New York, USA: John Wiley & Sons, Inc., 1967. 455 p.

Mela D. F. Letter to the editor - information theory and search theory as special cases of decision theory // Operations Research. 1961. Vol. 9(6). P. 907-909.

Koopman B. O. Search and information theory // Part of final report on stochastic processes in certain naval operations. New York, USA: Columbia University, 1967. P. 126-134.

Barker W. H. Information theory and the optimal detection search // Operations Research. 1977. Vol. 25. N 2. P. 304-314.

Pierce J. G. A new look at the relation between information theory and search theory // The maximum entropy formalism. Cambridge, USA: MIT Press, 1978. P. 339-402.

Jaynes E. T. Entropy and search theory. Maximum-entropy and Bayesian methods in inverse problems. Fundamental theories of physics. Dordrecht, Netherlands: Springer, 1985. Vol. 14. P. 1-8.

Shannon C. E. A mathematical theory of communication // Bell System Techn. Journal. 1948. Vol. 27. N 4. P. 623-656.

Ahlswede R., Wegener I. Suchprobleme (Eng. Search Problems). Stuttgart, Germany: Teubner Verlag, 1979. 273 p.

Information theory, combinatorics, and search theory: in memory of Rudolf Ahlswede. Eds H. Aydinian, F. Cicalese, C. Deppe. Vol. 7777 of Lecture Notes in Computer Science. Cambrige: Springer, 2013. 773 p. https://doi.org/10.1007/978-3-642-36899-8

Stone L. D. Theory of optimal search. New York, USA: Academic Press, 1975. 260 p.

Stone L. D., Royset J. O., Washburn A. R. Optimal search for moving targets. Switzerland: Springer, 2016. 312 p. (International Series in Operations Research & Management Science, N 237). https://doi.org/10.1007/978-3-319-26899-6_1

Koopman B. O. Search and screening. Operations evaluation group report. Alexandria, USA: Center for Naval Analyses. 1946. Vol. 56. 176 p.

Koopman B. O. The theory of search. The optimum distribution of searching effort // Operations Research. 1957. Vol. 5. P. 613-626.

De Guenin J. Optimum distribution of effort: An extension of the Koopman basic theory // Operations Research. 1961. Vol. 9. P. 1-7.

References

Ackoff R. L., Sasieni M. W. Fundamentals of operations research. New York, John Wiley & Sons Inc. Publ., 1967, 455 p.

Mela D. F. Letter to the editor - information theory and search theory as special cases of decision theory. Operations Research, 1961, vol. 9(6), pp. 907-909.

Koopman B. O. Search and information theory. Part of final report on stochastic processes in certain naval operations. New York, Columbia University Press, 1967, pp. 126-134.

Barker W. H. Information theory and the optimal detection search. Operations Research, 1977, vol. 25, no. 2, pp. 304-314.

Pierce J. G. A new look at the relation between information theory and search theory. The maximum entropy formalism. Cambridge, MIT Press, 1978, pp. 339-402.

Jaynes E. T. Entropy and search theory. Maximum-entropy and Bayesian methods in inverse problems. Fundamental theories of Physics. Dordrecht, Springer Publ., 1985, vol. 14, pp. 1-18.

Shannon C. E. A mathematical theory of communication. Bell System Techn. Jornal, 1948, vol. 27, no. 4, pp. 623-656.

Ahlswede R., Wegener I. Suchprobleme [ Search problems ]. Stuttgart, Germany, Teubner Verlag Publ., 1979, 273 p.

Information theory, combinatorics, and search theory: in memory of Rudolf Ahlswede. Vol. 7777 of Lecture Notes in Computer Science. Eds H. Aydinian, F. Cicalese, C. Deppe. Cambrige, Springer Publ., 2013, 773 p. https://doi.org/10.1007/978-3-642-36899-8

Stone L. D. Theory of optimal search. New York, USA, Academic Press, 1975, 260 p.

Stone L. D., Royset J. O., Washburn A. R. Optimal search for moving targets. Switzerland, Springer Publ., 2016, 312 p. (International Series in Operations Research & Management Science, N 237). https://doi.org/10.1007/978-3-319-26899-6_1

Koopman B. O. Search and screening. Operations evaluation group report. Alexandria, Center for Naval Analyses Publ., 1946, vol. 56, 176 p.

Koopman B. O. The theory of search. The optimum distribution of searching effort. Operations Research, 1957, vol. 5, pp. 613-626.

De Guenin J. Optimum distribution of effort: An extension of the Koopman basic theory. Operations Research, 1961, vol. 9, pp. 1-7.