Актуальность проблемы.
Поиск — явление, имеющее место во всех сферах человеческой деятельности. Всем хорошо известны такие процессы, как поиск полезных ископаемых, определение места перегрева доменных печей или каких-либо неисправностей оборудования, поиск косяков рыбы, нахождение источников заболевания или заражения, розыск преступников, поиск рынков сбыта или приобретения товаров, формирование оптимальных управленческих решений [1−8]. Различные спасательные операции часто основываются на различных стратегиях поиска, например, поиск и локализация места крушения корабля или самолета или поиск заблудившегося в лесу [9−15]. Кроме этого, многие радиолокационные и навигационные задачи являются поисковыми. Например, ориентация космических кораблей в пространстве или поиск объектов с целью дальнейшего сопровождения или установления радиоили телевизионного контакта [16−29]. Оптическое распознавание предметов, используемое при организации работы роботов-манипуляторов, также представляет собой задачу поиска [30−33]. Существуют и чисто военные задачи — поиск и обнаружение сил и средств противника (подводных лодок, кораблей, зенитных ракетных комплексов и т. д.), представляющих собой потенциальную угрозу [34−36].
Как правило, цель поиска заключается в обнаружении некоторого объекта в области его вероятного местоположения, уточнении его координат и дальнейшем сопровождении.
В силу ряда факторов реальные характеристики поисковых систем могут отличаться от заданных при организации поиска К таким характеристикам, в частности, относятся погрешности в воспроизведении траекторий сканирования. Они возникают, например, из-за неточностей в изготовлении устройств привода и генераторов разверток, посредством которых осуществляется движение в заданном направлении. В то же время, особенности обследуемой области также влияют на направление движения луча поисковой системы. Например, при локации луч сканирующего устройства, проходя через воздушные слои и облака с разными коэффициентами преломления может отклониться от заданной траектории движения. При поиске полезных ископаемых разнородные слои почвы также могут вызвать искажение траектории сканирования. Боковой ветер вызывает отклонение от курса вертолетов поисковых группы при поиске мест катастроф и людей, терпящих бедствие.
Вследствие этого, возникают непросмотренные участки области поиска, и появляется вероятность пропуска объекта Р"р [12,15,37- 41]. Следовательно, встает необходимость решения задачи, связанной с оценкой влияния ошибок в воспроизведении траектории сканирования на эффективность проведения поиска.
В первых работах по этой тематике [37,40−43] были предприняты попытки учесть такие вероятности пропуска при решении различных поисковых задачах. Однако в публикациях [37,41—43] Рпр принималась постоянной величиной и была независима от изменения значения или вероятностного характера отклонения (ошибки) луча от заданной траектории в процессе проведения поиска. В работе [40] была рассмотрена зависимость Рпр от величины ошибки воспроизведения, и был предложен способ ее снижения за счет введения перекрытий между витками траекторий просмотра. Но при этом были выведены аналитические выражения только дискретного поиска неподвижного объекта для траекторий «Простой растр» и «Прямоугольная спираль». К тому же, в работе использовалось допущения, что ошибка воспроизведения остается постоянной при реализации витка траектории сканирования и между величинами ошибки в соседних витках отсутствует корреляционная зависимость. Однако в реальных условиях организации сканирования это не всегда справедливо. Например, при прохождении лучом поискового устройства участков просматриваемой области с плавно изменяющимся коэффициентом преломления, такая корреляционная зависимость может иметь место [44,45].
Цель диссертационной работы.
Целью данной диссертационной работы является определение и исследование зависимости вероятности пропуска неподвижного объекта от величины ошибки воспроизведения траекторий просмотра в случае ее изменения при реализации витка траектории и оценка влияния этой вероятности на эффективность организации сканирования для различных поисковых задач.
Основные задачи исследования.
В соответствии с поставленной целью определены следующие задачи исследования: вывод аналитических выражений для определения вероятности пропуска при дискретном одностороннем поиске неподвижного объекта для случая изменения величины ошибки воспроизведения при реализации витка траектории сканирования «Простой растр» и «Прямоугольная спираль" — исследование зависимости вероятности пропуска объекта от величины ошибки воспроизведения и параметров траектории сканирования;
— разработка алгоритма определения вероятности пропуска при дискретном поиске неподвижного объекта по произвольной траектории сканирования с использованием перекрытий между витками;
— уточнение аналитических выражений для определения вероятности пропуска при наличии корреляционной зависимости между величинами ошибки воспроизведения в соседних участках траектории сканирования;
— постановка задач оптимизации поиска неподвижного объекта с учетом наличия ошибок в воспроизведении траектории сканирования и разработка алгоритмов их решения;
— формирование принципов использования полученных аналитических выражений для определения оптимального соотношения между параметрами траектории сканирования с целью оптимизации поиска неподвижного объекта;
— определение вероятности пропуска при многократном просмотре области поиска по произвольной траектории сканирования;
— разработка программного комплекса, позволяющего решить указанные выше задачи.
Методы исследования.
Методы исследования базируются на теории вероятностей и математическая статистика, дифференциальном и интегральном исчислениях, комбинаторном анализе, теории оптимизации, численных методах решения задач оптимизации.
Научная новизна.
1. Получены аналитические выражения для определения вероятности пропуска неподвижного объекта для случая изменения величины ошибки воспроизведения при реализации витка траекторий сканирования «Простой растр» и «Прямоугольная спираль» при дискретном просмотре области поиска.
2. Проведено исследование зависимости вероятности пропуска от величины ошибки воспроизведения и параметров траектории сканирования. Найдено условие, позволяющее определить величины параметров траектории (количество витков и стробов, величина перекрытия между ними), обеспечивающие снижение вероятности пропуска до заданного уровня.
— 93. Разработана методика определения вероятности пропуска неподвижного объекта при использовании произвольной траектории сканирования.
4. Исследована зависимость характеристик закона распределения вероятностей возникновения ошибок воспроизведения от количества просмотренных стробов траектории сканирования. Сформулированы принципы учета корреляционной зависимости между ошибками воспроизведения в соседних стробах траектории при определении вероятности пропуска, и уточнены выражения для ее расчета.
5. Модифицировано выражение для расчета максимальной полной вероятности обнаружения для случая наличия ошибок в воспроизведении траектории сканирования. Предложен комплексный критерий оптимизации, учитывающий влияние времени поиска на его эффективность, когда существуют ограничения на скорость сканирующего устройства.
6. Сформулированы задачи оптимизации для трех вариантов просмотра области поиска при изменении величины ошибки воспроизведения, и разработан алгоритм их решения.
7. Сформулированы принципы практического применения задач оптимального поиска неподвижного объекта при различных величинах поисковых ресурсов и законах распределения плотности вероятностей местоположения искомого объекта с целью определения оптимальных параметров траектории просмотра, при которых обеспечиваются заданные точностные характеристики системы сканирования и максимальная эффективность поиска.
8. Получены выражения для определения вероятности пропуска объекта при различном количестве просмотров области поиска, и проведено исследование зависимости этой вероятности от параметров траектории сканирования.
Практическая ценность результатов.
Полученные в диссертационной работе результаты позволяют :
— рассчитать вероятность пропуска неподвижного объекта вследствие ошибок в воспроизведении траектории сканирования любого вида, определить степень влияния этой вероятности на результаты поиска,.
— разработать алгоритмы организации просмотра заданной области и определить параметры траектории сканирования, которые позволят снизить Р"р, а следовательно, уменьшить временные затраты на обнаружение объекта и увеличить эффективность поиска при наличии ограниченного количества поисковых ресурсов. Выведенные в работе аналитические зависимости и разработанные алгоритмы снижения Р"р можно использовать при решении таких задач поиска, как :
— в спасательных операциях для определения координат места катастроф,.
— на производстве с целью поиска и локализации дефектов в оборудовании и на разных стадиях изготовления продукции,.
— в медицине при поиске злокачественных опухолей в организме,.
— для установления связи со спутниками, аэродинамическими мало скоростными объектами и наземными радиолокационными объектами, в военных операциях для поиска скоплений войск и бронетехники противника, а также в других задачах, в которых: а) объект поиска имеет ряд свойств, отличающихся от характеристик сканируемой области, б) объект поиска неподвижен или перемещается с такой скоростью, что за время поиска его перемещением можно пренебречь.
Реализация результатов.
1. На основе полученных в диссертационной работе аналитических выражений и разработанных алгоритмов сформулированных задач оптимизации поиска составлен программный комплекс, позволяющий для различных видов поисковых задач и априорных сведений об объекте и области поиска :
— рассчитать аналитическим путем вероятность пропуска неподвижного объекта вследствие ошибок в воспроизведении траекторий сканирования «Простой растр» и «Прямоугольная спираль" — получить и проанализировать зависимость Рпр от величины ошибки воспроизведения и перекрытия между витками указанных траекторий сканирования;
— выбрать способ снижения Рпр путем повторного просмотра области поиска или увеличения перекрытия между витками без существенных дополнительных затрат поисковых ресурсов (например, времени, отводимого на поиск);
— определить оптимальное соотношение между параметрами траектории сканирования позволяющее снизить Рпр и максимизировать эффективность поиска при наличии ограниченного количества поисковых ресурсов.
— 112. Результаты диссертации использованы на предприятии ООО «Томилинский электронный завод» при создании алгоритмов для разработки оптимальных траекторий тестирования поверхности и проверки толщины слоя меди в вытравленных дорожках печатных плат для блоков питания и зарядных устройств, с целью обнаружения и локализации мест возможных дефектов.
Апробация работы и публикации.
Основные результаты диссертационной работы докладывались и обсуждались на международных конференциях «Информационные средства и технологии» МФИ-96, МФИ-97, МФИ-98 и МФИ-99, на научной сессии МИФИ-98 и на Шестой международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика». Тезисы доклада опубликованы в «Трудах международного научно-технического семинара «Современные технологии в задачах управления, автоматики и обработки информации» (г.Алушта, 1997 г.). Результаты проведенных исследований вошли в госбюджетную работу № 190 005 865 по теме «Разработка методов алгоритмического и программного обеспечения прецизионного управления в сложных динамических системах», выполняемую в Московском энергетическом институте (Техническим университете) в период с января 1997 г. по декабрь 1999 г. под руководством д.т.н. проф. Державина О.М.
Результаты диссертационной работы опубликованы в работах [46−56].
Краткое содержание работы.
Диссертация состоит из введения, шести разделов, заключения, списка литературы и шести приложений.
— 1385.4. Выводы.
В данном разделе рассмотрен процесс поиска неподвижного точечного объекта при многократном просмотре заданной области пространства с использованием траекторий сканирования типа «Простой растр» и «Прямоугольная спираль». При этом, получены следующие результаты:
1) Выведены выражения для определения вероятности пропуска объекта Рпр из-за ошибок в воспроизведении траекторий сканирования «Простой растр» и «Прямоугольная спираль» при многократном просмотре области поиска.
2) Рассмотрены случаи сканирования с возвратом луча по первоначальной траектории и по траектории, повернутой на 90° относительно первоначальной. Даны рекомендации по их практическому использованию.
3) Проанализирована зависимость Рпр от количества витков в траектории, числа просмотров области поиска и перекрытия между витками для вышеуказанных случаев. Эта зависимость позволяет определить количество витков в траектории сканирования и стробов, необходимое для получения Рпр в заданном диапазоне.
4) Уточнено выражение для определения Р"р при использовании произвольной траектории сканирования. Рассмотрен случай, когда луч поискового устройства может пересекать линию своего движения в предыдущие моменты времени. Таким образом, рассмотренный способ расчета Рпр может быть применим в дальнейшем практически для любого вида траектории сканирования.
6. Программный комплекс «Поиск в условиях помех» и практическое применение результатов диссертационной работы.
В данном разделе рассмотрен программный комплекс «Поиск в условиях помех», созданный на основе полученных в предыдущих разделах математических выражений для расчета Рпр и оценки эффективности поиска при ошибках в воспроизведении траектории сканирования. Приведен перечень системных требований к вычислительным системам, на которых будет использоваться разработанная программа. Раскрыта структура программного обеспечения и рассмотрены алгоритмы работы с ним при решении задач оптимального поиска в условиях помех.
Рассмотрен пример практического применения результатов диссертационной работы при решении задачи поиска дефектов, образующихся при изготовлении печатных плат.
6.1. Структура программного комплекса «Поиск в условиях помех».
6.1.1. Среда программирования и системные требования к аппаратным ресурсам.
Программный комплекс «Поиск в условиях помех» предназначен для решения следующих задач :
— расчет величины вероятности пропуска неподвижного объекта вследствие ошибок в воспроизведении траектории сканирования «Простой растр» или «Прямоугольная спираль»;
— получение зависимости Р"р от величины ошибки воспроизведения, количества стробов, витков и перекрытия между ними для указанных выше траекторий;
— определение вида корреляционной функции, финального распределения вероятностей возникновения ошибки воспроизведения и количества стробов, которое необходимо просмотреть для получения этого распределения;
— расчет оптимальных значений параметров траектории сканирования (количество витков, величина перекрытия между ними) при решении задач оптимизации поиска неподвижного объекта, рассмотренных в Разделе 4;
— определение величины Рпр при многократном просмотре области поиска по траекториям сканирования «Простой растр» или «Прямоугольная спираль»;
— получение зависимости Рпр от величины ошибки воспроизведения, перекрытия между витками и количества просмотров для указанных выше траекторий;
— просмотр результатов исследований.
Программный комплекс «Поиск в условиях помех» создан на языке программирования Object Pascal 7.0 в среде Delphi 4. Этот язык обеспечивает хорошую реализацию модульного принципа построения программного обеспечения. В то же время, среда программирования Delphi 4 позволяет создавать экранные формы ввода исходных данных и просмотра полученных результатов и, тем самым, является одним из оптимальных средств быстрой реализации интерфейса, удобного для работы пользователя с программой.
Программное обеспечение предназначено для работы в операционной среде Windows 95 и выше. Поэтому для достижения достаточного уровня его быстродействия необходимо использовать ПЭВМ с параметрами не ниже перечисленных :
— процессор 80 486;
— оперативная память 8 Мб.
Свободное место на жестком диске, необходимое для пользовательского режима работы с программой — 500 Кб для программы и до 200 Кб для файлов с результатами исследований.
В случае доработки программного обеспечения с целью расширения круга решаемых им задач необходимо установить на компьютере среду программирования Delphi 4 или выше. При этом параметры ПЭВМ должны быть не ниже перечисленных: процессор Pentium с частотой от 100 МГц и вышеоперативная память 16 Мб (лучше 32 Мб).
Свободное место на жестком диске :
— для среды программирования — не менее 300 Мб,.
— для файлов с текстами программного обеспечения — не менее 1,2 Мб.
6.1.2. Интерфейс и структура программного обеспечения.
Программный комплекс «Поиск в условиях помех» разработан на модульной основе и включает в себя следующие типы модулей (рис. 6.1):
1) основное меню программы, служащее для выбора одной из указанных выше задач, или просмотра файлов с результатами их решения;
2) модули-формы, предназначенные для экранного ввода исходных данных и просмотра результатов решения задач (Приложение 5);
3) программные модули, содержащие в себе процедуры решения задач поиска объекта в условиях помех;
4) файлы с результатами решения задач.
Программное обеспечение позволяет решить четыре задачи поиска неподвижного объекта в условиях помех :
1) «Простой поиск неподвижного объекта» — расчет вероятности пропуска объекта из-за ошибок к воспроизведении траектории сканирования Р"р, а также получение зависимости Р"р от количества стробов, витков в траектории «Простой растр» или «Прямоугольная спираль» и перекрытий между ними для различных априорных сведений об объекте и области поиска;
2) «Оптимальный поиск неподвижного объекта» — решение задач оптимального поиска неподвижного объекта при наличии разного сочетания ограничений на время и скорость сканирования с использованием критерия оптимальности, основанного на максимизации полной вероятности обнаружения;
3) «Корреляционная зависимость» — определение вида корреляционной зависимости между отклонениями луча в соседних стробах траектории сканирования типа «Простой растр» или «Прямоугольная спираль» и финального распределения вероятности возникновения ошибок воспроизведения для различных априорных сведений об области поиска;
4) «Повторное сканирование» — расчет Рпр при многократном просмотре области поиска, а также получение зависимости Рпр от количества витков в траектории, перекрытий между ними и числа просмотров для различных априорных сведений об объекте и области поиска;
Каждая из этих задач складывается из экранной формы ввода данных и соответствующего ей программного модуля (рис. 6.1).
Рис. 6.1. Структурная схема программного обеспечения «Поиск в условиях помех».
Среди программных модулей имеют место :
1) модули, содержащие процедуры решения указанных выше четырех задач поиска неподвижного объекта в условиях помех :
— модуль «Rastrmod», предназначенный для определения Р"р при ошибках в воспроизведении траектории сканирования «Простой растр» для различного количества просмотров области поиска;
— модуль «Spirmod» служащий для определения Рпр в случае использования траектории «Прямоугольная спираль» для различного количества просмотров области поиска;
— модуль «Optimmod», предназначенный для решения задач оптимизации поиска неподвижного объекта при наличии ограниченного количества поисковых ресурсов;
— модуль «Korrmod», содержащий в себе процедуры определения корреляционной функции и финального распределения вероятностей возникновения ошибок воспроизведения;
2) модули, составляющие библиотеку вспомогательных процедур для расчета РПр для траекторий «Простой растр» и «Прямоугольная спираль».
— модуль «Constmod», содержащий описание всех основных констант и переменных, использующихся при решении задач;
— модуль «Intmod» предназначен для расчета вероятностей возникновения различных ошибок воспроизведения траекторий сканирования исходя из различных сведений о параметрах их законов распределения;
— модуль «Dintmod» содержит в себе процедуры для определения вероятностей нахождения объекта поиска в непросмотренных участках области его вероятного местоположения;
Все указанные выше модули и стартовый файл программы находятся в каталоге «Searching». Файлы с результатами имеют расширение «.res» и хранятся в каталоге «Result». Их содержимое можно просмотреть с помощью пункта основного меню «Результаты» (Приложение 5).
— 1446.1.3. Возможности расширения круга задач, решаемых программным комплексом.
Как указывалось ранее, программный комплекс «Поиск в условиях помех» построен по модульному принципу. Это означает, что при появлении новых алгоритмов решения задач поиска объектов в условиях помех для различных траекторий сканирования достаточно только написать соответствующий программный модуль и модуль экранной формы ввода исходных данных. Затем эти модули при помощи программной среды Delphi 4 подключаются к уже созданному программному обеспечению.
При этом, наличие библиотеки вспомогательных процедур и модулей, созданных для рассмотренных в диссертации задач поиска, позволяет значительно облегчить работу по созданию новых программных модулей, так как в них уже имеют место некоторые автоматизированные расчеты, как, например, определение вероятности нахождения объекта в непросмотренных участках области поиска или расчет корреляционной функции для ошибки воспроизведения.
В дальнейшем в программный комплекс «Поиск в условиях помех» можно включить, например, такие задачи, как :
— «Оптимальный поиск неподвижного объекта» — решение задач оптимизации поиска объекта с использованием критерия максимума апостериорной информации об объекте;
— «Простой поиск движущегося объекта» — определение зависимости вероятности пропуска от количества просмотренных витков траектории сканирования, величины перекрытия между ними и времени отведенного на поиск;
— «Оптимальный поиск движущегося объекта» — решения задач определения оптимальных значений параметров траекторий сканирования для поиска движущегося объекта при наличии ограниченного количества поисковых ресурсов и использовании критериев оптимизации, основанных на максимизации полной вероятности обнаружения объекта и величины апостериорной информации о нем.
Также в разработанном программном обеспечении возможно использование новых видов траекторий сканирования и различных законов распределения вероятностей местоположения объекта в области поиска и ошибки воспроизведения при решении указанных выше задач.
6.2. Порядок работы с задачами.
6.2.1. Задача «Простой поиск неподвижного объекта».
Эта задача позволяет на основании аналитических выражений, полученных в Разделе 2, произвести автоматический расчет вероятности пропуска объекта из-за ошибок к воспроизведении траектории сканирования (Рпр), а также получить зависимости Р"р от количества стробов, витков в траектории «Простой растр» или «Прямоугольная спираль» и перекрытий между ними для различных априорных сведений об объекте и области поиска.
Заключение
.
Диссертационная работа посвящена определению и исследованию зависимости вероятности пропуска объекта вследствие ошибок в воспроизведении траектории сканирования от величины и характера изменения этих ошибок, а также оценке влияния этой вероятности на эффективность организации различных поисковых задач.
В работе были рассмотрены задачи дискретного одностороннего поиска неподвижного точечного объекта в области его вероятного местоположения и получены следующие основные результаты :
1. Получены аналитические выражения для определения вероятности пропуска неподвижного объекта для случая изменения величины ошибки воспроизведения при реализации витка траекторий сканирования «Простой растр» и «Прямоугольная спираль» при дискретном просмотре области поиска.
2. Проведено исследование величины вероятности пропуска от величины ошибки воспроизведения и параметров траектории сканирования. Найдено условие, позволяющее определить величины параметров траектории (количество витков и стробов, величина перекрытия между ними), обеспечивающие снижение вероятности пропуска до заданного уровня.
3. Разработана методика определения вероятности при использовании произвольной траектории сканирования.
4. Исследована зависимость характеристик закона распределения вероятностей возникновения ошибок воспроизведения от количества просмотренных стробов траектории сканирования. Сформулированы принципы учета корреляционной зависимости между ошибками воспроизведения в соседних стробах траектории при определении вероятности пропуска объекта, и уточнены выражения для ее расчета.
5. Модифицировано выражение для расчета максимальной полной вероятности обнаружения для случая наличия ошибок в воспроизведении траектории сканирования. Предложен комплексный критерий оптимизации, учитывающий влияние времени поиска на его эффективность, когда существуют ограничения на скорость сканирующего устройства.
6. Сформулированы задачи оптимизации для трех вариантов просмотра области поиска при изменении величины ошибки воспроизведения, и разработан алгоритм их решения.
7. Сформулированы принципы практического применения задач оптимального поиска неподвижного объекта при различных величинах поисковых ресурсов и законах распределения плотности вероятностей местоположения искомого объекта с целью определения оптимальных параметров траектории просмотра, при которых обеспечиваются заданные точностные характеристики системы сканирования и максимальная эффективность поиска.
8. Получены выражения для определения Рпр при различном количестве просмотров области поиска, и проведены исследования зависимости Р"р от параметров траектории сканирования.
9. Разработан программный комплекс на языке программирования Delphi 4, позволяющий для различных начальных сведений об объекте и области поиска :
— рассчитать вероятность пропуска неподвижного объекта вследствие ошибок в воспроизведении траектории сканирования «Простой растр» и «Прямоугольная спираль»;
— получить зависимость Рпр от величины ошибки воспроизведения, перекрытия между витками указанных траекторий сканирования и количества просмотров области поиска;
— выбрать способ снижения Р"р путем увеличения перекрытия между витками, многократного просмотра области поиска или их сочетания без существенных дополнительных затрат поисковых ресурсов (например, времени, отводимого на поиск);
— определить оптимальное соотношение между параметрами траектории сканирования и количеством просмотров области поиска, позволяющее снизить Рпр;
— решить задачи оптимизации поиска неподвижного объекта при наличии различного сочетания ограниченного количества поисковых ресурсов (время поиска и скорость сканирующего устройства) для траекторий «Прямоугольная спираль» и «Простой растр».
Результаты диссертации использованы на предприятии ООО «Томилинский электронный завод» при создании алгоритмов для разработки оптимальных траекторий тестирования поверхности и проверки толщины слоя меди в вытравленных дорожках печатных плат для блоков питания и зарядных устройств, с целью обнаружения и локализации мест возможных дефектов (Приложение 6).
