Разработка алгоритмов поиска оптимального маршрута для БЛА при наблюдении им подвижных наземных объектов

Вид работы:

Дипломная (ВКР)
Предмет:

Транспорт, грузоперевозки
Язык:

Русский
,
Формат файла:
MS Word

423,92 Кб
Опубликовано:

2013-02-07

Скачать дипломную работу Читать текст online Заказать дипломную
*Помощь в написании! Посмотреть все дипломные работы

Вы можете узнать стоимость помощи в написании студенческой работы.

Разработка алгоритмов поиска оптимального маршрута для БЛА при наблюдении им подвижных наземных объектов

Введение и постановка задачи

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

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

Важным является тот факт, что разрабатываемые алгоритмы должны быть способны рассчитывать оптимальные маршруты в течение очень короткого промежутка времени, так как будут выполняться в реальном времени в составе программного обеспечения БЦВМ.

Данная дипломная работа посвящена разработке алгоритмов поиска оптимального маршрута для БЛА при наблюдении им подвижных наземных объектов, а также алгоритмов оптимального распределения объектов между БЛА. При разработке алгоритмов учитывается динамика БЛА в условиях воздействия бокового ветра.

Исходными данными поставленной задачи являются:

· характеристики БЛА;

· параметры движения БЛА (скорость движения, начальный угол курса;

· количество БЛА;

· начальное положение и характеристики движения наземных объектов;

· скорость бокового ветра;

· начальный и конечный пункты движения каждого БЛА.

Постановка задачи

Для заданных параметров объектов, БЛА и метеорологической обстановки необходимо определить оптимальную стратегию распределения объектов между БЛА и проложить оптимальный маршрут для каждого из БЛА. Критерием оптимальности следует считать минимум времени полета группы БЛА (временем полета грумы БЛА назовем время, через которое последний БЛА достигнет конечного пункта своего маршрута при условии, что все БЛА начали движение из начального пункта маршрута в один и тот же момент).

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

Анализируя исходные данные, можно сказать, что среди характеристик БЛА для реализации алгоритмов понадобятся следующие:

· диапазон изменения скорости и высоты полета БЛА;

· зависимость минимального радиуса разворота от скорости полета и скорости ветра.

Также оговаривается тот факт, что на борту БЛА присутствует аппаратура фото- или видеонаблюдения наземных объектов. Исходя из того, что современные объективы фотокамер позволяют провести фотосъемку в хорошем качестве с высоты до нескольких сот метров, выберем углы обзора камеры, учитывая, что камера должна полностью охватывать зоны недосягаемости БЛА (рисунок 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 Случай нахождения максимума для функции с локальными максимумами

Сильные стороны:

· простота реализации;

· надежность работы для унимодальных функций.

Слабые стороны:

· остановка в локальных минимумах, невозможность работы в случае, если пространство поиска имеет несколько минимумов;

· неопределенное время поиска.

Динамическое программирование

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

При решении задач с помощью динамического программирования необходимо проделать три шага:

) Разбиение задачи на подзадачи меньшего размера.

) Нахождение решения подзадач рекурсивно, проделывая этот же алгоритм.

) Использование полученного решения подзадач для конструирования решения глобальной задачи.

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

При решении задачи поиска оптимального маршрута методом динамического программирования довольно часто используется алгоритм Дейкстры. Принцип работы этого алгоритма заключается в том, что каждый пункт маршрута ассоциируется с вершиной графа. Каждой вершине этого графа сопоставляется метка, значением которой является минимальное известное расстояние от начальной вершины до текущей. [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 выбрать какое-то действие a_t. Также для принятия рационального решения агенту необходимо оценивать прошлое и будущее. Под прошлым подразумевается то, что агент воспринял какую-либо информацию и совершил какие-либо действия до текущего момента времени, а под будущим - что он ожидает и что собирается потом делать.

Функция, которая отображает набор пар наблюдение - действие до текущего момента времени в оптимальное действие в текущий момент времени называется стратегией агента

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

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

В случае, если агент использует для принятия решения оценки будущего, необходимо выстроить прогноз об изменении окружения агента после совершения им какого-либо действия. Здесь возможны два варинта:

· в детерминистическом мире модель перехода отображает единственным образом пару состояние-действие в новое состояние;

· в стохастическом мире модель перехода отображает пару состояние-действие в распределение вероятности состояний.

В качестве примера алгоритма, использующего мультиагентные системы, рассмотрим алгоритм, предложенный в [3]. Данный алгоритм основан на том, все БЛА связаны в единую сеть, внутри которой принимаются решения о распределении объектов наблюдения между ними. Как и во многих других схожих алгоритмах, принятие решения является коллективным и базируется на том, что каждый БЛА выдвигает предложение о том, к какому объекту он считает необходимым двигаться. Остальные БЛА в процессе переговоров могут принять или отвергнуть это решение.

Сам процесс принятия решения состоит в следующем. Каждый агент в течение одного цикла переговоров совершает 4 действия:

· отправляет или получает предложение,

· обдумывает полученное предложение,

· отправляет ответ (согласие или несогласие),

· принимает решение.

Каждый агент вычисляет выигрыш, полученный в том случае, если он последует за ней по следующей формуле

b_i(T_j) = V_Tjw_r - S_t,

где V_Tjw_r - «цена» объекта,

S_t - относительное время преследования объекта

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

На втором и третьем шагах, когда данные от всех БЛА собраны, каждый из них анализирует полученную информацию и принимает решение о согласии или несогласии и этим на основании следующих правил:

· если объект выбран только одним БЛА, то данное предложение одобряется;

· если объект выбран несколькими БЛА, то согласие посылается только тому БЛА, для которого максимален выигрыш;

· один БЛА может отправить только одно согласие для каждой цели;

· если все соседи данного БЛА (то есть те БЛА, от которых он находится в непосредственной близости) согласны с его целью, он получает право на принятие решения о целесообразности следования до его текущей цели;

Четвертый шаг заключается в анализе полученных ответов и принятии решения. Если БЛА получил согласия от всех соседей, он выполняет запланированное действие. Если он получил отказ хотя бы от одного из соседей, он участвует в следующем цикле переговоров. Если же БЛА получил отказ от всех своих соседей, он выполняет задачу поиска новых объектов.

Выделим сильные и слабы стороны данного подхода

Сильные стороны:

· постоянное взаимодействие между агентами;

· коллективное принятие решения всеми агентами.

Слабые стороны:

· в случае необходимости использования большой истории действий возрастает ресурсоемкость данного подхода;

· агент зачастую действует по аналогии с жадным алгоритмом, а значит его решение в общем случае нельзя считать оптимальным;

· необходимость использования стохастических прогнозов в случае использования информации об оценках будущей реакции окружения да действия агентов.

Задача многих коммивояжеров

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

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

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

Данный метод описан в работе [4]. В данной работе предлагается сначала провести кластеризацию всех объектов по методу k-средних. Этот метод заключается в том, что все объекты разбиваются на количество кластеров k, равное количеству БЛА следующим образом:

· случайным образом на поле решения задачи выбрасывается k точек, которые являются центрами кластеров (центроидами);

· каждый объект заносится в кластер того центроида, к которому он находится ближе всего;

· после того, как все объекты занесены в кластеры, позиции центроидов пересчитываются таким образом, чтобы суммарное расстояние до всех объектов оказалось минимальным;

· шаги 2 и 3 повторяются до тех пор, пока центроиды не перестанут передвигаться.

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

После проведения кластеризации к объектам внутри каждого кластера применятся алгоритм «упаковки», суть которого заключается в том, чтобы перевести координаты каждого из объектов в полярные, а замет отсортировать их по углу поворота, а затем по радиусу в порядке возрастания. Таким образом, получается некоторая последовательность облета объектов, которая будет оптимизироваться на следующих шагах.

К полученной последовательности применяется алгоритм имитации отжига (алгоритм поиска минимума некоторой функции), целевой функцией которого является время облета объектов в заданной последовательности.

Последним шагом данного метода является применение алгоритма поиска «Tabu search», суть которого сводится к тому, что в случае, если алгоритм находит решение, которое потенциально является оптимальным, он «запрещает» его, и «разрешает» движение в сторону максимизации времени полета БЛА. Таким образом, алгоритм препятствует «застреванию» поиска в локальных минимумах.

Сильные стороны:

· применение множества способов препятствования попаданию в локальные минимумы.

Слабые стороны:

· исключение взаимодействия между БЛА;

· применяется сразу несколько методов поиска и оптимизации, что существенно увеличивает время расчета;

· метод применим только для неподвижных объектов.

1.2 Разработка модели одиночных действий БЛА

Решается задача поиска оптимального маршрута облета движущихся объектов одним БЛА с учетом ветра. Разобьем её на несколько подзадач.

1. Поиск оптимального маршрута облета неподвижных объектов одним БЛА без учета ветра;

2. Учет подвижности объекта;

. Учет ветра;

Для решения задачи 1 запишем алгоритм перелета БЛА в точку с определенными координатами. Исходными данными для него являются:

1. Начальные координаты БЛА;

2. Начальный угол курса БЛА;

. Координаты объекта;

. Минимальный радиус разворота БЛА;

. Координаты точки.

Проиллюстрируем это на рисунке 1.2.1.

Рисунок 1.2.1 Начальные данные для задачи, где x_ЛА, y_ЛА - начальные координаты БЛА, x_О, y_О - начальные координаты объекта, R - минимальный радиус разворота БЛА, стрелкой указано начальное направление полета БЛА.

Для построения оптимальной траектории полета до точки разобьем полет на 2 этапа:

1. Полет по дуге радиусом R;

2. Полет по прямой до объекта.

Легко показать, что второй этап будет заключаться в полете по касательной, проведенной из точки (x_O, y_O) к ближайшей из окружностей, ограничивающих зону недосягаемости БЛА.

Найдем точку касания. Для этого обратимся к рисунку 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 для каждого объекта (Дx);

· относительные координаты по оси Y для каждого объекта (Дy);

· относительный угол курса для каждого объекта (Дш);

· скорость каждого объекта (V_i);

· скорость БЛА (V);

· минимальный радиус разворота БЛА (R_min).

Количество нейронов будет выбираться экспериментальным путем. Количество выходных нейронов будет соответствовать количеству объектов, на которое данная нейронная сеть рассчитана. Выходные значения нейронной сети будут формироваться таким образом, что, тот выход, который соответствует следующему в маршруте объекту (то есть тому объекту, к которому сейчас необходимо двигаться БЛА), будет переходить в активное состояние (значение этого выхода станет равным «1»), а все остальные выходы останутся в пассивном состоянии (их значение будет установлено в «0»). Данная нейронная сеть изображена на рисунке 1.3.1.

Рисунок 1.3.1 Нейронная сеть для замены модуля поиска оптимального маршрута

Вследствие того, что нейронная сеть выдает не весь маршрут, а только номер следующего его пункта, процесс нахождения оптимального маршрута теперь будет проходить в несколько итераций следующим образом. Сначала вычисляются относительные координаты всех объектов относительно текущего положения БЛА. Затем вычисляется время t, необходимое для подлета к этому объекту, а сам объект исключается из дальнейшей обработки. После этого рассчитывается новое положение всех объектов, которое они займут через время t. После этого запускается следующая итерация алгоритма для обновленных значений координат объектов. [5]

1.4 Разработка модели групповых действий БЛА

Теперь необходимо решить задачу распределения объектов между несколькими БЛА. Для простоты рассмотрим случай распределения объектов между двумя БЛА. Для этого назначим каждому БЛА область ответственности, как показано на рисунке 1.4.1.

Рисунок 1.4.1 Разбиение области задач на части. К₁, К₂ - конечные пункты маршрута первого и второго БЛА соответственно

После этого проанализируем, какие из объектов пересекут линию раздела областей за заданный промежуток времени t_К и разделим все объекты на три группы:

) объекты, принадлежащие области ответственности первого БЛА;

) объекты, принадлежащие области ответственности второго БЛА;

) Спорные объекты, которые за время t_Кпересекли линию раздела областей ответственности, отведенных каждому БЛА.

Далее примем, что начальные и конечные пункты маршрута каждого БЛА расположены в соответствии с рисунком 8 (точные значения расстояний и углов могут меняться в соответствии с текущей навигационной обстановкой, но они должны быть точно известны на момент начала работы алгоритма).

Таким образом, объекты, принадлежащие области каждого БЛА, будут закреплены за этим БЛА, а спорные объекты будут распределены между ними таким образом, чтобы минимизировать время облета всех объектов группой БЛА.

Рисунок 1.4.2 Пример распределения спорных объектов

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

Далее, будем присоединять списки с вариантами распределения спорных объектов к существующим спискам для каждого БЛА и применять к ним алгоритм поиска оптимального пути, описанный в пункте 1.2. После анализа всех составленных комбинаций, выбираем из них ту, которой соответствует наилучшее значение критерия оптимальности. Полученная комбинация и есть искомый вариант распределения объектов между БЛА.

На рисунке 1.4.3 изображена общая схема работы алгоритмов поиска оптимального маршрута.

Рисунок 1.4.3 Общая схема работы системы

1.5 Разработка программы, моделирование системы и анализ результатов

На основании алгоритмов, разработанных в пунктах 1.2 - 1.3, была реализована программа, предназначенная для поиска оптимального распределения объектов между двумя БЛА. Данная программа была реализована и выполнена на языке MATLAB в среде разработки MatLab 2008a.

Для реализации алгоритмов была выбрана среда матlab по следующим причинам:

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

) Возможность использования вычислительных сетей, что также позволяет существенно сократить время исследований.

Среди недостатков использования данной среды можно выделить лишь один - высокая стоимость коммерческой лицензии. [6]

Листинги исходных кодов приведены в приложении 1.

Моделирование работы модуля «Поиск оптимального маршрута одного БЛА»

Промоделируем работу данного модуля для случая поиска оптимального маршрута облета пяти объектов и проанализируем результаты. Исходные данные и результаты проиллюстрированы на рисунке 1.5.1 и в таблице 1.5.1. Следует также отметить, что координаты по осям X и Y отсчитываются от некоторой начальной точки с координатами (0,0).

Рисунок 1.5.1 Результат выполнения модуля «Поиск оптимального маршрута для одного БЛА»

Таблица 1.5.1. Исходные данные для эксперимента

	X, м	Y, м	V, м/с	Курс, град.
БЛА	-50	50	40	90
Первый объект	689	374	15	72
Второй объект	83	114	15	238
Третий объект	152	412	15	103
Четвертый объект	996	39	15	69
Пятый объект	106	480	15	271
Конечная точка движения	1050	50	-	-

Анализируя работу данного модуля, можно сказать, что он выполняется корректно и маршрут, который был сформирован, является оптимальным. Для доказательства построим график зависимости времени облета всех объектов от номера вершины дерева, с помощью которого осуществляется перебор вариантов облета (рисунок 1.5.2). Изображение дерева слишком велико, поэтому оно не приводится для данного примера.

Рисунок 1.5.2 График зависимости времени облета от номера вершины дерева

Таким образом, номер вершины дерева облета, соответствующей минимальному времени облета всех объектов - 114. Данной ветви соответствует маршрут 2, 5, 3, 1, 4, что соответствует иллюстрации на рисунке 1.5.1.

Время работы данного модуля составляет 57,3648 секунды. Как и ожидалось, время работы данного модуля не позволяет включить его в состав программного обеспечения БЦВМ, поэтому замена его на нейронную сеть оказалась оправданной.

Моделирование работы модуля «Поиск оптимального маршрута нескольких БЛА»

Теперь, после того, как мы убедились, что алгоритм выбора оптимального маршрута для одного БЛА работает корректно, проверим работу всей системы в целом (на примере двух БЛА), а затем проанализируем работу каждого из модулей, чтобы выяснить возможность применения данной системы в составе комплекса бортового программного обеспечения. Исходные данные для эксперимента приведены в таблице 1.5.2.

Таблица 1.5.2 Исходные данные для эксперимента

	X, м	Y, м	V, м/с	Курс, град.
Первый БЛА	-225	-57	40	90
Второй БЛА	-225	317	40	90
Первый объект	105	42	10
Второй объект	573	15	14	172
Третий объект	737	19	14	246
Четвертый объект	984	257	13	94
Пятый объект	177	119	10	281
Шестой объект	939	90	11	29
Седьмой объект	467	194	10	213
Конечный пункт маршрута первого БЛА	1502	-57	-	-
Конечный пункт маршрута второго БЛА	1502	-317	-	-

Скорость ветра зададим равной 3 м/с

Ниже приведены результаты одной итерации работы системы.

Модуль анализа движения объектов

Результатом работы модуля явилось следующее распределение объектов:

· Первый БЛА: 5-й и 6-й объекты;

· Второй БЛА: 4-й и 7-й объекты;

· Спорные объекты: 1-й, 2-й и 3-й объекты.

Время работы модуля составило 0,005 секунды.

Модуль генерации вариантов распределения объектов

Для выбранной итерации было назначено следующее распределение объектов:

· Первый БЛА: 1-й, 5-й, 3-й и 6-й объекты;

· Второй БЛА: 2-й, 4-й и 7-й объекты.

Время работы модуля составило 0,0131 секунды.

Модуль нахождения оптимального маршрута для одного БЛА

Для выбранной итерации были составлены следующие оптимальные маршруты:

· Первый БЛА: 1-й и 5-й - 3-й - 6-й объекты;

· Второй БЛА: 7-й - 2-й - 4-й объекты.

Следует заметить, что при пролете над пятым объектом в поле видимости камеры попал первый объект, поэтому был обработан вместе с пятым.

Время работы модуля составило 31,7279 секунды.

Модуль определения минимального радиуса разворота.

Для текущих значений скорости БЛА и скорости ветра был рассчитан минимальный радиус разворота R_min = 70 м.

Время работы модуля составило 0.000004 секунды.

Модуль запоминания оптимального маршрута

Маршрут, просмотренный на текущей итерации, сохранен для дальнейшей обработки.

Время работы модуля составило 0,0008 секунды.

Результаты работы системы

В результате работы системы было выбрано оптимальное распределение объектов и составлены оптимальные маршруты их облета двумя БЛА. На рисунке 1.5.3 изображены выбранные маршруты, а также показаны начальные пункты движения БЛА (они изображены в виде самолетов), конечные пункты движения первого и второго БЛА - К₁ и К₂ соответственно, начальные положения и направление движения объектов (они изображены в виде черных окружностей), а также точки «обслуживания» объектов (они изображены синими точками). Красные непрерывные линии показывают траектории движения БЛА по оптимальным маршрутам. Время работы всей системы составило 172.4834 секунды.

Таким образом, результаты моделирования показывают, что разработанная программа является работоспособной и маршруты, рассчитываемые с помощью нее, являются оптимальными. Пример дерева, по которому находится минимальный маршрут, приведен на рисунке 1.5.4. Рядом с каждой вершиной выводится время, необходимое для встречи с данным объектом, если БЛА будет следовать по маршруту, соответствующему исследуемой ветви дерева. Красным цветом указана ветвь дерева, соответствующая оптимальному маршруту.

Рисунок 1.5.3 Результат выполнения модуля «Поиск оптимального маршрута для нескольких БЛА»

Рисунок 1.5.4 Дерево перебора всех вариантов облета для первого БЛА (соответствие значений, указанных на вершине номерам объектов: «1» - 5-й объект, «2» - 6-й объект, «3» - 1-й объект, «4» - 3-й объект)

Моделирование работы системы с использованием нейронной сети и анализ результатов

Смоделируем работу созданной нейронной сети в среде Matlab с использованием встроенной утилиты nntool, предназначенной для работы с нейронными сетями.

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

· скорости движения БЛА и объектов постоянны и заданы заранее;

· объекты движутся в том же направлении, что и БЛА;

· количество объектов равно трем.

Таким образом, сгенерируем обучающую выборку для данной нейронной сети, изменяя нормированные значения относительных координат в пределах от 0 до 1 с шагом 0,1.

В ходе разработки и моделирования работы данной нейронной сети количество нейронов в скрытом слое было выбрано равным 35. Таким образом, данная нейронная сеть имеет структуру 14-35-3.

Моделирование данной нейронной сети производилось на ПЭВМ со следующими характеристиками:

· Тактовая частота процессора: 2 ГГц;

· Количество ядер процессора: 1;

· Объем памяти: 1,5 Гб.

Процесс генерации данной обучающей выборки занял 8 часов.

Процесс обучения нейронной сети закончился с ошибкой, равной 10^-2, что является хорошим результатом для данной нейронной сети. Промоделируем теперь работу данной нейронной сети и сравним ее результаты с результатами, выдаваемыми исходным алгоритмом.

Исходные данные для эксперимента представлены в таблице 1.5.3.1

Таблица 1.5.3 Исходные данные для эксперимента

	X, м	Y, м	V, м/с	Курс, град.
БЛА	-50	0	40	90
Первый объект	122	127	10	90
Второй объект	79	149	10	90
Третий объект	146	141	10	90
Конечный пункт маршрута БЛА	300	0	-	-

Скорость ветра примем равной нулю.

В результате работы исходный алгоритм выдал следующую последовательность облета объектов: 2-й, 1-й, и затем 3-й.

Нейронная сеть имела на выходах следующие значения:

· Первый выход: 0,0000

· Второй выход: 0,9994

· Третий выход: 0,0021

На втором шаге работы алгоритма нейронная сеть имела на выходах следующие значения:

· Первый выход: 0.9161

· Второй выход: 0.1097

· Третий выход: 0.1006

На последнем шаге работы алгоритма остался только один объект.

Таким образом, нейронная сеть предложила первым пунктом маршрута сделать второй объект (так как был активен второй выход). Вторым пунктом маршрута был предложен первый объект.

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

Теперь проверим работу нейронной сети в составе всей системы. Для этого проведем эксперимент с исходными данными, приведенными в таблице 1.5.4.

Таблица 1.5.4 Исходные данные для эксперимента

	X, м	Y, м	V, м/с	Курс, град.
Первый БЛА	-50	75	40	90
Второй БЛА	-50	125	40	90
Первый объект	60	80	10	90
Второй объект	100	100	10	90
Третий объект	140	70	10	90
Четвертый объект	80	140	10	90
Пятый объект	130	130	10	90
Конечный пункт маршрута первого БЛА	300	75	-	-
Конечный пункт маршрута второго БЛА	300	125	-	-

Минимальный радиус разворота БЛА в этом эксперименте был принят равным 20 м.

В результате работы система, использующая алгоритм полного перебора, выдала следующую последовательность облета объектов для двух БЛА:

Первый БЛА: 1-й, 2-й и затем 3-й объект;

Второй БЛА: 4-й и затем 5-й объект.

Система, использующая нейронную сеть, выдала следующую последовательность облета объектов:

Первый БЛА: 1-й, 2-й и затем 3-й объект;

Второй БЛА: 4-й и затем 5-й объект.

При этом на первой итерации работы алгоритма нейронная сеть для первого БЛА имела на выходах значения следующие значения:

· Первый выход: 0,9998

· Второй выход: 0,0000

· Третий выход: 0,0000

На второй итерации значения изменились на следующие:

· Первый выход: 0,0267

· Второй выход: 0,7650

· Третий выход: 0,0000

Соответственно, последним в маршруте остался объект номер три.

Нейронная сеть второго БЛА на первой итерации имела следующие значения на выходах:

· Первый выход: 0,9878

· Второй выход: 0,6347

· Третий выход: 0,0021

При этом на первый и второй входы нейронной сети были поданы координаты четвертого БЛА, а на третий вход - координаты пятого БЛА (в этом случае, если на несколько входов нейронной сети поданы одинаковые координаты, она будет классифицировать их как один объект).

Таким образом, мы убедились, что нейронная сеть корректно работает и в составе полной системы планирования группового полета БЛА.

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

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

Время, необходимое для одного цикла работы нейронной сети составляет 0.007731 секунды. Время процедуры, необходимой для расчета изменения координат объектов после того, как БЛА достигнет объекта, предлагаемого нейронной сетью составляет 0,000612 секунды. Таким образом, для просчета, например, оптимального маршрута для 10 БЛА потребуется 0,0834 секунды. Теперь рассчитаем, сколько такая задача заняла бы времени при применении исходного алгоритма. Для пяти объектов время расчета алгоритма составляет 51 секунду. Так как количество комбинаций, которое просчитывается в этом случае равно 5! = 120, на одну операцию расходуется 0,4250 секунды. Для десяти объектов это время составит 0.4250 · 10! = 1542240 секунд, что равно примерно 428 часам или 18 суткам.

Таким образом, мы можем использовать данную нейронную сеть для реализации модуля расчета оптимального маршрута одного БЛА. Суммарное время работы обновленной системы теперь не превышает 0,2 секунды, а значит, данная система может быть использована в составе комплекса программного обеспечения бортовой вычислительной системы.

2. Экономическая часть

Данный дипломный проект посвящен разработке интеллектуальной системы планирования маршрута облета группой беспилотных летательных аппаратов (БЛА) подвижных наземных объектов. Основная задача дипломного проекта - разработка программного продукта, позволяющего находить оптимальную последовательность облета наземных подвижных объектов, а так же корректировать ее в процессе полета с учетом вновь получаемой информации об объектах наблюдения. Критерием оптимальности маршрута было выбрано время полета. В ходе работы были исследованы уже существующие алгоритмы поиска кратчайшего пути, получены сведения об их недостатках и достоинствах, которые в дальнейшем были применены при разработке алгоритма, использованного для построения программного продукта, представленного в дипломном проекте.

Реализация данного алгоритма была выполнена на ЭВМ на высокоуровневом языке программирования Matlab в среде Matlab R2008a с использованием стандартных библиотек C/C++.

2.1 Оценка целесообразности разработки алгоритмов и программных продуктов

Для обоснования целесообразности разработки алгоритмов и программных продуктов (ПП) необходимо:

· Выбрать аналог

· Сформулировать перечень характеристик качества разработки по предлагаемому варианту ПП

· Определить конкретные значения характеристик, их значимость

При выборе характеристик качества разрабатываемых алгоритмов и ПП следует учитывать систему характеристик качества программных средств по стандарту ISO 9126:1991.

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

Анализируемые функциональные характеристики отражены в таблице 2.1.1.

Таблица 2.1.1 Характеристики качества алгоритмов и ПП

Характеристики качества ПП	Значения характеристик качества ПП		Значимость характеристик
	Аналог	Новый вариант
Пригодность для применения	1	2	0,2
Отсутствие ошибок	1	3	0,2
Понятность	1	5	0,05
Простота использования	1	4	0,05
Временная экономичность	1	3	0,2
Ресурсная экономичность	1	3	0,1
Стабильность	1	2	0,1
Внедряемость	1	2	0,1

На основании данных из таблицы найдем индекс технического уровня разрабатываемого ПП по формуле:

где Х_Hi, Х_Б_i - уровень i-ой функциональной характеристики соответственно нового и базового ПП;

м_i- значимость i-ой функционально-технической характеристики;

n - количество рассматриваемых характеристик.

Таким образом, рассчитаем индекс технического уровня:

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

2.2 Планирование разработки

Определение трудоёмкости

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

где t_О - затраты труда на подготовку описания задачи;

t_И - затраты труда на изучение и постановку задачи;

t_А - затраты труда на разработку алгоритма решения задачи;

t_К - затраты труда на программирование по блок-схеме;

t_ОТ - затраты труда на отладку программы;

t_Д - затраты труда на подготовку документации по ПП.

- Условное количество операторов в программе:

q - предполагаемое количество команд;

К_С - коэффициент сложности программ;

К_К - коэффициент коррекции программы при ее разработке

n - количество коррекций программы в ходе ее разработки.

К - коэффициент квалификации разработчика- увеличение затрат на изучение и постановку задачи вследствие ее сложности и новизны

Для разрабатываемого ПП:= 2000= 5

K_K = 0,1_C = 1,5

B = 2,5

K = 1,1

Таким образом:

t_О = 16;

Результаты вычислений занесем в таблицу 2.2.1:

Таблица 2.2.1 структура трудовых затрат на разработку алгоритмов и ПП

№	Наименование этапа работ	Доля работ на этапе в общем объеме работ, %
1	Подготовка описания задачи	0,77
2	Изучение и постановка задачи	6,7
3	Разработка алгоритма решения задачи	9,9
4	Программирование по блок-схеме	19,8
5	Отладка программы	39,7
6	Подготовка документации по ПП	23,1
Итого:		100

Календарное планирование

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

Производственный цикл каждого этапа определяется по формуле:

где Т_j - трудоёмкость j-того этапа работ, чел./час;

t_рд - продолжительность рабочего дня, час;

q_j - количество работников одновременно участвующих в выполнении работ на j-том этапе, чел.

Таким образом, рассчитаем:

Пересчитаем в календарные дни:

2.3 Определение затрат, себестоимости и цены

Затраты на создание алгоритмов и ПП определяют по следующим статьям расходов:

1. Материалы;

2. Специальное оборудование;

. Заработная плата основных исполнителей;

. Отчисления на единый социальный налог основных исполнителей;

. Страховые социальные расходы на производственный травматизм;

. Накладные расходы;

. Прочие расходы.

Расчет затрат на материалы

Затраты на материалы сведены в таблицу 2.3.1

Таблица 2.3.1 Затраты на материалы и покупные изделия

№ п/п	Наименование	Единицы измерения	Цена, руб.	Сумма, руб.
1	Внешний накопитель Kingston DataTraveler+	1 шт.	900
2	Ручки	3 шт.	10	30
3	Бумага (А4) SvetoCopy	1 пачка	200	200
	Итого			1130

Расчет затрат на спецоборудование

Затраты на спецоборудование отсутствуют.

Расчет заработной платы персонала

Заработная плата разработчиков программы рассчитывается на основе трудоемкости стадий работ. Часовые ставки определяются на основе должностных окладов разработчиков и разрядов работ (часовых тарифных ставок). Расчет заработной платы сведен в таблицу 2.3.2.

Таблица 2.3.2 Заработная плата основного персонала

№ этапа	Трудоемкость стадий, чел.-дн	Исполнители		Дневн. ставка, р	Сред. дневная ставка, р	З/п, р	З/п с уч. Премий (15%), р
		должность	числ.
1	2	Ведущий инженер	1	350	350	700	805
2	17	Ведущий инженер	1	400	400	6800	7820
3	22,5	Ведущий инженер	1	400	400	9000	10350
4	22,5	Программист	2	350	350	15750	18112,5
5	51	Программист	1	350	375	19125	21993,75
		Ведущий инженер	1	400
6	30	Программист	1	350	375	11250	12937,5
		Ведущий инженер	1	400
Всего	145					62625	72018,75

Расчет отчислений на социальные нужды

Норматив отчислений на социальные нужды составляет 26,2% от заработной платы основных исполнителей.

Таким образом:

Расчет накладных расходов

Накладные расходы определяются по формуле

где K_НАКЛ = 1..2.

Примем K_НАКЛ = 1, тогда:

Расчет накладных расходов

Накладные расходы составляют 5% от расходов на заработную плату основных исполнителей:

Таким образом:

Общие результаты по статьям расходов приведены в таблице 2.3.3.

Таблица 2.3.3 Затраты на создание алгоритмов и ПП

Наименование элементов и статей расходов	Затраты, руб.	Удельный вес, %
материалы	1130	0,6
специальное оборудование	-	-
заработная плата основных исполнителей	72018,75	42,9
отчисления на единый социальный налог основных исполнителей	18868,91	11,3
накладные расходы	72018,75	42,9
прочие расходы	3600	2.1
Итого:	167636,41	100

Цена предложения разработанных алгоритмов и ПП определяется с учетом рентабельности разработки как:

где З_ПП - затраты на создание алгоритмов и программных продуктов;

ЗП_пп - заработная плата основных исполнителей - разработчиков ПП;

с_ЗП - рентабельность разработки ПП по отношению к оплате труда основных исполнителей, обеспечивающая безубыточную деятельность (с_ЗП = 200 - 400%).

Примем с_ЗП = 250%

2.4 Определение и оценка показателей экономической эффективности

Основными показателями экономической эффективности являются: экономический эффект (Э), уровень экономической эффективности (Е), срок окупаемости вложений (Т_ОК).

Использование разработанных в данном дипломном проекте алгоритмов и ПП приводит к сокращению времени решения задачи в связи с применением более совершенных. В этом случае Э_ПП.Гсчитается следующим образом:

где ДТ_м_i - экономия машинного времени по i-ой задаче, час.;

С_вт - стоимость одного машинного часа, руб.;

n - количество задач, решаемых за год.

Разработанный алгоритм может использоваться до 50 раз в день. Таким образом, количество использований алгоритма в год составляет до 17800 раз в год. Время выполнения одной задачи при использовании разработанного ПП повышается примерно в снижается на 3 минуты. Таким образом, при стоимости одного машинного часа, равной 400 р., рассчитаем экономический эффект:

Уровень экономической эффективности и срок окупаемости вложений составляют в этом случае соответственно:

3. Охрана труда и окружающей среды

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

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

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

3.1 Особенности восприятия информации с дисплея

Компьютерный зрительный синдром

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

Каждый пользователь ПЭВМ знаком с неприятными ощущениями («песок» в глазах, жар, боль, пелена). Очень долгое время считалось, что это вызвано только излучением, исходящим от экрана, и не принимался во внимание тот факт, что восприятие информации, выдаваемой на дисплей, существенно отличается от более привычных способов, например, чтения книг. Современные мониторы обеспечивают достаточную степень безопасности. В частности, того излучения, которое собственно называется радиацией (гамма-лучи и нейтроны) монитор, в принципе, не производит. В нем нет устройств со столь высокой энергией. Опасными являются электростатические поля, которые способны разгонять микрочастицы до больших скоростей, которые, сталкиваясь с кожей лица и глазами, оказывают на них неблагоприятное действие. Но это верно лишь для дисплеев, построенных на технологии электронно-лучевых трубок. В современных жидкокристаллических и плазменных дисплеях данная проблема практически отсутствует. Однако, несмотря на это, неприятные ощущения и даже ухудшение здоровья все равно наблюдаются при длительной работе за современными ПЭВМ.

Изучая эту проблему, в 1998 году в США американские медики ввели в обиход новый термин - Компьютерный зрительный синдром (Сomputer Vision Syndrome, CVS). Это специфическое нарушение зрения (астенопия) у людей, проводящих много времени перед экраном компьютера. Считается, что этот синдром ежедневно возникает у 40% людей, работающих на компьютере, и периодически - у 92% пользователей.

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

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

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

В-третьих, мониторы зачастую имеют низкую контрастность, которая нашим глазам очень не нравится. Из-за нее глаза напрягаются и быстро устают.

В-четвертых, на наше зрение влияет и кадровая развертка.

В-пятых, зрение ухудшают блики на мониторе. Они появляются в виде отражения других светящихся объектов.

Негативное влияние оказывает так же неправильно выбранное расстояние от глаз до экрана, неудачные цвета. Кроме того, глаза быстрее устают, когда приходится постоянно перемещать взгляд с экрана на клавиатуру или бумажный лист.

Таким образом, для оптимизации восприятия информации, выдаваемой на дисплей и, следовательно, улучшения комфортности и ускорения работы оператора ПЭВМ необходимо внимательно подходить к организации выдачи информации на дисплей. Кроме того, неправильный выбор характеристик и настроек дисплея может повлечь за собой ущерб здоровью оператора.

3.2 Нормативные документы

Основными документами, нормирующими параметры видеодисплейных терминалов (ВДТ) являются СанПиН 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 Гц для дисплеев на плоских дискретных экранах.

*** Расчетные формулы для отклонений рабочего поля:

по вертикали:

где Н₁ - значение длины крайнего левого столбца;₂ - значение длины крайнего правого столбца;

по горизонтали:

где B₁ - значение длины верхней строки;₂ - значение длины нижней строки;

по диагонали:

где D₁, D₂ - значения длин диагоналей на рабочем поле.

На рабочем месте использовался дисплей Acer AL1916 (размер диагонали - 19»). Его настройки были выставлены следующим образом:

Контрастность: 50% от максимальной для данного дисплея;

Яркость: 50% от максимальной для данного дисплея;

Частота вертикальной развертки (частота обновления): 75 Гц.

Исходя из размера диагонали дисплея, величина проектного расстояния равна 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. Технологическая часть

Ввиду того, что в данном дипломном проекте требуется создание программного продукта высокого качества, рассмотрим в этом разделе такой вопрос, как технология создания, тестирования и отладки программного обеспечения.

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. Проектирование;

. Реализация;

. Тестирование и отладка;

. Сопровождения

Кроме того, сюда в настоящее время сюда так же добавился такой пункт, как сертификация или аттестация ПО. [12]

Рассмотрим каждый из этих пунктов подробнее.

Анализ требований и определение спецификаций

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

Существует два вида требований, рассматриваемых на данном этапе:

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

. Эксплуатационные требования определяют характеристики разрабатываемого программного обеспечения, проявляемые в процессе его использования. К таким характеристикам относят:

· правильность - функционирование в соответствии с техническим заданием. Это требование является обязательным для всякого программного продукта, но поскольку никакое тестирование не дает гарантии 100%-ной правильности, речь может идти об определенной вероятности наличия ошибок. Вероятность сбоя системы управления космическими полетами должна быть близка к нулю;

· универсальность - обеспечение правильной работы при любых допустимых данных и защиты от неправильных данных. Так же как в предыдущем случае, доказать универсальность программы невозможно, поэтому имеет смысл говорить о степени ее универсальности;

· надежность (помехозащищенность) - обеспечение полной повторяемости результатов, т.е. обеспечение их правильности при наличии различного рода сбоев. Источниками помех могут являться технические и программные средства, а также люди, работающие с этими средствами. В настоящее время существует достаточное количество способов избежать потерь информации при сбоях. Например, прием «создания контрольных точек», при котором сохраняются промежуточные результаты, что позволяет после программы продолжить работу с данными, записанными в последней контрольной точке. Возможно также уменьшить количество ошибок, используя дублирование систем или ввод избыточной информации;

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

· точность результатов - обеспечение погрешности результатов не выше заданной. Величина погрешности зависит от точности исходных данных, степени адекватности используемой модели, точности выбранного метода и погрешности выполнения операций в компьютере. Жесткие требования к точности предъявляют системы навигации (например, система стыковки космических аппаратов) и системы управления технологическими процессами;

· защищенность - обеспечение конфиденциальности информации. Наиболее жесткие требования предъявляются к системам, в которых хранится информация, связанная с государственной и коммерческой тайной. Для обеспечения защиты информации используют программные, криптографические, правовые и другие методы;

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

· эффективность - использование минимально возможного количества ресурсов технических средств (например, времени микропроцессора, объема оперативной памяти, объема внешней памяти, количества внешних устройств и др.). Эффективность оценивается по каждому ресурсу отдельно, поэтому требования эффективности часто противоречат друг другу. Например, чтобы уменьшить время выполнения программы, необходимо увеличить объем оперативной памяти;

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

· повторная входимость - возможность повторного выполнения без перезагрузки с диска. Данное требование обычно предъявляется к программному обеспечению, резидентно загруженному в оперативную память (например, драйверы);

· реентерабельность - возможность «параллельного» использования несколькими процессами. Чтобы удовлетворить этому требованию, необходимо создавать копию данных, изменяемых программой, для каждого процесса.

Четко сформулировать спецификации требований к разрабатываемому ПО, чтобы затем занести их в техническое задание, - достаточно сложная и ответственная задача, которая требует проведения предпроектных исследований. [12]

Проектирование программного обеспечения

В настоящее время существует два основных подхода к проектированию программного обеспечения: структурное и объектное.

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

Структурной называют схему, отражающую состав и взаимодействие по управлению частей разрабатываемого программного обеспечения.

Разработку структурной схемы программы обычно выполняют методом пошаговой детализации.

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

Компонентами структурной схемы программной системы или программного комплекса могут служить программы, подсистемы, базы данных, библиотеки ресурсов и т.п.

Функциональная схема (ГОСТ 19.701-90) - это схема взаимодействия компонентов программного обеспечения с описанием информационных потоков, состава данных в потоках и указанием используемых файлов и устройств.

Функциональные схемы, как правило, более информативны, чем структурные.

При объектном подходе используется разделение на логическое и физическое проектирование программных продуктов. Логическое проектирование заключается в разработке классов для реализации их экземпляров - объектов. Для этого требуется подробное описание полей и методов классов, а также связей между ними. Для этого используются статические диаграммы классов и объектов и динамические диаграммы последовательностей состояний и кооперации. Физическое проектирование предполагает построение программных компонентов из ранее определенных классов и объектов и размещение их на конкретных вычислительных устройствах. Разрабатываемые на этом этапе диаграммы - компонентов и развертывания. [12]

Тестирование и отладка программных продуктов

При тестировании программных продуктов применяются два основных метода тестирования - тестирование «черного» и «белого» ящика. Рассмотрим каждый их них подробнее.

Тестирование «черного ящика»

Известны: функции программы.

Исследуется: работа каждой функции на всей области определения.

Тесты «черного» ящика демонстрируют:

· как выполняются функции программ;

· как принимаются исходные данные;

· как вырабатываются результаты;

· как сохраняется целостность внешней информации.

При тестировании «черного ящика» рассматриваются системные характеристики программ, игнорируется их внутренняя логическая структура. Исчерпывающее тестирование, как правило, невозможно. Например, если в программе 10 входных величин и каждая принимает по 10 значений, то потребуется 1010 тестовых вариантов. Отметим также, что тестирование «черного ящика» не реагирует на многие особенности программных ошибок. [12]

Тестирование «белого ящика»

Известна: внутренняя структура программы.

Исследуются: внутренние элементы программы и связи между ними.

Объектом тестирования здесь является не внешнее, а внутреннее поведение программы. Проверяется корректность построения всех элементов программы и правильность их взаимодействия друг с другом. Обычно анализируются управляющие связи элементов, реже - информационные связи. Тестирование по принципу «белого ящика» характеризуется степенью, в какой тесты выполняют или покрывают логику (исходный текст) программы. Исчерпывающее тестирование также затруднительно. [12]

Методика тестирования программных систем

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

В начале осуществляется тестирование элементов (модулей), проверяющее результаты этапа кодирования ПС. На втором шаге выполняется тестирование интеграции, ориентированное на выявление ошибок этапа проектирования ПС. На третьем обороте спирали производится тестирование правильности, проверяющее корректность этапа анализа требований к ПС. На заключительном витке спирали проводится системное тестирование, выявляющее дефекты этапа системного анализа ПС.

Охарактеризуем каждый шаг процесса тестирования.

. Тестирование элементов. Цель - индивидуальная проверка каждого модуля. Используются способы тестирования «белого ящика».

Рисунок 4.2.4. Спираль процесса тестирования ПС

. Тестирование интеграции. Цель - тестирование сборки модулей в программную систему. В основном применяют способы тестирования «черного ящика».

. Тестирование правильности. Цель - проверить реализацию в программной системе всех функциональных и поведенческих требований, а также требования эффективности. Используются исключительно способы тестирования «черного ящика».

. Системное тестирование. Цель - проверка правильности объединения и взаимодействия всех элементов компьютерной системы, реализации всех системных функций.

Организация процесса тестирования в виде эволюционной разворачивающейся спирали обеспечивает максимальную эффективность поиска ошибок. Однако возникает вопрос - когда заканчивать тестирование?

Ответ практика обычно основан на статистическом критерии: «Можно с 95%-ной уверенностью сказать, что провели достаточное тестирование, если вероятность безотказной работы ЦП с программным изделием в течение 1000 часов составляет по меньшей мере 0,995».

Научный подход при ответе на этот вопрос состоит в применении математической модели отказов. Например, для логарифмической модели Пуассона формула расчета текущей интенсивности отказов имеет вид:

где - текущая интенсивность программных отказов (количество отказов в единицу времени); - начальная интенсивность отказов (в начале тестирования); р - экспоненциальное уменьшение интенсивности отказов за счет обнаруживаемых и устраняемых ошибок; t - время тестирования.

С помощью уравнения (8.1) можно предсказать снижение ошибок в ходе тестирования, а также время, требующееся для достижения допустимо низкой интенсивности отказов. [12]

Отладка программного продукта

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

Итак, процессу отладки предшествует выполнение тестового варианта. Его результаты оцениваются, регистрируется несоответствие между ожидаемым и реальным результатами. Несоответствие является симптомом скрытой причины. Процесс отладки пытается сопоставить симптом с причиной, вследствие чего приводит к исправлению ошибки. Возможны два исхода процесса отладки:

· причина найдена, исправлена, уничтожена;

· причина не найдена.

Во втором случае отладчик может предполагать причину. Для проверки этой причины он просит разработать дополнительный тестовый вариант, который поможет проверить предположение. Таким образом, запускается итерационный процесс коррекции ошибки.

Возможные разные способы проявления ошибок:

· программа завершается нормально, но выдает неверные результаты;

· программа зависает;

· программа завершается по прерыванию;

· программа завершается, выдает ожидаемые результаты, но хранимые данные испорчены (это самый неприятный вариант).

Характер проявления ошибок также может меняться. Симптом ошибки может быть:

· постоянным;

· мерцающим;

· пороговым (проявляется при превышении некоторого порога в обработке - 200 самолетов на экране отслеживаются, а 201-й - нет);

· отложенным (проявляется только после исправления маскирующих ошибок).

В ходе отладки мы встречаем ошибки в широком диапазоне: от мелких неприятностей до катастроф. Следствием увеличения ошибок является усиление давления на отладчика. Часто из-за этого давления разработчик устраняет одну ошибку и вносит две новые ошибки.

Английский термин debugging (отладка) дословно переводится как «ловля блох», который отражает специфику процесса - погоню за объектами отладки, «блохами». Рассмотрим, как может быть организован этот процесс «ловли блох».

Различают две группы методов отладки:

· аналитические;

· экспериментальные.

Аналитические методы базируются на анализе выходных данных для тестовых прогонов. Экспериментальные методы базируются на использовании вспомогательных средств отладки (отладочные печати, трассировки), позволяющих уточнить характер поведения программы при тех или иных исходных данных.

Общая стратегия отладки - обратное прохождение от замеченного симптома ошибки к исходной аномалии (месту в программе, где ошибка совершена).

В простейшем случае место проявления симптома и ошибочный фрагмент совпадают. Но чаще всего они далеко отстоят друг от друга.

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

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

Основное преимущество аналитических методов отладки состоит в том, что исходная программа остается без изменений.

В экспериментальных методах для прослеживания выполняется:

· Выдача значений переменных в указанных точках;

· Трассировка переменных (выдача их значений при каждом изменении);

· Трассировка потоков управления (имен вызываемых процедур, меток, на которые передается управление, номеров операторов перехода).

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

Недостаток экспериментальных методов отладки - в программу вносятся изменения, при исключении которых могут появиться ошибки. Впрочем, некоторые системы программирования создают специальный отладочный экземпляр программы, а в основной экземпляр не вмешиваются. (С.А, 2003) [13]

4.3 Сертификация бортового программного обеспечения

Под понятием «программное обеспечение, критичное с точки зрения безопасности» (Safety-Critical Software - для краткости будем называть его «критичное программное обеспечение») обычно понимают такое программное обеспечение, которое влияет на поведение систем, сбой которых может повлечь риск для человеческих жизней.

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

Главным препятствием, стоящим на пути применения «коробочных» программных продуктов в критических областях, является недостаточная информация о «родословной» изделий, т.е. о процессах разработки, тестирования, верификации и управления качеством и т.п. Эту проблему в значительной мере решает как лицензирование деятельности предприятий, так и сертификация соответствующей продукции на соответствие определенным требованиям, сформулированным, как правило, в виде стандартов или иных руководящих документов. К функциональной безопасности программного обеспечения имеет отношение ряд международных и национальных, общих и отраслевых стандартов, регламентирующих жизненный цикл технических систем. Основные из этих стандартов подробно рассмотрены в работе «Технологические процессы и стандарты обеспечения функциональной безопасности в жизненном цикле программных средств» (В.В Липаев). Мы же рассмотрим такой важный аспект разработки критичного программного обеспечения, как тестирование.

Тестирование является одним из видов верификации и направлено на определение того, соответствует ли программное обеспечение требованиям спецификации. Каким же образом можно понять, следует ли доверять проведенному тестированию или нет?

ГОСТ Р ИСО/МЭК 15408 (известный под названием «Общие критерии») в отношении тестирования вводит понятия «Покрытие» и «Глубина». Покрытие показывает полноту охвата тестами (т.е. покрытие тестами) функциональных возможностей объекта оценки, а глубина характеризует уровень детализации тестирования. При оценке корректности тестирования за рубежом часто используют классификацию и требования, установленные в стандарте DO-178B «Software Considerations in Airborne Systems and Equipment Certification» («Оценки программного обеспечения для сертификации бортовых авиационных систем и оборудования»), известный в Европе как ED-12B. DO-178B исходит из того, что при эксплуатации системы существуют потенциальные угрозы безопасности, возникающие при сбое программного обеспечения (например, останов двигателей самолета в полете), и возможных последствий такого сбоя.

Сертификация программного обеспечения на соответствие DO-178B, по сути дела, заключается в проверках, как реализованы средства предотвращения угроз. Очевидно, что, с одной стороны, не всегда ошибка в программе приводит к сбою системы, с другой стороны, сбой системы может произойти по причине, независящей от программы.

Поэтому сертификация программного обеспечения отдельно от системы, в состав которой она входит, не имеет смысла.

Исходя из возможных последствий сбоя, DO-178B определяет уровни опасности и соответствующие им уровни сертификации программного обеспечения (см. таблицу 4.3.1).

Таблица 4.3.1 Уровни сертификации программного обеспечения

Уровень	Влияние на безопасность
A	Программное обеспечение, сбой которого может привести к возникновению или способствовать возникновению катастрофического сбоя самолета.
B	Программное обеспечение, сбой которого может создать условия или способствовать созданию условий для опасного сбоя
C	Программное обеспечение, сбой которого может создать условия или способствовать созданию условий для крупного сбоя
D	Программное обеспечение, сбой которого может создать условия или способствовать созданию условий для малозначительного сбоя
E	Программное обеспечение, сбой которого не может влиять на самолет или на нагрузку пилота

B требует, чтобы каждая строка кода была выполнена в ходе тестирования.

Запрещается включение в состав приложения какого-либо дополнительного кода, не прошедшего тестирование. Для каждого уровня сертификации заданы свои требования к покрытию тестами проверяемого кода:

1. Покрытие операторов (Statement Coverage - SC) означает, что в ходе тестирования каждый оператор программы был вызван или использован не менее одного раза. Когда говорят о покрытии кода - «Code coverage» - обычно имеют ввиду именно SC.

2. Покрытие ветвей (Decision Coverage - DC) означает, что в ходе тестирования каждая точка входа в программу и выхода из нее была использована не менее одного раза так, что каждое возможное значение логических условий принималось не менее одного раза. По сути дела, это означает, что в ходе тестирования каждое логическое условие имело и значение «истина», и значение «ложь».

. Покрытие условий и ветвей (Modified Condition/Decision Coverage - MC/DC) означает, что в ходе тестирования каждая точка входа в программу и выхода из нее была использована не менее одного раза так, что каждое решение в программе принимало все возможные значения, и при этом было показано, какое влияние оказывает на решение каждое условие независимо от остальных условий. Для сложных логических операций необходимо разрабатывать таблицы истинности, что бы определить все возможные комбинации значений «истина» и «ложь».

В таблице 3.4.2 показано, какие из требований к покрытию кода тестами предъявляются на разных уровнях сертификации:

Таблица 4.3.2 Требования к покрытию кода

Уровень	Покрытие	Требования к покрытию
A	MC/DC	Уровень B + 100% MC/DC
B	DC	Уровень C + 100% DC
C	SC	Уровень D + 100% SC
D		100% покрытие требований
E		Нет требований

Наверное, трудно представить себе коммерческую разработку, к которой предъявляются требования по уровню E. Сертификация же программного обеспечения по уровню D имеет родственников в российской практике: приемо-сдаточные испытания и проверка соответствия реальных возможностей декларированным. Проверки по уровням A, B и C невозможны без специализированных инструментальных средств.

Разумеется, реализация требований DO-178B (впрочем, как и других нормативных документов) приводит к существенному увеличению стоимости продуктов, что связано со значительными затратами на разработку дополнительных тестов, проведения дополнительных процедур тестирования и на разработку дополнительной технической документации. В связи с этим на рынке программного обеспечения существуют инструментальные средства, помогающие автоматизировать процесс верификации программ. Такие инструменты могут поставляться как штатные компоненты в составе интегрированных сред разработки, так и в виде специализированных инструментов. [14]

4.4 Модели качества процессов конструирования

В современных условиях, условиях жесткой конкуренции, очень важно гарантировать высокое качество вашего процесса конструирования ПО. Такую гарантию дает сертификат качества процесса, подтверждающий его соответствие принятым международным стандартам. Каждый такой стандарт фиксирует свою модель обеспечения качества. Наиболее авторитетны модели стандартов ISO 9001:2000, ISO/IEC 15504 и модель зрелости процесса конструирования ПО (Capability Maturity Model - СММ) Института программной инженерии при американском университете Карнеги-Меллон.

Модель стандарта ISO 9001:2000 ориентирована на процессы разработки из любых областей человеческой деятельности. Стандарт ISO/IEC 15504 специализируется на процессах программной разработки и отличается более высоким уровнем детализации. Достаточно сказать, что объем этого стандарта превышает 500 страниц. Значительная часть идей ISO/IEC 15504 взята из модели СММ.

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

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

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

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

Начальный уровень (уровень 1) означает, что процесс в компании не формализован. Он не может строго планироваться и отслеживаться, его успех носит случайный характер. Результат работы целиком и полностью зависит от личных качеств отдельных сотрудников. При увольнении таких сотрудников проект останавливается.

Для перехода на повторяемый уровень (уровень 2) необходимо внедрить формальные процедуры для выполнения основных элементов процесса конструирования. Результаты выполнения процесса соответствуют заданным требованиям и стандартам. Основное отличие от уровня 1 состоит в том, что выполнение процесса планируется и контролируется. Применяемые средства планирования и управления дают возможность повторения ранее достигнутых успехов.

Следующий, определенный уровень (уровень 3) требует, чтобы все элементы процесса были определены, стандартизованы и задокументированы. Основное отличие от уровня 2 заключается в том, что элементы процесса уровня 3 планируются и управляются на основе единого стандарта компании. Качество разрабатываемого ПО уже не зависит от способностей отдельных личностей.

С переходом на управляемый уровень (уровень 4) в компании принимаются количественные показатели качества как программных продуктов, так и процесса. Это обеспечивает более точное планирование проекта и контроль качества его результатов. Основное отличие от уровня 3 состоит в более объективной, количественной оценке продукта и процесса.

Высший, оптимизирующий уровень (уровень 5) подразумевает, что главной задачей компании становится постоянное улучшение и повышение эффективности существующих процессов, ввод новых технологий. Основное отличие от уровня 4 заключается в том, что технология создания и сопровождения программных продуктов планомерно и последовательно совершенствуется.

Каждый уровень СММ характеризуется областью ключевых процессов (ОКП), причем считается, что каждый последующий уровень включает в себя все характеристики предыдущих уровней. Иначе говоря, для 3-го уровня зрелости рассматриваются ОКП 3-го уровня, ОКП 2-го уровня и ОКП 1-го уровня. Область ключевых процессов образуют процессы, которые при совместном выполнении приводят к достижению определенного набора целей. Например, ОКП 5-го уровня образуют процессы:

· предотвращения дефектов;

· управления изменениями технологии;

· управления изменениями процесса.

Если все цели ОКП достигнуты, компании присваивается сертификат данного уровня зрелости. Если хотя бы одна цель не достигнута, то компания не может соответствовать данному уровню СММ. [12]

Список литературы

1. Росс Клемент «Генетические алгоритмы: почему они работают? когда их применять?», Компьютерра №11/1999

2. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К «Алгоритмы: построение и анализ»/ Под ред. И.В. Красикова. - 2-е изд. - М.: Вильямс, 2005.

3. P.B. Sujit A. Sinha D. Ghose «Multiple UAV Task Allocation using Negotiation» AAMAS '06: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems New York, NY, USA: ACM Press (2006), p. 471-478.

. R. Nallusamy, K. Duraiswamy, R. Dhanalaksmi, P. Parthiban «Оptimization of non-linear multiple traveling salesman problem using k-means clustering, shrink wrap algorithm and meta-heuristics», International Journal of Nonlinear Science Vol.8 (2009) No.4, pp.480-487

. Glover, F. «Tabu Search - Part I», ORSA Journal on Computing 1989 1: 3, 190-206.

6. Головко В.А. «Нейронные сети: обучение, организация и применение», М.:ИЖПР, 2001

7. Дьяконов В.П. MATLAB 7.*/R2006/2007. Самоучитель. - М.: «ДМК-Пресс», 2008.

8. СанПиН 2.2.2/2.4.2198-07 (изменение №1 к СанПиН 2.2.2/2.4.1340-03) «Гигиенические требования к видеодисплейным терминалам, персональным электронно-вычислительным машинам и организация работы»

9. ГОСТ Р 50948-2001 «Средства отображения информации индивидуального пользования. Общие эргономические требования и требования безопасности»

. Соснин П.И. Вербиченко Д.С. «Методы и средства активизации внимания в человеко-компьютерном взаимодействии»

. Жоголев Е.А. «Лекции по технологии программирования», ВМК МГУ, 2000

. Гагарина Л.Г. «Технология разработки программного обеспечения» М.: Форум Инфра-М, 2009

. Орлов С.А. Технологии разработки программного обеспечения: Учебное пособие. 2-е изд. СПб.: Питер, 2003.

. Брауде Э.Д. «Технология разработки программного обеспечения», СПб.: Питер, 2004

. Золотарев С.В. «LynxOS-178 - коммерческая ОСРВ для авиации». - PC Week/RE, №22/2005.

Разработка алгоритмов поиска оптимального маршрута для БЛА при наблюдении им подвижных наземных объектов