Содержание к диссертации
Введение
1. Анализ методов и алгоритмов планирования траектории 11
1.1 Предметная область 11
1.2 Задача планирования как задача поиска пути на графе 17
1.3 Методы поиска пути на графе 20
1.3.1 Поиск пути на графе как расчет g -3Ha4euuu 20
1.3.2 Эвристические алгоритмы поиска пути 25
1.3.3 Обзор работ, посвященных алгоритмам поиска пути на графе для задачи планирования траектории 31
1.3.4 Выводы 36
1.4 Методы построения графов для решения задачи планирования траектории 37
1.4.1 Методы построения графов видимости 37
1.4.2 Методы построения разбиения Вороного 42
1.4.3 Методы извлечения графовых моделей непосредственно из цифровой карты местности
1.4.4 Выводы 48
1.5. Выводы 50
2. Метрические топологические графы и их применение в задачах планирования траектории 51
2.1. Основные определения 51
2.2 Метрики на МТ-графах 56
2.2.1 Метрика кратчайшего пути 56
2.2.2 Диагональная метрика
2.3 эвристический поиск пути на мт-графах 60
2.4 проблема локального минимума 65
2.5 Выводы 69
3. Иерархический подход к задаче поиска пути на МТ графе 70
3.1 Множество кратчайших путей на мт-графе 70
3.1.1 Операция поворота и взаимное расположение клеток МТ-графа 70
3.1.2 Структура множества кратчайших путей полностью проходимого МТ-графа 76
3.1.3 Нуль-траектории на МТ-графе 89
3.2 Простейшие иерархические алгоритмы поиска пути на мт-графе 92
3.2.1 Основные определения и утверждения 92
3.2.2 Простейшие реализации иерархического подхода к поиску пути на МТ-графе 96
3.3 Алгоритм HGA 99
3.3.1. Препятствия на МТ-графе 99
3.3.2 Стратегия выделения опорных клеток алгоритма HGA 108
3.3.3 Базовая реализация алгоритма HGA 109
3.3.4 Теоретические свойства базовой реализации алгоритма HGA 116
3.3.5 Эвристическая реализация алгоритма HGА 130
3.4. Выводы 140
4. Экспериментальное обоснование эффективности алгоритманса 142
4.1 Программно-аппаратный комплекс для проведения экспериментов 142
4.1.1 Аппаратный комплекс 142
4.1.2 Программный комплекс 142
4.2 Первая серия экспериментов 145
4.3. Вторая серия экспериментов 157
4.4. Третья серия экспериментов 161
4.5. Выводы 165
Заключение 166
Список литературы 168
- Методы поиска пути на графе
- Метрика кратчайшего пути
- Структура множества кратчайших путей полностью проходимого МТ-графа
- Вторая серия экспериментов
Введение к работе
Актуальность темы исследования
Проектирование и разработка беспилотных транспортных средств различного типа и назначения является одной из наиболее активно развивающихся областей в современной науке и технике. Основной целью, преследуемой исследователями в этой области, является повышение степени автономности разрабатываемых транспортных средств. Очевидно, что для достижения указанной цели необходимо создание эффективных алгоритмов планирования траектории, т.е. перемещения транспортного средства в пространстве (окружающей среде).
Задача планирования траектории в контексте автоматизации управления сложными техническим объектами (роботами, транспортными средствами и др.) изучается с 50-х годов XX века. Одним из первых проектов в этой области являлся известный проект Стэнфордского университета США по созданию робота SHAKEY в 1966-1972 гг. Именно он положил начало многолетним исследованиям методов и подходов к решению задач планирования траектории, продолжающимся по сей день. За последние годы были успешно реализованы десятки крупных проектов в этой области, например:
- DARPA URBAN CHALLENGE (соревнования беспилотных автомобилей в городских условиях, 2008г., США)
- NASA ARP (создание системы управления малым беспилотным вертолетом Yamaha RMAX II, предназначенным для разведки и мониторинга, 1998-2003 гг. США)
- MARS (разработка программного обеспечения для автономных наземных роботов, США, 1999-2004 гг.)
- VIAC (создание беспилотной модификации гражданского автомобиля и осуществление пробега протяженностью 13 000 км., Европейский Союз, 2010)
- Робокросс (соревнования автомобилей-роботов, Россия, 2010).
К сожалению, почти все методы планирования траектории, разработанные к текущему моменту и используемые в системах управления современными беспилотными транспортными средствами, являются достаточно ресурсоемкими. При этом большинство из них принципиально не способно решать задачи планирования траектории в условиях дефицита вычислительных ресурсов. Следовательно, известные методы неприменимы тогда, когда речь об автоматизации малых, полностью автономных беспилотных транспортных средств, т.к. подобные транспортные средства не могут быть оснащены мощными вычислителями в силу особенностей конструкции и ограниченной грузоподъемности.
Таким образом, представляются достаточно актуальными задачи создания эффективных (в вычислительном смысле) методов планирования траектории, применимых в системах управления малыми, полностью автономными транспортными средствами нового поколения. Настоящая работа посвящена исследованию и решению некоторых возникающих в этой области задач, что свидетельствует о ее актуальности.
Теоретической и методологической основой исследования послужили труды отечественных и зарубежных ученых в области искусственного интеллекта Д.А. Поспелова, Г.С. Осипова, В.Л. Стефанюка, Дж. МакКарти, Н. Нильсона, исследования в области робототехники В.Б. Мелехина, Л.С. Берштейна, Р. Аркина, С. Труна, работы в области исследования эвристических алгоритмов поиска пути на графе М. Лихачева, С. Коенига, работы в смежных областях (управление, генетический алгоритмы) Л.Н. Никифоровой, В.М. Курейчика.
Цели и задачи исследования
Целью диссертационной работы является разработка новых вычислительно-эффективных методов планирования траектории на плоскости.
Для достижения поставленной цели в работе решены следующие задачи:
-
Выполнен анализ существующих методов построения графов, являющихся моделями предметной области в задачах планирования траектории и методов поиска пути на указанных графах. Предложена и исследована графовая модель, отражающая особенности задачи планирования траектории на плоскости – метрический топологический граф (МТ-граф).
-
Разработаны принципы иерархической декомпозиции задачи планирования траектории и алгоритм планирования траектории, реализующий эти принципы – HGA*.
-
Исследованы свойства алгоритма HGA* при определенных ограничениях. Предложены модификации алгоритма HGA*, предназначенные для решения различных типов задач планирования траектории на плоскости.
-
Разработаны программные средства для оценки вычислительной эффективности различных алгоритмов планирования траектории. Проведена серия вычислительных экспериментов, направленных на сравнение разработанного алгоритма HGA* с аналогами.
Методы исследования
В диссертационной работе использованы методы искусственного интеллекта, теории множеств, математической логики, теории графов.
Научная новизна работы
Традиционно, для решения задачи планирования траектории в качестве модели предметной области используются взвешенные графы. Вершинам графа соответствуют географические координаты точек пространства, весам ребер – соответствующие расстояния. Такое представление предметной области позволяет использовать для решения поставленной задачи различные алгоритмы поиска пути на графе, среди которых особый интерес представляет алгоритмы эвристического поиска семейства A*. В настоящее время существует множество модификаций алгоритма A*, каждая из которых предназначена для решения задач планирования траектории с определенным типом ограничений. Однако, практически все алгоритмы семейства A*, разработанные к настоящему времени, принципиально не способны решать задачу локального минимума и, как следствие, строить планы в условиях дефицита вычислительных ресурсов, а именно, процессорного времени и рабочей памяти. Таким образом, необходимы разработка и исследование новых методов поиска пути на графе, опирающихся на иные принципы, нежели известные алгоритмы семейства A*. В настоящей работе предлагается новый метод решения поставленной задачи, опирающийся на принцип иерархической декомпозиции. Описывается новый алгоритм поиска пути, реализующий указанный принцип.
Важным вопросом в решении задачи планирования траектории является вопрос построения графа, моделирующего окружающую среду для объекта управления (беспилотного транспортного средства). К распространенным графовым моделям, используемым для решения подобного рода задач, относятся граф видимости и разбиение Вороного. Однако, методы построения указанных графов не применимы для решения практических задач навигации беспилотных транспортных средств, т.к. основаны на использовании «непрерывных» моделей окружающего пространства, в то время как в памяти бортового вычислителя транспортного средства хранится дискретная цифровая карта местности. В работе предлагается и исследуется новая графовая модель, отражающая особенности задачи планирования траектории на плоскости – метрический топологический граф, которая может быть извлечена непосредственного из цифровой карты местности.
Таким образом, научная новизна работы заключается в исследовании и разработке новой графовой модели и нового метода поиска пути на графе в рамках решения задачи планирования траектории на плоскости.
Практическая значимость работы
Методы и алгоритмы, полученные в диссертации, могут быть использованы при разработке систем управления беспилотными транспортными средствами нового поколения.
Методы и алгоритмы реализованы в виде независимых программных модулей и используются в следующих проектах:
-
«Интеллектуальная система поддержки автоматизированного маловысотного полета вертолета», проект Российского Фонда Фундаментальных исследований № 09-07-00043-а
-
«Развитие методов анализа полуструктурированной информации и моделирования целенаправленного поведения», выполняемого в рамках федеральной целевой программы «Научные и научно-педагогические кадры инновационной России».
-
«Развитие методов интеллектуального управления на основе анализа потоков данных», проект 2.2 Отделения нанотехнологий и информационных технологий Российский академии наук.
Апробация работы
Основные положения работы докладывались и обсуждались на следующих научных конференциях и семинарах:
-
XII национальная конференция по искусственному интеллекту с международным участием (КИИ-2010), 2010, г. Тверь.
-
Общемосковский научный семинар «Проблемы искусственного интеллекта», 2010, г. Москва.
-
III международная конференция «Системный анализ и информационные технологии – САИТ 2009», сентябрь 2009, г. Звенигород
-
IX международная научной конференция им. Таран Т.А «Интеллектуальный анализ информации – ИАИ-2009», май 2009, г. Киев, Украина.
-
XLIII всероссийская конференции по проблемам математики, информатики, физики и химии Российского университета дружбы народов, апрель 2008, г. Москва.
Публикации
По теме диссертационной работы опубликовано 9 печатных работ (в том числе 2 публикации в ведущих рецензируемых научных изданиях, рекомендованных Высшей аттестационной комиссией).
Личный вклад соискателя
Результаты, выносимые на защиту, получены автором самостоятельно.
Структура и объем работы
Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа изложена на 184 стр. машинописного текста, содержит 8 таблиц, 86 рисунков, 1 приложение, библиография включает 75 наименований.
Методы поиска пути на графе
В настоящее время известно большое число методов и алгоритмов поиска (кратчайшего) пути на неориентированном взвешенном графе. Условно их можно разделить на две категории: классические методы и методы искусственного интеллекта. Принципиальная разница между алгоритмами указанных категорий заключается в том, что первые нацелены на получение оптимального решения, без учета особенностей предметной области, вторые используют различные эвристики, (формализованные знания о предметной области) для снижения вычислительной нагрузки, (что особенно-актуально в области управления БТС) и нацелены на получение допустимого решения. К классическим алгоритмам относятся- такие алгоритмы, как алгоритм поиска кратчайшего пути с помощью обхода графа в ширину, алгоритм поиска кратчайшего пути с помощью обхода" графа в глубину, алгоритм Дейкстры и т.д. К алгоритмам, использующим методы искусственного интеллекта, относятся алгоритм А и его многочисленные вариации (WA , Anytime A , ARA , D , FSA , LP A , HP А и т.д.).
Несмотря на существенную разницу между алгоритмами из разных категорий принцип, с помощью которого они осуществляют поиск пути — один. Он заключается в итерационном обходе вершин графа и присваивании (расчете) для каждой вершины определенных числовых характеристик, с помощью которых впоследствии отыскивается решение задачи. Опишем этот процесс.
Предположим, что для каждой вершины графа s известен вес кратчайшего пути в эту вершину из вершины sstart. Обозначим эту величину как g (s) и будем ссылаться на нее как на g -значение вершины s. Тогда для того, чтобы отыскать кратчайший путь из из sstart в sgoai, достаточно осуществить регрессивный поиск по алгоритму, представимому в виде следующей последовательности шагов: Шаг 1. Выбрать в качестве текущей вершины s вершину sgoai
В основе методов обхода графа для расчета # -значений лежат два понятия - понятие g-значения вершины (g(s)) и понятие раскрытия вершины. Под g-значением вершины s понимается вес кратчайшего пути из sstart в s, зафиксированный к текущей итерации алгоритма обхода. Фактически g-значение вершины - есть оценка веса кратчайшего пути из начальной вершины в рассматриваемую. При этом g(s) g (s). Для выполнения этого неравенства перед началом работы алгоритма обхода полагается g(s)=co\/s?$starb g(sslart)=0. В ходе работы алгоритма g-значения одних вершин уменьшаются за счет раскрытия других вершин, пока не будет выполнено равенство g(s)=g (s).
Под раскрытием вершины s подразумевается выполнение процедуры, алгоритм которой приведен на рис. 1.6. Для( всех вершин s смежных с s проверяется - может ли быть величина gts ) уменьшена за счет перехода из раскрываемой вершины, и если может, то происходит обновление gis1). Заметим, что раскрытие вершины s не влияет на величину g(s), которая может измениться лишь вследствие раскрытия некоторой вершины из adj(s).
Процедура раскрытия вершины графа. В процессе обхода графа вершины раскрываются последовательно, начиная с вершины sstart. Множество вершин графа, с приписанными (в результате раскрытия некоторой вершины) g-значениями добавляется (сохраняется) в множество кандидатов на последующее раскрытие. Такое множество принято называть списком OPEN. После добавления вершин, список OPEN упорядочивается каким-либо образом1, и из него выбирается минимальная вершина в смысле заданного порядка. Она подлежит раскрытию на следующей итерации. И так происходит до тех пор, пока список OPEN не будет исчерпан, что говорит о стабилизации g-значений (то есть о «превращении» их в g -3Ha4eH ).
Метрика кратчайшего пути
Пусть-тгО/,-, а!к)={аіор, aiiJb ai2jl, ..., alsJs} - путь из ay в а1к на МТ-графе Ату.п, Тогда переходом назовем пару смежных клеток пути {аЫр.,, а„ J%), v: l v s. Обозначим число переходов, составляющих путь яг, как N{K)=HJjz)+Nh{n)+Nv{7z), где Л (яг) - число переходов между горизонтально-смежными клетками, ІУу(яг) - число переходов между вертикально-смежными клетками, Ncfcv) - число переходов между диагонально-смежными клетками.
Заметим, что іУ(яг)=яг-1, где яг - число клеток, входящих в путь яг. Вес пути ж определяется как сумма весов переходов по всем смежным клеткам, входящим в данный путь: с(ж)=Ус(а, , ,а, , ) v=l Кратчайшим путем из ay в a\k будем называть такой путь ж (ау, a/k), что V ЖФ-Ж с(ж ) с(ж). Рассмотрим отдельно случай, когда ay=aik, то есть когда начальная и целевая клетки совпадают. В этом случае будем считать (по определению), что путь ж(а,у, aik) имеет вид ж(ау, аік)=ж(ау, ау)={ау}, а вес пути определяется как: с(ж(ау, ау))=с(ж (ау, ау)=0.
Используя приведенное выше описание МТ-графа, задачу планирования траектории на плоскости можно формально представить в виде тройки: PTask=(MT-Gr, astartIstar(J, agoaugoau) и сформулировать следующим образом. Пусть на МТ-графе зафиксированы начальная astarti startJ и целевая agoaii goau клетки, такие что &startl startfr&goall goaU astartlstartj , agoallgoaU l- НеобхОДИМО НаЙТИ ПуТЬ 1t(astart[ starU Qgoaiigoau), то есть последовательность клеток МТ-графа ж={аЮ]о, аир, ai2j2, ..., aisjs} такую, что aiOJo astartIstarU, aisjs=agoangoaU, Vv: l v s, (aiv.1Jv.„ aivJv)eADJ.
Глубиной решения задачи планирования назовем величину max{\goalI-startl], \goalJ-startJ\}. Фактически глубина решения - есть число переходов в кратчайшем возможном пути из astartIstartJ в agoa!Igoau. Как и раньше (см. раздел 1.2) путь из astartItStaru в ag0aii,goau будем называть допустимым путем или допустимым решением задачи» планирования. В качестве критерия оптимальности для оценки допустимых решений задачи будем рассматривать функционал min{c(;r)} . То есть 7r =SP(Ssur,,S ,)r кратчайший путь из astarti startJ в agoaU goau соответствует оптимальному решению задачи планирования траектории БТС на плоскости.
Отметим, что решение задачи планирования заключается в нахождении хотя бы одного (кратчайшего) пути на заданном графе, а не описание в явном
В предыдущем разделе было введено понятие веса перехода между смежными клетками МТ-графа как значения некоторой функции с: ADJ- {cilv, cd, +00}, где с& ChV — некоторые константы, связанные соотношением: cd=k-chv, 1 к 2. Определим с помощью функции с и констант Chv cd две различные метрики на МТ-графе АтХп.
Покажем, что такое определение удовлетворяет свойствам метрики. 1. Пусть ау аік, тогда с(л: )=0 по определению. s Пусть с(я: )=0. По определению с(г )=Ус(я: . ,а{ . ). В случае, »-Л- vJv v=l если awj0 и aUJs различны, то данная сумма больше нуля, т.к. содержит два или более неотрицательных слагаемых (см. определение веса перехода между смежными клетками). Таким образом, если с(ж )=0, то необходимо начальная и целевая клетки совпадают. Итак, difltj, aik)=c(7U {ay, aik))=0 о ау=а1к. слагаемых с{ж(ау, ЙГО)) и с(ж(а , #/&)). При этом с(ж (ау, а аік))=с(л (ау, Ovw))+cfa (aw, а1к)). В свою очередь с(ж (ау, а аік)) с(ж {ач; аік)) по определению кратчайшего пути. Таким образом, с(ж (ау, а У)+с(ж (аУМ„ аік)) с(ж (ау, aik)). 3.2. Поскольку клетки были выбраны произвольно, можно утверждать, что:
Итак, мы показали, что вес кратчайшего пути, как функция начальной и целевой клеток, задает метрику на МТ-графе. Данная метрика позволяет говорить о расстоянии между двумя клетками, как о весе кратчайшего пути, который в свою очередь складывается из весов переходов между смежными клетками.
Доказательства данных свойств будут приведены в последующих разделах работы. Пока же примем указанные утверждения верными без доказательства.
Любому (корректно-определенному) МТ-графу соответствует взвешенный граф, который может быть описан с помощью следующего набора правил: каждой клетке МТ-графа соответствует вершина графа; множеству ADJ МТ-графа соответствует множество ребер графа (смежным клеткам МТ-графа соответствуют смежные вершины графа); веса ребер, соединяющих смежные вершины графа, равняются весам переходов между соответствующими клетками МТ-графа. Таким образом, можно утверждать, что для МТ-графов справедливы те же алгоритмы поиска, что и для графов, в частности алгоритмы поиска семейства А . При этом, если в качестве эвристики использовать одну из функций, определяющих метрику на МТ-графе, то согласно [Pearl, 1984] такая эвристика будет монотонной и допустимой. Соответственно, при реализации алгоритма возможно использования списка CLOSED для предотвращения повторного обхода клеток.
Структура множества кратчайших путей полностью проходимого МТ-графа
Оценим емкостную сложность алгоритма HGA и сравним ее с соответствующей оценкой алгоритма А , использующего в качестве эвристики диагональную метрику МТ-графа, - 0(Е ), где D=max{\goalI-startl\, \goalJ-startJ\) (см. раздел 2.3).
Для оценки емкостной сложности алгоритма HGA (при рассматриваемых ограничениях) заметим, что для реализации алгоритма нет необходимости хранения частичных планов (множество РРС) в явном виде. Действительно, достаточно лишь для каждой из вновь выделяемых опорных клеток сохранять указатель на предыдущую опорную (то есть клетку, являющуюся начальной клеткой секции, в результате разбиения которой и была выделена текущая опорная клетка). Схематично это факт изображен на Рис. 3.25.
Очевидно, что при рассматриваемых ограничениях (в частности при ограничении Б1), каждая опорная клетка может ссылаться не более чем на две предыдущих. Заметим, что, если ни одно препятствие не лежит между o-stanistaru и agoangoaU , то требуется хранение 2 опорных клеток. Если между astartutara и agoangoau лежит 1 препятствие, то требуется хранение не более 6» клеток; если - 2 препятствия, то - не более 10; и так далее. По принципу математической индукции получаем, что всего требуется хранить не более 2+4- W опорных клеток, где W - число препятствий, лежащих между astarti staru и agoaii goau- Очевидно, что, в силу ограничения Б1, W не может превышать значения goalJ-startJ. Более того, число препятствий, лежащих между starti staru и agoau goaU не может превышать максимума в {goalJ-startJ)l2 препятствий, достижение которого возможно, если ширина всех препятствий составляет 1 клетку. Т.к. клетка, agoau goau расположена правее agoau goau, то \goalJ-startJ\ \goalI-startl\. Следовательно, D max{\goalI-startI\, \goalJ-startJ\} =\goalJ-startJ\=goaU-startJ.
Таким-1 образом, еслиг объем памяти, требуемый- для хранения- одной (опорной) клетки МТ-графа-оценивается как 0(4), то емкостная сложность алгоритма HGA (при указанных ограничениях) составляет 0(D), где D -глубина решения задачи планирования. В то время как, емкостная сложность алгоритма А при использовании метрики в качестве эвристики (то есть при использовании лучшей из доступных эвристик)4 составляет (см. раздел 2.3) 0(D2).
Полученные оценки емкостной сложности сравнимы между собой, т.к. объем памяти, требуемый для хранения клеток, одинаков в обоих случаях. Действительно, при А поиске, хранение клетки подразумевает под собой хранение (как минимум) одной целочисленной величины (g-значение) и одного указателя (на родительскую клетку). При HGA поиске требуется хранение двух указателей. Принимая во внимание тот факт, что для большинства вычислительных систем, объем оперативной памяти, выделяемой для величины типа «указатель», равен объему памяти, выделяемой для целочисленной переменной, то можно считать, что в обоих случаях требуется одинаковый объем памяти для хранения клетки, который может быть оценен как 0(1). Следовательно, оценки емкостной сложности обоих алгоритмов сравнимы.
Пусть на МТ-графе содержится лишь одно препятствие - obs\. Тогда, очевидно, что либо оно расположено между начальной и целевой клетками, либо нет. В последнем случае, алгоритм закончит свою работу, не произведя ни одной полной итерации (на шаге 3 будет возвращен частичный путь РР"={а3{ага staru, agoau goaij}, являющийся допустимым). В первом случае потребуется разбиение одной секции (astarti start/, agoaii goaij), которое будет осуществлено на первой итерации алгоритма, и на шаге 2 второй итерации, будет осуществлен выход. Таким образом, если МТ-граф содержит одно препятствие, то потребуется осуществление не более 1 полной итерации алгоритма.
Если МТ-граф содержит два препятствия - obs\, obs2, то потребуется осуществление не более 3 итераций алгоритма HGA . Максимальное число итераций будет осуществлено в следующем случае. На первой итерации непроходимая секция {astartI startJ, agoa!I goaij) разбивается с помощью клеток bcellui(obs\), bcellur(obs\) и bcelldi(obs{), bcelldr(pbs\), что приводит к созданию частичных путей PPf={astartI startJ, bcelluiobs{), bcellur(obsl), agoau goaU}, PP2={astartistaru, bcellu{obsx), bcellur(obsx), agoaUgoau} (Без ограничения общности можно считать, что с(РР{) с(РР2У). На второй итерации, на шаге 2 выбирается частичный путь РР\, секция {bcellur(obs\\ agoau goau), которого является непроходимой, и на шагах 7-10 этой же итерации разбивается с помощью клеток bcellui(obs2), bcellur(obs2) и bcelld&pbsz), bcelldr(obs2). Таким образом, к концу второй итерации множество РРС содержит три элемента: PP\\={astartistartJ, bcellufabsi), bcellur(obsi), bcellui(obs2), bcellur(obs2\ agoaugoaU}, PP\f={ starti startJ, bcellui(obs{), bcellur(obs{), bcellul(obs2), bcellur(obs2), agoaiIgoaU}, PPr fastarti starts, bcellul(obsi), bcell„(pbs\) agoai1: goaU} . Прш этом? PPu и PPh, являются допустимыми? (т.к. МТ-граф- содержит: лишь два; препятствия); .т c(PP$ c(iPP{i)wc(PP-2) c(PP\?) (иначе выход из; алгоритмашоследуеъ еще:до завершениям третье итерации): Нал третьей итерациш на шаге; 2 . выбирается? частичный путь PP2={astartI starUr. bcelluiobsv), bcellur{obs{)y, agoaU goau}\ секция {bcelldripbsi);agoaijgoau) которот является непроходимо юна шагах 7-Шэтой1 же итерации8 разбивается с помощью клеток- bcellui(obs2); bcellur(pbs2) и bcelldiipbs hcelldripbs i). Таким образом; к концу второшитерации множество РРЄ содержит, 4 элемента: PP\\={astartistarU,bcelMpbs{) ceU)J PPhrfastanistara bcellifabs bceWtfabs bc PPh {astartrstartj celldi(obs\) b PPk={astartistaru,bcell:di(obsi)ibcelI d Приэтомшсечастичныепути являютсядопустимыми; т.к. МТ-граф содержит лишь, два- препятствия. Следовательно,, на. четвертой итерации, на шаге 2 будет выбратодин из указанных путей; и, осуществлен-выход из: алгоритма;
Вторая серия экспериментов
Вторая серия экспериментов, была- направлена на изучение эффективности алгоритма HGA при поиске путинна;; МТ-графе, содержащем прямоугольные, препятствия разной длины. Цель экспериментов заключалась в том, чтобы проверить насколько хорошо (и хорошо ли) алгоритм справляется с большим числом «небольших» препятствий.
Для проведения экспериментов: было сгенерировано 50 МТ-графов, размером1101 (т) на 101 (п) клеток (так что глубина решения- (D); составляла 100 клеток в каждом случае), заполненных, прямоугольными препятствиями; Ширина прямоугольников (d) была фиксирована, и. составляла 1 клетку,. длина препятствий (/) составляла 2, 5, 10, 15, 25: клеток (по? 10 МТ-графовна каждое значение /было сгенерировано). Степень заполнения препятствия; (А,) была зафиксирована на отметке 0,5 во всех случаях. Генерация-МТ-графов происходила с помощью алгоритма описанного в предыдущем разделе. Данные о характеристиках сгенерированных МТ-графов сведены в таблицу
Также как и раньше, в каждом эксперименте сравнивались между собой следующие выходные параметры алгоритмов: Waig - вес пути, найденного алгоритмом algn (измеряетсяв клетках); Qaig - число клеток МТ-графа, рассмотренных при поиске пути, алгоритмом alg (измеряется в клетках); Taig — время, затраченное алгоритмом alg на поиск пути (измеряется в миллисекундах); E Qaig={QaiglWaig) - коэффициент емкостной эффективности alg (безразмерная величина); ENQaig-{QaiglWaig) {QA IWA ) — нормированный коэффициент емкостной эффективности alg (безразмерная величина). Усредненные значения указанных параметров, полученные в результате проведенных экспериментов, приведены в таблице 4.6.
Алгоритмы WA -3, WA -5, HGA значительно превосходят алгоритм А по показателям временной и емкостной эффективности. При этом, как и ранее (см. предыдущий раздел), значения указанных показателей для WA -3, WA -5 фактически совпадают (именно поэтому на вышеприведенных рисунках отображены только результаты работы одного из указанных алгоритмов).
Алгоритм HGA превосходит алгоритмы WA -3, WA -5 по рассматриваемым параметрам емкостной эффективности. При этом вес пути, найденного алгоритмом HGA , практически совпадает с весом кратчайшего пути. Показатели временной эффективности HGA находятся на уровне WA -3, WA -5 при обработке МТ-графов, содержащих прямоугольные препятсвия длиной 2, 5 и 10 клеток, и превосходят показатели WA -3, WA -5 на МТ-графах, содержащих прямоугольные препятсвия длиной 15 и 25 клеток.
Таким образом, полученные результаты позволяют утверждать, что производительность алгоритма HGA при поиске пути на МТ-графах, содержащих прямоугольные препятствия, не зависит, от размеров последних. Другими словами, алгоритм хорошо справляется с задачами планирования траектории как при наличии большого числа «небольших» препятствий, так и при наличии небольшого числа «больших» препятствий. При этом показатели емкостной и временной эффективности алгоритма HGA превосходят показатели аналогов.
Рассматривалась задача автоматического построения траектории маловысотного полета вертолета в городских условиях. МТ-графы представляли собой модели двух фрагментов карты Москвы. Препятствиям соответствовали высотные здания, которые должен облетать в горизонтальной плоскости воображаемый вертолет.
На каждом их двух МТ-графов 10 раз случайным образом выбирались начальная и целевая клетки так, чтобы глубина решения равнялась 100 клеткам. Между собой сравнивались алгоритмы A , WA -5, HGA . Также как и раньше, в каждом эксперименте отслеживались и сравнивались межу собой следующие выходные параметры алгоритмов: Waig - вес пути, найденного алгоритмом alg14 (измеряется в клетках); Qaig - число клеток МТ-графа, рассмотренных при поиске пути, алгоритмом alg (измеряется в клетках); Taig - время, затраченное алгоритмом alg на поиск пути (измеряется в миллисекундах); EQaig-iQaigfWaig) - коэффициент емкостной эффективности alg (безразмерная величина); ENQaig={Qaig/Waig) {QA IWA ) - нормированный коэффициент емкостной эффективности alg (безразмерная величина).
Результаты проведенных экспериментов позволяют сделать следующие выводы. Во-первых, отыскание оптимальных решений задачи планирования траектории (поиска пути на МТ-графе) на практике нецелесообразно из-за чрезмерно высокой ресурсоемкости. Так, в ходе экспериментов было установлено, что время ожидания оптимального решения указанной задачи, найденного с помощью алгоритма А , может достигать 10 минут. Во-вторых, использование взвешенных эвристик при поиске, в частности эвристик с весами 3 (алгоритм WA -3) и 5 (WA -5), позволяет существенно сократить вычислительную нагрузку, как по времени, так и по памяти. Однако, показанные алгоритмами WA -3 и WA -5 результаты, практически идентичны, из чего можно заключить, что дальнейшее повышение веса эвристики не приведет к улучшению результатов. То есть, на практике существует определенный «предел» эффективности, который не может быть преодолен при использовании алгоритмов семейства А для решения поставленной задачи. В-третьих, указанный «предел» эффективности может быть преодолен за счет использования принципа иерархической декомпозиции, предложенного в работе. Так алгоритм HGA , реализующий этот принцип, существенно превосходит алгоритмы семейства А по показателям емкостной эффективности, при этом не уступая (а зачастую и превосходя) аналогам по показателям временной эффективности для рассмотренного класса задач.
