Размещено на http://www.allbest.ru/

Самарский Государственный Технический Университет

Факультет автоматики и информационных технологий

Кафедра "Электронные Системы и Информационная Безопасность"

Курсовая работа

по дисциплине: Методы искусственного интеллекта

"Алгоритм планирования пути на местности"

Самара 2013



Содержание

Введение

Алгоритм А*

Проект SHAKEY

Первые БПЛА

Планирование пути из пункта А в пункт Б по дорогам общего пользования для автомобиля

Алгоритм выбора оптимального маршрута по пересеченной местности

Алгоритм оптимального движения в транспортной сети

Алгоритм прокладки оптимального маршрута при комбинированном движении

Алгоритм HGA*

Список используемой литературы



Введение

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

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



Алгоритм А*

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

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

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

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

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

? проложить оптимальный маршрут от множества стартовых точек к заданной конечной точке;

? проложить оптимальный маршрут от множества стартовых точек к заданному множеству конечных точек;

? проложить оптимальный маршрут от заданной стартовой точки к заданной конечной точке;

? построить фронт транспортной доступности с заданным уровнем затрат по отношению к множеству стартовых точек.

Известный базовый алгоритм прокладки оптимальных маршрутов основан на методе динамического планирования Форда-Беллмана на взвешенных графах (1956 - 1958 гг.). В приложении к транспортной задаче на пересеченной местности вершинами графа являются центры элементарных участков карты, а дуги соответствуют переходам между центрами смежных участков. Для транспортной сети вершинами графа являются узлы транспортной сети, а дуги соответствуют переходам между узлами, то есть дорогами. Множество алгоритмов, предложенных в последующие годы (алгоритмы Дейкстры, Калаба, A* и др.), в основном, являются вариациями базового алгоритма для частных постановок, благодаря чему достигается более высокая вычислительная эффективность данных алгоритмов по сравнению с базовым алгоритмом. Но это всего лишь доработка базового алгоритма.

Разработка алгоритмов, способный эффективно прокладывать маршрут на местности началась еще в середине 20 века, но видимый результат появился лишь в начале 70-х годов.

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

Проект SHAKEY 1971г.

Стэнфордский исследовательский институт

С 1966 по 1972 год, центр искусственного интеллекта в SRI International (Стэнфордский исследовательский институт) провел исследование системы мобильного робота по прозвищу "Шеки". Наделенный ограниченной способностью воспринимать и моделирование окружающей среды, Shakey мог выполнять задачи, требующие планирования (поиск оптимального маршрута на плоскости, и перестановка простых объектов). Проект "Shakey" привел к большому прогрессу в области технологии искусственного интеллекта.

В 1969 году для демонстрации Shakey был выпущен 24-минутный фильм "Shakey: эксперименты в обучении робота и планирования". Возможности компьютерных наук и искусственного интеллекта поразили воображение публики. 10 апреля 1968 в статье New York Times, о Шеки было написано, как о "первом электронном человеке" (что, естественно, являлось преувеличением). В ноябре 1970 года, Национальный Географический Журнал также выпустил статью о Shakey в статье о существующих способов использования возможностей компьютеров.

Первоначально, Shakey контролировался компьютером SDS-940, приобретенные в 1966 году с 64 тыс. 24-разрядных слов памяти. С помощью программирования на языке Фортран и Lisp, решение проблем Шейки было сделано в QA30. К тому моменту, когда фильм был сделан, программы Шейки заняли свыше "300 000 36-разрядных слов" (~ 1.35МБ).

Основной сферой использования алгоритма планирования пути на местности являются беспилотные летательные аппараты.

Первые БПЛА

В 1898 году Никола Тесла разработал и продемонстрировал миниатюрное радиоуправляемое судно.

В 1910 году, вдохновлённый успехами братьев Райт, молодой американский военный инженер из Огайо Чарльз Кеттеринг предложил использовать летательные аппараты без человека. По его замыслу управляемое часовым механизмом устройство в заданном месте должно было сбрасывать крылья и падать, как бомба, на врага. Получив финансирование армии США, он построил и с переменным успехом испытал несколько устройств, получивших названия The Kattering Aerial Torpedo,Kettering Bug, но в боевых действиях они так и не применялись. В Германии разрабатывается проект радиоуправляемого беспилотного бомбардировщика Fledermaus.

В 1933 году в Великобритании разработан первый БПЛА многократного использования Queen Bee. Были использованы три отреставрированных биплана Fairy Queen, дистанционно управляемые с судна по радио. Два из них потерпели аварию, а третий совершил успешный полёт, сделав Великобританию первой страной, извлёкшей пользу из БПЛА. Эта радиоуправляемая беспилотная мишень под названием DH82A Tiger Moth использовалась на королевском Военно-морском флоте с 1934 по 1943 г. Армия и ВМФ США с 1940 годаиспользовали ДПЛА Radioplane OQ-2 в качестве самолёта-мишени.

В течение Второй мировой войны немецкие учёные вели разработки нескольких радиоуправляемых типов оружия, включая управляемые бомбы Henschel Hs 293 и Fritz X, ракету Enzian и радиоуправляемый самолёт, наполненный взрывчатым веществом. Несмотря на незавершённость проектов, Fritz X и Hs 293 с успехом использовались на Средиземном море против бронированных военных кораблей. Были разработаны и применялись управляемые планирующие авиабомбы.

В СССР в 1930--1940 гг. авиаконструктором Никитиным разрабатывался торпедоносец-планер специального назначения (ПСН-1 и ПСН-2) типа "летающее крыло" в двух вариантах: пилотируемый тренировочно-пристрелочный и беспилотный с полной автоматикой. К началу 1940 г. был представлен проект беспилотной летающей торпеды с дальностью полёта от 100 км и выше (при скорости полёта 700 км/ч). Однако этим разработкам не было суждено воплотиться в реальные конструкции. В 1941 году были удачные применения тяжёлых бомбардировщиков ТБ-3 в качестве БПЛА для уничтожения мостов.

В США запустили в массовое производство БПЛА-мишень Radioplane OQ-2 для тренировки лётчиков и зенитчиков. Также, в 1944 году был применён впервые в мире классический ударный БПЛА -- Interstate TDR. Помимо этого, военными США был создан целый ряд управляемых авиабомб, включая наиболее совершенное технические оружие, примененное в годы войны -- самонаводящуюся планирующую бомбу ASM-N-2 Bat, первое в мире оружие схемы "выстрелил-и-забыл", не требующее вмешательства оператора. После войны разработки беспилотных летательных аппаратов в США временно сместились в сторону создания управляемых ракет и авиабомб, лишь в 60-х вернувшись к идее неударных БПЛА.

После Второй мировой войны.

В СССР 23 сентября 1957 года КБ Туполева получило госзаказ на разработку мобильной ядерной сверхзвуковой крылатой ракеты среднего радиуса действия. Созданная конструкция нашла применение в качестве мишени, а также при создании беспилотных самолётов разведчиков Ту-123 "Ястреб", Ту-143 "Рейс" и Ту-141 "Стриж", стоявших на вооружении ВВС СССР с 1964 по 1979 год. Ту-143 "Рейс" на протяжении 70-х годов поставлялся в африканские и ближневосточные страны.

В начале 1960-х годов дистанционно-пилотируемые летательные аппараты использовались США для слежения за размещениями ракет на Кубе и в Советском Союзе -- после того, как были сбиты RB-47 и два U-2, для выполнения разведывательных работ была начата разработка высотного беспилотного разведчика Red Wadon (модель 136). БПЛА имел высоко расположенные крылья и малую радиолокационную и инфракрасную заметность.

Во время войны во Вьетнаме, с ростом потерь американской авиации от ракет вьетнамских ЗРК, возросло использование БПЛА. В основном они использовались для ведения фоторазведки, иногда для целей РЭБ. Аппараты применялись для ведения фоторазведки, ретрансляции сигнала, разведки радиоэлектронных средств, РЭБ и в качестве ложных целей для усложнения воздушной обстановки. Но полная программа БПЛА была окутана тайной настолько, что её успех, который должен был стимулировать развитие БПЛА после конца военных действий, в значительной степени остался незамеченным.

Примеры и способы применения на практике:

1) Планирование пути из пункта А в пункт Б по дорогам общего пользования для автомобиля.

2) Планирование пути из пункта А в пункт Б для пешехода.

3) Планирование пути из пункта А в пункт Б по пересеченной местности.

4) Планирование пути в помещения (квартиры, офисы и т.п.).

5) Планирование перемещения БПЛА и БТС.



Планирование пути из пункта А в пункт Б по дорогам общего пользования для автомобиля

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

В настоящее время лидерам в этой области является компания Google.

Беспилотный автомобиль Google -- проект компании Google по развитию технологии беспилотного автомобиля. В настоящий момент проект реализует лаборатория Google X, возглавляет проект инженер Себастьян Тран, директор лаборатории искусственного интеллекта Стенфордского университета, чья команда занималась проектом Стэнли в Стенфордском университете. Команда, разрабатывающая беспилотный автомобиль, также часто называемый Гугломобиль, включает 15 инженеров Google.

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

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

В сентябре 2012 года, власти штата Калифорния легализовали использование автомобилей с функцией автопилота.

Краткое описание системы.

Система использует информацию, собранную сервисом Google Street View (сервися Google, предоставляющего пользователю фотографии улиц), видеокамеры, датчик LIDAR, установленный на крыше, радары в передней части авто и датчик, подключенный к одному из задних колёс, который помогает определить позицию автомобиля на карте.В 2010 году Google протестировал несколько автомобилей, оборудованных такой системой. В реальных условиях, без участия человека, автомобиль проехал около 1600 км полностью автономно и ещё 225 308 км с частичным участием человека. Единственное дорожно-транспортное происшествие произошло, когда другой автомобиль въехал в гуглмобиль, стоящий на светофоре. По утверждению Google, их автоматизированная система может снизить количество ДТП, травм и смертей, в то же время, используя топливо и дороги более эффективно.

В проекте участвуют 10 автомобилей: 6 Toyota Prius, 3 Lexus RX460h и 1 Audi TT, а также 12 водителей и 15 инженеров.

В 2012 году компания Google сообщила в своём блоге о том, что их автомобили проехали уже более 480 тысяч километров с минимальным участием человека. Это позволило компании снизить экипаж автомобилей до одного человека. Так же было заявлено, что начались тестирования системы на участках со сложным рельефом. Это значительно расширяет возможности использования системы.

Недостатки системы.

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

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

Алгоритм выбора оптимального маршрута по пересеченной местности

Модель местности

Карта местности представлена в виде матрицы Z = z(y, x), где каждый элемент определяет максимальные затраты на преодоление участка с координатами (y, x). Участок местности, соответствующий элементу матрицы, считается квадратом со стороной d , правильно ориентированным вдоль координатных осей. Под координатами участка понимаются матричные индексы: y - номер строки матрицы, x - номер столбца. Максимальные затраты соответствуют пересечению участка по диагонали. Полагается, что затраты при пересечении вдоль любой координатной оси в 2 раз меньше максимальных.

При переходе с данного участка на смежный участок будем считать, что переход осуществляется из центра одного участка в центр другого. Затраты на переход равны среднему значению затрат по двум смежным участкам: z12 = (z1 + z2 ) 2 . Затраты на маршруте определяются суммой затрат по всем переходам между точками маршрута:

где N - число точек маршрута. При построении оптимального маршрута на каждом шаге необходимо выбирать направление дальнейшего движения. Результат выбора называется шаговым управлением и обозначается ck . Управление всей операцией состоит из совокупности шаговых управлений: C = c1, c2,…cm?1 .

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

C = c(y, x) и Q = q(y, x), а шаговое перемещение реализуется в пределах маски размером

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

Фильтрующий алгоритм

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

В предлагаемом алгоритме матрица накопленных затрат Q и матрица направлений C интерпретируются как двумерные изображения. Значение каждого элемента матрицы соответствует уровню яркости изображения. Алгоритм построения веера оптимальных траекторий реализуется как многоступенчатый пространственный параметрический ранговый фильтр минимума с маской размером 3Ѓ~3 (рис. 1).

Рисунок 1 - Многоступенчатый фильтр оптимальных затрат

Рисунок 2 - Маска пространственного фильтра

Фильтрация производится над матрицами накопленных затрат Q = q(y, x) и матрицей шаговых управлений C = c(y, x). Матрица Z = z(y, x) определяет параметр фильтра для каждой точки (элемента) матриц Q и C . Веер траекторий строится от множества стартовых точек и распространяется по всем направлениям карты. Эффект пространственной фильтрации матриц эквивалентен ослаблению дуг в алгоритме Форда-Беллмана. Размещение фильтрующей маски в точке с координатами (y, x) показано на рис. 2. Число ступеней фильтра заведомо не определено, каждая ступень улучшает предыдущее решение. Матрица затрат Z содержит относительные затраты, приведенные к диапазону [0,1] ( 0 - минимальные затраты, 1 - максимальные затраты в пределах зоны). Непреодолимые области имеют значение Ѓ‡. Матрица может иметь необрабатываемые области, которые помечены символом NaN. Значение элемента матрицы z(y, x) используется как параметр пространственного фильтра в точке (y, x). Матрица накопленных затратQ = q(y, x) имеет размер матрицы Z и содержит следующие области:

? необрабатываемая область - точки помечены символом NaN. При выполнении пространственной фильтрации эти точки пропускаются и не участвуют в обработке;

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

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

Рисунок 3 - Возможные варианты шаговых управлений

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

При движении маски вдоль границы только часть точек, покрываемых маской, может быть использована для вычисления накопленных затрат. Это означает, что в процессе вычисления шаговых управлений будут пропущены некоторые направления из-за того, что будущее движение нам пока не известно. После первой ступени фильтрации будут получены оценки накопленных затрат для всех точек матрицы Q (оценки первого приближения). При этом в матрице направлений C(y, x) все элементы будут содержать направления маршрута первого приближения. Последующие ступени фильтрации позволяют уточнить первое приближение.

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

Реализация алгоритма

Ступень 1. На первой ступени фильтрации алгоритм распространяется от стартовых точек в виде волны. Фронт волны строится следующим образом. Множество стартовых точек рассматривается как начальный фронт волны. Маска позиционируется в стартовую точку карты и в матрицах затрат Z , Q просматриваются все точки, покрываемые маской. Точки, для которых значения в матрице Z равны Ѓ‡, а значения в матрице Q конечны, переносятся в список граничных точек. Просматриваются все стартовые точки и строится общий список. Далее список редактируется, из него удалятся повторяющиеся точки (редактирование может производиться и при смене позиции маски). Логические условия построения нового фронта имеют вид:



(1)

где координаты y и x принадлежат полю движущейся маски, y* , x* - координаты точек текущего фронта волны. Фильтрация выполняется для всего списка граничных точек. С этой целью маска позиционируется центром в граничную точку (y, x) и выполняется вычисление нового значения накопленных затрат по следующему правилу:

(2)

где j, i = 0, ±1 - индексы маски с ненулевыми значениями элементов. Полагается, что

z00 (y, x)=0 . В центральных областях карты матрица фильтрующей маски имеет вид:

Матрица маски наполняется нулями при пересечении границы карты. Значение соответствующего элемента матрицы шаговых управлений устанавливается по позиции точки минимума в выражении (2):

(3)

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

Ступень 2 и последующие. Последовательно просматриваются все точки карты, для которых q(y, x) ? NaN и выполняется коррекция значений матриц Q и C, следуя формулам (2) и (3). Фильтрация заканчивается, когда матрицы Q двух смежных ступеней совпадают. Дополнительный эффект ускорения вычислений достигается за счет рекурсивного принципа фильтрации.

Построение оптимального маршрута. При построении маршрута возможны следующие варианты:

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

2. Конечная точка не задана, но определено множество, которому она принадлежит. В этом случае на заданном множестве необходимо найти точку, в которой q(y, x)>min и далее повторить алгоритм пункта 1.

3. Если заданы начальная и конечная точки, то алгоритм необходимо выполнить для начального фронта, состоящего из одной стартовой точки.

Построение фронта транспортной доступности. В матрице накопленных затрат ищутся точки, удовлетворяющие условию: q ( y, x) ? L, где L - уровень затрат на линии фронта. Степень приближения может быть задана, например, в процентах от уровня L .



Алгоритм оптимального движения в транспортной сети

Модель транспортной сети

Транспортная сеть (рис. 4) представляется топологической моделью в виде взвешенного графа G. Ребра графа соответствуют однородным сегментам транспортной сети, а узлы - точкам ветвления или иным точкам интереса (стартовым точкам, конечным точкам, точкам сети, ближайшим к заданному объекту и т.д.). Каждому ребру графа поставлено в соответствие значение временных затрат на преодоление сегмента. Сегментные затраты определяются геометрической длиной сегмента и средней скоростью движения объекта вдоль сегмента.

Постановка задачи по прокладке маршрута в транспортной сети не отличается от задачи маршрутизации по пересеченной местности.

Описание алгоритма

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

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



Реализация алгоритма

Взвешенный граф транспортной сети задается квадратной матрицей затрат Z = z(i, j). Размер матрицы определяется числом вершин в графе. Каждый элемент матрицы представляет собой затраты на перемещение между смежными вершинами. В общем случае матрица может быть не симметрична ( z(i, j) ? z( j,i)). Если вершины не являются смежными, то значение элемента матрицы равно ? . Кроме того элемент матрицы может иметь 0, если i = j или значение NaN - такой сегмент не участвует в построении оптимального маршрута. Накопленные затраты сохраняются в массиве Q. Каждый элемент массива соответствует вершине графа. Первоначально всем элементам массива Q присваивается значение ? . Элементу массива Q присваивается значение NaN, если все сегменты окружения для соответствующей вершины графа имеют значение NaN.

Ступень 1. На первой ступени алгоритма накопление затрат происходит в виде волны от стартовых точек. Фронт волны строится следующим образом. Множество стартовых точек рассматривается как начальный фронт волны. Алгоритм фокусируется в стартовой точке, в матрице весов Z и массиве накопленных затрат Q. Просматриваются все сегменты и узлы ближайшего окружения. Точки, для которых значения в массиве Q равны Ѓ‡ , и при этом соответствующие значения в матрице сегментных затрат Z конечны, переносятся в список граничных точек. Просматриваются все стартовые точки и строится общий список. Далее список редактируется, из него удалятся повторяющиеся точки. Логическая формула построения нового фронта имеет вид: iЃё Front если{q(i) = Ѓ‡ & z(i, j) Ѓ‚ Ѓ‡, NaN}. (4)

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

(5)

Значение соответствующего элемента массива шаговых управлений устанавливается по позиции точки минимума в выражении (5):

(6)

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

Ступень 2 и последующие.

Последовательно просматриваются все точки зоны, для которых q(i) Ѓ‚ NaN и выполняется коррекция значений, массивов Q и C, следуя выражениям (5) и (6). Фильтрация заканчивается либо когда массивы двух смежных ступеней совпадают, либо после выполнения заданного числа ступеней фильтрации.

Построение оптимального маршрута.

При построении маршрута возможны следующие варианты:

1. Стартовых точек несколько. Необходимо проложить маршрут от ближайшей стартовой точки

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

2. Конечная узловая точка не задана, но определено множество, которому она принадлежит. В этом случае на заданном множестве необходимо найти узловую точку, в которой q(ik )ЃЁ min и далее повторить алгоритм пункта 1.

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

Построение фронта транспортной доступности.

Фронт транспортной доступности представляет собой линию (изохрону), в каждую точку которой можно попасть из стартовой точки примерно при одном и том же уровне затрат L . В массиве накопленных затрат Q ищутся точки, удовлетворяющие условию: q(i) ? L . Степень приближения должна быть задана (например, в процентах от уровня L ). Узловым точкам изохроны соответствуют координаты (xi , yi ). По этим координатам можно приближенно построить фронт транспортной доступности, соединив их отрезками прямых линий.

Алгоритм прокладки оптимального маршрута при комбинированном движении

Комбинированное движение состоит из этапа движения по транспортной сети с использованием транспортных средств и этапа движения по пересеченной местности.

Построение первого приближения

1. С помощью волнового алгоритма определяются достижимые затраты на перемещение из стартового узла во все узлы транспортной сети.

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

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

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

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

Уточнение решения

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

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

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

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

5. Выделяется оптимальная стартовая точка.

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

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

Алгоритм HGA*

Алгоритм HGA* (Hierarchical A* for MT-Graphs) использует совершенно другой подход к решению задачи планирования -- иерархический. Задача рекурсивно разбивается на иерархическую сеть подзадач, решение которых считается известным. Алгоритм использует графы специальной структуры -- метрические, топологические (МТ-графы). МТ-граф -- это неупорядоченная пара: MT-Gr=<A,d>, где А -- множество клеток, представляющее матрицу

алгоритм траектория граф маршрут



d - метрика на множестве .

Клетку МТ-графа будем называть проходимой, если aij=0; непроходимой, если aij=1.

Графически МТ-граф можно представить в виде таблицы, содержащей m строк и n столбцов. Ячейки таблицы соответствуют клеткам aij, проходимым и непроходимым. Упорядоченную пару клеток МТ-графа <aij, akl> назовем секцией. Секция считается проходимой, если прямая, проходящая через клетки секции не содержит непроходимых клеток.

Частичным путем из начальной клетки в целевую будем называть последовательность клеток МТ-графа PP = {ai0,j0, ai1,j1, ai2,j2,...,ain,jn}. При этом если каждая из секций <ai0,j0, ai1,j1>, <ai1,j1, ai2,j2>,…, <ain-1,jn-1, ain,jn> является проходимой, то такой путь будем называть допустимым, иначе -- недопустимым. Клетки, входящие в частичный путь будем называть опорными. Таким образом, задача поиска пути на МТ-графе сводится к построению допустимого частичного пути. Другими словами, для решения задачи необходимо выделить множество клеток, называемых опорными, между которыми может быть построен путь любыми стандартными средствами, например путем построения дискретной прямой по алгоритму Брезенхема.

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

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



Список используемой литературы

Статья журнала "Искусственный интеллект" 3'2008

А.Ю. Дорогов, В.Ю. Лесных, И.В. Раков, Г.С. Титов Санкт-Петербургский государственный электротехнический университет, Россия "Алгоритмы оптимального движения мобильных объектов по пересеченной местности и транспортной сети"

Информационно-телекоммуникационные технологии и матмоделирование -- 2012

Размещено на Allbest.ru

...