Применение генетических алгоритмов для эффективного решения задачи навигации

Министерство образования и науки Российской ФедерацииФедеральное государственное автономное образовательное учреждениевысшего профессионального образования«Московский физико-технический институт(государственный университет)»Факультет управления и прикладной математикиКафедра информатикиПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВДЛЯ ЭФФЕКТИВНОГО РЕШЕНИЯ ЗАДАЧИ НАВИГАЦИИВыпускная квалификационная работа(магистерская диссертация)Направление подготовки: 03.04.01 Прикладные математика и физикаВыполнил:студент 973а группыБорисяк Максим АлександровичНаучный руководитель:к.ф.-м.н., доцентУстюжанин Андрей ЕвгеньевичМосква 2015Soderanie1 Vvedenie32 Postanovka zadaqi i predvaritel~noe issledovanie2.12.22.32.42.52.6Kriterii kaqestva .

. . . . . . . . . . . . . . . . . . . . . . . . . .Algoritmy navigacii . . . . . . . . . . . . . . . . . . . . . . . . .Qastiqno nabldaemy markovski process printi rexeniDopolnitel~nye predpoloeni . . . . . . . . . . . . . . . . . .Naivny algoritm . . . . . . . . . . . . . . . . . . . . . . . . . . .Motivaci . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .3 Genetiqeskie metody navigacii3.13.23.33.43.5Model~ . . . . . . . . .volcionny podhodAdaptacionny podhodMeta-model~ . . . . . .Obuqenie bez uqitel ................................................................................................................................................................................4710141717191919222428324 Qislenny ksperiment335 Zaklqenie366 Dal~nexa rabota3721ВведениеВ настоящее время с появлением новых возможностей в робототехнике становятся актуальными задачи искусственного интеллекта.

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

Другим похожим классом являетсянавигация на дальние расстояния в известном окружении, которые представляют интерес только в случае непрерывных координат и также успешно решаются методамитеории оптимального управления. Среди прикладных систем особенно стоит отметитьRobot Operating System1 представляющую в том числе окружение для осуществлениенавигации подобного рода.В контексте данной работы, особое внимание нужно уделить генетическим алгоритмам обхода препятствий, результаты который были продемонстрированы в недавнихработах ([2], [3], [4]). Следуя стандартному подходу области искусственного интеллектак построению агентов, обобщенную задачу навигации (которая в этом случае выглядит так же как и общая задача планирования) можно сформулировать как нахождениеоптимальной стратегии (либо близкой к оптимальной):Π(θ) = arg max Q(θ, ψ)ψ∈MM ⊆ F(O, A)где θ ∈ Θ — описание окружения, ω ∈ O — наблюдение, a ∈ A — действие, Q(·, ·) —функция качества, M — некая модель, F(X, Y ) — множество всех отображений из Xв Y .

Учитывая постановку задачи обхода препятствий информацию об окружении θможно однозначно восстановить из любого наблюдения ω, поэтомуΠ(θ) ≡ ψ ∗Так же в силу особенностей навигации алгоритм реализующий стратегию ψ ∗ , который в общем виде имеет вид ψ[s, ω] : Sψ × O 7→ Sψ × A, где Sψ — некое пространство состояний алгоритма, без значительных потерь в производительности может бытьпредставлен в виде алгоритма-таблицы: ψ[ω] : O 7→ A. Такие алгоритмические модели содной стороны устойчивы к малым возмущениям, с другой обычно имеют высокую размерность, что делает простой генетический поиск более вычислительно эффективнымпо сравнению с классическими методами оптимизации.

Однако в случае с известнымокружением, такая модель оказывается далеко не самой эффективной, и часто такие задач успешно решаются аналитически, что делает обозначенные выше работы ценнымитолько как демонстрация возможности применение генетический методов.Условие частично наблюдаемого окружения (обычно, область действия сенсоровмного меньше размеров самого окружения) порождает новый класс задач, начиная1Главная страница проекта: http://ros.org3от оценки текущего местоположения и построение карты окружения до интеллектуальной прокладки маршрута.

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

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

Более подробно о методах построения карты, обработки показаний сенсоров и так далее можно узнать, например, из [5], [6], [7], [8], [9],[10].В качестве окружения робота была выбрана одна из самых простых моделей — двумерная прямоугольная клеточная карта фиксированных размеров, где каждая клеткаможет быть либо свободной, −1, либо занятой, 1, при этом робот может находитьсятолько в свободных клетках:U = {−1, 1}W ×H \ U ;(1)где U — множество всех карт размера W × H со значениями −1, 1 таких, что всегдасуществует хотя бы один путь между двумя различными свободными точками, требующий не менее одного действия, U — соответственно, множество карт, где любаясвободная точка изолирована.Роботу позволено совершать три действия (A): повороты и движение на клеткувперед.

Также у робота есть текущее направление из D = {d | d ∈ Z2 , kdk = 1} иположение r ∈ R = 1, W × 1, H. Парой (r, d) ∈ R × D описывается текущее состояниеробота.A = {TURNLEFT, FORWARD, TURNRIGHT};ϕ : U × R × D × A → R × D;ϕ(l, r, d, TURNLEFT) = (r, TURNLEFT(d));ϕ(l, r, d, TURNRIGHT) = (r, TURNRIGHT(d));((r, d),l(r + d) = 1ϕ(l, r, d, FORWARD) =(r + d, d), иначе4(2)(3)(4)(5)(6)где ϕ — функция «физики» окружения l, TURNLEFT(·), TURNRIGHT(·) — функцииповорота вектора направления на π, −π соответственно.У робота есть только один сенсор — зрение, которое задается функцией v:V = {−1, 0, 1}W ×H ;v : U ×R×D →V;∀l ∈ U ∀(r, d) ∈ R × D ∀(x, y) ∈ R : v(l, r, d)(x, y) 6= 0 ⇒ v(l, r, d)(x, y) = l(x, y);(7)(8)(9)Здесь значение 0 в клетке выступает в роли неизвестного участка карты, а свойство(9) означает согласованность зрения с реальным окружением, то есть значение зренияв любой точке карты может быть либо 0, либо соответствовать реальному окружениюl.Мы будем использовать лишь две функции зрения:(l(x, y), (x − x0 )2 + (y − y0 )2 ≤ r2 ;var (l, x0 , y0 )(x, y) =(10)0,иначе;(l(x, y), 1 ∈/ Linel (x0 , y0 , x, y) ∧ (x − x0 )2 + (y − y0 )2 ≤ r2 ;vtr (l, x0 , y0 )(x, y) =(11)0,иначе;где Linel (x0 , y0 , x, y) — 4-х связная прямая между точками (x0 , y0 ) и (x, y), не включающая точку (x, y).

Как не сложно заметить, функции зрение открывают только областиокружения в радиусе r текущей позиции. r > 0 будем называть радиусом зрения.Для удобства включим в множество возможных наблюдений O текущее положениии конечную точку:O =R×D×V ×RВ общем случае, задача состоит в нахождении алгоритма навигации A.Определение 1. Алгоритмом навигации A2 с пространством состояний SA называется пара (ψ, s0 ), такая что:ψ : SA × O → SA × A;s0 ∈ S A ;Определение 2. Пусть дан алгоритм навигации A = (ψ, s0 ) и заданы функция зрения v(·, ·, ·) и изначально открытая область v0 .

Будем говорить, что алгоритм Aпроецирует путь π = ϕ∗ (A, l, r0 , d0 , rf , v0 ) в окружении l с открытой областью v0 , с2Сразу заметим, что рассматриваются только алгоритмы, которые заведомо завершают свою работу, поэтому процедура ψ определяется как отображение.5начальным состоянием (r0 , d0 ) и целевой точкой rf , если:s0(st , at )ωtr0 , d0s0 ;ψ(ω t−1 , st−1 );(rt , dt , v t , rf );r0 , d0 ;(ϕ(l, rt−1 , dt−1 , at ), rt−1 6= rf(rt , dt ) =(rt−1 , dt−1 ),иначеv0vtπ0πtt========≥v0 ;v t−1 ⊗ v(l, rt , dt );(r0 , d0 );(rt , dt );1;(min t | ∀τ ≥ t : rτ = rf , ∃τ : rτ = rfT =∞,иначе(12)(13)(14)(15)При этом T называется длиной пути π или |π|. Аналогично ϕ∗ вводятся функции s∗ ,a∗ , ω ∗ , r∗ , d∗ возвращающие соответствующие последовательности.

Для удобстваTтак же введем функцию Φ∗ (A, l, r0 , d0 , rf , v0 ) = {(st , at , rt , dt , ω t )}t=0 . Если изначальнооткрытая область v0 не указана, то π = ϕ∗ (A, l, r0 , d0 , rf ) = ϕ∗ (A, l, r0 , d0 , rf , v(l, r0 , d0 )),аналогично для Φ∗ .Для удобства дальнейшего рассмотрения, заметим, что алгоритму навигации на входподается аккумулированная карта окружения ((14)):(v 1 ⊗ v 2 )ij = vij1 ⊗ vij2 ;x, x = y;x⊗y =x, y = 0;y, x = 0;(16)(17)В силу условия согласованности зрения (9) уравнение (17) описывает все возможныеслучаи и просто означает добавление информации об исследованных областях.

Заметим, что эта процедура не более, чем упрощение, так как в любой алгоритм можнодобавить процедуру построение аккумулированной карты окружения.Определение 3. Кортеж θ = (l, r0 , d0 , rf ) ∈ U × R × D × R будем называть задачейнавигации в окружении l с начальной позицией (r0 , d0 ) и целью rf , если существуетнепрерывный путь π ∈ (R×D)∗ (а значит и набор команд для реализации этого пути)из позиции (r0 , d0 ) в точку rf .Множество Θ 6= ∅ будем называть набором задач, если:Θ ⊆ {θ | θ = (l, r0 , d0 , rf ), l ∈ U, r0 , rf ∈ R, d0 ∈ D, θ — задача навигации }Определение 4.