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

На правах рукописи .

Яковлев Константин Сергеевич

ИССЛЕДОВАНИЕ МЕТОДОВ И РАЗРАБОТКА АЛГОРИТМОВ АВТОМАТИЧЕСКОГО ПЛАНИРОВАНИЯ ТРАЕКТОРИИ НА

ПЛОСКОСТИ

Специальность 05.13.17 Теоретические основы информатики

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

-2 ДЕК 2010

Москва-2010

004615026

Работа выполнена в Учреждении Российской академии наук Институте системного анализа РАН.

Научный руководитель: доктор физико-математических наук,

профессор

Осипов Геннадий Семенович (заместитель директора по науке, ИСА РАН)

Официальные оппоненты: доктор технических наук,

профессор

Вагин Вадим Николаевич (профессор, МЭИ ТУ)

кандидат физико-математических наук Виноградов Дмитрий Вячеславович (старший научный сотрудник, ВИНИТИ РАН)

Ведущая организация: Учреждение Российской академии наук

Институт проблем управления РАН

Защита состоится "УУ7 2010 г., в [Ч_ часов на заседании

диссертационного совета ДМ 002.084.01 при ИПС им. А.К. Айламазяна РАН по адресу: 152021, Ярославская область, Переславский район, с. Веськово, ул. Петра I, д.4а.

С диссертацией можно ознакомиться в библиотеке ИПС им. А.К. Айламазяна РАН.

Автореферат разослан "_[£" Оцтабэд 2010 г.

Ученый секретарь

диссертационного совета ДМ 002.084.01 * кандидат технических наук ^^¿Ъ/м

С.М. Пономарева

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования

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

Задача планирования траектории в контексте автоматизации управления сложными техническим объектами (роботами, транспортными средствами и др.) изучается с 50-х годов XX века Одним из первых проектов в этой области являлся известный проект Стэнфордского университета США по созданию робота SHAKEY в 1966-1972 гг. Именно он положил начало многолетним исследованиям методов и подходов к решению задач планирования траектории, продолжающимся по сей день. За последние годы были успешно реализованы десятки крупных проектов в этой области, например:

- DARPA URBAN CHALLENGE (соревнования беспилотных автомобилей в городских условиях, 2008г., США)

- NASA ARP (создание системы управления малым беспилотным вертолетом Yamaha RMAXII, предназначенным для разведки и мониторинга, 1998-2003 гг. США)

- MARS (разработка программного обеспечения дня автономных наземных роботов, США, 1999-2004 гг.)

- VIAC (создание беспилотной модификации гражданского автомобиля и осуществление пробега протяженностью 13 000 км., Европейский Союз, 2010)

- Робокросс (соревнования автомобилей-роботов, Россия, 2010).

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

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

Теоретической и методологической основой исследования послужили труды отечественных и зарубежных ученых в области искусственного интеллекта Д.А. Поспелова, Г.С. Осипова, В.Л. Стефанюка, Дж. МакКарти, Н. Нильсона, исследования в области

робототехники В.Б. Мелехина, Л.С. Берштейна, Р. Аркина, С. Трупа, работы в области исследования эвристических алгоритмов поиска пути на графе М. Лихачева, С. Коенига, работы в смежных областях (управление, генетический алгоритмы) Л.Н. Никифоровой, В.М. Курейчика.

Цели и задачи исследования

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

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

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

2. Разработаны принципы иерархической декомпозиции задачи планирования траектории и алгоритм планирования траектории, реализующий эти принципы - ЬЮА*.

3. Исследованы свойства алгоритма НОА* при определенных ограничениях. Предложены модификации алгоритма НОА*, предназначенные для решения различных типов задач планирования траектории на плоскости.

4. Разработаны программные средства для оценки вычислительной эффективности различных алгоритмов планирования траектории. Проведена серия вычислительных экспериментов, направленных на сравнение разработанного алгоритма 1ЮА* с аналогами.

Методы исследования

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

Научная новизна работы

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

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

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

Практ ическая значимость работы

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

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

1. «Интеллектуальная система поддержки автоматизированного маловысотного полета вертолета», проект Российского Фонда Фундаментальных исследований № 09-07-00043-а

2. «Развитие методов анализа полуструктурированной информации и моделирования целенаправленного поведения», выполняемого в рамках федеральной целевой программы «Научные и научно-педагогические кадры инновационной России».

3. «Развитие методов интеллектуального управления на основе анализа потоков данных», проект 2.2 Отделения нанотехнологий и информационных технологий Российский академии наук.

Апробация работы

Основные положения работы докладывались и обсуждались на следующих научных конференциях и семинарах:

1. XII национальная конференция по искусственному интеллекту с международным участием (КИИ-2010), 2010, г. Тверь.

2. Общемосковский научный семинар «Проблемы искусственного интеллекта», 2010, г. Москва.

3. III международная конференция «Системный анализ и информационные технологии -САЙТ 2009», сентябрь 2009, г. Звенигород

4. IX международная научной конференция им. Таран Т.А «Интеллектуальный анализ информации - ИАИ-2009», май 2009, г. Киев, Украина.

5. XLIII всероссийская конференции по проблемам математики, информатики, физики и химии Российского университета дружбы народов, апрель 2008, г. Москва.

Публикации

По теме диссертационной работы опубликовано 9 печатных работ (в том числе 2 публикации в ведущих рецензируемых научных изданиях, рекомендованных Высшей аттестационной комиссией).

Личный вклад соискателя

Результаты, выносимые на защиту, получены автором самостоятельно.

Структура и объем работы

Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа изложена на 184 ар. машинописного текста, содержит 8 таблиц, 86 рисунков, 1 приложение, библиография включает 75 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

ПодМТ-графом будем понимать неупорядоченную тройку МТ-Ог={Л, Л, с), где:

А - множество клеток, представляющее собой матрицу A„,„={a,j}: а^Ovl, V7,_/: 0<i<m, 0</</г,/я,леМ{0);

d-метрика на множестве Л{а,^еЛ, ау=0};

с: £■—>(0, +со) - коммутативная функция, определяющая веса переходов между клетками МТ-графа (здесь, ЕаЛ М).

Для упрощения записи будем обозначать МТ-граф как А„х„. Величину т - будем называть высотой, а п - шириной МТ-графа Величины i, j будем называть координатами либо индексами клеток МТ-графа Клетку МТ-графа будем называть проходимой, если %=0, и -непроходимой, если <%=1. Если МТ-граф содержит лишь проходимые клетки, то будем называть такой МТ-граф полностью проходимым.

Две различные клетки а,Ц1, а12реА„*„ будем называть смежными, если |íi-Í2|<1a1/'i-./2|<1. Две различные клетки а„;!, a0j2eAm*n будем называть горизонтально смежными, если |!1-'г|=0л71-л|=1; вертикально смежными, если Ií'i-i^IaI/V^^O; диагонально смежными, если |ii-Í2|=1a1/i-_/2|=1- Множество всех смежных клеток для a¡¡ обозначим как adj(a,j). Пусть ADJcA хА - множество всех пар смежных клеток, c*we(0, +оо), cj^kcbv, l¿k<2. Определим функцию с: £->(0, +а>) следующим образом с: ADJ-* {chv. сл,

Вес перехода из клетки a¡¡ в клетку ац, (или, что то же самое, из клетки ац, в клетку аи) будем обозначать c(a,j, ац). При этом:

da,¡, ait)=chv, если д,/=0 л ац=0 и клетки a¡¡, ац являются горизонтально или вертикально смежными;

с{а,р a¡¡)=Cd, если a:j=0 л ац=0 и клетки a,¡, ац являются диагонально смежными; da,j, ац)=+со, если a,j=l va/t=1.

Задача планирования траектории формально представляется в виде тройки:

PTask=<MT-Gr, a„an¡,mnj, agoaugmu), и формулируется следующим образом. Пусть на МТ-графе зафиксированы различные проходимые клетки: начальная а,шг,пшп1 и целевая agaai¡goau- Необходимо найти путь ldp„artlstard, agoallgoau), то есть последовательность клеток МТ-графа зг={а,0> а,иъ аар, ■■■, auj,} такую, vioamp-anonisunJ, au¡,=agoaiisoaU, Vv: l<v<s a,„p£adj(a,^

Весом пути гг будет называть величину с(л), равную сумме весов переходов по всем смежным клеткам, входящим в путь. Величину D=тах{\startI-goa!I\, \starU-goaU\} будем называть глубиной решения задачи. Число переходов, составляющих путь л, будем обозначать как N(K)=H¿.j:)+Nh(x)-tNj(K), где Щл) - число переходов между горизонтально-смежными клетками, NJ,x) — число переходов между вертикально-смежными клетками, NJjt) - число переходов между диагонально-смежными клетками.

Кратчайшим путем из asanis uní в agoaugoau будем называть такой путь X*(as,artl¡¡arü, agoatlgmu), ЧТО Vl&X* с{ж*)<с(ж). БуДСМ считать, что кратчайший путь из asían]starü в OgooiigtwU соответствует оптимальному решению задачи планирования траектории на плоскости.

В качестве метрики на МТ-графе может использоваться, в частности, функция:

а,1'а,к + если A,(a,J1as)<AJ(aj).,cll)'

именуемая диагональной метрикой. Здесь aa)=A,=|i-/|; Д/a,/, аа)=Д/=|/-Л|.

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

Любому МТ-графу может быть поставлен в соответствие взвешенный граф. Таким образом, алгоритмы поиска пути на графах применимы и для МТ-графов. Среди всех алгоритмов поиска пути, особый интерес представляют алгоритмы эвристического поиска семейства А*, т.к. с одной стороны существуют такие модификации алгоритма А*, которые гарантируют построение кратчайшего пути, с другой - алгоритмы семейства А* на практике характеризуются меньшей вычислительной нагрузкой, по сравнению с классическими методами, такими как алгоритм Дейкстры, поиск в ширину и т.д. Если в качестве эвристики при поиске использовать одну из функций, определяющих метрику на МТ-графе, то такая эвристика будет монотонной и допустимой. Следовательно, алгоритм А*, использующий в качестве эвристики функцию Н гарантирует построение кратчайшего пути. Теоретическая оценка вычислительной сложности алгоритма А* (как по времени, так и по памяти) составляет 002). При этом на практике использование лучшей из доступных эвристик (а именно - диагональной метрики МТ-графа) зачастую не приводит к существенному сокращению пространства поиска, и теоретическая оценка вычислительной сложности совпадает с практической. Это происходит из-за т.н. проблемы локального минимума

Для описания сути проблемы необходимо подробней остановиться на принципе функционирования эвристических алгоритмов поиска пути на МТ-графе. Фактически, все алгоритмы поиска пути на МТ-графе (в том числе и эвристические) опираются на принцип итерационного обхода клеток МТ-графа, начиная с начальной. На каждой итерации алгоритма для каждой клетки (да), смежной с текущей - ay, рассчитывается т.н. g-значение (gfa*))> равное весу кратчайшего пути го aslanistanj в аш. Клетка <% помечается как родительская для клетки аш и исключается из дальнейшего рассмотрения; клетка аш добавляются в список кандидатов на дальнейшее рассмотрение. На очередной итерации алгоритма в качестве текущей клетки a,j из указанного списка выбирается та, которая минимизирует значение J{a,j)=gia,j}^h(a,j), где А(%) - значение эвристической функции для клетки % Так продолжается до тех пор, пока из списка не будет выбрана целевая клетка. Когда это произойдет, искомый путь восстанавливается с использованием родительских указателей. То есть, начиная с целевой клетки в искомый путь добавляются клетки, являющиеся родительскими для текущей, до тех пор, пока не будет добавлена начальная клетка.

Суть проблемы локального минимума заключается в неравномерном распределении /значений по клеткам МТ-графа при наличии непроходимых клеток.

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

1 Имеется в виду вес кратчайшего пути, найденного к текущей итерации алгоритма.

На рис. 1(6) белым цветом помечен путь, найденный с помощью алгоритма А* (с использованием диагональной метрики МТ-графа в качестве эвристики), серым цветом -клетки, для которых рассчитаны ^-значения. Именно количеством таких клеток определяется в общем случае вычислительная сложность алгоритмов семейства А*. Очевидно, что подавляющее большинство рассмотренных в ходе поиска клеток, не имеют отношение к решению задачи, то есть не являются ни родительскими клетками для клеток входящих в искомый путь, ни самими таковыми клетками. Данная проблема и носит название проблемы локального минимума, применительно к рассматриваемой задаче.

Традиционным (и фактически - единственно возможным по состоянию исследований на текущий момент) путем разрешения проблемы локального минимума и сокращения емкостной и временной сложности алгоритма А*, является использование взвешенных эвристик, т.е эвристик вида \мЫрц), и<>1, при поиске. Однако, можно утверждать (на основании анализа рассматриваемого примера и схожих с ним), что применение взвешенных эвристик принципиально не решает проблему локального минимума, т.к. повышение веса эвристики зачастую не сопровождается сокращением числа рассматриваемых клеток, а лишь приводит к ухудшению качества найденного решения задачи планирования (к увеличению веса построенного пути). Более того, можно утверждать что, всегда существует такое значение и<, дальнейшее увеличения которого не приводит ни к сокращению пространства поиска ни к изменению веса найденного пути - см. рис. 1(в), 1(г).

Рис. 1. Проблема локального минимума, а) Исходный МТ-граф; б) Результат работы алгоритма А*; в)

У\ГА*, №=3; г) \\'А*> и<=5.

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

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

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

Определим на МТ-графе Атх„ операцию элементарного поворота ROT следующим образом: ROT(Am*„)=RAn**, где RA„y„={ra,j} - МТ-граф с высотой п и шириной т, т.ч.

1 / Vz j: 0<i<m, d£j<n.

Обозначим ROf(A„x„}=Am*„, ROf(A„*„)=ROT(A„*n) ROf(Am*„)=ROT(RO?(A„*„)), ROf(A„,„)=ROT(ROf(A„ *„)),..., ROr{Am*„y=ROT{ROr-l(An*n)).

Имеет место следующее утверждение.

Утверждение 1. ROT^jA^^A

Следствие. ROfM(Am,„)= ROT\Amm) VksN, i=О,1,2,3.

Будем называть МТ-графы ROTl{Am„\ ROf(Am*„), ROf(Am,„) двойственными для МТ-графа А„,„.

Определим операцию взятия индекса клетки аш МТ-графа Ат%„ следующим образом: /(a№)=v (взятие i-ro индекса), j(am)=w (взятие j-го индекса).

Рассмотрим следующие величины А,(аи, aik)=\i(aij)-i(ati\=\i-l\; А/(%. а»)=1/(%Н(ад)| =1М|.

С использованием этих величин введем следующие определения.

Будем говорить, что клетка ац расположена правее клетки a,j, если Д/>А, и J(aii)>j(a,j). Будем говорить, что клетка ац расположена левее клетки щ, если Д^Д, и j(aik)<j(a,j). Будем говорить, что клетка ац расположена выше клетки % если ДйД/ и ¡(ац)>г(ау). Будем говорить, что клетка ац расположена ниже клетки atj, если Л,>Ду и ¡(ац)<1(ау).

Справедливы следующие утверждения.

Утверждение 2. Для любых о,у, ацеАтх„, таких что j{aa)<j(a,j), верно, что j(rau)>j(ra,j) либо j{faikp>j(faij)b где га,у, гац- клетки МТ-графа ROT(A„*„), соответствующие клеткам % ац; щ, гац- клетки МТ-графа ROTi(Am^), соответствующие клеткам <%, ац.

Утверждение 3. Для любых iацеАтх„, таких что j(auc)-j(aij), верно, что j(rau)>j(raij) либо j(faiîpj(fa,j), где щ, гац- клетки МТ-графа ROT(Am*„), соответствующие клеткам я,уз ац; гад, гол - клетки МТ-графа ROTl(Amx„), соответствующие клеткам а,у, ац.

Утверждение 4.

Для любых a,j, ацеАт*п, таких что j(flu)>j{çtij), верно, что А/ау, ац)>Ы{а,], ац) либо Д,(га,у, гад)>Д,(га,;, гац), где га5, гац - клетки МТ-графа ROT(Am*„), соответствующие клеткам ад, ац.

Утверждение 5. Для любых клеток a,j, ацеА„*„, клетка ац расположена правее клетки ау либо на самом графе А„*„, либо на одном из двойственных ему МТ-графов ROT(Amx„), ROf(Am*n), ROf(Am*„).

Таким образом, без ограничения общности можно полагать, что при рассмотрении задачи планирования траектории PTask целевая клетка МТ-графа расположена правее начальной.

Далее в работе исследуется структура множества кратчайших путей на МТ-графе. Докрывается ряд лемм.

Лемма 1. Пусть я{a,j, aa)={fl/oр, апр, апfi, ..., ai.j,} - путь на МТ-Графе А„*„ (при этом ад-расположена правее aij), тогда We[/'; к] Заея: j(a)=r.

Лемма 2. Пусть n*{a,j, ацг)={а/0р, апр, апр, ■ ■■, а„,,} - кратчайший путь на полностью проходимом МТ-Графе Лт*„ (при этом ац расположена правее atJ), и cj=k-ci,v, \<к<2, тогда Va,„y„ at.,,jr.,EZ* выполняется соотношение: j„. ¡>jv.

В работе также показывается, что без ограничения общности можно считать, что лемма 2 верна и для МТ-графов АК,„, т.ч. с^к-сь-,, 1<к<2

Лемма 3. Пусть я(ау, аа)={а,0р, а„>,, a,2jl,..., а„р} - путь на МТ-Графе Ая*„ (при этом ац расположена правее ац) и !>i (/</) тогда Vre [/; /] (Vre[/; ¿]) Заел-*: /(а)=г.

Лемма 4. Пусть ?r*(a,j, fl/i)={a,oр, an р, аар, ..., а„ j,} - кратчайший путь на полностью проходимом МТ-Графе Ат%„ (при этом ац. расположена правее a,j), и cj^k-cim \<к<1 и £>/ (l<i), тогдаVa/vj„ а^^ея* выполняется соотношение: /v+i>iv (iv+iä/v).

Лемма 5. Пусть <ад)={ад>р, a<iр, aap, •••, - кратчайший путь на полностью проходимом МТ-Графе А„<„ (при этом ац расположена правее а,у), тогда Va„>,,е,т* выполняется соотношение: jv+\>jv.

Лемма 6. Пусть лац)={а,0р, а, аа р.....at,j,) - кратчайший путь на полностью

проходимом МТ-Графе Л„*„ (при этом ац расположена правее ач), тогда Лг(.т)-Дг (=\k-j\~k-j).

Следствие. Пусть х'(аи, ац)={а,а р, апß, aafi, ..., а„р) - кратчайший путь на полностью проходимом МТ-Графе Ат*„ (при этом ац расположена правее a:j), и с^с^ тогда c{i:*)=AfCj=Aj-Cf,^H(a,j, ац).

Замечание к следствию. По определению кратчайшего пути верно и обратное утверждение: если вес пути ж*(%, ац) равняется Д/сД=ДгС^), то он является кратчайшим.

Лемма 7. Пусть ж*(ац, ац)={а№ J0, а,,;ь аар, ..., ahJ,} - кратчайший путь на полностью проходимом МТ-Графе Ат,„ (при этом ац расположена правее <%), и с^гк-с^, 1<£<2, тогда N/x*)=Д„ Щх*)=АгА„ NJz*)=0.

Следствие. Пусть ац)={а10р, а,ч,, айр.....а„>} - кратчайший путь на полностью

проходимом МТ-Графе Л„*„ (при этом ац расположена правее %), тогда фг*)=

=Arcj+(ärM)-CH,=H(aij, ац).

Замечание к следствию. По определению кратчайшего пути верно и обратное утверждение: если вес пути гi*(atj, ац) равняется ArcjH.Aj-A,) c>,v, то он является кратчайшим.

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

Теорема 1. Пусть МТ-траф Ая%„ является полностью проходимым, при этом cj=k-c>„„ 1<£<2. Последовательность смежных проходимых клеток МТ-графа ж*(%, aif= {ац,р=ау, аЛр, aafi,..., аи^=ац) является кратчайшим путем из atj в ац (ац расположена правее a,J) тогда и только тогда, когда Va,„^ аЫ1 j„, ея* выполняется соотношение^1>> и Л'<Х;г*)=Л„ Щк*)=АгА,

Теорема 2. Пусть МТ-граф Ат,.„ является полностью проходимым, при этом су=сау. Последовательность смежных проходимых клеток МТ-графа лд)=

¿гцуь Як/г, - а11р=аа} является кратчайшем путем из а.у в ац (а^ расположена правее ау) тогда и только тогда, когда Уа„/„ ам¿»¡ел* выполняется соотношение:

Опираясь на доказанные выше утверждения (а именно леммы 1-7, теоремы 1-2) опишем структуру множества кратчайших путей на МТ-графе.

Пусть Ат,„ - полностью проходимый МТ-граф, при этом сг=ксь, 1<к<2. Обозначим множество кратчайших путей из ау в ац как ¿'/■(а,;, ац). В соответствии с теоремой 1, каждый элемент ЯР - последовательность смежных клеток, начинающаяся с щ, заканчивающаяся ац, насчитывающая Д;+1 клеток (среди который отсутствуют вертикально-смежные), при этом число переходов между диагонально-смежными клетками, составляет Д/, а число переходов между горизонтально-смежными - А/-&¡. Заметим так же, что если некоторый путь ж* является кратчайшим для МТ-графа Ллхл, т.ч. с^к-с^, \<к<1, то ж* являепся кратчайшим и для соответствующего МТ-графа с с<гсы. Таким образом, если £/"(%, а&) - множество кратчайших путей из а¡к в ац на МТ-графе Ат*„, т.ч. с</=сь, то £?"(%, ац)з$Р(ау, ац).

Пусть граф А„*п является частично проходимым (при этом клетки ау и ац. - проходимы). Тогда говорить об элементе множества 5Р(а,], ац), как о пути - неуместно, т.к. он может содержать непроходимые клетки МТ-графа. В таком случае (здесь и далее, когда речь идет о частично проходимых МТ-графах) будем называть элементы множества 5Р нуль-траекториями.

Формальное определение нуль-траектории между проходимыми клетками ау и ац на МТ-графе А„хЛ (при условии, что ац расположена правее ау) может звучать следующим образом: нуль-траектория - это последовательность клеток МТ-графа &(<%, ал)={ай> оц/|, аар,..., ац;,}, такая что: аюр=ау, а^а„р и \Л>: 1<у<г, (сг,м а^^)еАШ и \Л>: 1<у<у,/,=./»-!+1 и Л^й")^ и Щ^гИДг-Д,. Весом нуль-траектории будем называть величину фг(ау, ац)), определяемую аналогично весу пути л(%, ац). При этом (см. леммы 6,7) с(Гг(% ац))гН(ау, ац).

Для построения нуль-траектории на МТ-графе может использоваться широко-извесгный в области машинной графики алгоритм Брезенхема. Его характерной особенностью является тот факт, что алгоритм Брезенхема строит нуль-траекторию максимально близкую к отрезку «дискретной прямой», проходящей через клетки (точки) ау, ац.

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

Секцией будем называть упорядоченную пару клеток МТ-графа (ау, ац). Секция (ау, ац) проходима тогда и только тогда, когда нуль-траектория 1г(ау, ац) содержит лишь проходимые клетки. Весом секции назовем величину с((ау, ац))=с('г(%> °1к))гЩау, ац).

Пусть ау, ац е А„*„, при этом ауМц , а,/=0, ац=0. Частичным путем из ау в ац будем называть последовательность клеток МТ-графа РР=[аир, ап а^р, ..., такую что апр=ау, а„р=ац. Если при этом каждая из секций (алр, ап]\), (ап],, аПр),..., (а,,,а„ является проходимой, то частичный путь РР будем называть допустимым, в противном случае - недопустимым. Клетки, входящие в частичный путь будем называть опорными. Вес

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

Используя приведенную выше терминологию, задача планирования траектории PTa.sk может рассматриваться, как задача отыскания на МТ-графе допустимого частичного пути из "nanisiaru в a,¿oa>jgooii- Другими словами справедливо следующее утверждение.

Утверждение 6. Задача планирования PTask эквивалентна задаче отыскания допустимого частичного пути из auanimni в ctgoaugoau, в том смысле, что, имея допустимый частичный пугь PP(a,j, ац), путь 7c(a,¡, au) может быть получен автоматически.

Доказательство утверждения заключается в явном описании алгоритма, по которому искомый путь Tt{a¡¡, au) может быть получен из PP(a¡j, a¡¡¡).

Будем называть путь л/>/>(%, полученный из допустимого частичного пути РР{аи, au) (по описанному алгоритму), путем восстановленным из PP(a¡¡, ац).

Если xppe.SP(a¡j, ац), то есть, если ярр является кратчайшим путем на МТ-графе из клетки a¡j в клетку ац, то будем называть соответствующий допустимый частичный путь SP -оптимальным.

Доказываются следующие утверждения.

Утверждение 7. Пусть PP(at¡, аи)={ац,р, а„р, аир,..., а„у,} - допустимый частичный путь из a,¡ в a¡í на МТ-графе Ат,„ таком, что cj=c/,v. Тогда itfpeSP(a,,, ац), если клетка a¡„i _/»,, расположена правее а„> V0<v<s

Утверждение 8. Пусть PP(a¡j, аи)={а№р, a¡¡j¡, aajl.....a¡,p} - допустимый частичный путь

из ац в ац на МТ-графе А„„„ таком, что сегк-с^, 1<к<2. Тогда лppeSP(atj, ац), если клетка a^+i расположена правее ар V0<v<s и ¿w+i>(\, VO<v<¿ (либо iVhSj» V0<v<s).

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

Шаг 1. Сформировать множество частичных путей кандидатов РРС, первоначально Содержащее ЛИШЬ ЧаСТИЧНЫЙ ПУТЬ PP={astanlslanJ, OgeaUgoolj}-

Шаг 2. Выбрать из РРС кратчайший частичный путь РР2.

Шаг 3. Если текущий частичный путь РР является допустимым, то вернуть PP.

Шаг 4. Выбрать две опорные клетки, я, и a¡¡¡, входящие в РР3.

Шаг 5. Построить нуль-траекторию tr(a¡j, au).

Шаг 6. Если нуль-траектория t¡ia,¡, ац) проходима, то перейти к шагу 2.

Шаг 7. Случайным образом выбрать Л'клеток C¡, С2,-.., С„ еА.

Шаг 8. Разбить РР на N вариантов, а именно - для каждого РРеРРС, содержащего последовательность a¡у, au выполнить следующие шаги:

а) скопировать /УЛ'раз в РРС;

б) для каждого из N скопированных частичных путей заменить последовательность a¡¡ на Щ, C¡, a¡£, a¡¡. Ci, a¿,... ; a¡¡. С», а» соответственно.

Шаг 9. Перейти к шагу 2.

2 Кратчайший частичный путь - путь с минимальный значением С(РР)

' Здесь и далее будем предполагать, что выбираютсл клетки, образующие первую непроходимую секцию » РР.

Процесс, выполняемый на 7-8 шагах алгоритма, будем называть разбиением секции (a,j, ац). Клетки ay, ait, выбираемые на шаге 2, будем называть локальными начальной и целевой клетками соответственно. В соответствии с утверждением 5, как и раньше будем считать, что локальная целевая клетка всегда располагается правее локальной начальной.

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

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

Множество смежных непроходимых клеток МТ-графаЛтхП будем называть препятствием: obs-{aianj,, ai2p,..., a^j а„>=1, Vv=0,1,2,..., s, seN). Будем говорить,

что препятствие obs расположено между клетками a,j и аи, если trifty, an)r\obs*0. При этом клетку aetiiay, aIk)r\obs такую, что Va'efr^, au)r\obs\ j(a)<j(a'), будем называть клеткой, в которой нуль-траектория tr{an, an) пересекает препятствие obs.

Множество ¡c(obs)={a[ aeobs, Va'eobs: j{a')>j{a)} будем называть множеством левых крайних клеток препятствия. Множество rc(obs)~{a] aeobs, Vo"еobs: j(d)<j(a)} будем называть множеством правых крайних клеток препятствия.

Будем говорить, что клетка аеАт*„ лежит выше (ниже) препятствия obs, если aeobs, j(a')<j(a)<j(a") и Sbeobs: i(a)>i(b) (i(a)<i(b)), где a'elc(obs), a"erc(obs).

Обозначим множество всех препятствий МТ-графаЛЯхЛ как OBS={obso, obs\,..., obsui obs, - препятствие, 0<i<№}, где И7-общее число всех препятствий на МТ-графе.

Пусть obs,, obsjeOBS. Будем говорить, что препятствие obs, располагается (лежит) выше/над (ниже/под) препятствием obsj, если 3aeobst, a'eobsf. j(a)~j{af), i{a)>i(a') (Baeobsi, cfeobsf.j(a)=j(J),i(a)<i(a')).

Введем следующее ограничения:

А) Все препятствия на МТ-графе имеют прямоугольный вид.

Б) Ни одно препятствие не располагается над или под другим, и также начальная и целевая клетка не расположены над (или под) препятствием.

Справедливо следующее утверждение.

Утверждение 9. Пусть ау, ац - проходимые клетки на МТ-графе Ат*п (при этом аш расположена правее atJ) и препятствие obs лежит между ау и аш. Тогда путь л(ау, ац) необходимо содержит клетки расположенные выше (либо ниже) препятствия.

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

В работе описывается процедура GetBaseCells, которая возвращает 4 клетки МТ-графа, ограничивающие прямоугольное препятствие, так как это показано на рис. 2. Входными

данными для процедуры являются локальная целевая и начальная клетки ^ и 5, соответственно) некоторого частичного нуги РРеРРС и клетка X, в которой нуль-траектория g) пересекает некоторое (прямоугольное) препятствие оЬя. Суть процедуры заключается в итерационном обходе клеток, лежащих на границе препятствия, по и против часовой стрелки (начиная с клетки X) для определения индексов клеток Л, В, С, О. С помощью этих клеток не составляет труда осуществить разбиение секции <5, g> по следующему алгоритму: для каждого РРеРРС, содержащего последовательность з, й выполнить: Шаг 1. Скопировать РР в РР1 и РР2 Шаг 2. В РР1 заменить последовательность я, g на л, А, В, g Шаг 3. В РР2 заменить последовательность g на Д С, %

Рис. 2. Разбиение <s, g> секции с помощью клеток, возвращенных процедурой GetBaseCells.

Если процедура GetBaseCells возвращает только клетки А и В (либо С и D), то нет необходимости в копировании частичного пути РР, требуется лишь замена s, g на s, А, В, g (s, D, С, g). Если же A =B=C=D=null, то не существует пути из s в g, что в свою очередь означает, что не существует решения рассматриваемой задачи планирования. Таким образом, детерминированный алгоритм построения допустимого частичного пути на МТ-графе -HGA* - может быть представлен в следующем виде.

Шаг 1. Сформировать множество частичных путей кандидатов РРС, первоначально содержащее лишь частичный путь PP={astanisunj, agoaii goau} ■

Шаг 2. Выбрать из РРС частичный путь PP.

Шаг 3. Если текущий частичный путь РР является допустимым, то вернуть PP.

Шаг 4. Выбрать две опорные клетки, % и аш, входящие в PP.

Шаг 5. Построить нуль-траекторию fr(%, ait).

Шаг 6. Если нуль-траектория tiiay, аш) проходима, то перейти к шагу 2.

Шаг 7. Выполнить процедуру GetBaseCells.

Шаг 8. Если все клетки, возвращенные GetBaseCells, равны null, то осуществить выход (пути из as,ardstanj в agmngoaU в не существует).

Шаг 9. Осуществить разбиение секции (ау, а/к) с помощью найденных клеток.

Шаг 10. Перейти к шагу 2.

В работе проводится теоретический анализ свойств алгоритма HGA* при указанных ограничениях. Показывается, что емкостная и временная сложность алгоритма может быть оценена как 0(D) (где D - глубина решения задачи), в то время, как сложность эвристических алгоритмов семейства А* - ООО2). Устанавливаются критерии оптимальности алгоритма.

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

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

Был произведен экспериментальный анализ алгоритмов HGA*, A*, WA*-3 и WA*-5 (WA*-* - алгоритм А*, использующий взвешенную эвристику с весом х). Для этого были проведены три серии экспериментов по отысканию пути на МТ-графах. Между собой сравнивались следующие выходные параметры (показатели, индикаторы) алгоритмов:

iVaig - вес пути, найденного алгоритмом alg\

Qaig - число клеток МТ-графа, рассмотренных при поиске пути;

Taig - время, затраченное алгоритмом alg на поиск пути;

EQaigHQaiglWaig) - коэффициент емкостной эффективности alg-,

ENQaig=(Qaig/Wai^/(QA<JWje)- нормированный коэффициент емкостной эффективности alg.

В первой серии экспериментов было сгенерировано 150 МТ-графов с различной степенью заполнения препятствиями, Я (0,3; 0,5; 0.8)5. Начальная и целевая клетки выбирались таким образом, чтобы глубина решения составляла 50, 100, 250, 500 и 1000. Препятствиями являлись прямоугольники шириной 1 клетку и длиной (в среднем) -10 клеток. Усредненные (по всем прогонам) результаты экспериментов на МТ-графах с Я.=0,3 представлены ниже.

Таблица. 1. Результаты экспериментов на МТ-графах с параметром Я,=0,3.

Выходные Глубина pi шения

Алгоритм параметры 50 100 250 500 1000

А* 567 1165 2804 5809 11483

А* Qa- 320 1291 7405 23332 97132

А* Та- 1,36 26,09 932,80 10230,51 172512,39

А* eqa. 0,56 1,11 2,64 4,02 8,46

А» enqa. 1,00 1,00 1,00 1,00 1,00

WAV3 «Wj 612 1239 3134 6454 12769

WA*-3 Qwa'-Î 193 365 968 1970 3890

WA*-3 Тил'-i 0,22 0,65 4,21 16,22 61,58

WA*-3 EQwa'-i 0,32 0,29 0,31 0,31 0,30

WA*-3 ENQwa-.i 0,56 0,27 0,12 0,08 0,04

WA*-5 УГглч 625 1252 3194 6545 12962

WA*-5 Qm'-з 191 363 959 1951 3864

WA*-5 Tw-j 0,21 0,64 4,06 15,55 59,78

WA*-5 EQwa'-i 0,31 0,29 0,30 0,30 0,30

WA*-5 ENQ„a.., 0,54 0,26 0,11 0,07 0,04

HGA* Whoa- 571 1191 2908 6036 11930

HGA* qiiga- 29 105 294 539 1029

HGA* Тна{' 0,11 0,51 2,40 9,61 39,93

HGA* EQhga• 0,05 0,09 0,10 0,09 0,09

HGA* ENQhg.1 • 0,09 0,08 0,04 0,02 0,01

* Для подсчета веса пути использовались следующие значения величин с^ и 10, 14.

5 Использовалась следующая формула А. где/ - площадь препятствия, -V - число препятствий,

т - высота МТ-графа я - ширина МТ-графа.

При проведении второй серии экспериментов было сгенерировано 50 МТ-графов с фиксированной степенью заполнения препятствиями: л.=0,5. Глубина решения была зафиксирована на отметке 100. Ширина препятствий была фиксирована и составляла 1 (клетку). Средняя длина препятствий / составляла 2, 5, 10, 15, 25 клеток (по 10 МТ-графов для каждого значения I было сгенерировано).

Результаты первой и второй серии экспериментов позволяют сделать следующие выводы.

Алгоритмы \УА*-3, \УА*-5, ГЮА* значительно превосходят алгоритм А* по показателям временной и емкостной эффективности. При этом, значения указанных показателей для \УА*-3, '\УА*-5 практически совпадают.

Алгоритм НОА* превосходит алгоритмы WA*-3, WA*-5 по рассматриваемым показателям емкостной эффективности. При этом вес пуш, найденного алгоритмом НОА*, практически совпадает с весом кратчайшего пуш. Показатели временной эффективности ЬЮА* находятся на уровне \УА*-3, WA*-5.

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

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

В заключении приведены основные результаты, полученные в диссертационной работе.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Предложена и исследована новая графовая модель, отражающая особенности задачи планирования траектории на плоскости - метрический топологический граф (МТ-граф).

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

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

Предложены различные модификации алгоритма НОА* для различных типов задач планирования траектории.

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

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

СПИСОК ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ РАБОТ

1. Яковлев К.С. Архитектуры систем управления автономными беспилотными аппаратами. Труды XLIV Всероссийской конференции по проблемам математики, физики и информатики. Секция «программные системы». М.: РУДН. 2008. - 0,35 п.л.

2. Яковлев К.С. Методы решения проблемы локального минимума при планировании траектории. Труды IX международной научной конференция им.Таран Т.А. «Интеллектуальный анализ информации ИАИ-2009», Киев: ПРОСВ1ТА, 2009. 0,32 п.л.

3. Яковлев К.С. Автоматическое планирование в современных системах управления. Тезисы докладов XLV Всероссийской конференции по проблемам математики, информатики, физики и химии. М.: РУДН, 2009. - 0,06 п.л.

4. Осипов Г.С., Тихомиров ИЛ., Хачумов В.М., Яковлев К.С. Интеллектуальное управление транспортными средствами: стандарты, проекты, реализации // Авиакосмическое приборостроение, № 6, 2009. М: НАУЧТЕХЛИТИЗДАТ, 2009. -0,88 пл., из них автора 0,24 пл.

5. Яковлев К.С. Графы специальной структуры в задачах планирования траектории. Труды III международной конференции «Системный анализ и информационные технологии САИТ-2009». М: ИСА РАН, 2009. - 0,53 п.л.

6. Никифорова Л.Н., Яковлев К.С. Маловысотный полет вертолета и проблемы его автоматизации // Искусственный интеллект и принятие решений, 3,2009. М: ИСА РАН, 2009. - 0,42 п.л., в том числе автора 0,1 п.л.

7. Сарафанов В.Ю., Яковлев К.С. Методы планирования траектории в динамической среде. Тезисы докладов XLVI Всероссийской конференции по проблемам математики, информатики, физики и химии. М.: РУДН, 2010. - 0,1 п.л, в том числе автора 0,06 пл.

8. Яковлев К.С. HGA*: эффективный алгоритм планирования траектории на плоскости // Искусственный интеллект и принятие решений, 2, 2010. М: ИСА РАН, 2010.-0,78 пл.

9. Яковлев К.С. Иерархический подход в задачах планирования траектории на плоскости. Труды 12-й Национальной конференции по искусственному интеллекту. М: ФИЗМАТЛИТ, 2010. - 0,6 п.л.

В работе [4] соискателю принадлежит описание архитектуры и функциональных компонент системы управления беспилотным летательным аппаратом UCAR, в [7] -описание метода планирования траектории в динамической среде, в [6] - описание одной из фаз маловысотного полета вертолета.

Подписано в печать:

29.09.2010

Заказ № 4201 Тираж - 100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

ВВЕДЕНИЕ.4>

Актуальность темы.

Цели и задачи исследования.

Методы исследования.

Научная новизна работы и результаты, выносимые на защиту.б

Практическая значимость рХботы.

Апробация работы.

Публикации.

Структура и объем работы.

Основное содержание работы.91. АНАЛИЗ МЕТОДОВ И АЛГОРИТМОВ ПЛАНИРОВАНИЯ ТРАЕКТОРИИ.

1.1 Предметная область. 1.2 Задача планирования как задача поиска пути на графе.

1.3 Методы поиска пути на графе.

1.3.1 Поиск пути на графе как расчет g*-знaчeнuй.

1.3.2 Эвристические алгоритмы поиска пути.

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

1.3.4 Выводы.

1.4 Методы построения графов для решения задачи планирования траектории.

1.4.1 Методы построения графов видимости.

1.4.2 Методы построения разбиения Вороного.

1.4.3 Методы извлечения графовых моделей непосредственно из цифровой карты местности .:.

1.4.4 Выводы.

1.5. Выводы.

2. МЕТРИЧЕСКИЕ ТОПОЛОГИЧЕСКИЕ ГРАФЫ И ИХ ПРИМЕНЕНИЕ В ЗАДАЧАХ ПЛАНИРОВАНИЯ ТРАЕКТОРИИ.

2.1. Основные определения.

2.2 Метрики на МТ-графах.

2.2.1 Метрика кратчайшего пути.

2.2.2 Диагональная метрика.

2.3 Эвристический поиск пути на МТ-графах.

2.4 Проблема локального минимума.

2.5 Выводы.

3. ИЕРАРХИЧЕСКИЙ ПОДХОД К ЗАДАЧЕ ПОИСКА ПУТИ НА МТ-ГРАФЕ.

3.1 Множество кратчайших путей на МТ-графе.

3.1.1 Операция поворота и взаимное расположение клеток МТ-графа.

3.1.2 Структура множества кратчайших путей полностью проходимого МТ-графа.

3.1.3 Нуль-траектории на МТ-графе.

3.2 Простейшие иерархические алгоритмы поиска пути на МТ-графе.

3.2.1 Основные определения и утверждения.

3.2.2 Простейшие реализации иерархического подхода к поиску пути на МТ-графе.

3.3 Алгоритм ША*.

3.3.1 Препятствия на МТ-графе.

3.3.2 Стратегия выделения опорных клеток алгоритма НСА*.

3.3.3 Базовая реализация алгоритма НСА*.•.

3.3.4 Теоретические свойства базовой реализации алгоритма НСА *.

3.3.5 Эвристическая реализация алгоритма НСА *.

3.4. Выводы.

4. ЭКСПЕРИМЕНТАЛЬНОЕ ОБОСНОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМА НвА*.

4.1 Прогтаммно-аппаратный комплекс для проведения экспериментов.

4.1.1 Аппаратный комплекс.

4.1.2 Программный комплекс.

4.2 Первая серия экспериментов.

4.3. Вторая серия экспериментов.

4.4. Третья серия экспериментов.

4.5. Выводы.

Актуальность темы

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

Задача планирования траектории в- контексте автоматизации управления сложными техническим объектами (роботами, транспортными средствами и др.) изучается с 50-х годов XX века. Одним из первых проектов в этой области являлся известный проект Стэнфордского университета США по созданию робота SHAKEY в 1966-1972 гг. Именно он положил начало многолетним исследованиям методов и подходов к решению- задач планирования траектории, продолжающимся по сей день. За последние годы были успешно реализованы десятки крупных проектов в этой области, например:

- DARPA URBAN CHALLENGE (соревнования беспилотных автомобилей в городских условиях, 2008г., США)

- NASA ARP (создание системы управления малым беспилотным вертолетом Yamaha RMAX II, предназначенным для разведки и мониторинга, 1998-2003 гг. США)

- MARS (разработка программного обеспечения для автономных наземных роботов, США, 1999-2004 гг.)

- У1АС (создание беспилотной модификации гражданского' автомобиля и осуществление пробега протяженностью 13 ООО км., Европейский Союз, 2010)

- Робокросс (соревнования автомобилей-роботов, Россия, 2010).

К сожалению, почти все методы планирования' траектории, разработанные к текущему моменту и используемые в системах управления современными беспилотными транспортными' средствами, являются-достаточно ресурсоемкими. При этом большинство из них принципиально не способно решать задачи планирования траектории в условиях дефицита* вычислительных ресурсов. Следовательно, известные методы неприменимы тогда, когда^ речь об автоматизации малых, полностью« автономных беспилотных транспортных средств, т.к. подобные транспортные средства не" могут быть оснащены» мощными вычислителями в силу особенностей конструкции И' ограниченной грузоподъемности.

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

Цели и задачи исследования

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

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

1. Выполнен анализ существующих методов построения графов, являющихся моделями предметной области в задачах планирования траектории и методов поиска пути на указанных графах. Предложена и исследована графовая модель, отражающая особенности задачи планирования траектории на плоскости — метрический топологический граф (МТ-граф).

2. Разработаны принципы иерархической декомпозиции задачи планирования траектории1 и алгоритм планирования траектории, реализующий эти принципы - БЮА*.

3. Исследованы свойства алгоритма НХЗА* при ^определенных ограничениях. Предложены модификации алгоритма ЕЮА*, предназначенные для решения различных типов задач планирования траектории на плоскости.

4. Разработаны программные средства для оценки вычислительной эффективности различных алгоритмов планирования траектории. Проведена серия вычислительных экспериментов, направленных на сравнение разработанного алгоритма НХЗА* с аналогами.

Методы исследования

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

Научная новизна работы и результаты, выносимые на защиту

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

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

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

Практическая значимость работы

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

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

1. «Интеллектуальная система поддержки автоматизированного маловысотного полета вертолета», проект Российского Фонда Фундаментальных исследований № 09-07-00043-а

2. «Развитие методов анализа полуструктурированной информации и моделирования целенаправленного- поведения», выполняемого- в рамках федеральной целевой программы «Научные и научно-педагогические кадры инновационной России».

3. «Развитие методов- интеллектуального управления на основе анализа потоков данных», проект 2.2 Отделения нанотехнологий и информационных технологий Российский академии наук.

Апробация работы

Основные положения работы докладывались и обсуждались на следующих научных конференциях и семинарах:

1. XII национальная конференция по искусственному интеллекту с международным участием (КИИ-2010), сентябрь 2010, г. Тверь.

2. Общемосковский научный семинар «Проблемы искусственного интеллекта», март 2010, г. Москва.

3. III международная конференция «Системный анализ и-информационные технологии - САЙТ 2009», сентябрь 2009, г. Звенигород

4. IX международная научной конференция им. Таран Т.А «Интеллектуальный анализ информации - ИАИ-2009», май 2009, г. Киев, Украина.

5. ХЫП всероссийская конференции по проблемам математики, информатики, физики и химии Российского' университета дружбы народов, апрель 2008, г.Москва.

Публикации

Основные результаты, полученные по теме диссертационной работы, опубликованы в 9 печатных работах (в том числе 2 публикации' в ведущих ' рецензируемых научных изданиях, рекомендованных Высшей^ аттестационной комиссией, 6 публикаций в трудах научных конференций).

Структура и объем работы

Диссертация- состоит из введения, трех глав" заключения, списка

Основные результаты работы.

Предложена и исследована новая графовая модель, отражающая особенности задачи планирования траектории на плоскости — метрический топологический граф (МТ-граф).

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

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

Предложены различные модификации алгоритма НвА* для различных типов задач планирования траектории.

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

С помощью разработанной программной системы выполнено более 200 вычислительных экспериментов, показавших значительное превосходство алгоритма БЮА* над существующими аналогами с точки зрения использования вычислительных ресурсов.

Заключение

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

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

1. Т. Кормен и д/?., 2005. Кормен Т.Х., ЛейзерсошЧЖ, Ривест Р:Л;, Штайш К. Глава 33. Вычислительная: геометрия? // Алгоритмы: построение и анализ. 2-е издание. М.: «Вильяме». 2005.

2. Левитин, 2006.;; А. В. Левитин; Алгоритмы: введение: в разработку и анализ. М.: «Вильяме», 2006.

3. Люгер,, 2005.; Щ Ф1 Люгер; Искусственный* интеллект. Стратегии: и» методы решения сложных проблем;-М: Вильяме, 2005.

4. Прапарата и Шеймос, 1989. Прапарата Ф., Шеймос М. Вычислительная геометрия: введение. М;: Мир, 1989. С. 478.

5. Рассел и: Норвиг, 2006. Рассел С., Норвиг П. Искуственный интеллект: современный подход. Пер. с англ. и ред. К. А. Птицына. 2-е изд. М.: Вильяме, 2006.

6. Яковлев, 2008. Яковлев К.С. Архитектуры систем управления автономными, беспилотными аппаратами. Труды XLIV всероссийской конференции:по проблемам математики, физики и информатики. Секция «программные системы». М.: РУДН. 2008; С. 40-50.

7. Яковлев,,2009а.'Яковлев К.С. Методьърешения проблемы локального минимума при планировании траектории. // Труды- IX международной научной конференция им.Таран Т.А. «Интеллектуальный^ анализ информации ИАИ-2009», Киев: ПРОСВГГА, 2009. С. 451-457.

8. Яковлев, 20096. Яковлев К.С. Графы специальной.структуры в.задачах планирования траектории. Труды III международной конференции «Системный анализ и информационные технологии САИТ-2009». М: ИСА РАН, 2009. С. 226-234.

9. Albus J. et al, 2002. Albus J. et al, 4D/Real-time Control System (4D/RCS): AReference Model Architecture for Unmanned Vehicle Systemsv2.0, NIST, NISTIR6910, 2002.

10. Alt, 1995.iAlt O. S. H. The voronoi diagram of curved objects, in Proc. 11th Annual ACM Symposium on Computational Geometry, 1995.

11. Asano et al, 1986. T. Asano, T. Asano, L. J. Guibas, J. Hershberger, and H. Imai. Visibility of disjoint polygons. Algorithmica, 1:49-63, 1986.

12. Aurenhammer, 1991. F. Aurenhammer. Voronoi diagrams — A survey of a fundamental data structure. ACM Computer Surveys 23 (3), 1991.

13. Bagchi and Mahanti, 1983. Bagchi A. and Mahanti A. Search algorithms under different kinds of heuristics: a comparative study. Journal of the ACM, 30(1):1-21, 1983.

14. Berg et al, 2008. M. Berg, O. Cheong, M. Kreveld, and M. Overmars.

15. Computational Geometry: Algorithms and Applications, 3rd ed. Springer,1. April 2008.

16. Bole and Cytowski, 1992. Bole L. and Cytowski J. Search methods forartificial intelligence. Academic press, London, 1992.

17. Bresenham, 1965. J. E. Bresenham. Algorithm for computer control of adigital plotter. //IBM SystemsJournal, Vol. 4, No.l, 1965.4,

18. Choset and Burdick, 1995. Choset H. and Burdick J. Sensor based planning, part I: The generalized voronoi graph. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 1995.

19. Dean and Boddy, 1988. T. L. Dean and M. Boddy. An analysis of time-dependent planning. In Proceedings of the National Conference on Artificial Intelligence, AAAI-88, 1988.

20. Dechter and Pearl, 1985. Dechter R. and Pearl J. Generalized best-first search strategies and the optimality of A*. Journal of the ACM, 32(3):505-536, 1985.

21. Dehne and Klein, 1997. F. Dehne and R. Klein, "The big sweep": On the power of the wavefront approach to Voronoi diagrams, Algorithmica 17:19— 32, 1997.

22. Dijkstra, 1959. E. W. Dijkstra. A note on two problems in connexion with graphs. //Numerische Mathematik, 1:269-271, 1959.

23. Ebendt and Drechsler, 2009. Ebendt R. and Drechsler R. Weighted A* search unifying view and application. Artificial Intelligence, 173(14): 13101342,2009.

24. Edelkamp et al, 2008. Edelkamp S. et al, External-Memory Graph Search. In Proceedings of 18th International Conference on Automated Planning and Scheduling September 14-18, 2008, Sydney, Australia.

25. Edelsbrunner, 1987. H. Edelsbrunner. Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, vol. 10. Springer-Verlag, 1987.

26. Fortune, 1986. S. Fortune. A sweepline algorithm for Voronoi diagrams. Proceedings of the second annual symposium on Computational geometry. Yorktown Heights, New York, United States, pp.313-322. 1986.

27. Furcy and Koenig, 2005. Furcy D. and Koenig S. Scaling up WA* with commitment and diversity. In Proceedings of the International Joint Conference on Artificial Intelligence, IJCAI-05, 2005.

28. Gasching, 1979. Gasching J. Performance measurement and analysis of certain search algorithms. Ph.D. thesis, Carnegie-Mellon University. Department of Computer Science, 1979.

29. Gelperin, 1977. Gelperin D. On the optimality of A*. Artificial Intelligence 8(l):69-76, 1977.

30. Ghosh and Mount, 1991. Ghosh, S. and Mount, D., An output sensitive algorithm for computing visibility graphs // SIAM Journal on Computing, 20:888-910,1991.

31. Hart et al> 1968. Hart, P., Nilsson, N., & Raphael, B. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics (SSC), 4(2):100-107, 1968.

32. Heinz et alt 1995. Heinz B., Joseph G., David K., Werman M., Linear time Euclidean distance transform algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17:529-533, May 1995.

33. Held, 1998. M. Held, Voronoi diagrams and offset curves of curvilinear polygons // Computer-Aided Design, 30:287-300, 1998.

34. Huang and Chung, 2004. Huang, H.P. and Chung, S.Y. Dynamic visibility graph for path planning // In Proceedings of conference on Intelligent Robots and Systems, 2004 (IROS 2004), 3:2813-2818, 2004.

35. Ikeda and Imai, 1994. Ikeda T. and Imai T. Fast A* algorithms for multiple sequence alignment. In Genome Informatics Workshop, 1994.

36. Kitamura et al, 1998. Y. Kitamura, M. Yokoo, T. Miyaji, and S. Tatsumi. Multi-state commitment search. In Proceedings of 10th IEEE International Conference on Tools with Artificial Intelligence, 1998.

37. Klein and Wood, 1988. R. Klein and D. Wood. Voronoi diagrams based on general metrics in the plane, In Proc. 5th Annual Symposium on Theoretical Aspects of Computer Science (STACS '88), Berlin, 1988.

38. Koll and Kaindl, 1992. Koll A. and Kaindl H. A new approach to dynamic weighting. In Proceedings of the 10th European Conference on Arti cial Intelligence (ECAI-92), John Wiley and Sons, 1992.

39. Korf, 1985. Korf R. Depth-first iterative deepening: An optimal admissible tree search. Artificial Intelligence, 27(1):97-109, 1985.

40. Korf, 1990. Korf R. Real-time heuristic search. Artificial Intelligence, 42(2-3): 197-221, 1990.

41. Korf, 1993. Korf R. Linear-space best-first search. Artificial Intelligence, 62(l):41-78, 1993.

42. Korf, 1998. Korf R.E., Artificial intelligence search algorithms, CRC Handbook of Algorithms and Theory of Computation, M.J. Atallah (Ed.). Boca Raton, FL: CRC Press, 1998.

43. Latombe, 1991. Latombe, J., Robot Motion Planning. Kluwer Academic Publishers, 1991.

44. Lee, 1978. D. T. Lee. Proximity and reachability in the plane. PhD thesis, University of Illinois, Urbana, IL, 1978.

45. Likhachev et al, 2003. M. Likhachev, G. Gordon, and S. Tlirun. ARA*: Anytime A* with provable bounds on sub-optimality. In Proc. of Advances in Neural Information Processing Systems. MIT Press, 2003.

46. Likhachev et al, 2005a. M. Likhachev, D. Ferguson, G. Gordon, A. Stentz, S. Thrun, Anytime Dynamic A*: An Anytime, Replanning Algorithm, Proceedings of the International Conference on Automated Planning and Scheduling, ICAPS-05, 2005.

47. Likhachev et al, 2005b. M. Likhachev, Search-based planning for large dynamic environments, Ph.D. thesis, Carnegie Mellon University, 2005.

48. Liu and Arimoto, 1991. Liu, Y.H. and Arimoto, S;, Proposal of tangent graph and extended- tangent' graph for path planning of mobile robots // Próc. 1991 IEEE ICRA, 1:312-317, 1991.

49. Luger and Stubblefield, 2005. Luger G. and Stubblefield W. Artificial Intelligence: Structures and Strategies for Complex Problem Solving (5th ed.). The Benjamin/Cummings Publishing Company, Inc., 2005.

50. Mazon and Recio, 1991. M. L. Mazon and T. Recio. Voronoi diagrams based on strictly convex distances on the plane. Manuscript, Departamento De Matemáticas^ Universidad de Cantabria, Santander, España, 1991.

51. Nilsson, 1980. Nilsson N. J. Principles of Artificial Intelligence. Palo Alto, California: Tioga Publishing Company, 1980.

52. Pearl, 1984. Pearl J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984.

53. Pearl and Kim, 1982. Pearl J. and Kim,, J. Studies: in semi-admissible heuristics. IEEE Transactions on Pattern Analysis, and Machine Intelligence, PAMI-4. 1982. ' .

54. Pohl, 1970a. Pohl I. First results on the effect of error in heuristic search. Machine Intelligence, 5:219-236, 1970

55. Pohl, 1970b. Pohl I. Heuristic search viewed as pathfinding in a graph. Artificial Intelligence, l(3):193-204, 1970.

56. Pohl, 1977. Pohl I. Practical and theoretical considerations in heuristic search algorithms, Machine Intelligence 8, Elcock E. W. and Michie D. (Eds.). New York: Wiley, 1977.

57. Rabin, 2000. Rabin S. A* speed optimizations, Game Programming GemSj DeLoura M. (Ed.). Rockland, MA: Charles River Media, 2000.

58. Reese, 1999. B; Reese. AlphA*: An e-admissible Heuristic Search Algorithm. Institute for Production Technology, University of Southern Denmark 1999 -http://homel.stofanet.dk/breese/astaralpha-submitted.pdf.gz

59. Russel, 1992. Russel S. Efficient memory-bounded search method. In Proceedings of the 10th European Conference on Artifficial Intelligence, ECAI-92. 1992.

60. Russel and Norvig, 2003. Russell S. J', and Norvig P. ArtificialTntelligence: A Modern Approach. Upper Saddle River, N.J.: Prentice Hall, 2003

61. Sen and Bagchi, 1989. Sen A.K. and Bagchi A. Fast recursive formulations for best-first search- thah allow controlled use of memory. In Proceedings of International Joint Conference on Artificial Intelligence, IJCAI-89, 1989.

62. Shamos and Hoey, 1975. M. I. Shamos and D. Hoey. Closest-point problems. In Proceedings 16th IEEE Symposium on Foundations of Computer Science, 1975, pages 151-162.

63. Stentz and Likhachev, 2008. Stentz A. and Likhachev M., R* Search. Proceedings of the National1 Conference on Artificial Intelligence (AAAI), 2008.

64. Sun et al, 2007. X. Sun, M. Druzdzel, C. Yuan. Dynamic Weighting A* search-based MAP algorithm for Bayesian networks. In Proceedings of the International Joint Conference on Artificial Intelligence, IJCAI-07. 2007.

65. Vempaty et al, 1991. Vempaty N.R., Kumar V. and Korf R. Depth-first vs best-first search. In Proceedings of National Conference on Artificial Intelligence, AAAI-91, 1991

66. Wah and Shang, 1994. Wah B. and Shang Y. A comparative study of IDA*-style searches. In Proceedings of the 6th International Conference on Tools with Artificial Intelligence (ICTAI-94), IEEE Computer Society, 1994.

67. WeizI, 1985. E. Welzl. Constructing the visibility graph for n line segments in 0(n2) time. Inform. Process. Lett., 20:167-171, 1985.

68. Wong, 1991. K. Wong. An efficient implementation of Fortune's plane-sweep algorithm for Voronoi diagrams. Technical Report DCS-182-IR, Department of Computer Science, University of Victoria, Victoria, BC, Canada, October 1991.

69. Wooden, 2006. D.T. Wooden. Graph-based Path Planning for Mobile Robots, PhD thesis, Georgia Institute of Technology, 2006.

70. Yoshizumi et al, 2000. Yoshizumi T., Miura T., Ishida T. A* with partial expansion for large branching factor problems. In Proceedings of the 17th National Conference on Artificial Intelligence (AAAI-2000), AAAI/MIT Press, 2000.

71. Zhou and Hansen, 2002. R. Zhou and E. A. Hansen. Multiple sequence alignment using A*. In Proc. of the National Conference on Artificial Intelligence (AAAI), 2002.

72. Zhou and Hansen, 2007. R. Zhou and E. A. Hansen. Anytime Heuristics Search. Journal of Artificial Intelligence Research, 28 (1): 267-297, 2007.