Некоторые модели поиска движущегося объекта. тема диссертации и автореферата по ВАК РФ 05.00.00, кандидат технических наук Новожилова, Лидия Михайловна

• Новожилова, Лидия Михайловна
• кандидат технических наук
• 1975

Оглавление диссертации кандидат технических наук Новожилова, Лидия Михайловна

Введение.

ГЛАВА I. Математические модели теории поиска. Обзор

§ I. Теория поиска-одна из основных моделей исследования операций

§ Степени развития математических моделей поиска

§ 3.Статические модели поиска

§ Динамические модели поиска неподвижного объекта . . . /

§ я.Динамические модели поиска движущегося объекта

§ б.Моделирование процесса поиска на ЦВМ

§ ?.Игровые постановки задач поиске.

Выводы.

ГЛАВА 2. Модели поиска движущегося объекта.Критерии оптимизации. Вероятность обнаружения объекта к заданному моменту времени.

§ I.Основная модель поиска движущегося объекта.Критерии оптимизаций.

§ 2.Развертка процесса поиска во времени

§ 3.Вероятность обнаружения объекта к заданному моменту

Бремени

§ ¿¡-.Рекуррентное соотношение для определения оптимальной стратегии поиска

§ Пример определения оптимальной стратегии для одной частной постановки задачи. ' '—'!—' ^

В ы В о 2 ы.'

ГЛАВА 3.Некоторые критерии оптимизации при неограниченной длительности поиска.

§ I.Вероятность обнаружения объекта

§ 2,Максимальная скорость сходимости вероятности обнаружения ?

§ 3.Минимум математического ожидания времени поиска,необходи мый для обнаружения объекта. У

§ 4.Пример определения оптимальной стратегии П. У

Выводы.

ГЛАВА 4-. Вероятность обнаружения движущегося объекта при бесконечной длительности поиска

§ I.Разложимость матрицы А.

§ 2.Вероятность обнаружения при максимальном собственном числе равном единице.

Выводы.¿

Введение диссертации (часть автореферата) на тему «Некоторые модели поиска движущегося объекта.»

Поиск с давних времен пронизывает различные области человеческой деятельности. Многие практические задачи поиска,такие как промысловые, заготовки сырь,з,разведки запасов месторождений полезных ископаемых ,были решены задолго до возникновения математических моделей. Они составили эмпирическую основу теории поиска.

Проблема создания математических моделей поиска возникла сравнительно недавно,в начале 40-х годов. Время возникновения этой пробле мы определилось,главным образом,взаимодействием двух факторов. Первый фактор-внутренняя логика развития эмпирической основы теорик подготовил процесс математизации поиска. Осуществление этого процес са было вызвано вторым фактором-потребностью современной науки,техники и материального производства в точных методах поиска,учитывающих специфику области приложения.

В химических исследованиях это связано с выделением специфических химических компонент / 3 /; в теории связи-с поиском и обнаружением сигналов /4/,/5/; в генетике-с изучением и управлением ростом и развитием популяций / 3 /; в математике-с поиском экстремумов функций / б /; / 7 /, /8/; в геологии-с поисками месторождений полезных ископаемых / 9 /. Разработка методов контроля качества продукции и устранения неисправностей,учет »хранение и поиск информации содержат в качестве составляющей задачу поиска. Существует,крои того,огромное число военных задач поиска сил и средств противника, представляющих собой потенциальную угрощу,например,самолетов в небе подводных лодок и корэблей в море,мин и артиллерийских установок не суше. При организации спасательных работ также встает задача поиске / 10 /. Таким образом,создание математических моделей поиска-это очередная ступень,которой достигло развитие теории поиска р на которую эта наука должна была подняться с тем,чтобы она вообще могла двигаться вперед.

Фсновные понятия теории поиска формируются в начале 40-х годов. Математические модели были впервые опубликованы Купманом в 194-6 году/2 /,и его имя до настоящего времени связывается с решением задач поиска в случае единовременных и ограниченных затрат не поиск. Интенсивный рост числа публикаций,начавшийся в 50-годы, способствовал накоплению большого числа научных результатов. Это, в свою очередь,привело к тому,что к нэчалу 60-х годов разрозненные задачи поиска начинают оформляться в научную теорию. У нас в страж в 1964 году появилась монография коллектива 8Еторов,посвященная поиску в Еоенном деле / I /. В|вей нашли отражение несколько аспектов новой научной теории - теории поиска:статический (совокупность выраженных в ней знаний)»индуктивно-динамический (обогащение теорш новыми положениями,полученными в результате непосредственного изучения действительности) и дедуктивно-динамический (обогащение теории положениями,получающимися в результате ее дедуктивного развития) .

I ходе дальнейшего развития математические модели поиска становятся более универсальными,происходит накопление новых знаний и обогащение теории новыми положениями. Теорию поиска можно рассматривать как сформировавшуюся научную теорию. Действительно,эта теория имеет глубокую эмпирическую основу. Теория поиска использует аппарат и модели математики и исследования операций. Эти науки составляют теоретическую основу и логику теории поиска. Совокупносч магматических моделей поиска и выведенных е рамках теории следствий »теорем и утверадений с их доказательствами составляют предмез 1 ное содержание теории поиска.

В диссертационной работе рассмотрены некоторые дискретные модели поиска движущегося об$е|кт8.Наряду с этим ,дан обзор развития теории поиска и предпринята попытка построения содержательной классификации известных моделей поиска.

Диссертация состоит из введения,четырех глав,заключения и приложений.

Заключение диссертации по теме «Технические науки», Новожилова, Лидия Михайловна

ВЫВОДЫ

1. Если цепь Маркова,описывающая движение объекта,однородная, то для сходимости ряда матриц необходимо и достаточно,чтобы матрица (1-С)А была неразложима.

В этом случае ряд (ЗИ2) сходится к единице.

2.Если С >0,то ряд (3.12) сходится к единице при любых р

3.Если С >0 и (С) = 1 ,то матрица А разложимая; здесь г (с)-максимальное собственное число матрицы (1-С) А , Если с - ,с2 ) где С/\ имеет I компонент и <^ = 0, <^>0 ,то матрица

А - ( А* 0 где А>( размерности V 4 ^ .

4.Если матрица А - (0' д ) ,то для сходимости ряда р , б ) к единице необходимо и до ста точно, что бы начальное распределение р -(^^рг) имело |х,= 0;> ,где р>| размерности

5.Если Д5 - субстохастическая матрица и содержит строки с суммой элементов,равной единице,то и в этом случае можно получить вероятность обнаружения (З.М),равной единице,если

М^Ч >0, кб[£|иД

6.Если матрица А ^ не содержит строк,сумма элементов которых равна единице,то вероятность обнаружения будет меньше единицы.

- Я6

ЗАКЛЮЧЕНИЕ

Во введении и в первой главе дан обзор теории поиска и предложена содержательная классификация существующих математических моделей поиска.В соответствии с этой классификацией модели поиске деля^тся на модели поиска неподвижного объекта и модели поиске движущегося объекта. Модели поиска движущегося объекта можно,в свою очередь,разбить на модели одностороннего и двустороннего поиска.

Во П -ой главе даны модели поиска одностороннего поиска и поставлена задача отыскания максимума вероятности обнаружения объекта к заданному моменту времени в общем случае,когда число возможных состояний объекта конечно,и процесс движения объекта представляется неоднородной цепью Маркова. Для случая,когда условная вероятность обнаружения объекта с (Ч)) »где с )-сумма средств,выделенных для поиска в момент времени t »выведено рекуррентное соотношение для опреле-ления оптимальной стратегии. Оптимальная стратегия представлена в явном виде для случая,когда ц(Ч,сЮ) « с Ц) с неизменной областью значений функции с ( "Ь ): (О

При этом оптимальная стратегия поиска-это последовательность осмотра ячеек,на которой достигается максимум вероятности обнаружения объекта. Получен алгоритм определения оптимальной стратегии поиска. Решение иллюстрируется графом. Искомой последовательности ячеек соответствует последовательность вершин,через которые проходит путь максимальной длины. Приводится вычислительная схема решения задачи,

В третьей главе рассматривается процесс поиска неограниченной длительности. Поставлены задачи определения распределений средств поиска,при которых:

1/скорость возрастания вероятности обнаружения максимальна, 2/математическое ожидание времени поиска,необходимого для обнаружения объекта,минимально.

Определено решение задачи I/ и указаны методы решения задачи 2/ для случая,когда процесс движения объекта представлен в виде однородной марковской цепи.

Вектор распределения средств поиска,доставляющий минимальное значение максимальному собственному числу матрицы (1-С)А- есть стратегия поиска,доставляющая максимум скорости возрастания вероятности обнаружения движущегося объекта.

Для определения минимума математического ожидания числа шагов, необходимого для обнаружения объекта,могут быть использованы, например,градиентные методы,

В четвертой главе исследуются вопросы о зависимости величины вероятности обнаружения объекте от структуры матрицы А и начального распределения вероятностей местонахождения объекта.

Автор выражает глубокую признательность Н.Г.Баринову и А.Б. Ковригину за руководство работой,внимание и всестороннюю помощь.

Автор выражает так же признательность сотрудникам НИИ ВМ-ПУ и сотрудникам кафедры автоматизации сложных систем факультета Ш-ПУ,а также сотрудникам лаборатории методов оптимизации автоматизированных систем управления,принявшим участие в обсуждении работы,за внимание и многочисленные критические замечания,во многом способствовавшие улучшению работы. I

Список литературы диссертационного исследования кандидат технических наук Новожилова, Лидия Михайловна, 1975 год

1. ЕМЕЛЬЯНОВ Л.А., АБЧУК В.А., ЛАШИН В.П., СУЗДАЛЬ В.Г. Теория поиска в военном деле, М., Воениздат, 1964.

2. Koopman В.О., Search and Screening, Operations Evaluation Group, Office of the Chief of Naval Operation?, Reportno, 56, 172 1946.

3. James B. Mac. Queen, Optimal Policies of a Class of Search and Evaluation Problems, Management Science, 10 (1964)» 4» 796-759.

4. Kushner H.J., Methods for the Adaptive Optimization of Binary Detection Systems (Lincoln Lab., Mass. Inst, of Tech., Lexington Report no 22g-2, Nov.9, 1962).

5. Gonstantine Gumacos, Analisis of an Optimim Sync Search Prosedure, IEEE Transactions on comanication sistems, v.CS-11, 1, 1963.

6. СЕМЕНЧУК B.E., ШИЛЬМАН С.В., Поиск экстремума функции на основ© априорной марковской модели градиентов, Изв. АН СССР, Техническая кибернетика, 1974, 5, 25-31.

7. Chew М.С., A.Sequential search Procedure, Ann. Math(l Stat., v.38 (1967), no.2, 494-502.

8. Fox В., Landi B.M., Searching for the Multiplier in One Constraint Optimization Problems, Opns. Res., v.13, mo.2 (1970), 253*262.

9. ОЛЕЙНИКОВ A.H., ГЕДЬТМАН Л.С., Модель оптимального поведения при решении одной задачи поиска, Ленинградский горный институт им.Г.В.Плеханова, "Применение ЭВМ в геологии и в горном деле", Материалы первого научного семинара, Ленинград, 1971.

10. Richardson H.R., Lowrens B.S., Operations Analisis During the Underwater Search for Scorpion, Habal Research Logistics Quarterly, v.18, (1971), 2, 141-157.

11. ВОРОБЬЕВ H.H., Опыт описания структуры и проблематики исследования операций, Тезисы Докладов 1-ой Всесоюзной конференции по исследованию операций, 1972.

12. Koopman, Bernard О., The theory of Search, Operation Research: I/ Kinematic Bases, v.4, 3 (1956);1./ Target Detection, v.4, 5 (1956); III/ The Optimum Distribution of Searching Sffort,T.5,5(1957

13. ДАНСКИН Дж.М., Теория максимина и ее приложения к задачам распределения вооружения, М., "Сов.радио", 1970.

14. Charnee A., Cooper V., The Theory of Search: Optimum Distribution of Search Effort, Xanagment Science, v.5» 1, 4450 (1958).5. de Guenin, Jacqus, Optimum Distribution of Efforts an Extension of the Koopman Basic Theory, Opns. Res,, v.9, 1 (1969).

15. Dobbie, J.M., Search Theory: A Sequential Approach, Hav. Res. Logistics Quart.щ v.10, 4 (1963), 323&334.

16. Zahl, S,, An Allocation Problem with Applications to Operations Research Statistics, Opns, Res., v.10, no.3 (1963).

17. Kazuo Tada, Tansaku Doryoku no Haibun ni Kansuru Kosatsu (II), Keie Kagaku (Japan), v.8 (1965), Ho 4, 218-224.

18. Gilbert»B.H., Optimal Search Strategies, J.Soc.Indust, Appl. Math., v.7, 4 (1959).

19. Hellman,0., Bayesian Expression for the Probability that Searcher Will Pind a Target, Unternehmensforschung, v.12, 3t 1968, 178-179.

20. Smith G.A.B., The counterfort coun problem. Math.Gas, 1947, 31-39.

21. Gluss, В., An Optimal Bolicy for Detecting a Fault in a Complex System, Opns.Res., v.7, 4 (f959), 468-477.

22. Shies В., Approximatly Optimal One-Dimensional Search Po-lisies in Wich Seareh Costs Vary Through Time, Opns. Res., v.9 (1961).

23. Blachman, N., Broschan P., Optimum Search for Objects Having Unknown Arrival Times, Opns. Res., v.17» 5 (1959).

24. СТАРОВЕРОВ O.B., Об одной задаче поиска, Теория вероятностей и ее применения, 8 (1963), 2, 196-201.

25. ЛЮБАХОВ Ю.В., 0 рациональном планировании операций поиска, Изв. АН СССР, Техническая кибернетика, 1964, 1-94-100.

26. Matula D., A Periodic Optimal Search, American Math. Monthly, v.17 (1964), 15-21.

27. Ross, S.W., A Problem in Optimal Search and Stop, Opns. Res., v.17, (1960), 984-992.

28. Chew, M.G., A Sequential Search Procedure, Ann. Math. Stat., v.38 (1967), 494-502.

29. Chew M.C., Optimal Stopping in a Discrete Search Problem, Opns. Res., v.21, 3 (1973), 741-747.31• Black W., Discrete Sequential Search. Information and Controle 8, 152-162 (1965).

30. Вопросы статистической теории радиолокации, под общей ред.

31. Г.П.Тартаковского, том I, изд-во "Оов.радио", М., 1963, стр.174—179.

32. ВАЙЬД А., Последовательный анализ, Физмативиз, I960.

33. Pollock S.M,, Sequential Seach and Detection, Opns. Res. Center, MIT., Cambridge, Mass. Tech. Report no.5 Contract Monr-3963, (06) , 131 pp., 1964.

34. Snyder M.A., Stone L.D., Search Theory in the Presenece of False Targets, 35 national Meeting of the Operations Researcl Society of America, Denver Colorado, June 17, 1969.

35. Smith M., An Optimal Discrete Space Sequential Search Procedure Wieh Considers Raise Alame and False Dismissal Instrument Errors, Dept of Statistics, Southern Methodist University, THEMIS Contract Report no.35, May 1969.

36. Pollock S.M., Seach Detection and Subsequent Action: Some Problems on the Interfaces, Opns. Res., 1971, т.19, 3» 559.

37. ЛЮБАТОВ Ю.В., Оптимальная процедура локализаций неисправности в модуляризованной радиоэлектронной схеме, Изв. АН СССР, Техническая кибернетика, 1964, 4, 19-26.

38. АРКИН В.И., Задача оптимального распределения поисковых усилий, Математический институт им.Стеклова, XXI (т.71), Теория вероятностей, 1964.

39. АРКИН В.И., Задача оптимального распределения поисковых усилий, Теория вероятностей и ее применение, 1964,9,1,179-I8C

40. АРКИН В.И. Некоторые экстремальные задачи, связанные с теорией поиска, Теория вероятностей и ее применения,1965,10,3, 593-596.

41. Danskin J.M., On Koopraan's Addition Theorem in Search Theory, Institute of Haval Studies, Cambrige, Mass., 1964.

42. Dovvie, J.M., Some Problems, in Search Theory ( см.библиографию к 73 , I 13) .44. шшт С.С. Некоторые задачи дискретного поиска и методы их рещения. Автореферат диссертации на соискание ученой степени канд.фез.мат.наук, Ленинград, 1964.

43. КИСЛИЦЫН С.С., 0 задачах дискретного поиека, Кнберветика, 1966, 4, 64-70.

44. Huffman, A method §от the construction of minimum vedunda-cy codes, "Proc. IRE, 40, 9, 1952, 1098-1101 ( русский перевод см. н Кибернетический сб.", Л 3, 79-81).

45. Sandelious М., On an optimal search prosedure, Amer. Math. Monthly, 68, 2, 1961, 133-134.

46. Renjri. A., Statistical laws of accumulation of information, "Bull. Inst. Intermal. Statist", 33-rd session, Paris, 1-7, 1961.

47. Renyi A., Egy altalanos modszer valoszimisegs-zamitsi te-letek byzonyi tasara es annak nehany alhalmazasa, "Magyar tud. acad. Mat. es fiz. tud. oszt. kozl", 11, 1 (1961), 79105.

48. Renyi A., As infomacio-akkumulacio statisztikus forvenyaAzer-usegeirol, 12, 1 (1962), 15-33.1. A A5t. Picard C., Theorie des queetionaires, These doct. Sci. math. Рас, Sci. Iniv. Paris, 1964.

49. Cairns S.S., Balance scale sorting, "Bull. Amer. Mth. Soc"., 62, 2, 1956, 177.

50. Cairns S.S., Balance scale sorting, Amer, Math. Hontly, 70, 2, 1963, 136-148.

51. Bellman R., Glass B., On various versions of the defective coin problem. Inform, and Controle, 4, N 2-3, (1961), 118131.

52. Steinhaus, Mathimatical snapshots, Ney-York, 1950, 143-145.

53. Klein M., A Note on Sequential Search, Hav. Res. Log. Quart, 1968, v. 15, 469t474.

54. Pollock S.M., A Simple Model of Search for a Moving Target, Opns. Res.» v.18, (1970), 883-903.

55. Bobbie J.H., A Two-Cell Model of Search for a Moving Target, Opns. Res., v.22 (1974), 1 (Fab.), 79-92.

56. Schweitzer P.J., Threshold Probabilities when Searching for a Moving Target, Opns. Res., v.19, (1971), 3.

57. НОВОЖИЛОВА Л.М., Определяющие средства и понятия языков : моделирования дискретных систем, сб. "Методы и модели управления", вып.7, Рижский политехнический институт, Рига, 1974.

58. НОВОЖИЛОВ Г.В., НОВОЖИЛОВА Л.М., Некоторые вопросы математического обеспечения ЭВМ в АСУП, Сб. авторефераторов РИР,Л7( 1973) ,ШШЭШ,УДК 681.3.06:658.012.011.56.7-727.

59. НОВОЖИЛОВА Л.М., НОВОЖИЛОВ Г.В., Языки моделирования систем с дискретными событиями, сб.авторефератов РИР, В 7 (1973) НИИЭИР, УДК 681.3.06:62-501, 7, 7-719.

60. Bram J., A2-Player N-Region Search Game, Operation Evaluation Group, Office of Natral Operations, IHM31, January 17, 1963, D. no AD-402914.

61. Johnson S.M., A Search Game, Advancea in Game Theory M.Dresher, L.Shaply, A.Tucker (eds.), Prinston University Press, Princeton Hew Fersey, 39-48, 1964.

62. Ueuts M.F., A Multistage Search Game, Jourmalof Society for industrial and applied mathematics, v.11, no.2, 1963.

63. Morris R.C., Studies in Search for a Conseicous Evader, U.S. G.R.P., Document no AD-284832, 1962.

64. Arnold R.D., Avoidance in One Dimension a Continueus-Mat-rix Game, Operations Evaluation Group, Office of Chief of Naval Operation, Washington, D.O., 0EFIRM-10 (AD277 843), 14 pp., lletanuary, 1962.

65. КИБЕЦ В.Ф., 0СТАШЕВСКИЙ И.П., Об одной игре поиска с движущимися объектами, Кибернетика, 1973, I.69* Minoru Sakaguchi, Two-Sided Search Games, Journal of the OR Sof Japan, 16 (1973), 4 (Dec), 207-225.

66. Giammo T.P., On the probability of Success in a Sudden Death Search with Intermittent Moves Confined to a Finite Ared. SIAm Revew 5, 41-51 (1963).

67. НОВОЖИЛОВА Л.М., К задаче поиска движущейся точки, сб. "Методы и модели управления", РШ, Рига, 1975, вып.9,

68. Danskin J.M., A Heliocopte Versas Submarine Search Game. Opns fies., vgl6, 3 (May-Jane 1968), 509-517.

69. Bobbie J.M., A Survey on Search Theory, Opns. Res., v.16, 3 (1968).§§ 2,3,4

70. КОЛМОГОРОВ A.H., Основные понятия теории вероятностей, изд. второе, "Наука", M., 1974.

71. ФЕШШР В., Введение в теорию вероятностей и ее примеиения, -Мир", M., 1967.

72. ШНТРЯГШ 1.С., БОЛТЯНСКИЙ В.Г., ГАМКРЕЛВДЗЕ.Р.В., ШЩШКО Е.Ф., Математическая теория оптимальных процессов, "Наука", M., 1969.

73. БЕДЛМАН Р., КАЛАЕА Р., Динамическое программирование и современная теория управления, "Наука", M., 1969.

74. БЕДЛМАН Р., ДРЕЙФУС С., Прикладные задачи динамического программирования, "Наука", M., 1965.

75. БЕЛЛМАН Р., ГЛЙГСБЕРГ И., ГРОСС 0., Некоторые вопросы математической теории процессов управления, ИЛ, M., 1961.

76. ВАЛЬД А., Последовательный анализ, Физматгиз, I960 .

77. ХОВАРД P.A., Д мнашческое программирование ж марковские процессы, M., 1964,

78. КЕМЕНИ Дж., Конечные цепи Маркова, M., 1970.

79. РОМАНОВСКИЙ В.И., Дискретные цени Маркова, «.-!., Гостех-издат, 1949.

80. ФАДЕЕВ Д.К., ФАДЦЕЕВА В.Н., Вычислительные методы линейной абгебры, изд. второе, М.-Л., 1963.

81. МАРКУС М., МИНК X., Обзор по теории матриц и матричных неравеяств, "Наука", M., 1972.

82. БЕЛЛМАЕ Р., Введение в теорию матриц и матричных неравенств, "Наука", М., 1969.

83. ПАРОЛИ М., Локализация характеристических чисел матриц и ее применение, ИЛ., М., i960.

84. ГАНТМАХЕР Ф.Р., Теория матриц, М. "Наука", 1967.

85. ДШЬЯНОВ В.Ф., 1АЖЗЗЕЙ0В В.Н., Введение в шнимакс., "Наука" i., 1972.

86. ДАНСКИН Дж.М., Теория максимина и ее приложения к задачам распределения вооружения, М., "Сов.радио", 1970.

87. КЕПИ Р.Дж., Метод градиентов, Сб." Методы оптимизации", под ред. Дж.Лейтмана, "Наука", М, 1965.

88. БАСАКЕР Р., СААТИ Т., Конечные графы и сети, "Наука", М., 1974.

89. ПРОПОЙ А.И., Элементы теории оптимальных дискретных процессов, М., 1973.

90. ВАГНЕР Г., Основы исследования операций, 1,2,3 т.т., Т., 1972-73.

91. ЛАНКАСТЕР К., Математическая экономика, "Сов.радио", М., 1972.

92. МОИСЕЕВ H.H., Численные методы в теории оптимальных систем, М., 1971.

93. ФАН ЛЯНЬ-ЦЕНЬ, ВАНЬ ЧУ-СЕН, Дискретный принцип максимума, "Мир? 1967.

94. ЗОНТЕНДЕЙК Г. , Методы возможных направлений, ЙЛ., М., 1963.

95. ЛЬЮС Р.Д., РАЙФА X., Игры и решения, Ш., М., 1961.

96. Позиционные игры под ред.Воробьева H.H. и Врублевской И.Н., "Наука", М., 1967.

97. Обнаружение и опознание сигналов, Симпозиум 16, под ред. Ломова, М., 1966 (ХШЩ Международный психологический конгресс

98. МОИСЕЕВ H.H., Численные методы теории оптимальных управлений, использующие вариации в пространстве состояний, Кибернетика, 1966, 3, I.

99. Визинг В.Г., Графовая модель оптимизации в задачах очередности, Кибернемка, » I, 1975.