WWW.DOC.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные документы
 

«ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ БАКАЛАВРСКАЯ РАБОТА Разработка и реализация алгоритма поиска пути для автономного транспортного средства ...»

МИНОБРНАУКИ РОССИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«НОВОСИБИРСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ» (НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ, НГУ)

Факультет информационных технологий Кафедра систем информатики Направление подготовки: 230100 ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ БАКАЛАВРСКАЯ РАБОТА

Разработка и реализация алгоритма поиска пути для автономного транспортного средства в заранее неизвестном окружении Кузаков Дмитрий Евгеньевич «К защите допущена» Научный руководитель Заведующий кафедрой, инженер-программист д. ф.-м. н., профессор ЗАО «СофтЛаб-НСК», Лаврентьев М. М./………….… Дьяков М. С./………… «……»………………2014г. «……»………………2014г.

Дата защиты: «……»………………2014г.

Автор Кузаков Д. Е./………… Новосибирск, 2014г.

МИНОБРНАУКИ РОССИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«НОВОСИБИРСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ» (НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ, НГУ)



Факультет информационных технологий Кафедра систем информатики Направление подготовки: 230100 ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА

УТВЕРЖДАЮ

Зав. кафедрой Лаврентьев М. М.

………………….

«……»……………………………20…г.

ЗАДАНИЕ

НА ВЫПУСКНУЮ КВАЛИФИКАЦИОННУЮ БАКАЛАВРСКУЮ РАБОТУ

Студенту Кузакову Дмитрию Евгеньевичу Тема: «Разработка и реализация алгоритма поиска пути для автономного транспортного средства в заранее неизвестном окружении».

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

Структурные части работы:

Реализация кинематической модели транспортного средства;

Разработка и реализация алгоритма поиска пути на заданной карте препятствий;

Разработка и реализация алгоритма решения задачи в заранее неизвестном окружении;

Проведение тестирования разрабатываемых алгоритмов.

–  –  –

Содержание

ВВЕДЕНИЕ

ГЛАВА 1 Обзор литературы

1.1 Введение

1.2 Алгоритмы обхода карты

1.2.1 Алгоритм Дейкстры

1.2.2 Алгоритм A*

1.2.3 Алгоритм LPA*

1.2.4 Алгоритм D* Lite

1.3 Алгоритмы разбиения карты

1.4 Алгоритмы карты дорог (Probabilistic Roadmap Methods, PRM)

1.4.1 Простейшие PRM-алгоритмы

1.4.2 Быстрорастущие случайные деревья (Rapidly-exploring Random Tree).......... 18 1.4.3 Expansive Space Trees

1.5 Алгоритмы потенциального поля

ГЛАВА 2 Основная часть

2.1 Постановка задачи

2.2 Поиск пути на заданной карте препятствий

2.2.1 Используемая эвристика

2.3 Общий алгоритм поиска пути

2.4 Алгоритм расчета пути на заданной карте препятствий





2.4.1 Релаксация вершины

2.5 Расчет эвристик

–  –  –

2.6 Модель движения ТС

ГЛАВА 3 Реализация

3.1 Требования

3.2 Сценарии использования программы.

3.3 Структура программы.

3.4 Структура реализации модуля поиска пути.

3.4.2 Классы поиска пути

3.4.3 Классы расчета эвристик

3.4.4 Вспомогательные классы

3.5 Тестирование

3.5.1 Тестирование производительности

3.5.2 Тестирование корректности

Заключение

Список обозначений и сокращений.

Литература

ВВЕДЕНИЕ

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

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

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

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

Так как изменение входных данных происходит постоянно по мере движения АТС, актуальность получаемого пути относительно этих данных напрямую зависит от скорости его вычисления. Это накладывает ограничения на производительность реализации алгоритма.

Был разработан и реализован алгоритм планирования пути с учетом постоянного изменения окружения и позиции ТС.

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

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

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

ГЛАВА 1 Обзор литературы

1.1 Введение В данном разделе описаны различные алгоритмы, решающие задачу поиска пути для АТС. Данная задача заключается в следующем. Даны состояния старта и финиша (см. список обозначений и сокращений), а также карта препятствий. Для алгоритмов, работающих в динамическом окружении, карта препятствий постоянно обновляется. Кроме этого, имеется некоторый алгоритм, позволяющий найти простой проезжаемый путь между состояниями АТС, находящимися близко друг к другу, не учитывающий препятствия (как правило, данный алгоритм имеет константную оценку сложности). Задача поиска пути состоит в том, чтобы, используя такой алгоритм, найти проезжаемый путь (collision-free path) для АТС из состояния старта в состояние финиша на данной карте препятствий.

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

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

1.2.1 Алгоритм Дейкстры Входные данные: взвешенный граф с неотрицательными весами ребер.

Выходные данные: кратчайший путь в данном графе.

Данный алгоритм описан в [7]. Принцип работы алгоритма заключается в следующем.

Каждой вершине графа сопоставляется метка — оценка минимальной длины пути в нее из вершины старта. Алгоритм работает пошагово — на каждом шаге он рассматривает одну вершину и пытается уменьшить метки смежных вершин. Работа алгоритма завершается, когда все вершины посещены.

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

Затем итеративно происходит следующее.

1. Если все вершины посещены, алгоритм завершается.

2. В противном случае, из ещ не посещнных вершин выбирается вершина Х, имеющая минимальную метку. Рассматриваются всевозможные маршруты, в которых она является предпоследним пунктом.

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

Время работы алгоритма Дейкстры зависит от способа хранения множества непосещенных вершин и способа обновления меток. Пусть V – количество вершин, а E — количество ребер в графе. В простейшем случае, когда для поиска вершины с минимальным значением пути просматривается все множество вершин, а для хранения этих величин используется массив, время работы алгоритма O( 2 ). Для разреженных графов (то есть таких, для которых E много меньше 2 ) непосещенные вершины можно хранить в двоичной куче, а в качестве ключа использовать значения кратчайшего пути. В этом случае временная оценка составляет ( log + log ).

–  –  –

Входные данные: взвешенный граф с неотрицательными весами ребер.

Выходные данные: кратчайший путь в данном графе.

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

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

1.1.2.1 В статье [8] описан алгоритм нахождения пути для ТС на карте препятствий, основанный на алгоритме А*. Пространство состояний представлено четырьмя измерениями (две координаты, угол поворота АТС и направление движения – вперед или назад).

Входные данные: четырехмерные состояния старта и финиша ТС, карта препятствий.

Выходные данные: проезжаемый путь на карте препятствий.

Для поиска пути используется вариация алгоритма А*, использующая в качестве эвристики сложную функцию.

Ее значение для любой клетки равняется максимуму из значений двух функций:

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

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

–  –  –

В статье [13] описаны алгоритмы решения задачи расчета кратчайшего пути в динамически изменяющемся графе: LPA* и D* Lite.

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

Выходные данные: кратчайший путь в данном графе.

Алгоритм Lifelong Planning A* (LPA*) основан на той же идее, что и алгоритм А*. Он использует две характеристики вершин. Метка вершины g – длина кратчайшего найденного пути в эту вершину. Правостороннее значение (right-hand side value, rhs) – сложная функция.

Для некоторой вершины Х она определяется как минимальное среди всех предшественников значение суммы метки и расстояния от него до Х (для вершины, соответствующей состоянию старта, оно принимается равным 0):

–  –  –

Также используется понятие устойчивой вершины. Вершина v является таковой, если выполняется равенство = ().

Как и алгоритм A* (1.2.2), LPA* использует эвристику для определения порядка рассмотрения вершин. Для данного алгоритма эта функция должна быть неотрицательна и удовлетворять неравенству треугольника: 1 1, 2 + (2 ). Вершины хранятся в очереди, сортируемой в соответствии с этой эвристикой.

Изначально значения меток и rhs всех вершин устанавливаются равными бесконечности.

Затем итеративно происходит следующее:

–  –  –

Алгоритм итерируется до тех пор, пока вершина, соответствующая состоянию финиша, не станет устойчивой. Как только это произошло, это означает, что кратчайший путь на текущей карте найден.

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

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

–  –  –

Входные данные: взвешенный граф с неотрицательными весами ребер.

Выходные данные: кратчайший путь в данном графе.

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

При этом, во время движения АТС изменения карты препятствий происходят в основном близко к текущему положению АТС.

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

Так, D* Lite является модификацией алгоритма LPA*. Он работает аналогично LPA*, но прокладывает путь в противоположном направлении, т.е от состояния финиша к состоянию старта АТС. Нужно заметить, что в этом случае вершина финиша постоянно изменяется, а значит, эвристика должна удовлетворять вышеуказанным ограничениям для каждого из ее положений.

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

Один из таких алгоритмов описан в статье [18]. В представленном алгоритме все клетки принадлежат к одному из трех типов: свободные, непроходимые и смешанные (в которых точно есть как препятствия, так и свободное от них пространство). Изначально единственная клетка – это вся карта.

Затем в цикле происходит следующее:

–  –  –

1.4.1 Простейшие PRM-алгоритмы 1.4.1.1 Алгоритмы такого типа впервые были описаны в [25] и [12].

Алгоритм состоит из двух фаз – фаза изучения карты и фаза запроса.

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

Граф итеративно заполняется следующим образом:

–  –  –

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

3. Между T и рассматриваемой вершиной графа проводится ребро, если выполнены следующие условия: между ними существует проезжаемый путь, и добавление этого ребра не приведет к появлению циклов в графе.

Это происходит до тех пор, пока количество вершин в графе не достигнет определенного значения (задается параметром). После этого граф необходимо сделать связным, добавив ребра для соединения вершин из различных компонент.

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

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

Рисунок 1 Пример неэффективной работы алгоритма: полученный граф (слева), полученный после сглаживания путь для АТС (справа сплошной) и оптимальный путь (справа пунктир).

1.4.1.2 В статье [27] предложен следующий вариант PRM-алгоритма. На этапе добавления новой вершины в граф, случайные состояния будут выбираться не во всем свободном пространстве, а на «средней линии» свободного пространства. Таким образом, алгоритм состоит из следующих частей.

1. Генерация «средней линии». Она представляет собой границу диаграммы Вороного [26] свободного пространства. Отмечается, что генерация диаграммы для всего пространства затратна, поэтому рассматривается только «средняя линия» двумерного подпространства, соответствующего координатам положения АТС в пространстве.

–  –  –

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

В связи с данной проблемой в статье [4] предложен новый способ выбора положения вершин в графе. Предлагается выбирать их случайным образом, но вероятность выбора некоторой точки карты в качестве вершины поставить в зависимость от ее близости к препятствиям. Это объясняется тем, что для поиска пути на больших свободных от препятствий участках карты достаточно относительно небольшого количества вершин, в то время как для преодоления узких проходов необходима высокая плотность расположения вершин.

1.4.1.4 Решению этой проблемы посвящена также статья [23]. Описываемый метод Small-Step Retraction состоит из двух этапов. На первом этапе происходит поиск пути в расширенном свободном пространстве (т.е в котором размеры препятствий уменьшены на определенную константную меру), что позволяет избавиться от узких проходов. На втором этапе происходит локальный пересмотр траектории в местах, где найденный путь пересекается с препятствиями в исходном пространстве.

1.4.1.5 Алгоритм под названием «Lazy Significant Edge Algorithm» (LSEA) описан в [21]. Данный алгоритм оперирует графом состояний АТС. Он состоит из следующих этапов:

–  –  –

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

1.4.2 Быстрорастущие случайные деревья (Rapidly-exploring Random Tree) 1.4.2.1 Алгоритм с их применением впервые описан в статье [15]. Его суть заключается в построении дерева путей. Изначально дерево состоит из одной точки старта.

Затем итеративно выполняется следующее:

1. Выбирается случайная точка карты;

2. Ищется вершина дерева, из которой путь до выбранной точки будет кратчайшим;

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

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

1.4.2.2 В статье [16] были предложены улучшения данного алгоритма. Для этого использовалась идея о том, чтобы строить дерево, ориентируясь на точку финиша. Таким образом, на каждой итерации построения дерева, вместо случайного состояния с некоторой вероятностью может быть взята либо точка финиша, либо случайное состояние из окрестности точки финиша, радиус которой равен расстоянию по прямой от точки финиша до ближайшей вершины дерева. Такая стратегия позволяет дереву «расти» сильнее всего в направлении финиша, а также помогает отследить момент, когда путь уже готов и осталось только соединить его с точкой финиша.

1.4.2.3 В статье [17] описан вариант двунаправленного алгоритма RRT. Одновременно запускается построение деревьев из точки старта и из точки финиша. На каждой итерации происходит следующее:

1. Одно из деревьев "растет" по вышеописанному алгоритму (1.3.2.1) в направлении случайной точки, получая новую вершину Т.

–  –  –

1.4.2.4 В статье [24] было предложено улучшение двунаправленного алгоритма RRT для решения следующей проблемы. Проверка наличия препятствий между двумя состояниями обычно занимает много времени. При этом проверка состояния на допустимость выполняется быстро, а вероятность того, что путь между двумя близкими друг к другу допустимыми состояниями пересечет препятствие, мала.

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

1.4.2.5 В статье [5] были придуманы улучшения для алгоритма RRT (т.н. Extended RRT) для решения задачи в динамическом окружении. Основная идея заключается в том, что обычно различия карты между двумя соседними запусками алгоритма невелики. Поэтому точки дерева на каждом запуске алгоритма сохраняются, создавая так называемый «кэш точек пути». Во время следующего запуска алгоритма, на каждой итерации достроения дерева вместо взятия случайной точки карты с некоторой вероятностью может быть взята точка из кэша.

1.4.3 Expansive Space Trees Алгоритмы с использованием деревьев этого типа оценивают полезность добавления некоторого состояния в граф с точки зрения заполнения свободного пространства.

Полезность состояния определяет вероятность, с которой оно будет добавлено в граф.

1.4.3.1 Алгоритм использующий данный тип деревьев, описан в статье [10]. Алгоритм состоит из двух фаз, выполняемых итеративно:

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

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

1.4.3.2 Позже этот алгоритм был модифицирован для поиска пути для робота, двигающегося по модели Рида-Шеппа [22] в статье [11]. Новая проблема, связанная с используемой моделью движения, заключается в том, что не в каждую точку пространства можно попасть абсолютно точно. В связи с этим вводится понятие конечной области – области, состояния из которой считаются подходящими для финиша. В связи с этим алгоритм не является двунаправленным и строит только одно дерево из состояния старта. Условием завершения алгоритма является достижение любого состояния из конечной области.

1.4.3.3 В статье [6] предложен двунаправленный алгоритм исследования пространства с помощью EST-деревьев. На каждой итерации построения происходит следующее:

–  –  –

1,2,…) – векторы направлений, выбранных на предыдущих итерациях.

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

4. Предпринимается попытка соединения деревьев. Для этого используется вершина, выбранная в пункте 1. Для нее выбирается направление движения, ведущее к ближайшей вершине другого дерева. Затем выбирается расстояние шага аналогично пункту 3, и таким образом, либо деревья соединяются полученным ребром, либо в дерево добавляется новая вершина.

Алгоритм завершается, когда произошло соединение деревьев.

1.5 Алгоритмы потенциального поля Алгоритмы данного типа оперируют заданным в пространстве состояний потенциальным полем – множеством векторов, сопоставленных состояниям. Каждый из данных векторов указывает наиболее выгодное направление движения из соответствующего состояния. На основе данного поля производится поиск пути.

Яркий пример алгоритма такого типа описан в [2].

Потенциальное поле в данном алгоритме строится с помощью построения диаграммы Вороного [26] относительно препятствий. Для каждого состояния вектор потенциального поля складывается из двух слагаемых. Первое слагаемое – вектор, направленный к рассматриваемому состоянию от ближайшего препятствия. Второе слагаемое – вектор, направленный из состояния старта в состояние финиша.

Путь по построенному полю находится следующим образом:

Находятся состояния, соответствующие локальным минимумам поля. Эти состояния складываются в непрерывные кривые.

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

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

–  –  –

2.1 Постановка задачи Цель данной работы – решение задачи поиска пути для АТС в заранее неизвестном окружении. Для достижения данной цели были поставлены следующие задачи:

–  –  –

2.2 Поиск пути на заданной карте препятствий Наиболее крупной подзадачей является нахождение пути для АТС на заданной карте препятствий. Для этой подзадачи пространство состояний АТС представлено четырехмерными состояниями, включающими в себя:

–  –  –

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

Информация о направлении движения АТС учитывается при подсчете значения веса найденного пути. Для этого используются штрафы, увеличивающие стоимость движения задним ходом.

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

–  –  –

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

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

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

2.2.1 Используемая эвристика В качестве эвристики используется сложная функция. Ее значение для любой вершины равняется максимуму из значений двух функций:

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

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

Значения эвристики подсчитываются соответственно клеткам пространства состояний и хранятся в соответствии с ними.

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

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

Кроме того, путь для АТС становится более устойчивым.

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

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

2.3 Общий алгоритм поиска пути Текущая реализация общего алгоритма поиска пути итеративно вычисляет путь для каждого полученного набора входных данных. Каждой итерации необходима информация о текущем положении АТС, состоянии финиша, карте препятствий и последний найденный путь (ПНП). Итерация алгоритма состоит из следующих частей (Рисунок 3):

Получение данных о текущих положении АТС и карте препятствий от программы управления АТС.

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

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

В противном случае производится проверка наличия следующих изменений:

–  –  –

Если ни одно из данных изменений не обнаружено, то ПНП является искомым путем для АТС.

В противном случае, производится расчет эвристики(а) и рассчитывается новый путь с использованием информации о ПНП.

Найденный путь передается программе управления АТС.

Рисунок 3 Общий алгоритм поиска пути

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

Изначально очередь содержит только состояние старта ТС.

Итеративно выполняются следующие действия (Рисунок 4):

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

–  –  –

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

2.4.1 Релаксация вершины При релаксации вершины рассматриваются все достижимые из нее вершины. Для этого производится попытка проезда (см. 2.6) из соответствующего ей состояния в трех направлениях: не меняя направления движения, с поворотом налево при максимальном угле поворота и с поворотом направо. Для каждого из полученных состояний выполняются следующие действия (Рисунок 5):

–  –  –

Полученное значение сравнивается с текущим значением кратчайшего пути в клетку, соответствующую рассматриваемой вершине.

–  –  –

Эта вершина добавляется в очередь, если она не была добавлена туда ранее.

2.5 Расчет эвристик Для расчета значений используемых эвристик применяется алгоритм Дейкстры (Dijkstra 1959). Алгоритм Дейкстры аналогичен алгоритму А*, но использует другой способ определения приоритета вершины. А именно, релаксация вершин происходит в порядке убывания значения текущей оценки на кратчайший путь (см. 1.2.1).

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

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

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

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

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

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

Этот алгоритм рассматривает каждую вершину не единожды, а до тех пор, пока происходит улучшение длины кратчайшего пути.

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

Алгоритм Беллмана-Форда [3].

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

–  –  –

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

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

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

Для каждого из этих способов возможно как движение вперед, так и в режиме заднего хода. Нужно заметить, что движение АТС в этих случаях различается между собой. При движении вперед рассчитываемая траектория описывает движение точек задней оси АТС, а при движении задним ходом – передней.

–  –  –

где x, y – текущие координаты ТС в пространстве, – текущий угол поворота, – скорость движения, – угол поворота переднего колеса, L – расстояние между осями колес. Данные формулы взяты из книги [14].

–  –  –

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

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

Важна производительность реализации. Этим обусловлен выбор в качестве языка программирования C++.

Функциональные и нефункциональные требования приведены в таблицах (Таблица 2, Таблица 3).

Таблица 2 Функциональные требования № Описание Программа должна поддерживать размеры карты препятствий до 1000x1000 клеток.

Программа должна поддерживать любые размеры АТС, не превышающие размера карты.

Входные данные: текущее положение АТС, карта препятствий, состояние финиша, размеры карты препятствий и размеры АТС должны подаваться программе в виде входных параметров.

Результатом работы программы должен быть проезжаемый путь для АТС.

Таблица 3 Нефункциональные требования № Описание Программа должна работать с произвольной предоставленной извне кинематической моделью АТС.

Программа должна работать с произвольной предоставленной извне функцией проверки столкновения АТС с препятствиями.

Программа должна быть реализована с использованием языка программирования C++.

Среднее время подсчета не должно превышать 0.2 секунды на карте размера 100x100.* Максимальное время подсчета не должно превышать 1 секунды на карте размера 100x100.

*Время указано для ПК с параметрами, описанными в разделе Тестирование (3.5).

3.2 Сценарии использования программы.

Реализованная программа может использоваться двумя видами актеров (в терминах UML) – внешними приложениями и сторонними разработчиками.

Основной сценарий использования программы для внешнего приложения (Рисунок 8)

– выполнение поиска пути. До его выполнения программа должна получить исходные данные. Для этого предоставлены следующие сценарии использования: Задать параметры АТС (максимальный угол поворота колеса, скорость движения, расстояние между осями колес, расстояния от центра АТС до осей) и задать исходные данные задачи (карта препятствий, состояния старта и финиша).

Рисунок 8 Сценарии использования программы для внешнего приложения

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

–  –  –

Модуль поиска пути. Выполняет все функции, связанные с нахождением пути.

Модуль тестирования.

Содержит функции для тестирования реализованной функциональности, в том числе:

1) тестирование корректности и производительности реализации алгоритма поиска пути;

2) тестирование корректности и производительности вычисления траектории движения АТС;

3) тестирование реализации алгоритма проверки АТС на карте препятствий;

4) тестирование корректности и производительности подсчета значений эвристики.

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

–  –  –

Point – предназначен для хранения четырехмерного состояния с целочисленными значениями координат.

RealPoint – предназначен для хранения четырехмерного состояния с вещественными значениями координат.

–  –  –

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

Map хранит карту препятствий. Содержит высоту и ширину карты, а также массив объектов типа Obstacle, соответствующий набору препятствий карты.

–  –  –

Диаграмма классов данной части представлена на рисунке (Рисунок 13).

Класс AStarComparator является вспомогательным для класса расчета пути. Он предоставляет функцию сравнения приоритета двух объектов HeuristicDistancePoint.

–  –  –

ComputeController производит поиск пути на изменяющейся карте препятствий. При обновлении данных (карты препятствий и текущего положения АТС) данный класс определяет отличие новой карты от предыдущей, а также проверяет нахождение текущего положение на рассчитанном ранее пути.

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

–  –  –

DistanceComputer - класс, осуществляющий расчет эвристик. (см. 2.5) 3.4.4 Вспомогательные классы Диаграмма классов данной части представлена на рисунке (Рисунок 15).

ConfigurationContainer – класс, считывающий параметры алгоритма из файла.json.

–  –  –

Для тестирования производительности алгоритма использовался ЭВМ на базе процессора Intel Xeon X5660 с тактовой частотой 2.8 ГГц и объемом оперативной памяти 8 Гб. Использовались карты препятствий различного размера до 100x100 клеток. Препятствия для карт генерировались случайным образом.

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

Параметры АТС были взяты с прототипа реального автомобиля и имеют следующие значения (Таблица 4):

–  –  –

Тестирование производительности выполнялось на картах разного размера и с различным количеством препятствий. Ниже приведено среднее время выполнения итерации описанной реализации алгоритма (Таблица 5). Также было измерено среднее время выполнения итерации алгоритма без использования информации о последнем посчитанном пути (Таблица 6) и произведено сравнение результатов измерений (Таблица 7).

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

–  –  –

3.5.2 Тестирование корректности Также произведено тестирование корректности как алгоритма поиска пути в неизвестном окружении, так и алгоритма поиска на заданной карте препятствий.

Для тестирования алгоритма поиска пути на заданной карте препятствий создан набор тестовых карт, позволяющих отследить работу алгоритма в определенных случаях. Кроме проверки корректности работы алгоритма, это позволяет выявить особенности движения АТС в определенных ситуациях (Рисунок 16, Рисунок 17, Рисунок 18).

Рисунок 16 Слева направо: путь для АТС размера 1x2 клетки без возможности заднего хода, размера 2x4 клетки без возможности заднего хода, размера 2x4 клетки с возможностью заднего хода.

Зеленым цветом выделена точка старта, красным – точка финиша. Синие точки обозначают движение вперед, оранжевые – задним ходом.

Для тестирования алгоритма поиска пути в условиях неизвестного окружения используется симулятор автомобиля в виртуальном пространстве (Рисунок 19), а также экспериментальный образец автомобиля.

–  –  –

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

–  –  –

Разработан и реализован алгоритм поиска пути для автономного транспортного средства в неизвестном окружении, а именно:

1. Реализована кинематическая модель автомобиля с двумя колесными осями.

Траектория движения АТС рассчитывается на основе физических параметров АТС. Рассматриваются различные варианты движения АТС: по прямой, с поворотом вправо или влево, также для каждого из этих вариантов рассчитывается движение задним и передним ходом.

2. Разработан и реализован алгоритм поиска пути на заданной карте препятствий.

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

3. Разработан и реализован алгоритм решения задачи поиска пути в заранее неизвестном окружении.

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

4. Реализована система тестирования описанных алгоритмов в виртуальном пространстве и проведена апробация реализованного подхода на экспериментальном образце роботизированного ТС в реальном окружении.

Использование при вычислении пути информации о предыдущих расчетах значительно уменьшило время работы разработанной системы (в среднем более чем в 10 раз на использованном наборе тестовых данных), что позволило достичь требуемой производительности.

–  –  –

АТС – автономное транспортное средство.

Состояние – набор свойств АТС, отражающий его характеристики, изменяющиеся при движении (например, положение в пространстве, ориентацию и др.).

Возможное (допустимое) состояние – состояние, при нахождении в котором АТС не сталкивается с препятствиями.

Свободное пространство – множество всех возможных состояний.

Путь АТС – набор состояний, задающий траекторию движения АТС из одного состояния в другое.

Проезжаемый путь – путь, содержащий только возможные состояния.

Состояние старта – исходное состояние АТС.

Состояние финиша – конечное состояние АТС.

–  –  –

1. Akinc M., Bekris K.E., Chen B.Y., Ladd A.M., Plaku E., Kavraki L.E. Probabilistic roadmaps of trees for parallel computation of multiple query roadmaps // International Symposium on Robotics Research, ser. Springer Tracts in Advanced Robotics (STAR). – 2003.

2. Barraquand J., Latombe J.-C., Robot Motion Planning: A Distributed Representation Approach // The International Journal of Robotics Research. – 1991. – V. 10. – №6. – P. 628-649.

3. Bellman R. On a routing problem // Quarterly of Applied Mathematics. – 1958. – №16. – P.

87-90.

4. Boor V., Overmars M.H., Stappen A.F. The Gaussian sampling strategy for probabilistic roadmap planners // IEEE International Conference on Robotics and Automation. – 1999. – V. 1. – P. 473-479..

5. Bruce J., Veloso M. Real-time randomized path planning for robot navigation // Robocup 2002: Robot Soccer World Cup VI, Lecture Notes in Computer Science, Springer. – 2003. – V. 2752. – P. 288-295.

6. Burns B., Brock O. Single-query motion planning with moving obstacles // IEEE International Conference on Robotics and Automation. – 2007. – P. 3307-3312

7. Dijkstra E.W. A note on two problems in connexion with graphs // Numerische Mathematik.

– 1959. – №1. – P. 269-271.

8. Dolgov D., Thrun S., Montemerlo M., Diebel J. Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments // The International Journal of Robotics Research.

– 2010. – №29. – P. 485-501.

9. Hart P.E., Nilsson N.J., Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths // Systems Science and Cybernetics, IEEE Transactions 1968. – V. 4. – issue 2. – P. 100-107.

10. Hsu D., Kindel R., Latombe J.-C., Rock S. Randomized kinodynamic motion planning with moving obstacles // International Journal of Robotics Research. – 2002. – V. 21. – №3. – P.

233-255.

11. Hsu D., Sanchez G., Sun Z. Hybrid PRM sampling with a cost-sensitive adaptive strategy // IEEE Interantional Conference on Robotics and Automation. – 2005. – P. 3885-3891.

12. Kavraki L.E., Svestka P., Latombe J.-C., Overmars M.H. Probabilistic roadmaps for path planning in high-dimensional configuration spaces // IEEE Transactions on Robotics and Automation. – 1996. – V. 12. – №4. – P. 566-580.

13. Koenig S., Likhachev M. D* Lite // AAAI/IAAI. – 2004. – V. 25. – №2. – P. 99–112.

14. LaValle S.M. Planning algorithms / Cambridge University Press. – University of Illinois. – 2006. – 786 p.

15. LaValle S.M. Rapidly-exploring random trees: A new tool for path planning. Technical report / Iowa State University. – 1998. – 4 p.

16. LaValle S.M., Kuffner J.J. Randomized Kinodynamic Planning // IEEE International Conference on Robotics and Automation. – 1999. – V. 1. – P. 473-479.

17. Lie T.-Y., Shie Y.-C. An incremental approach to motion planning with roadmap management // IEEE International Conference on Robotics and Automation. – 2002. – V. 4.

– P. 3411-3416.

18. Lingelbach F. Path planning using probabilistic cell decomposition. Monograph / Royal Institute of Technology. – 2005. – 73 p.

19. Morales M., Rodriguez S., Amato N. Improving the connectivity of PRM roadmaps // IEEE International Conference on Robotics and Automation. – 2003. – P. 4427-4432.

20. Plaku E., Bekris K.E., Chen B.Y., Ladd A.M., Kavraki L.E. Sampling-based roadmap of trees for parallel motion planning // IEEE Transactions on Robotics. – 2005. – V. 21. – №4.

– P. 597-608.

21. Polden J., Pan Z., Larkin N., Van Duin S. Path Planning with a Lazy Significant Edge Algorithm (LSEA) // International Journal of Advanced Robotic Systems. – 2013. – V. 10. – P. 1-8.

22. Reeds J.A., Shepp L.A. Optimal paths for a car that goes both forwards and backwards // Pacific Journal of Mathematics. – 1990. – V. 145. – №2. – P. 367-393.

23. Schwarzer F., Saha M., Latombe J.-C. Adaptive Dynamic Collision Checking for Single and Multiple Articulated Robots in Complex Environments // IEEE Transactions on Robotics. – 2005. – P. 338-353.

24. Sanchez G., Latombe J.-C. On delaying collision checking in PRM planning: Application to multi-robot coordination // International Journal of Robotics Research. – 2002. – V. 21. – №1. – P. 5-26.

25. Svestka P. A probabilistic approach to motion planning for car-like robots. Technical Report / Department of Information and Computing Sciences, Utrecht University. – 1993. – 93 p.

26. Voronoi G. Nouvelles applications des paramtres continus la thorie des formes quadratiques. Deuxime mmoire. Recherches sur les parallllodres primitifs // Journal fr die reine und angewandte Mathematik. – 1908. – V. 134. – P. 198-287.

27. Wilmarth S. A., Amato N. M., Stiller P. F. MAPRM: A probabilistic roadmap planner with sampling on the medial axis of the free space // IEEE International Conference on Robotics and Automation. – 1999. – P. 1024-1031.



Похожие работы:

«1 1.ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Программа разработана на основе составлена на основе программы "Подготовка к ЕГЭ по физике (общеобразовательные классы)" 2007г., авторы: Е.Н.Бурцева, доцент кафедры физико-математических дисциплин и информатики ККИДППО, Л.Н.Тернова...»

«Новые Продукты MDU коллективного пользования SFU индивидуального пользования Profiler Программируемый фильтр усилитель Настоящая программируемая многоканальная головная станция усиливает, фильтрует и выравнивает цифровые и аналоговые сигналы для установок коллективных телевизионных приёмов (MATV). Технология ана...»

«Санкт-Петербургский Государственный Университет Т.М. Петрова, Н.А. Позднякова, Ю.В. Соколова Методическое руководство для практических занятий по дисциплине "Аэрокосмические методы исследований" (для студ...»

«МИНОБРНАУКИ РОССИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ "САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ АКАДЕМИКА С.П.КОРОЛЕВА (НАЦИОНАЛЬНЫЙ...»

«Российская академия наук Сибирское отделение Институт систем информатики им. А. П. Ершова Л.В. Городняя ПАРАДИГМЫ ПРОГРАММИРОВАНИЯ Часть 2 Языки низкого уровня Препринт Новосибирск 2015 Препринт является второй частью серии "Парадигмы программирования", посвященн...»

«ОБЩЕЕ РУКОВОДСТВО К ИНТЕРПРЕТАЦИИ РИСУНКОВ. Существует ряд общих положений, которые необходимо учитывать в процессе интерпретации рисунков. Главным является то, что рисует испытуемый в рамках заданной или на свободную тему, как он это делает (эмоции, комментарии, действия, их...»

«Московский государственный университет печати имени Ивана Фёдорова Кафедра медиасистем и технологий Анна Юрьевна Филиппович ВЕНЗЕЛЬ, ЭКСЛИБРИС Лекции по дисциплине ИСКУССТВО ШРИФТА Для студентов, осваивающих...»

«1. Цели освоения дисциплины Целью освоения дисциплины "Архитектура и принципы интеграции корпоративных информационных систем" является освоение современных подходов и технологий создания и интеграци...»

«R MODULRN PROGRAMOVATELN AUTOMATY ПРОГРАММИРУЕМЫЕ КОНТРОЛЛЕРЫ TECOМАT TC700 Содержание ПРОГРАММИРУЕМЫЕ КОНТРОЛЛЕРЫ TECOМАT TC700 15-е издание август 2008г. СОДЕРЖАНИЕ 1. ОЗНАКОМЛЕНИЕ С ПРОГРАММИРУЕМЫМИ КОНТРОЛЛЕРАМИ "TECOМАT TC700" 1.1....»

«Методика дистанционного обучения Термин "программирование" обычно связывают с составлением программ для компьютеров, хотя это понятие использовалось давно до появления вычислительн...»

«,ФЕДЕРАЛЬНОЕ АГЕНТСВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования Тихоокеанский государственный университет УТВЕРЖДАЮ Проректор по учебной работе С.В. Шалобанов ""_200г. ПРОГРАММА ДИСЦИПЛИНЫ по кафедре Прикладная математика и информа...»








 
2017 www.doc.knigi-x.ru - «Бесплатная электронная библиотека - различные документы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.