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

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

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

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

 

 

 

 

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Выполнил студент: III-АИТ-2

Задорожный А.М.

 

Проверил преподаватель:

Буканов Ф.Ф.

 

 

 

Самара 2013

 

Содержание

Введение………………………………………..…………………………………………..………….. 3

 

Алгоритм А*………………..…………………….………………………………………..………….. 3

 

Проект SHAKEY ……………………………………………………………….…………………….. 5

 

Первые БПЛА …………………………..…………………………………..………...……………… 6

 

Планирование пути из пункта А в пункт Б

по дорогам общего пользования для автомобиля…………………..…………………………....…. 7

 

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

 

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

 

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

 

Алгоритм HGA*………………………..…………………………………..………...……………… 17

 

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

 

 

 

 

 

 

 

Введение

Создание эффективных методов планирования траектории является важной и

актуальной научной задачей. Ее актуальность подтверждается потребностью в

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

компонентом которых является планировщик.

 

Для решения задачи планирования траектории целесообразно моделировать

предметную область взвешенным графом, где вершинам соответствуют географические

координаты точек пространства, а ребрам — расстояния. Таким образом, задача

планирования рассматривается, как задача поиска пути на графе. Традиционно, решение

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

 

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