Обзор существующих методов и подходов к планированию групповых действий. Разработка модели одиночных и групповых действий беспилотного летающего аппарата. Создание программы и ее экономическая целесообразность. Модели качества процессов конструирования.
При низкой оригинальности работы "Разработка алгоритмов поиска оптимального маршрута для БЛА при наблюдении им подвижных наземных объектов", Вы можете повысить уникальность этой работы до 80-100%
При этом с ростом числа объектов время решения задачи растет экспоненциально, так как количество возможных вариантов равно n!, где n - число объектов (рисунок 1.1.1). Например, в нашем случае, в результате работы алгоритма мы будем получать множество восьмибитных строк, большинство из которых не будут годиться для решения задачи, так как некоторые объекты будут учтены несколько раз, а некоторые могут быть вообще не учтены. В первую очередь, алгоритм эффективен только для унимодальных функций, так как при работе этого алгоритма решение всегда «идет» вверх. После проведения кластеризации к объектам внутри каждого кластера применятся алгоритм «упаковки», суть которого заключается в том, чтобы перевести координаты каждого из объектов в полярные, а замет отсортировать их по углу поворота, а затем по радиусу в порядке возрастания. Выходные значения нейронной сети будут формироваться таким образом, что, тот выход, который соответствует следующему в маршруте объекту (то есть тому объекту, к которому сейчас необходимо двигаться БЛА), будет переходить в активное состояние (значение этого выхода станет равным «1»), а все остальные выходы останутся в пассивном состоянии (их значение будет установлено в «0»).
Введение
В настоящее время в мире значительно возрастает роль беспилотной авиации. Среди задач, решаемых с помощью беспилотных летательных аппаратов, особое место занимают задачи наблюдения наземных объектов. При решении данной задачи крайне важна оперативность получения данных об объекте наблюдения. Существует ряд алгоритмов построения оптимального маршрута облета объектов, однако большинство из них рассчитано только на неподвижные объекты, что значительно ограничивает их применимость для решения целого ряда актуальных задач. В случае использования существующих алгоритмов, рассматривающих неподвижные объекты, полученный оптимальный маршрут может оказаться далек от оптимального при движении хотя бы одного из наблюдаемых объектов. В связи с этим, возникает необходимость разработки алгоритмов, которые учитывают подвижность наблюдаемых объектов при решении задачи поиска оптимального маршрута их облета, что позволит оптимально расходовать имеющиеся ресурсы (время, топливо) и тем самым повысить оперативность наблюдения.
Во многих случаях для решения задачи наблюдения за наземными объектами целесообразно использование группы БЛА для обеспечения оперативности получения информации о множестве движущихся объектов, что ведет к необходимости разработки алгоритмов координации действий группы БЛА.
Важным является тот факт, что разрабатываемые алгоритмы должны быть способны рассчитывать оптимальные маршруты в течение очень короткого промежутка времени, так как будут выполняться в реальном времени в составе программного обеспечения БЦВМ.
Данная дипломная работа посвящена разработке алгоритмов поиска оптимального маршрута для БЛА при наблюдении им подвижных наземных объектов, а также алгоритмов оптимального распределения объектов между БЛА. При разработке алгоритмов учитывается динамика БЛА в условиях воздействия бокового ветра.
Исходными данными поставленной задачи являются: · характеристики БЛА;
· параметры движения БЛА (скорость движения, начальный угол курса;
· количество БЛА;
· начальное положение и характеристики движения наземных объектов;
· скорость бокового ветра;
· начальный и конечный пункты движения каждого БЛА.
Постановка задачи
Для заданных параметров объектов, БЛА и метеорологической обстановки необходимо определить оптимальную стратегию распределения объектов между БЛА и проложить оптимальный маршрут для каждого из БЛА. Критерием оптимальности следует считать минимум времени полета группы БЛА (временем полета грумы БЛА назовем время, через которое последний БЛА достигнет конечного пункта своего маршрута при условии, что все БЛА начали движение из начального пункта маршрута в один и тот же момент).
При расчете оптимального маршрута необходимо учесть возможность воздействия бокового ветра, изза которого БЛА может отклоняться от выбранного курса, что в свою очередь меняет длину траектории и оптимальность маршрута.
Анализируя исходные данные, можно сказать, что среди характеристик БЛА для реализации алгоритмов понадобятся следующие: · диапазон изменения скорости и высоты полета БЛА;
· зависимость минимального радиуса разворота от скорости полета и скорости ветра.
Также оговаривается тот факт, что на борту БЛА присутствует аппаратура фото- или видеонаблюдения наземных объектов. Исходя из того, что современные объективы фотокамер позволяют провести фотосъемку в хорошем качестве с высоты до нескольких сот метров, выберем углы обзора камеры, учитывая, что камера должна полностью охватывать зоны недосягаемости БЛА (рисунок 1). Зоны недосягаемости - это те зоны, в которые БЛА не может попасть из своего текущего положения в силу того, что его разворот производится по окружности, радиус которой определяется его характеристиками. аппарат программа беспилотный летающий
Рисунок 1. Выбор углов обзора камеры
Примем высоту полета БЛА равной 200 метров. Радиус разворота БЛА в отсутствие ветра равен 60 метрам. Исходя из этого, рассчитаем углы обзора камеры по продольной и поперечной осям самолета:
При появлении бокового ветра необходимо скорректировать высоту таким образом, чтобы для нового минимального радиуса разворота выполнялись те же условия.
1. Специальная часть
1.1 Аналитический обзор существующих методов и подходов к планированию групповых действий
Обзор существующих методов поиска оптимального маршрута при одиночном полете БЛА
В настоящее время существует множество методов решения данной задачи, таких как полный перебор, динамическое программирование, генетические алгоритмы, жадные алгоритмы, метод восхождения и многие другие. Рассмотрим некоторые из них подробнее для того, чтобы оценить, подходят ли они для решения задачи, поставленной в данном дипломном проекте.
Полный перебор
Полный перебор всех возможных вариантов является самым простым решением задачи. Этот метод решает задачу поиска оптимального маршрута «в лоб». Основой метода полного перебора является составление и расчет всех возможных последовательностей облета объектов. Данный метод всегда дает оптимальное решение задачи, однако требует для выполнения большого количества времени и вычислительных ресурсов БЦВМ. При этом с ростом числа объектов время решения задачи растет экспоненциально, так как количество возможных вариантов равно n!, где n - число объектов (рисунок 1.1.1).
Рисунок 1.1.1 Зависимость времени выполнения алгоритма от числа объектов
Сильные стороны: · простота реализации;
· найденное решение всегда оптимально.
Слабые стороны: · Колоссальное время решения задачи.
· Необходимость использования больших объемов памяти.
Генетические алгоритмы
Генетические алгоритмы - метод оптимизации, который основан на принципах, наблюдаемых в природе. Они сочетают в себе такие качества, как высокая скорость работы, малая вероятность остановки в локальных минимумах пространства поиска. Работа генетических алгоритмов основана на принципах естественного отбора и использует множество понятий и определений, заимствованных из генетики. Это такие понятия, как хромосома, ген, приспособленность, мутация, отбор, скрещивание и другие.
В начале работы алгоритма генерируется начальная популяция - набор особей, характеризуемых хромосомами. Каждая хромосома представляет собой строку. В этой строке закодирована информация о маршруте полета БЛА. Например, если у нас имеются 4 объекта, которые необходимо облететь, мы можем закодировать хромосому в виде двоичной строки таким образом, что каждые 2 бита будут представлять собой номер объекта в двоичном коде. От выбора кодировки хромосомы зачастую зависит эффективность применения генетического алгоритма. Например, в нашем случае, в результате работы алгоритма мы будем получать множество восьмибитных строк, большинство из которых не будут годиться для решения задачи, так как некоторые объекты будут учтены несколько раз, а некоторые могут быть вообще не учтены. Соответственно такой вариант кодирования можно считать не очень удачным.
После создания начальной популяции (обычно она создается случайным образом) следует отобрать некоторое число особей в качестве родителей для будущих поколений. Существует несколько алгоритмов выбора, однако самым популярным является правило рулетки. Рассмотрим его несколько подробнее.
Для каждой из особей в существующей популяции производится вычисление функции приспособленности (функция, которая является критерием оптимальности того или иного маршрута). После этого колесо рулетки разделяется на сектора, каждый из которых соответствует определенной особи, а его размер пропорциональна значению функции приспособленности этой особи. Далее, «запуская» рулетку необходимое число раз, мы отбираем особи в популяцию родителей (если сгенерированное случайное число попадает в сектор, соответствующий определенной особи, то она попадает в популяцию родителей). При этом одна и та же особь может быть выбрана в популяцию родителей несколько раз, таким образом, вероятность наиболее приспособленной особи участвовать в образовании потомства выше, чем у менее приспособленного).
После того, как популяция родителей создана, мы случайным образом отбираем двоих (или более, в зависимости от конкретной реализации алгоритма) и с некоторой вероятностью производим операцию скрещивания. Эта операция заключается в том, что хромосомы двух родителей разделяются на несколько частей (в дальнейшем будем рассматривать случай, когда хромосома разделяется на две части) в точках, называемых точками скрещивания, и обмениваются этими частями. Таким образом, мы получаем две особи следующего поколения (рисунок 1.1.2).
Рисунок 1.1.2 Операция скрещивания
Операция отбора двух родителей и скрещивания повторяется до тех пор, пока мы не наберем нужное количество особей для следующего поколения.
После окончания операции скрещивания из вновь созданной и предыдущей популяций отбирается некоторое количество лучших особей таким образом, чтобы итоговый размер популяции отобранных особей соответствовал исходному размеру.
Затем производится операция мутации. Она заключается в том, что с очень маленькой вероятностью каждый бит особи может быть изменен на противоположный (рисунок 1.1.3). Это необходимо для того, чтобы исключить такие ситуации, когда, например, во всей популяции первый бит каждой хромосомы равен нулю, и, таким образом, невозможно получить в результате скрещивания значение единицы на его месте.
Рисунок 1.1.3 Мутация
После проведения всех этих операций заканчивается одно поколение генетического алгоритма и производится проверка на условие останова. Условием останова может быть, например, количество выполненных поколений или очень маленькая изменчивость наилучшего решения в нескольких популяциях. Если условие останова не соблюдено, то все операции генетического алгоритма повторяются заново с текущей популяцией. В противном случае наилучшее решение из текущей популяции принимается в качестве оптимального [1]. Схема работы генетического алгоритма представлена на рисунке 1.1.4.
Рисунок 1.1.4 Схема работы генетического алгоритма
Сильные стороны работы ГА: · практически полная независимость от характеристик пространства поиска;
· малая зависимость от характера критерия оптимальности;
· найденное решение практически всегда является оптимальным.
Слабые стороны: · сложность реализации;
· большая зависимость от выбора варианта кодирования хромосомы.
Метод восхождения
Это один из самых простых методов поиска оптимального пути. При решении задачи с помощью этого метода сначала генерируется случайное решение, затем в него вносится некоторое изменение (меняется местами пара городов), и эти два решения сравниваются между собой. В случае если новый маршрут короче, он принимается в качестве исходного на следующем шаге работы алгоритма. Если же этот маршрут длиннее, то в качестве исходного для следующего шага принимается старый маршрут. На следующей итерации процесс повторяется. Если в течение некоторого числа итераций изменений не происходит (решение не улучшается), то процесс останавливается и текущее решение принимается в качестве оптимального.
Но у данного алгоритма имеются некоторые недостатки. В первую очередь, алгоритм эффективен только для унимодальных функций, так как при работе этого алгоритма решение всегда «идет» вверх. Таким образом, если пространство поиска простое и содержит лишь один максимум, то мы всегда сможем найти оптимальное решение с помощью данного метода (Рисунок 1.1.5). В любом другом случае велика вероятность того, что алгоритм остановится в локальном минимуме, а глобальный максимум найден не будет (Рисунок 1.1.6). [1]
Рисунок 1.1.5 Случай нахождения максимума для унимодальной функции
Рисунок 1.1.6 Случай нахождения максимума для функции с локальными максимумами
Сильные стороны: · простота реализации;
· надежность работы для унимодальных функций.
Слабые стороны: · остановка в локальных минимумах, невозможность работы в случае, если пространство поиска имеет несколько минимумов;
· неопределенное время поиска.
Динамическое программирование
При решении задачи поиска оптимального маршрута очень часто пользуются динамическим программированием. Основной его принцип заключается в том, что большая задача разбивается на некоторое количество подзадач, оптимальное решение которых, в свою очередь, может быть использовано для решения глобальной задачи.
При решении задач с помощью динамического программирования необходимо проделать три шага: 1) Разбиение задачи на подзадачи меньшего размера.
2) Нахождение решения подзадач рекурсивно, проделывая этот же алгоритм.
3) Использование полученного решения подзадач для конструирования решения глобальной задачи.
При этом каждая подзадача, в отличие, например, от метода полного перебора, решается только один раз и запоминается в специальной таблице. Значения из этой таблицы в дальнейшем используются при решении задач более высокого уровня.
При решении задачи поиска оптимального маршрута методом динамического программирования довольно часто используется алгоритм Дейкстры. Принцип работы этого алгоритма заключается в том, что каждый пункт маршрута ассоциируется с вершиной графа. Каждой вершине этого графа сопоставляется метка, значением которой является минимальное известное расстояние от начальной вершины до текущей. [2]
Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке. Пусть требуется найти расстояния от 1-й вершины до всех остальных.
Рисунок 1.1.7 Представление задачи в виде графа
Кружками обозначены вершины, линиями - пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» - длина пути. Рядом с каждой вершиной красным обозначена метка - длина кратчайшего пути в эту вершину из вершины 1.
Рисунок 1.1.8 Введение меток для каждой вершины
Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Ее соседями являются вершины 2, 3 и 6. Первый по очереди сосед вершины 1 - вершина 2, потому что длина пути до нее минимальна. Длина пути в нее через вершину 1 равна кратчайшему расстоянию до вершины 1 длина ребра, идущего из 1 в 2, то есть 0 7 = 7. Это меньше текущей метки вершины 2, поэтому новая метка 2-й вершины равна 7.
Рисунок 1.1.9
Аналогичную операцию проделываем с двумя другими соседями 1-й вершины - 3-й и 6-й.
Рисунок 1.1.10
Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Дейкстра). Вычеркнем ее из графа, чтобы отметить, что эта вершина посещена.
Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.
Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю. Соседями вершины 2 являются 1, 3, 4.
Первый (по порядку) сосед вершины 2 - вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.
Следующий сосед вершины 2 - вершина 3. Если идти в нее через 2, то длина такого пути будет = 7 10 = 17. Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.
Рисунок 1.1.11
Еще один сосед вершины 2 - вершина 4. Если идти в нее через 2-ю, то длина такого пути будет = кратчайшее расстояние до 2 расстояние между вершинами 2 и 4 = 7 15 = 22. Поскольку 22< , устанавливаем метку вершины 4 равной 22.
Рисунок 1.1.12
Все соседи вершины 2 просмотрены, замораживаем расстояние до нее и помечаем ее как посещенную.
Рисунок 1.1.13
Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3. После ее «обработки» получим такие результаты:
Рисунок 1.1.14
Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин (Это будут по порядку 6, 4 и 5).
Рисунок 1.1.15а
Рисунок 1.1.15б
Завершение выполнения алгоритма. Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й - 9, до 4-й - 20, до 5-й - 20, до 6-й - 11.
Сильные стороны: · простота реализации;
· быстрота работы;
· известное заранее время поиска.
Слабые стороны: · свойство «отсутствия последствий», то есть невозможность работы в случае подвижных объектов.
Жадный алгоритм
Существует несколько вариантов работы жадного алгоритма, но, в целом, их принцип сводится к тому, что находится оптимальное решение для каждой локальной задачи, но решение глобальной задачи может в общем случае не являться оптимальным. Для задачи поиска оптимального маршрута это вырождается в то, что следующим всегда выбирается объект, «ближайший» к текущему положению БЛА. Но в данном случае маршрут, который получается в результате, не всегда является оптимальным (Рисунок 1.1.16). [2]
Рисунок 1.1.16 Сравнение оптимального пути (черные стрелки) и пути, полученного с помощью жадного алгоритма (красные стрелки)
Как видно из рисунка 1.1.16, маршрут из начальной точки Н в конечную точку К, полученный с помощью жадного алгоритма, отличается от оптимального.
Сильные стороны: · простота реализации;
· быстрота работы;
· известное заранее время поиска.
Слабые стороны: · неоптимальное решение глобальной задачи.
Выбор алгоритма для поставленной задачи
Мы рассмотрели основные алгоритмы поиска оптимального маршрута. Проведем анализ этих методов и определим, подходят ли они для решения поставленной задачи.
Жадный алгоритм не подходит для решения в силу того, что в общем случае не дает оптимального результата.
Методы динамического программирования обладают свойством отсутствия последствий, а, значит, их нельзя применять для решения задачи с подвижными объектами в классическом исполнении.
Метод восхождения чувствителен к наличию локальных минимумов на пространстве поиска, а, следовательно, его применение тоже не будет давать оптимального результата в большинстве случаев.
Генетические алгоритмы и метод полного перебора полностью подходят для решения поставленной задачи, но генетические алгоритмы довольно сложны в исполнении, а, в силу того, что в дальнейшем в данном дипломном проекте могут быть применены нейросетевые технологии для сокращения времени работы алгоритмов, воспользуемся методом полного перебора.
Обзор существующих методов оптимизации групповых действий
На сегодняшний день наиболее известными метода являются применение мультиагентных систем и решение задачи многих коммивояжеров. Рассмотрим их подробнее.
Мультиагентные системы
Данные системы созданы для решения различных задач искусственного интеллекта, в которых присутствует несколько участников.
Агент - это нечто, способное воспринимать свое окружение через сенсоры и изменять его своими действиями.
Современный подход к искусственному интеллекту основан на понятии рационального агента, который всегда старается оптимизировать свои действия. Однако агенты редко являются одиночными системами. Чаще всего они взаимодействуют друг с другом, образуя систему, называемую мультиагентной.
Процесс принятия решения агентом происходит следующим образом. Предположим, что на каждом шаге работы системы агент может из конечного набора возможных действий A выбрать какое-то действие at. Также для принятия рационального решения агенту необходимо оценивать прошлое и будущее. Под прошлым подразумевается то, что агент воспринял какую-либо информацию и совершил какие-либо действия до текущего момента времени, а под будущим - что он ожидает и что собирается потом делать.
Функция, которая отображает набор пар наблюдение - действие до текущего момента времени в оптимальное действие в текущий момент времени называется стратегией агента
Но нахождение такой функции далеко не всегда является решаемой задачей, более того, сохранение всей истории действий требует больших объемов памяти. Поэтому необходимо использовать более простые стратегии. Например, можно использовать только текущее наблюдение для принятия решения. В этом случае агент является рефлекторным.
Однако использование такого агента может быть довольно эффективно. Во многих задачах текущее состояние окружения несет в себе всю необходимую информацию о своей истории. Про такое окружение говорят, что оно является Марковским, или несет в себе свойство Маркова.
В случае, если агент использует для принятия решения оценки будущего, необходимо выстроить прогноз об изменении окружения агента после совершения им какого-либо действия. Здесь возможны два варинта: · в детерминистическом мире модель перехода отображает единственным образом пару состояние-действие в новое состояние;
· в стохастическом мире модель перехода отображает пару состояние-действие в распределение вероятности состояний.
В качестве примера алгоритма, использующего мультиагентные системы, рассмотрим алгоритм, предложенный в [3]. Данный алгоритм основан на том, все БЛА связаны в единую сеть, внутри которой принимаются решения о распределении объектов наблюдения между ними. Как и во многих других схожих алгоритмах, принятие решения является коллективным и базируется на том, что каждый БЛА выдвигает предложение о том, к какому объекту он считает необходимым двигаться. Остальные БЛА в процессе переговоров могут принять или отвергнуть это решение.
Сам процесс принятия решения состоит в следующем. Каждый агент в течение одного цикла переговоров совершает 4 действия: · отправляет или получает предложение, · обдумывает полученное предложение, · отправляет ответ (согласие или несогласие), · принимает решение.
Каждый агент вычисляет выигрыш, полученный в том случае, если он последует за ней по следующей формуле bi(Tj) = VTJWR - St, где VTJWR - «цена» объекта, St - относительное время преследования объекта
Таким образом, для каждой цели БЛА формирует списки выигрышей, полученных от следования за каждым объектом, и рассылает другим БЛА номер того объекта, за который он получит максимальную выгоду.
На втором и третьем шагах, когда данные от всех БЛА собраны, каждый из них анализирует полученную информацию и принимает решение о согласии или несогласии и этим на основании следующих правил: · если объект выбран только одним БЛА, то данное предложение одобряется;
· если объект выбран несколькими БЛА, то согласие посылается только тому БЛА, для которого максимален выигрыш;
· один БЛА может отправить только одно согласие для каждой цели;
· если все соседи данного БЛА (то есть те БЛА, от которых он находится в непосредственной близости) согласны с его целью, он получает право на принятие решения о целесообразности следования до его текущей цели;
Четвертый шаг заключается в анализе полученных ответов и принятии решения. Если БЛА получил согласия от всех соседей, он выполняет запланированное действие. Если он получил отказ хотя бы от одного из соседей, он участвует в следующем цикле переговоров. Если же БЛА получил отказ от всех своих соседей, он выполняет задачу поиска новых объектов.
Выделим сильные и слабы стороны данного подхода
Сильные стороны: · постоянное взаимодействие между агентами;
· коллективное принятие решения всеми агентами.
Слабые стороны: · в случае необходимости использования большой истории действий возрастает ресурсоемкость данного подхода;
· агент зачастую действует по аналогии с жадным алгоритмом, а значит его решение в общем случае нельзя считать оптимальным;
· необходимость использования стохастических прогнозов в случае использования информации об оценках будущей реакции окружения да действия агентов.
Задача многих коммивояжеров
В своей исторической формулировке задача коммивояжера заключается в том, чтобы найти оптимальный путь торговца между некоторым количеством пунктов маршрута из начальной точки в конечную. При этом в исходной задаче коммивояжера рассматривается только один торговец. В задаче многих коммивояжеров рассматривается поиск пути для нескольких торговцев, причем каждый пункт маршрута должен быть посещен один раз одним из торговцев.
Очевидно, что вместо торговцев в данной задаче также могут быть представлены БЛА, которым нужно облететь некоторое количество наземных объектов.
Существует множество подходов к решению данной задачи, среди которых есть только два универсальных - это генетические алгоритмы и метод полного перебора, которые будут описаны в пункте 1.1.2. Остальные же методы решения данной задачи решают его лишь приближенно в общем случае. Рассмотрим один из таких методов - метод кластеризации.
Данный метод описан в работе [4]. В данной работе предлагается сначала провести кластеризацию всех объектов по методу k-средних. Этот метод заключается в том, что все объекты разбиваются на количество кластеров k, равное количеству БЛА следующим образом: · случайным образом на поле решения задачи выбрасывается k точек, которые являются центрами кластеров (центроидами);
· каждый объект заносится в кластер того центроида, к которому он находится ближе всего;
· после того, как все объекты занесены в кластеры, позиции центроидов пересчитываются таким образом, чтобы суммарное расстояние до всех объектов оказалось минимальным;
· шаги 2 и 3 повторяются до тех пор, пока центроиды не перестанут передвигаться.
Таким образом, алгоритм выделяет группы объектов, которые максимально схожи внутри себя, но при этом максимально различны между собой.
После проведения кластеризации к объектам внутри каждого кластера применятся алгоритм «упаковки», суть которого заключается в том, чтобы перевести координаты каждого из объектов в полярные, а замет отсортировать их по углу поворота, а затем по радиусу в порядке возрастания. Таким образом, получается некоторая последовательность облета объектов, которая будет оптимизироваться на следующих шагах.
К полученной последовательности применяется алгоритм имитации отжига (алгоритм поиска минимума некоторой функции), целевой функцией которого является время облета объектов в заданной последовательности.
Последним шагом данного метода является применение алгоритма поиска «Tabu search», суть которого сводится к тому, что в случае, если алгоритм находит решение, которое потенциально является оптимальным, он «запрещает» его, и «разрешает» движение в сторону максимизации времени полета БЛА. Таким образом, алгоритм препятствует «застреванию» поиска в локальных минимумах.
Сильные стороны: · применение множества способов препятствования попаданию в локальные минимумы.
Слабые стороны: · исключение взаимодействия между БЛА;
· применяется сразу несколько методов поиска и оптимизации, что существенно увеличивает время расчета;
· метод применим только для неподвижных объектов.
1.2 Разработка модели одиночных действий БЛА
Решается задача поиска оптимального маршрута облета движущихся объектов одним БЛА с учетом ветра. Разобьем ее на несколько подзадач.
1. Поиск оптимального маршрута облета неподвижных объектов одним БЛА без учета ветра;
2. Учет подвижности объекта;
3. Учет ветра;
Для решения задачи 1 запишем алгоритм перелета БЛА в точку с определенными координатами. Исходными данными для него являются: 1. Начальные координаты БЛА;
2. Начальный угол курса БЛА;
3. Координаты объекта;
4. Минимальный радиус разворота БЛА;
5. Координаты точки.
Проиллюстрируем это на рисунке 1.2.1.
Рисунок 1.2.1 Начальные данные для задачи, где ХЛА, УЛА - начальные координаты БЛА, ХО, УО - начальные координаты объекта, R - минимальный радиус разворота БЛА, стрелкой указано начальное направление полета БЛА.
Для построения оптимальной траектории полета до точки разобьем полет на 2 этапа: 1. Полет по дуге радиусом R;
2. Полет по прямой до объекта.
Легко показать, что второй этап будет заключаться в полете по касательной, проведенной из точки (XO, YO) к ближайшей из окружностей, ограничивающих зону недосягаемости БЛА.
Найдем точку касания. Для этого обратимся к рисунку 1.2.2.
Рисунок 1.2.2 Нахождение точки касания
Найдем угол :
Теперь, зная этот угол, легко найти координаты точки касания:
После того, как мы определили точки касания, выберем из них ту, при полете через которую мы будем двигаться в сторону объекта. Для этого введем несколько дополнительных углов (рисунок 1.2.3).
Рисунок 1.2.3 Выбор точки касания
Здесь - углы между векторами скорости БЛА и осью Х в точках касания.
- углы между прямыми, соединяющими точки касания с объектом, и осью X.
Далее, из двух пар - и - выбирается та, углы в которой совпадают по величинам. Это и будет искомая точка, через которую БЛА должен полететь, чтобы выйти на участок полета по прямой до объекта.
Теперь определим длину траектории, для чего введем еще один угол , характеризующий угол поворота вектора скорости от начального положения до положения, которое он займет в выбранной точке касания (Рисунок 1.2.4).
Рисунок 1.2.4 Нахождения угла
Теперь длину траектории можно определить как
Аналогичным образом находим длину траектории в случае полета по второй окружности. После того, как получены длины траекторий при полете по двум окружностям, выбираем ту из траекторий, длина которой будет минимальна.
Задачу учета подвижности объекта будем решать следующим образом. Мы предполагаем, что в течение того времени, за которое БЛА сблизится с объектом, последний будет двигаться прямолинейно с постоянной скоростью. Таким образом, мы можем найти точку, по прибытии в которую БЛА «встретится» с объектом. Иллюстрация этого процесса приведена на рисунке 1.2.5.
Рисунок 1.2.5 Поиск точки упреждения
Для нахождения точки упреждения мы можем записать следующие функции: 1. Функция, определяющая время движения объекта до одной из точек, расположенных на прямой, по которой движется объект;
2. Функция, определяющая время движения БЛА до вышеуказанной точки.
Таким образом, мы получаем две функции, точка пересечения которых является решением поставленной задачи (рисунок 1.2.6).
Рисунок 1.2.6 Функциональные зависимости времени перелета в точку нахождения объекта от расстояния, пройденного объектом
Теперь мы легко можем рассчитать координаты точки встречи БЛА и объекта и время перелета в эту точку.
Для учета влияния ветра при поиске оптимальной траектории следует ввести некоторые ограничения на угол крена (т.е. оставить «запас» для компенсации влияния ветра на разворотах). В конечном счете, это скажется лишь на минимальном радиусе разворота БЛА, т.к. все вышеизложенные алгоритмы способны решить задачу поиска оптимального маршрута при заданном радиусе разворота.
Теперь, когда готовы все алгоритмы поиска минимальной длины траектории перелета из текущего положения в определенную точку, мы можем решить задачу поиска оптимального маршрута БЛА по облету группы движущихся объектов. Эту задачу мы будем решать с помощью метода полного перебора.
Для этого построим полное дерево, в котором расположим все возможные комбинации облета объектов. Таким образом, например, для трех объектов получим дерево, изображенное на рисунке 1.2.7.
Рисунок 1.2.7 Пример дерева для трех объектов
На этом рисунке в кружках показаны номера объектов, которые на данном шаге должен пролететь БЛА.
Также следует отметить, что в случае, если при пролете ЛА над очередным объектом, в области в области обзора бортовой фотокамеры оказываются другие объекты, то они сразу же обрабатываются, а время перелета до этих объектов считается равным нулю.
Теперь, используя вышеописанные алгоритмы, найдем длины всех маршрутов и выберем из них минимальную. Этот маршрут и будет искомым.
Данный алгоритм используется для решения задачи, относящейся к классу так называемых NP-полных задач, поэтому время, затрачиваемое на ее решение, растет экспоненциально с ростом числа входных данных. Из этого следует, что данный алгоритм не подходит для включения его в состав программного обеспечения БЦВМ. Известно, что нейронные сети являются мультипараллельными структурами, позволяющими за минимальное время решать задачи аппроксимации сложных нелинейных зависимостей. Поэтому в работе предлагается заменить трудоемкий и вычислительно затратный алгоритм полного перебора на быстродействующую нейронную сеть.
1.3 Разработка нейронной сети - аналога модуля «Поиск оптимального маршрута для одного БЛА»
Для замены модуля «Поиск оптимального маршрута для одного БЛА» будем использовать нейронную сеть с прямыми связями (feedforward network) с одним скрытым слоем, на вход которой будут подаваться следующие значения: · относительные координаты по оси X для каждого объекта (Дх);
· относительные координаты по оси Y для каждого объекта (Ду);
· относительный угол курса для каждого объекта (Дш);
· скорость каждого объекта (Vi);
· скорость БЛА (V);
· минимальный радиус разворота БЛА (Rmin).
Количество нейронов будет выбираться экспериментальным путем. Количество выходных нейронов будет соответствовать количеству объектов, на которое данная нейронная сеть рассчитана. Выходные значения нейронной сети будут формироваться таким образом, что, тот выход, который соответствует следующему в маршруте объекту (то есть тому объекту, к которому сейчас необходимо двигаться БЛА), будет переходить в активное состояние (значение этого выхода станет равным «1»), а все остальные выходы останутся в пассивном состоянии (их значение будет установлено в «0»). Данная нейронная сеть изображена на рисунке 1.3.1.
Рисунок 1.3.1 Нейронная сеть для замены модуля поиска оптимального маршрута
Вследствие того, что нейронная сеть выдает не весь маршрут, а только номер следующего его пункта, процесс нахождения оптимального маршрута теперь будет проходить в несколько итераций следующим образом. Сначала вычисляются относительные координаты всех объектов относительно текущего положения БЛА. Затем вычисляется время t, необходимое для подлета к этому объекту, а сам объект исключается из дальнейшей обработки. После этого рассчитывается новое положение всех объектов, которое они займут через время t. После этого запускается следующая итерация алгоритма для обновленных значений координат объектов. [5]
1.4 Разработка модели групповых действий БЛА
Теперь необходимо решить задачу распределения объектов между несколькими БЛА. Для простоты рассмотрим случай распределения объектов между двумя БЛА. Для этого назначим каждому БЛА область ответственности, как показано на рисунке 1.4.1.
Рисунок 1.4.1 Разбиение области задач на части. К1, К2 - конечные пункты маршрута первого и второго БЛА соответственно После этого проанализируем, какие из объектов пересекут линию раздела областей за заданный промежуток времени ТК и разделим все объекты на три группы: 1) объекты, принадлежащие области ответственности первого БЛА;
2) объекты, принадлежащие области ответственности второго БЛА;
3) Спорные объекты, которые за время ТК пересекли линию раздела областей ответственности, отведенных каждому БЛА.
Далее примем, что начальные и конечные пункты маршрута каждого БЛА расположены в соответствии с рисунком 8 (точные значения расстояний и углов могут меняться в соответствии с текущей навигационной обстановкой, но они должны быть точно известны на момент начала работы алгоритма).
Таким образом, объекты, принадлежащие области каждого БЛА, будут закреплены за этим БЛА, а спорные объекты будут распределены между ними таким образом, чтобы минимизировать время облета всех объектов группой БЛА.
Рисунок 1.4.2 Пример распределения спорных объектов
Для оптимального распределения объектов между БЛА, объекты, принадлежащие каждому БЛА, занесем в соответствующий список, а из спорных объектов составим все возможные комбинации распределения между БЛА.
Далее, будем присоединять списки с вариантами распределения спорных объектов к существующим спискам для каждого БЛА и применять к ним алгоритм поиска оптимального пути, описанный в пункте 1.2. После анализа всех составленных комбинаций, выбираем из них ту, которой соответствует наилучшее значение критерия оптимальности. Полученная комбинация и есть искомый вариант распределения объектов между БЛА.
На рисунке 1.4.3 изображена общая схема работы алгоритмов поиска оптимального маршрута.
Рисунок 1.4.3 Общая схема работы системы
1.5 Разработка программы, моделирование системы и анализ резул
Список литературы
Основными документами, нормирующими параметры видеодисплейных терминалов (ВДТ) являются САНПИН 2.2.2/2.4.2198-07 (изменение №1 к САНПИН 2.2.2/2.4.1340-03) «Гигиенические требования к видеодисплейным терминалам, персональным электронно-вычислительным машинам и организация работы» и ГОСТ Р 50948-2001 «Средства отображения информации индивидуального пользования. Общие эргономические требования и требования безопасности».
САНПИН 2.2.2/2.4.1340-03 регламентирует следующие параметры изображения ВДТ: · Яркость белого поля и ее колебания в пределах рабочего поля
· Контрастность - отношение максимальной яркости изображения к минимальной с учетом отражений, возникающих за счет внешней освещенности экрана.
· Временная нестабильность изображения - непреднамеренное изменение во времени яркости изображения на экране дисплея
· Пространственная нестабильность изображения - непреднамеренные изменения положения фрагментов изображения на экране.
Согласно этому документу, визуальные параметры видеодисплейных терминалов должны удовлетворять требованиям, приведенным в таблице 3.2.1. [7]
Таблица 3.2.1 Визуальные параметры ВДТ, контролируемые на рабочих местах по САНПИН 2.2.2/2.4.1340-03
N Параметры Допустимые значения
1 Яркость белого поля Не менее 35 кд/МІ
2 Неравномерность яркости рабочего поля Не более -20%
3 Контрастность (для монохромного режима) Не менее 3:1
4 Временная нестабильность изображения (мелькания) Не должна фиксироваться
5 Пространственная нестабильность изображения (дрожание) Не более 2 х 10 (-4L), где L - проектное расстояние наблюдения, мм
ГОСТ Р 50948-2001 охватывает большее количество параметров ВДТ и выводимой на них информации. В этом документе рассмотрены следующие пункты, касающиеся эргономических характеристик ВДТ: · Требования к качеству восприятия информации, отображаемой на дисплеях;
· Эргономические требования к цветовым параметрам.
· Требования безопасности к визуальным параметрам.
Далее рассмотрим подробнее некоторые пункты этого документа.
Требования к качеству восприятия информации, отображаемой на дисплеях
Для точного считывания информации и обеспечения комфортных условий ее восприятия работа с дисплеями должна проводиться при таких сочетаниях значений яркости и контраста изображения, внешней освещенности экрана, углового размера знака и угла наблюдения экрана, которые входят в оптимальные или предельно допустимые (при кратковременной работе) диапазоны.
Допустимые диапазоны значений внешней освещенности экрана, углового размера знака и угла наблюдения экрана для типов дисплеев, на которые этот стандарт распространяется, - по ГОСТ Р 50923; для других типов дисплеев - по ТУ на конкретный тип дисплея.
В этой части ГОСТ Р 50923-96 предъявляет к дисплею следующие требования: · Дисплей на рабочем месте оператора должен располагаться так, чтобы изображение в любой его части было различимо без необходимости поднять или опустить голову;
· Дисплей на рабочем месте должен быть установлен ниже уровня глаз оператора. Угол наблюдения экрана оператором относительно горизонтальной линии взгляда не должен превышать 60°;
· Отношение яркостей в зоне наблюдения должно быть не более 10:1.
На данном рабочем дисплей расположен так, что нет необходимости перемещаться относительно него, угол между горизонтальной линией и линией взгляда не превышает 30°, а отношение яркостей не превышает 7:1.
Эргономические требования к цветовым параметрам
Данный пункт регламентирует: · Максимальное количество цветов, при котором человек может комфортно воспринимать информацию.
Число цветов, одновременно отображаемых на экране дисплея, должно быть минимальным. Для точной идентификации цвета каждый заданный по умолчанию набор цветов должен включать не более 11 цветов, а при необходимости проведения быстрого поиска, основанного на распознавании цветов, следует применять не более 6 различных цветов;
· Благоприятные и неблагоприятные для восприятия цвета.
Насыщенные крайние цвета видимого спектра приводят к нежелательным эффектам глубины изображаемого пространства и не должны применяться для изображений, которые требуют непрерывного просмотра или чтения.
Здесь следует также отметить еще некоторые пожелания, не приведенные в рассматриваемом документе, но оказывающие довольно значимое влияние на качество восприятия информации, выдаваемой на дисплей ВДТ. При выборе цветовой гаммы предпочтение следует отдавать зелено-голубой части спектра. Белый, зеленый и оранжевый цвета дают одинаковую четкость при негативной полярности. При наблюдении с больших расстояний зеленый и оранжевый цвета видны лучше, тогда как белый несколько способствует уменьшению числа ошибок чтения. Если учитывать цветовую слепоту и цветное бинокулярное зрение, то красный и голубой цвета не рекомендуются.
· Благоприятные и неблагоприятные сочетания цветов фона и текста.
Для чтения текстов, буквенно-цифровых знаков и символов при отрицательной полярности изображения не следует применять синий и красный цвета спектра на темном фоне и красный цвет спектра на синем фоне, а для чтения текстов, буквенно-цифровых знаков и символов при положительной полярности изображения не следует применять синий цвет спектра на красном фоне. Для точного распознавания и идентификации цветов должны применяться цветное изображение переднего плана на ахроматическом фоне или ахроматическое изображение переднего плана на цветном фоне.
На рабочем месте одновременно используется не более 2-3 цветов при просмотре документов и написании программ. Чаще всего используются сочетания черного текста на белом фоне или желтого текста на синем фоне. При просмотре цветных изображений чаще всего используется белый фон.
Требования безопасности к визуальным параметрам
Здесь приведены требования, предъявляемые к яркости, контрастности, временной и пространственной нестабильности изображения, искажениям изображения по рабочему полю, а так же к характеристикам знаков (букв, цифр). Все эти требования сведены в таблице 3.2.2.
Приведем некоторые определения, использующиеся в данном пункте.
Яркость знака - яркость, измеренная в центре матрицы знака при всех включенных элементах изображения.
Проектное расстояние наблюдения - расстояние между глазом оператора и центром знака, отображенного на экране, указанное в нормативной документации на дисплей.
Таблица 3.2.2 Визуальные параметры ВДТ, контролируемые на рабочих местах по ГОСТ Р 50948-2001
N Параметры Допустимые значения
1 Яркость знака Не менее 35 кд/МІ для дисплеев на ЭЛТ и не менее 20 кд/МІ для плоских дискретных экранов
2 Неравномерность яркости рабочего поля Не более -20%
3 Неравномерность яркости элементов знака Не более -20%
4 Яркостный контраст изображения Не менее 3:1 (для плоских дискретных экранов при угле наблюдения от минус 40° до плюс 40°)
5 Яркостный контраст внутри знака и между знаками Не менее 3:1
6 Ширина контура знака от 0,25 до 0,5 мм
7 Степень несведения цветов в любом месте многоцветного экрана для дисплеев на ЭЛТ не более 3,4 у при проектном расстоянии наблюдения*
8 Временная нестабильность изображения (мелькания) Не должна быть зафиксирована**.
9 Амплитуда смещения изображения (пространственная нестабильность изображения - дрожание) не более 2Ч10-4l, где l - проектное расстояние наблюдения, мм
10 Изменение размеров однотипных знаков по рабочему полю Не более ±5% высоты знака
11 Максимальная разность длин строк текста на рабочем поле Не более 2% средней длины строки
12 Максимальная разность длин столбцов текста на рабочем поле не более 2% средней длины столбца
13 Отклонение формы рабочего поля от прямоугольника по вертикали*** Не более 0,02
14 Отклонение формы рабочего поля от прямоугольника по горизонтали*** Не более 0,02
15 Отклонение формы рабочего поля от прямоугольника по диагонали*** Не более 0,04
* Если в документации на дисплей не оговорено проектное расстояние наблюдения, то его принимают равным 50 см для дисплеев с размером экрана по диагонали 14» - 17» и 75 см - для экранов 19» - 21».
** Для дисплеев на ЭЛТ частота обновления изображения должна быть не менее 75 Гц при всех режимах разложения, гарантируемых нормативной документацией на конкретный тип дисплея и не менее 60 Гц для дисплеев на плоских дискретных экранах.
*** Расчетные формулы для отклонений рабочего поля: по вертикали: , где Н1 - значение длины крайнего левого столбца;
H2 - значение длины крайнего правого столбца;
по горизонтали:
, где B1 - значение длины верхней строки;
B2 - значение длины нижней строки;
по диагонали: , где D1, D2 - значения длин диагоналей на рабочем поле.
На рабочем месте использовался дисплей Acer AL1916 (размер диагонали - 19»). Его настройки были выставлены следующим образом: Контрастность: 50% от максимальной для данного дисплея;
Исходя из размера диагонали дисплея, величина проектного расстояния равна 75 см.
Проведем необходимые расчеты и измерения и занесем результаты в таблицу 3.2.3.
Таблица 3.2.3 Результаты измерений и расчетов визуальных параметров ВДТ
N Параметры Допустимые значения
1 Яркость знака Не менее 26,5 кд/МІ
2 Неравномерность яркости рабочего поля 12,3%
3 Неравномерность яркости элементов знака 6,5%
4 Яркостный контраст изображения Не менее 10:1 (для плоских дискретных экранов при угле наблюдения от минус 135° до плюс 135°)
5 Яркостный контраст внутри знака и между знаками Не менее 10:1
6 Ширина контура знака 0,294 мм
7 Временная нестабильность изображения (мелькания) Не фиксируется
8 Амплитуда смещения изображения (пространственная нестабильность изображения - дрожание) Не фиксируется
Также следует заметить, что при проведении теста на качество антибликового покрытия отраженная яркость не превышала 0,2 кд/МІ, что составляет менее 1% минимальной яркости рабочего поля. [8]
3.3 Улучшение подачи информации оператору
Выше были рассмотрены требования, обеспечивающие комфортную для глаз работу оператора ПЭВМ. Таким образом, оператор может работать за ВДТ продолжительное время без утомления и вреда для здоровья. Рассмотрим теперь некоторые особенности восприятия информации в целом.
Глаз человека, воспринимающий излучение, можно характеризовать следующими признаками: · энергетические (диапазон воспринимаемых яркостей, в том числе дающих ощущение ослепления, контрастность);
· информационные - пропускная способность;
· пространственные - острота и поле зрения, объем восприятия;
· временные - латентный период реакции, длительность инерции ощущения, критическая частота мелькания, время адаптации, длительность информационного поиска.
Как видно, нормативы, приведенные в ГОСТ Р 50948-2001 и САНПИН 2.2.2/2.4.1340-03 затрагивают лишь первый, третий и четвертый признаки. Однако, принимая во внимание оставшийся информационный признак, а так же частично нерассмотренный пространственный, можно существенно улучшить продуктивность и качество работы оператора ПЭВМ, тем самым, снизив время его пребывания за ВДТ, а, следовательно, и воздействие вредных факторов.
Рассмотрим более подробно методы, позволяющие оптимизировать восприятие информации, выдаваемой на дисплей ВДТ, выделить наиболее значимые ее части и уменьшить время поиска необходимой информации среди всей массы данных.
Активизация внимания
Термин «внимание» можно определить как способность человека сосредотачиваться на определенной области дисплея и находящемся в этой области фрагменте текста или образе (объекте). Активизация внимания - это своего рода изменение его характеристик, способствующее повышению эффективности восприятия информации, предъявляемой оператору. Довольно эффективным методом активизации внимания являются логические ударения. Рассмотрим их немного подробнее.
Логические ударения
Логическими ударениями принято называть психолого-аппаратные приемы, направленные на привлечение внимания пользователя к определенному объекту. Психологическое действие логических ударений связано с уменьшением времени зрительного поиска и фиксации оси зрения по центру главного объекта. Наиболее часто используемыми приемами для создания логических ударений являются: изображение главного объекта более ярким цветом, изменение размера, яркости, расположения или выделение проблесковым свечением, применение различных типов и цветов шрифта.
Например, в случае ошибки при написании программы, компилятор сообщает «В функции fprintf() пропущена скобка». При этом больше никакой информации не приводится (рисунок 3.3.1). На поиск данной ошибки уходит несколько секунд. Если же подсветить строку, в которой допущена ошибка другим цветом, то на поиск ошибки программист практически не затратит времени (рисунок 3.3.2).
Рисунок 3.3.1 Отсутствие логического ударения
Рисунок 3.3.2 Логическое ударение в виде выделения цветом
Количественной оценкой логического ударения является его интенсивность. Интенсивность зависит от соотношения цвета и яркости объекта по отношению к фону, от изменения относительных размеров объекта по отношению к размерам предметов фона изображения. Наилучшим является выделение либо более ярким, либо более контрастным цветом, хуже - выделение проблесковым свечением, изменением размера или яркости.
Для привлечения внимания к объекту возможно использование нескольких логических ударений одновременно (например, сопровождение ошибки звуковым сигналом помимо выделения цветом). Тогда интенсивность логического ударения объекта будет равна сумме этих логических ударений. Одновременное выделение нескольких объектов логическими ударениями с близкой интенсивностью приводит к рассеиванию внимания и, как следствие, к быстрому развитию утомления оператора.
После сосредоточения внимания на определенном объекте следует попытаться передать его содержание средствами, как можно более понятными для человека. Как известно, одним из таких средств является графическое представление материала.
Графическое представление
Человеческий глаз в реальном мире все время воспринимает какие-либо зрительные образы, буквенно-цифровое представление информации для него непривычно. Поэтому, например, результаты каких-либо опытов следует выводить на дисплей в виде графиков. Это значительно ускоряет восприятие и обработку информации мозгом. Недостатком такой формы представления является относительная неточность, поэтому графики можно дополнять таблицами, если это необходимо. Следует так же обратить внимание на то, что человеческий мозг, в первую очередь, анализирует контуры предоставленного ему изображения. Исходя из этого, наиболее оптимальной формой представления функциональных зависимостей являются графики в виде непрерывных линий.
Сравним, например, вывод функциональной зависимости в виде таблицы и графика и поиск ее максимума в определенном интервале (Рисунок 3.3.3). Для поиска максимума в табличных данных затрачивается различное время (от нескольких секунд до нескольких минут в зависимости от количества информации), а для аналогичного анализа графика - менее секунды.
Рисунок 3.3.3 Сравнение табличного и графического представления
Аналогичным образом, описания каких-либо структур лучше приводить в виде структурных схем или диаграмм, а алгоритмов - в виде блок-схем.
Следует также обратить внимание на тот факт, что в процессе восприятия человеку свойственно отвлекаться от текущей задачи и концентрироваться на фоновых мыслях, зачастую не имеющих непосредственного отношения к текущей работе. Время возврата к выполняемой задаче сугубо индивидуально и зависит от множества субъективных факторов. Но наличие внешних раздражителей существенно сокращает этот период, тем самым, повышая производительность работы. Таким образом, необходимо помимо концентрирования внимания оператора на отдельных объектах, еще и правильно выстраивать сценарий (последовательность) подачи информации. Это способствует вхождению оператора в правильный рабочий режим, выработке навыков правильной организации работы с воспринимаемым материалом.
И, наконец, при построении таких систем выдачи информации следует так же учитывать то, что для каждого человека процесс активизации внимания является сугубо индивидуальным, поэтому необходимо учитывать возможность изменения сценариев с тем, чтобы каждый оператор мог настроить их для наиболее эффективной работы. [9]
4. Технологическая часть
Данный дипломный проект посвящен разработке интеллектуальной системы планирования маршрута облета группой беспилотных летательных аппаратов (БЛА) подвижных наземных объектов. Основная задача дипломного проекта - разработка программного продукта, позволяющего находить оптимальную последовательность облета наземных подвижных объектов, а так же корректировать ее в процессе полета с учетом вновь получаемой информации об объектах наблюдения. Критерием оптимальности маршрута было выбрано время полета. В ходе работы были исследованы уже существующие алгоритмы поиска кратчайшего пути, получены сведения об их недостатках и достоинствах, которые в дальнейшем были применены при разработке алгоритма, использованного для построения программного продукта, представленного в дипломном проекте.
Реализация данного алгоритма была выполнена на ЭВМ на высокоуровневом языке программирования Matlab в среде Matlab R2008a с использованием стандартных библиотек C/C .
Ввиду того, что в данном дипломном проекте требуется создание программного продукта высокого качества, рассмотрим в этом разделе такой вопрос, как технология создания, тестирования и отладки программного обеспечения.
4.1 Понятие технологии программирования
В современном мире всеобщей компьютеризации и информации требования, предъявляемые к программному обеспечению (ПО) и вообще к программным продуктам (ПП) весьма высоки. В связи с этим обеспечение удовлетворяющих пользователя потребительских качеств программы, таких как надежность, быстродействие, соответствие заявленным возможностям, полнота документации, возможности расширения, развития без строгого соблюдения определенной технологии практически невозможно.
Технология программирования в широком смысле - совокупность абсолютно всех технологических процессов создания программного средства (ПС) от момента зарождения идеи о данном ПС до составления необходимой документации. [10]
4.2 Жизненный цикл программного продукта
В основе разработки и дальнейшего применения программного обеспечения пользователем лежит понятие жизненного цикла, который, в сущности, является моделью его создания и использования, отражающей различные состояния, начиная с момента осознания необходимости появления данного ПО и заканчивая моментом его полного выхода из употребления.
Существуют несколько моделей жизненного цикла (ЖЦ), каждая из которых определяет различную методологию создания систем, тем не менее все без исключения модели ЖЦ включают в себя пять этапов и связей между ними с детальным описанием действий, моделей и результатов каждого этапа. Приведем названия и кратное содержание каждого этапа в соответствии с ГОСТ 19.102-77.
1. Техническое задание: · постановка задачи;
· выбор критериев эффективности;
· проведение предварительных научно-исследовательских работ (НИР);
· разработка ТЗ.
2. Эскизный проект: · структура входных и выходных данных;
· уточнение методов решения;
· общий алгоритм;
· разработка документации эскизного проекта.
3. Технический проект: · уточнение структуры входных и выходных данных;
· разработки алгоритмов;
· формы данных;
· семантика и синтаксис языка;
· структура программы;
· конфигурация технических средств;
· план работ.
4. Рабочий проект: · программирование и отладка;
· разработки документации;
· подготовка и проведение испытаний;
· корректировка программы и документов по итогам испытаний.
5. Внедрение: · передача программы и документов для сопровождения;
· оформление акта;
· передача в Фонд алгоритмов и программ (ФАП).
Рассмотрим наиболее распространенные модели жизненного цикла ПО в хронологическом порядке их появления.
Каскадная модель
Эта модель является первой по времени появления. Последовательность выполнения ее этапов показана на рисунке 4.2.1.
Рисунок 4.2.1. Каскадная модель
Она характеризуется следующими основными особенностями: · последовательным выполнением входящих в ее состав этапов;
· окончанием каждого предыдущего этапа до начала следующего;
· отсутствием временного перекрытия этапов;
· отсутствием (или определенным ограничением) возврата к предыдущим этапам;
· наличием результата только в конце разработки.
Выявление и устранение ошибок в каскадной модели производится только на стадии тестирования, которая может растянуться во времени или вообще никогда не завершиться. [11]
Итерационная модель
Эта модель стала следующей стадией развития теории проектирования ПО. По-другому ее еще называют поэтапной моделью с промежуточным контролем. Основной ее особенностью является наличие обратных связей между этапами, вследствие чего появляется возможность проведения проверок и корректировок проектируемой системы на каждой стадии разработки. В результате трудоемкость отладки по сравнению с каскадной моделью существенно снижается.
Рисунок 4.2.2 Итерационная модель
Итерационность модели проявляется в обработке ошибок, выявленных промежуточным контролем. Если на каком-либо этапе в ходе промежуточной проверки обнаружена ошибка, допущенная на более ранней стадии разработки, необходимо повторить весь цикл работ этой стадии. При этом анализируются причины ошибки и корректируются в случае необходимости исходные данные этапа или его содержание.
Но в том случае, если в процессе разработки изменятся начальные требования, итерационная модель окажется неэффективной. [11]
Инкрементная модель
Инкрементная модель является классическим примером инкрементной стратегии конструирования. Она объединяет элементы последовательной каскадной модели с итерационной философией.
Каждая линейная последовательность здесь вырабатывает поставляемый инкремент ПО. Например, ПО для обработки слов в 1-м инкременте реализует функции базовой обработки файлов, функции редактирования и документирования; во 2-м инкременте - более сложные возможности редактирования и документирования; в 3-м инкременте - проверку орфографии и грамматики; в 4-м инкременте - возможности компоновки страницы.
Первый инкремент приводит к получению базового продукта, реализующего базовые требования (правда, многие вспомогательные требования остаются нереализованными).
План следующего инкремента предусматривает модификацию базового продукта, обеспечивающую дополнительные характеристики и функциональность.
По своей природе инкрементный процесс итеративен, но, в отличие от итерационной, инкрементная модель обеспечивает на каждом инкременте работающий продукт. [12]
Спиральная модель
Данная модель поддерживает итерации поэтапной модели, но особое внимание уделяется начальным этапам проектирования: анализу требований, проектированию спецификаций, предварительному проектированию и детальному проектированию.
Рисунок 4.2.3. Спиральная модель
Каждый виток спирали соответствует поэтапной модели создания фрагмента или версии ПО, уточняются цели и требования к программному обеспечению, оценивается качество разработанного фрагмента или версии и планируются работы следующего витка разработки. Таким образом, углубляются и конкретизируются все детали проектируемого ПО, в результате получается продукт, удовлетворяющий всем требованиям заказчика. [12]
Компонентно-ориентированная модель
Компонентно-ориентированная модель является развитием спиральной модели и тоже основывается на эволюционной стратегии конструирования. В этой модели конкретизируется содержание квадранта конструирования - оно отражает тот факт, что в современных условиях новая разработка должна основываться на повторном использовании существующих программных компонентов.
Программные компоненты, созданные в реализованных программных проектах, хранятся в библиотеке. В новом программном проекте, исходя из требований заказчика, выявляются кандидаты в компоненты. Далее проверяется наличие этих кандидатов в библиотеке. Если они найдены, то компоненты извлекаются из библиотеки и используются повторно. В противном случае создаются новые компоненты, они применяются в проекте и включаются в библиотеку.
Достоинства компонентно-ориентированной модели: · уменьшает на 30% время разработки программного продукта;
· уменьшает стоимость программной разработки до 70%;
· увеличивает в полтора раза производительность разработки.
Итак, основными этапами разработки ПО являются: 1. Анализ требований;
2. Проектирование;
3. Реализация;
4. Тестирование и отладка;
5. Сопровождения
Кроме того, сюда в настоящее время сюда так же добавился такой пункт, как сертификация или аттестация ПО. [12]
Рассмотрим каждый из этих пунктов подробнее.
Анализ требований и определение спецификаций
Один из наиболее ответственных этапов создания программного продукта - этап постановки задачи. На этом этапе принимаются важные решения относительно функций создаваемого ПО, эксплуатационных ограничений, накладываемых на него. Производится выбор архитектуры, среды разработки ПО, интерфейса пользователя и т.д. От этого выбора будет зависеть качество и стоимость конечного программного продукта.
Существует два вида требований, рассматриваемых на данном этапе: 1. Функциональные требования описывают сервисы, предоставляемые программной системой, ее поведение в определенных ситуациях, реакцию на те или иные входные данные и действия, которые система позволит выполнять пользователям. При написании функциональных требований необходимо учитывать, что чем они будут подробнее, тем более точная оценка работ по срокам и стоимости будет произведена перед разработкой технического задания на создание программного обеспечения. Функциональные требования документируются в спецификации требований к программному обеспечению, где описывается как можно более полно ожидаемое поведение системы.
2. Эксплуатационные требования определяют характеристики разрабатываемого программного обеспечения, проявляемые в процессе его использования. К таким характеристикам относят: · правильность - функционирование в соответствии с техническим заданием. Это требование является обязательным для всякого программного продукта, но поскольку никакое тестирование не дает гарантии 100%-ной правильности, речь может идти об определенной вероятности наличия ошибок. Вероятность сбоя системы управления космическими полетами должна быть близка к нулю;
· универсальность - обеспечение правильной работы при любых допустимых данных и защиты от неправильных данных. Так же как в предыдущем случае, доказать универсальность программы невозможно, поэтому имеет смысл говорить о степени ее универсальности;
· надежность (помехозащищенность) - обеспечение полной повторяемости результатов, т.е. обеспечение их правильности при наличии различного рода сбоев. Источниками помех могут являться технические и программные средства, а также люди, работающие с этими средствами. В настоящее время существует достаточное количество способов избежать потерь информации при сбоях. Например, прием «создания контрольных точек», при котором сохраняются промежуточные результаты, что позволяет после программы продолжить работу с данными, записанными в последней контрольной точке. Возможно также уменьшить количество ошибок, используя дублирование систем или ввод избыточной информации;
· проверяемость - возможность проверки получаемых результатов. Для этого необходимо документально фиксировать исходные данные, установленные режимы и другую информацию, которая влияет на получаемые результаты. Особенно это сказывается, когда сигналы поступают непосредственно от датчиков;
· точность результатов - обеспечение погрешности результатов не выше заданной. Величина погрешности зависит от точности исходных данных, степени адекватности используемой модели, точности выбранного метода и погрешности выполнения операций в компьютере. Жесткие требования к точности предъявляют системы навигации (например, система стыковки космических аппаратов) и системы управления технологическими процессами;
· защищенность - обеспечение конфиденциальности информации. Наиболее жесткие требования предъявляются к системам, в которых хранится информация, связанная с государственной и коммерческой тайной. Для обеспечения защиты информации используют программные, криптографические, правовые и другие методы;
· программная совместимость - возможность совместного функционирования с другим программным обеспечением. Чаще всего в данном случае речь идет о функционировании программы под управлением заданной операционной системы. Однако может потребоваться обмен данными с некоторой другой программой. В этом случае точно оговаривается формат передаваемых данных; аппаратная совместимость - возможность совместного функционирования с некоторым оборудованием. Это требование формулируют в виде минимально возможной конфигурации оборудования, на котором будет работать данное программное обеспечение. Если предполагается использование нестандартного оборудования, то для него должны быть описаны интерфейсы;
· эффективность - использование минимально возможного количества ресурсов технических средств (например, времени микропроцессора, объема оперативной памяти, объема внешней памяти, количества внешних устройств и др.). Эффективность оценивается по каждому ресурсу отдельно, поэтому требования эффективности часто противоречат друг другу. Например, чтобы уменьшить время выполнения программы, необходимо увеличить объем оперативной памяти;
· адаптируемость - возможность быстрой модификации с целью приспособления к изменяющимся условиям функционирования. Оценить эту характеристику количественно практически невозможно. Можно только констатировать, что при разработке данного ПО использовались приемы, облегчающие его модернизацию;
· повторная входимость - возможность повторного выполнения без перезагрузки с диска. Данное требование обычно предъявляется к программному обеспечению, резидентно загруженному в оперативную память (например, драйверы);
· реентерабельность - возможность «параллельного» использования несколькими процессами. Чтобы удовлетворить этому требованию, необходимо создавать копию данных, изменяемых программой, для каждого процесса.
Четко сформулировать спецификации требований к разрабатываемому ПО, чтобы затем занести их в техническое задание, - достаточно сложная и ответственная задача, которая требует проведения предпроектных исследований. [12]
Проектирование программного обеспечения
В настоящее время существует два основных подхода к проектированию программного обеспечения: структурное и объектное.
При структурном подходе к проектированию прежде всего необходимо определить структурные компоненты и связи между ними. Полученная в результате структура ПО должна быть представлена в виде структурной или функциональной схем и спецификаций ее компонентов.
Структурной называют схему, отражающую состав и взаимодействие по управлению частей разрабатываемого программного обеспечения.
Разработку структурной схемы программы обычно выполняют методом пошаговой детализации.
Структурные схемы пакетов программ разрабатывают для каждой программы пакета по отдельности, поскольку организация программ в пакеты не предусматривает передачи управления между ними.
Компонентами структурной схемы программной системы или программного комплекса могут служить программы, подсистемы, базы данных, библиотеки ресурсов и т.п.
Функциональная схема (ГОСТ 19.701-90) - это схема взаимодействия компонентов программного обеспечения с описанием информационных потоков, состава данных в потоках и указанием используемых файлов и устройств.
Функциональные схемы, как правило, более информативны, чем структурные.
При объектном подходе используется разделение на логическое и физическое проектирование программных продуктов. Логическое проектирование заключается в разработке классов для реализации их экземпляров - объектов. Для этого требуется подробное описание полей и методов классов, а также связей между ними. Для этого используются статические диаграммы классов и объектов и динамические диаграммы последовательностей состояний и кооперации. Физическое проектирование предполагает построение программных компонентов из ранее определенных классов и объектов и размещение их на конкретных вычислительных устройствах. Разрабатываемые на этом этапе диаграммы - компонентов и развертывания. [12]
Тестирование и отладка программных продуктов
При тестировании программных продуктов применяются два основных метода тестирования - тестирование «черного» и «белого» ящика. Рассмотрим каждый их них подробнее.
Тестирование «черного ящика»
Известны: функции программы.
Исследуется: работа каждой функции на всей области определения.
Тесты «черного» ящика демонстрируют: · как выполняются функции программ;
· как принимаются исходные данные;
· как вырабатываются результаты;
· как сохраняется целостность внешней информации.
При тестировании «черного ящика» рассматриваются системные характеристики программ, игнорируется их внутренняя логическая структура. Исчерпывающее тестирование, как правило, невозможно. Например, если в программе 10 входных величин и каждая принимает по 10 значений, то потребуется 1010 тестовых вариантов. Отметим также, что тестирование «черного ящика» не реагирует на многие особенности программных ошибок. [12]
Тестирование «белого ящика»
Известна: внутренняя структура программы.
Исследуются: внутренние элементы программы и связи между ними.
Объектом тестирования здесь является не внешнее, а внутреннее поведение программы. Проверяется корректность построения всех элементов программы и правильность их взаимодействия друг с другом. Обычно анализируются управляющие связи элементов, реже - информационные связи. Тестирование по принципу «белого ящика» характеризуется степенью, в какой тесты выполняют или покрывают логику (исходный текст) программы. Исчерпывающее тестирование также затруднительно. [12]
Методика тестирования программных систем
Процесс тестирования объединяет различные способы тестирования в спланированную последовательность шагов, которые приводят к успешному построению программной системы (ПС). Методика тестирования ПС может быть представлена в виде разворачивающейся спирали (рисунок 4).
В начале осуществляется тестирование элементов (модулей), проверяющее результаты этапа кодирования ПС. На втором шаге выполняется тестирование интеграции, ориентированное на выявление ошибок этапа проектирования ПС. На третьем обороте спирали производится тестирование правильности, проверяющее корректность этапа анализа требований к ПС. На заключительном витке спирали проводится системное тестирование, выявляющее дефекты этапа системного анализа ПС.
Охарактеризуем каждый шаг процесса тестирования.
1. Тестирование элементов. Цель - индивидуальная проверка каждого модуля. Используются способы тестирования «белого ящика».
Рисунок 4.2.4. Спираль процесса тестирования ПС
2. Тестирование интеграции. Цель - тестирование сборки модулей в программную систему. В основном применяют способы тестирования «черного ящика».
3. Тестирование правильности. Цель - проверить реализацию в программной системе всех функциональных и поведенческих требований, а также требования эффективности. Используются исключительно способы тестирования «черного ящика».
4. Системное тестирование. Цель - проверка правильности объединения и взаимодействия всех элементов компьютерной системы, реализации всех системных функций.
Организация процесса тестирования в виде эволюционной разворачивающейся спирали обеспе
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
