Р
Оптимальное и Эффективное Планирование Пути для частично-известных окружении
Anthony Stentz
The Robotics Institute; Carnegie Mellon University; Pittsburgh, PA 15213
еферат
Задача планирования траекторий для подвижного робота получила значительное внимание в исследовательской литературе. Большинство работ принимает, что робот имеет полную и точную модель среды прежде, чем это начинает двигаться; меньшее количество внимания было уделено проблеме частично известного окружения. Это ситуация возникает для зондирующего робота или того, который должен двигаться к конечное расположение без карты ландшафта. Существующие подходы планируют начальный путь, основанный на известной информации и затем изменяют план локально или повторно планируют весь путь, поскольку робот обнаруживает препятствия с помощью датчиков, жертвуя оптимальностью или вычислительной эффективностью соответственно. Эта бумага представляет новый алгоритм, D*, способный к планированию путей в неизвестном, частично известном, и в измененяющемся окружении эффективным, оптимальным, и полным способом.
1.0 Введение
Исследовательская литература адресовала экстенсивно движение, планирующее проблему для одного или большее количество роботов, перемещающихся через поле препятствий к цели. Большинство этой работы принимает, что среда полностью известна прежде, чем робот начинает движение (см. Latombe [4] для хорошего обзора(осмотра)). Оптимальные алгоритмы в этой литературе ищут пространство состояний (например, граф видимости, ячейки сетки) используя трансформацию дистанций [2] или эвристику [8], чтобы найти самый близкий путь от состояния начала робота до цели. Стоимость пути может быть определена, чтобы быть расстоянием путешествия, израсходованная энергия, время подвергало опасности, и т.д.
К сожалению, робот не может иметь частичной или никакой информации относительно среды прежде, чем это начинает, чтобы пересечь, но оборудовано датчиком, который является способным к измерению среды, поскольку это перемещается. Один подход к планированию пути в этом сценарии должен генерировать "глобальный" путь, используя известную информацию и затем пытаться "локально" обходить препятствия на маршруте, обнаруженном [1] датчиками. Если маршрут полностью затруднен, новый глобальный путь запланирован. Lumelsky [7] первоначально принимает, что среда будет лишенным из препятствий и перемещает робот непосредственно к цели. Если препятствие затрудняет путь, шаги робота вокруг периметра до отметки на препятствии самый близкий, цель найдена. Робот затем продолжает двигаться непосредственно к цели снова. Pirzadeh [9] утверждает что принимая эту стратегию, тем самым робот блуждает относительно среды, пока это не обнаруживает цель. Робот неоднократно перемещается в смежное расположение с самой низкой стоимостью и увеличивает стоимость пути, каждый раз посещает эти расположения, это, чтобы оштрафовать позже пересекает того же самого пространство. Korf [3] использует начальная информация карты, чтобы оценить стоимость к цели для каждого состояния и эффективно модифицирует это с издержками перебора с возвратами как шаги робота через среду.
В то время как эти подходы полны, они также неоптимальны в смысле, что они не генерируют самый короткий данный путь по стоимости от информации с датчика, поскольку считается что начальная информация правильна и неизмена. Это возможно для того чтобы сгенерировать оптимальное поведение, вычисляя оптимальный путь из известной информации карты, перемещая робот по пути, до тех пор пока не достигает цели, или датчики обнаруживают расхождение между картой и окружением, модифицируя карту, и затем повторно планируя новый оптимальный путь от текущего расположения робота до цели. Хотя этот подход "в лоб", но такой подход оптимален, хотя это может быть чрезвычайно неэффективно, особенно в обширных средах, где цель - далеко и немного существует информации об карте. Zeiinsky [15] увеличил эффективность, используя дерево квадрантов [13], чтобы представить свободное и с препятствием пространство, таким образом уменьшая число состояний для поиска в пространстве. Для естественного ландшафта, однако, карта может содержать разные проходимости в каждом расположении, располагающемся по пространству, таким образом делая деревья квадрантов, несоответствующие или неоптимальные.
Эта бумага представляет новый алгоритм для производства оптимальных путей для робота, действующего с датчиком и картой окружения. Карта может быть полной, пустой, или содержать частичную информацию относительно окружения. Для регионов окружения, которые являются неизвестными, карта, могут содержать приблизительные информационные, вероятностные модели для размещения, или даже эвристические оценки. Алгоритм - функционально эквивалент, оптимальному перепланировщику "в лоб", но это гораздо более эффективен.
Алгоритм сформулирован в терминах оптимальной проблемы нахождения пути внутри направленного графа, где дуги помечены значениями стоимости, которые могут располагаться над континуумом. Датчик робота способен измерить стоимости дуги около робота, и известные и оцененные значения дуги включают карту. Таким образом, алгоритм может использоваться для любого представления планирования, включая графы видимости [5] и структуры ячейки сетки. Бумага описывает алгоритм, иллюстрирует операцию, представляет неофициальные доказательства soundness, оптимальности, и законченности, и затем заканчивается с эмпирическим сравнением алгоритма оптимальному перепланировщику.
2.0 D* Алгоритм
Имя алгоритма, D *, было выбрано, потому что это походит На A* [8], за исключением того, что это динамически в смысле, который параметры стоимости дуги могут изменяться в течение процесса решения задач. Если движение робота правильно соединено с алгоритмом, D* генерирует оптимальные траектории. Этот раздел начинается с определений и нотации, используемой в алгоритме, представляет D* алгоритм, и закрывается иллюстрацией его.
2.1 Определения
Цель планировщика пути состоит в том чтобы переместить робот из некоторого расположения в мире к расположению цели, такой, чтобы избегать всех препятствий и минимизирует положительный показатель стоимости (например, длина пути). Пространство состояний может быть сформулировано как набор состояний, обозначающих расположение робота соединенных направленными дугами, каждая из которых имеет связанную стоимость. Робот стартует в специфическом состоянии и движется вдоль дуг (подвергающийся стоимостью обхода) к другим состояниям, пока не достигает состояния в цели, обозначенного G. Каждое состояние X за исключением G имеет backpointer ( указатель возврата ) к следующему состоянию Y обозначенным b (X) = Y. D*, использует backpointers, чтобы проложить пути к цели. Стоимость прохождения дуги из состояния Y, в состояние X имеет положительное значение получающиеся с помощью функции стоимости дуги c(X, Y). Если Y не имеет дуги к X, то c (X, Y) не определена. Два состояния X и Y являются соседями в пространстве, если c (X, Y) или c (Y, X) определены.
Подобно A*, D* содержит OPEN список состояний. Список OPEN используется, чтобы распространить информацию о изменениях для функции стоимости дуги и чтобы вычислять стоимость пути по состояниям в прострастве. Каждое состояние X имело бы связанный тэг t(X), такой что t(X) = NEW, если X никогда не был в списке OPEN, t(X) = OPEN, если X в настоящее время в списке OPEN, и t (X) = CLOSED, если X - больше не в списке OPEN. Для каждого состояния X, D* поддерживает оценку суммы стоимости дуги от X до G, данного функцией стоимости пути h (G, X). При соответствующих условиях, эта оценка эквивалентна оптимальной (минимальной) стоимости из состояния X к G, данному неявной функцией o (G, X). Для каждого состояния X в списке OPEN (то есть, t (X) = OPEN ), ключевая функция, k (G, X), определена, чтобы быть равной минимуму h (G, X) прежде, чем изменение и все значения, принятые h (G, X) с тех пор X было помещено в список OPEN. Ключевая функция классифицирует состояние X в списке OPEN в одном из двух типов: поднимающееся состояние RAISE, если k (G, X) < h (G, X), и низкое состояние LOWER, если k (G, X) = h (G, X). D* использует состояния RAISE в списке OPEN, чтобы распространить информацию о увеличений стоимости пути (например, из-за увеличиваемой стоимости дуги) и состояния LOWER, чтобы распространить информацию относительно уменьшений стоимости пути (например, из-за уменьшенной стоимости дуги или нового пути к цели). Распространение происходит в пространстве через повторяющееся удаление состояний из списка OPEN. Каждый раз состояние удаляется из списка, это расширяется, чтобы передать изменения стоимости для соседей. Эти соседи по очереди помещены в список OPEN , чтобы продолжить процесс.
Состояния в списке OPEN сортируются по значениям ключевой функции. Параметр kmin определен, чтобы быть минимумом min(k(X)) для всех X таких, что t(X) = OPEN. Параметр kmin представляет важный порог в D*: путь стоящий меньше чем, или равно kmin оптимален, и больше чем kmin не может быть оптимальным. Параметр kold определен, чтобы быть равным kmin до самого нового удаления состояния из списка OPEN. Если никакие состояния не были удалены, kold неопределен..
Упорядоченые состояния, обозначаются {X1,XN} определены, чтобы быть последовательностью если b(Xi+1)=Xi для всех i такой что 1 <= i < N и Xi!=Xj для всех (i,j) таких что l <= i < j <= N. Таким образом, последовательность определяет путь backpointers из XN до X1. Последовательность {X1,XN} определена, чтобы быть монотонной, если (t(Xi) = CLOSED и h(G, Xi) < h(G, Xi+1)) или (t(Xi) = OPEN и k(G,Xi) < h (G, Xi+1)) для всех i таких что 1 <= i < N. D* создает и поддерживает монотонную последовательность {G, X}, представляя уменьшение текущих или ниже-ограниченных издержек пути, для каждого состояния X, который является или был в списке OPEN. В данной последовательности состояний {X1,XN}, состояние Xi - предок состояния Xj если 1 <= i < j <= N и потомок Xj если l <= j < i <= N.
Для всех двух-состояний функций, включающих состояние в цели, следующая запись стенографии используется: f(X)=f(G,X). Аналогично, для последовательностей запись {X} = {G, X} используется. Запись f(o) используется, чтобы обратиться к функции, независящей от области.
2.2 Описание Алгоритма
D* алгоритм состоит из двух основных функций: PROCESS - STATE ( состояние - процесс ) и MODIFY - COST (модификация -стоимость). PROCESS - STATE используется, чтобы вычислить оптимальные издержки пути к цели, и MODIFY - COST - используется, чтобы заменить функции стоимости дуги с(o) и вводить воздействия на состояния в списке OPEN. Первоначально, t(o) установливает все состояний в NEW, h (G) установлена в нуль, и G помещено в список OPEN. Первая функция, PROCESS - STATE, не неоднократно вызывается до тех пор пока состояние робота, X, удалено из списка OPEN (то есть, t (X) = CLOSED) или значение -1 возвращено, в котором отметка или последовательность {X} была вычислена или не существует соответственно. Робот затем продолжает не следовать за backpointers в последовательности {X} пока происходит это или он достигает цели или обнаруживает, что ошибка в функции стоимости дуги c(o) (например, из-за обнаруженного препятствия). Вторая функция, MODIFY - COST, немедленно называется для корректировки c(o), и воздействия на состояния в списке OPEN. Пусть Y, будет состояние робота, в котором обнаружина ошибка в c(o). Вызывая PROCESS - STATE, до тех пока она не возвращает kmin >= h (Y), изменения стоимости распространяются, чтобы установить Y такой что h(Y) = o (Y). В этой отметке, возможно новая последовательность {Y} была создана, и робот продолжает следовать за backpointers в последовательности к цели.
Алгоритмы PROCESS - STATE и MODIFY - COST представлены ниже. Внедренные подпрограммы MIN - STATE ( минимум - состояние ), которое возвращает состояние в списке OPEN с минимумом значение k (o) (NULL, если список пуст); GET - KMIN, который возвращает kmin для списка OPEN (-1, если список пуст); DELETE (X), который удаляет состояние X из списка OPEN и устанавливает t (X) = CLOSED; и INSERT (X, hnew), который вычисляет k (X) = hnew если t (X) = NEW, k (X) = min (k (X), hnew) если t (X) = OPEN, и k (X) = min (h (X), hnew), если t (X) = CLOSED, устанавливает h (X) = hnew и t (X) = OPEN, и помещает или заново позиционирует состояние X в списке OPEN, сортируемом при помощи k (o).
В функции PROCESS - STATE в строках LI - L3, состояние X с самым низким значением k (o) удалено из списка OPEN. Если X - LOWER состояние (то есть, k (X) = h (X)), стоимость пути оптимальна, так как h (X) равен старому kmin. В строках L8 - L13, каждый сосед Y к X исследован, чтобы видеть, может ли стоимость пути быть понижена. Дополнительно, состояние соседа, которое NEW, получают начальное значение стоимости пути, и изменяют стоимость, распространяются каждому соседу Y который имеет backpointer к X, независимо от того, является ли новая стоимость большей чем или меньше чем старая. Так как эти состояния - потомки X, любое изменение для стоимости пути X воздействует на их издержки пути также. Backpointer Y переназначен (если необходимо) так, чтобы монотонная последовательность {Y} была создана. Все соседи, которые получают новую стоимость пути, помещены в список OPEN, так, чтобы они распространили изменения стоимости для их соседей.
Если X в состояние RAISE, стоимость пути не может быть оптимальна. Прежде X распространяет изменения стоимости для соседей, оптимальные соседи исследованы в строках L4 - L7, чтобы видеть, может ли h (X) быть уменьшен. В строках L15 - L18, изменения стоимости распространяются к новым состояниям и непосредственным потомкам таким же образом что касается LOWER состояний. Если X способен к уменьшить стоимость пути состояния, но X не непосредственный потомок (строки L20 и L21), X помещен обратно на списке OPEN для будущего расширения. Это показывает в следующем разделе, что это действие требуется, чтобы избежать создавать петлю в backpointers. Если стоимость пути X способна быть уменьшенной подоптимальным соседом (строки L23 через L25), сосед помещен обратно на списке OPEN. Таким образом, модификация "отложена", пока сосед не имеет оптимальную стоимость пути.
Function: PROCESS-STATE ()
LI X = MIN- STATE ()
L2 ifX = NULL then return –I
L3 k^ = GET-KMIN( ); DELETE(X)
L4 if k^ < h(X) then
L5 for each neighbor Y of X:
L6 if h(Y) < k^ and h(X) > h(Y) + c(Y, X) then
L7 b(X) = Y-, h(X) = h(Y)+c(Y, X)
L8 if k^ = h(X) then
L9 for each neighbor Y of X:
LIO i{t(Y)=NEWor
Lll (b(Y) = X and h(Y) ^ h(X) + c(X, Y)) 'or
L12 (b(Y)^X and /i(r)>/i(X)+ c(X, Y)) then
L13 b(Y) = X-, INSERT(Y, h(X) + c(X, Y))
L14 else
L15 for each neighbor Y of X:
L16 ift(Y)=NEWor
LI 7 (b(Y) = X and h(Y) ^ h(X) + c(X, Y) ) then
L18 b(Y) = X-, INSERT(Y, h(X) + c(X, Y))
L19 else
L20 if b(Y) * X and h(Y) > /i(X) + c(X, Y) then
L21 INSERT(X, h(X))
L22 else
L23 if b(Y) -t X and /i(X) > h(Y) + c(Y, X) and
L24 t(Y) = CLOSED and /i(Y) > k^ then
L25 INSERT(Y, h(Y))
L26 return GET-KMIN( )
В функции MODIFY - COST, функция стоимости дуги обновляется с измененным значением. Так как стоимость пути для состояния Y изменится, X помещен в список OPEN. Когда X расширен через PROCESS-STATE, это вычисляет новый h (Y) = h (X) + c (X, Y) и помещает Y в список OPEN. Дополнительные расширения состояния распространяют стоимость потомкам Y.
Function: MODIFY-COST (X, Y, cval)
LI c(X, Y) = cval
L2 if t(X) = CLOSED then INSERT(X, h(X))
L3 return GET-KMIN( )
2.3 Иллюстрация алгоритма
Роль состояний RAISE и LOWER являются самым важным в алгоритмt. RAISE состояния (то есть, k (X) < h (X)) распространяют увеличения стоимости, и LOWER состояния (то есть, k (X) = h (X)) распространяют уменьшения стоимости. Когда стоимость пересекающего дуга увеличивается, воздействующееся соседнее состояние помещено в список OPEN, и увеличение стоимости распространяется через RAISE состояния через все последовательности состояний, содержащие дугу. Поскольку RIASE состояния входят в контакт с соседними состояниями более низкой стоимости, эти более LOWER состояния помещены в OPEN список, и их под-последовательности уменьшают стоимость предварительно повышенных состояний везде, где возможно. Если стоимость пересекающего дуга уменьшена, уменьшение распространяется через LOWER состояния через все последовательности состояний, содержащие дугу, также как соседние состояния, чья стоимость может также быть понижена.
Р
исунок 1: Backpointers Основанный на Начальном Распространении
Р
исунок 1 через Рисунок 3 иллюстрирует операцию алгоритма для " потенциал хорошо " путь, планирующий проблему. Пространство планирования состоит из 50 x 50 сетки ячеек. Каждая ячейка представляет состояние и соединена с восьмью соседями через двунаправленные дуги. Значения стоимости дуги малы для ПУСТЫХ ячеек и предельно большие для ячеек ПРЕПЯТСТВИЯ 1. Робот размера в пункт и оборудован датчиком контакта. Рисунок 1 показывает результаты оптимального вычисления пути от цели до всех состояний в пространстве планирования. Два серых препятствия сохранены в карте, но черное препятствие - нет. Стрелки описывают функцию backpointer; таким образом, оптимальный путь к цели для любого состояния может быть получен, прослеживая стрелки от состояния до цели. Обратите внимание, что стрелки отклоняют вокруг серый, известные препятствия, но проход через черное, неизвестное препятствие.
Рисунок 2: LOWER Состояния Перемещаются из колодца
Робот начинается в центре левой границы(стенки) и следует за backpointers к цели. Когда это достигает неизвестного препятствия, это обнаруживает расхождение между картой и миром, модифицирует карту, цвета индикатор ячейки, серый, и вводит ячейку препятствия в OPEN список. Backpointers переназначен, чтобы переместить робот по неизвестному препятствию и затем отступать. Рисунок 2 иллюстрирует информационное распространение после того, как робот обнаружил, колодец запечатан. Путь робота показывается в черном и состояния в OPEN списке в сером. RAISE состояния, выезжают из колодца передающих увеличений стоимости пути. Эти состояния активизируют LOWER состояния вокруг "губы" колодца, которые перемещаются вокруг верхних и нижних препятствий и переназначают backpointers из колодца.
1. Значение стоимости дуги ПРЕПЯТСТВИЯ должно быть выбрано, чтобы быть большим чем самая длинная возможная последовательность ПУСТЫХ ячеек так, чтобы простой порог мог использоваться на стоимости пути, чтобы определить, прошел ли оптимальный путь к цели через препятствие.
Рисунок 3: Конечная Backpointer Конфигурация
Этот процесс полон, когда более LOWER состояния достигают ячейки робота, в которой отметке робот перемещается вокруг более менее стоящего препятствия цели (Рисунок 3). Обратите внимание, что после пересекающегося, backpointers только частично модифицируются. Backpointers внутри колодца указывать(отметка) направленный наружу, но они в левой половине пространства планирования все еще указывают в колодец. Все состояния имеют путь к цели, но оптимальные пути вычислены к ограниченному числу состояний. Этот эффект иллюстрирует эффективность D*. Модификации backpointer, необходимые гарантировать оптимальный путь для робота ограничены окрестностью препятствия.
Рисунок 4 иллюстрирует планирование пути в fractally сгенерированный ландшафт. Среда - 450 x 450 ячеек. Серые области - пять раз более трудные пересечь чем белые области, и черные области - не проходимы. Черная кривая показывает путь робота от более низкого левого угла до верхнего данного права полная, априорно карту среды. Этот путь упоминается как всезнающий оптимальный. Рисунок 5 показывает планирование пути в том же самом ландшафте с оптимистической картой (весь белый). Робот оборудован круговым полем просмотра с радиусом с 20 ячейками. Карта модифицируется с информацией датчика как шаги робота, и расхождения введены в OPEN список для обработки D*. Из-за недостатка априорной информации карты, робот управляет ниже большой преграды в центре и блуждает в тупиковый перед перебором с возвратами вокруг последнего препятствия цели. Результирующий путь - приблизительно дважды стоимость всезнающего оптимального. Этот путь оптимален, однако, дан информация, робот имел, когда это приобретало это.
Рисунок 4: Планирование Пути в Полной Карте
Рисунок 5: Планирование Пути в Оптимистической Карте
Рисунок 6 иллюстрирует ту же самую проблему при использовании грубой информации карты, созданной составляющий в среднем издержки дуги в каждой квадратной области. Эта информация карты точна достаточно, чтобы регулировать робот к правильной стороне центральной преграды, и результирующий путь - только 6 %, больший в стоимости чем всезнающий оптимальный.
Рисунок 6: Планирование Пути к Карте грубый разрешающая способность
3.0 Правильность, Оптимальность, и ЗаконченностьПосле того как все состояния X были инициализированы t (x) = NEW и G был введен в OPEN список, функция PROCESS-STATE неоднократно вызывается, чтобы создать последовательность состояний. Функция MODIFY-COST вызывается чтобы сделать изменения для C ( o) и для того чтобы посеять эти изменениями в OPEN списке. D* проявляет следующие свойства: Свойство 1: Если t (X) != NEW, то последовательность {X} создана и монотона. Свойство 2: Когда значение k min возвращается при помощи PROCESS_STATE равным или превышающим h (X), тогда h (X) = o (X). Свойство 3: Если путь от X до G существует, и область поиска содержит конечное число состояний, {X} будет создан после конечного числа обращений к PROCESS-STATE. Если путь не существует, PROCESS_STATE возвратит -I с t (X) = NEW. Сойство 1 - сойство привильности: если однажды состояние было посещено, конечная последовательность backpointers к цели может быть создана. Свойство 2 - свойство оптимальности. Это определяет условия, при которых цепочка backpointers к цели является оптимальной. Свойство 3 - свойство законченности: если путь от X до G существует, то он будет создан. Если никакой путь не существует, это будет сообщено за конечное время. Все три свойства поддерживаются независимо от шаблона доступа для функций MODIFY-COST и PROCESS-STATE. Для краткости, доказательства для вышеупомянутого три свойства неформальны. См. Stentz [14] для детализированного, формальные доказательства. Рассмотрим свойство 1 сначала. Всякий раз, когда PROCESS-STATE попадает в NEW состояние, это назначает b ( o) для того чтобы указывать на существующую последовательность состояний и устанавливает h( o), чтобы сохранить монотонность. Монотонные последовательности впоследствии управляются, изменяя функции t( o), h( o), k( o), b( o). Когда состояние X помещено в OPEN список (то есть, t (X) = OPEN), k (X) установлен к h (X), сохраняют монотонность для состояний с backpointers к X. Аналогично, когда состояние X удалено из списка, значения h( o) его соседей увеличиваются если необходимо, чтобы сохранить монотонность. Backpointer состояния X, b (X), может только быть переназначен к Y, если h (Y) < h (X) и если последовательность {Y} содержит не RAISE состояния. Поскольку {Y} содержит не RAISE состояния, значение h( o) каждого состояния в последовательности должно быть меньше чем h (Y). Таким образом, X не может быть предок Y, и петля в backpointers не может быть создана. Следовательно, если однажды состояние X было посещено, последовательность {X} была создана. Последующие изменения гарантируют, что последовательность {X} все еще существует. Рассмотрите свойство 2. Каждый раз состояние вставлено или удалено из OPEN списка, D* значения модифицирует h( o) так, чтобы k (X) <= h (Y) + C (Y, X) для каждой пары состояний (X, Y) такой, что X является OPEN, и Y CLOSED. Таким образом, когда X выбран для расширения (то есть, k min = k (X)), CLOSED соседи X не могут уменьшать h (X) ниже чем k min, так же не могут это и OPEN соседи, поскольку их h( o) должны быть большие чем k min. Состояния, помещенные в OPEN список в течение расширения X значений должны иметь k( o) большее чем k (X); таким образом, k min увеличивает или остается тем же самый с каждым вызовом PROCESS-STATE. Если значения состояния с h( o) значение меньше чем или равны k old являются оптимальными, когда состояния с h( o) значениями между (включая) k old и k min являются оптимальным, так как никакие другие состояния в OPEN списке не могут уменьшать их стоимости пути. Таким образом значения, состояния с h( o) меньше чем или равный k min оптимальны. При помощи индукции, PROCESS-STATE создает оптимальные последовательности для всех не доступных состояний. Если стоимости дуги с(X, Y) изменяется, функция MODIFY-COST помещает X в OPEN список, после которого k min является меньше чем или равный h (X). Поскольку нет состояния Y с h (Y) <= h (X) можно воздействовать при помощи изменения стоимости дуги, свойство все еще поддерживаться. Рассмотрите свойство 3. Каждый раз состояние расширяется через PROCESS-STATE, это помещает NEW соседей в OPEN список. Таким образом, если последовательность {X} существует, это будет создано, если не состояние в последовательности, Y, никогда не будет выбрано для расширения. Но если однажды состояние было помещено в OPEN список, k ( o) значение не может увеличиваться. Таким образом, из-за монотонности k min, состояние Y будет в конечном счете выбрано для расширения. 4.0 Экспериментальные РезультатыD* сравнивался с оптимальным перепланировщиком, чтобы проверить оптимальность и определять уточнение эффективности. Оптимальный перепланировщик первоначально планирует одиночный путь от цели до состояния начала. Робот продолжает следовать за путем, пока датчик не обнаруживает ошибку в карте. Робот модифицирует карту, планирует новый путь от цели до текущего расположения, и повторяет, пока цель не достигнута. Оптимистическая эвристическая функция g (X) используется, чтобы фокусировать поиск, такой что g (X) равняется стоимости "прямой лини" пути от X до расположения робота, принимающего все ячейки в пути EMPTY. Перепланировщик неоднократно расширяет состояния в OPEN списке с минимумом g (X) + h (X) значения. Поскольку g (X) - нижняя граница на фактической стоимости с X на робот для всех X, перепланировщик - оптимальный [8]. Два алгоритма сравнивались при планировании проблем изменяющегося размера. Каждая среда была квадратна, состоящий из состояния начала в центре левой границы и целевого состояния в центре правой границы. Каждая среда состояла из смеси препятствий карты (то есть, доступный роботу прежде, чем пересекают) и неизвестные препятствия, измеримые датчиком робота. Используемый датчик осматривал 10 клеток вокруг. Рисунок 7 показывает модель среды с 100,000 состояниями. Препятствия карты показываются в сером и неизвестные препятствия в черном. Таблица 1 показывает результаты сравнения для сред размера 1000 до 1,000,000 ячейки. Исполнение на CPU время для SPARC-10 процессора перечислены наряду с коэффициентом ускорения выпуска продукции D* над оптимальным перепланировщиком. Для обоих алгоритмов, сообщенное время выполнения это общие CPU время для всего перепланирования, необходимого, чтобы переместить робот от состояния начала до целевого состояния, после того, как начальный путь был запланирован. Для каждого размера среды, два алгоритма сравнивались на пяти беспорядочно-произведенных средах, и время выпонения были усреднены. Коэффициенты ускорения для каждого размера среды были вычислены как среднее из пяти испытаний. Время выполнения для каждого алгоритма во многом зависит от сложности среды, включая число, размер, и размещение препятствий, и соотношения на карте неизвестных препятствий. Результаты указывают, что, поскольку среда увеличивается в размере, эффективность D* над оптимальным перепланировщиком увеличивается быстро. Интуиция для этого результата та что D* перепланирует путь локально, когда он обнаруживает неизвестное препятствие, но оптимальный перепланировщик генерирует новую глобальную траекторию. При увеличении среды размера, локальные траектории остаются константой в сложности, но при глобальной траекторий увеличении сложности. Рисунок 7: Типичная Среда для сравнения алгоритмов  Таблица 1: Сравнение D* с Оптимальным Перепланировщиком
Algorithm
|
1,000
|
10,000
|
100,000
|
1,000,000
|
Replanner
|
427 msec
|
14.45 sec
|
10.86 min
|
S0.82 min
|
D*
|
261 msec
|
1.69 sec
|
10.93 sec
|
16.83 sec
|
Speed-Up
|
1.67
|
10.14
|
56.30
|
229.30
| 5.0 Заключения5.1 Резюме Эти бумаги представляют D *, provably оптимальный и эффективный путь, планирующий алгоритм для оборудованных датчиком роботов. Алгоритм может обрабатывать полный спектр априорной информации карты, в пределах от полной и точной информации карты к отсутствию информации карты. D* - очень общий алгоритм и может применяться к проблемам в искуственном интеллекте другом чем планирование движения робота. В наиболее общей форме, D* может обрабатывать любую проблему оптимизации стоимости пути, где параметры стоимости изменяются в течение поиска решения. D* наиболее эффективен, когда эти изменения обнаружены близко текущая отправная точка в области поиска, которая имеет место с роботом, оборудованным бортовым датчиком. See Stentz [14] for an extensive description of related applications for D*, including planning with robot shape, field of view considerations, dead-reckoning error, changing environments, occupancy maps, potential fields, natural terrain, multiple goals, and multiple robots. 5.2 Future WorkДля неизвестных или частично-известных ландшафтов, недавнее исследование адресовало зондирование и карту, формирующую проблемы [6] [9] [10] [ll] [15] в дополнение к пути, находящему проблему. Использование стратегии подъема издержек для предварительно посещенных состояний, D* может быть расширено до задач зондирования поддержки. Quad деревья ограничили использование среды со стоимостью значений расположение над континуумом, если среда не включает большие области с константой пересечения издержки. Будущая работа включит представление QUAD дерева для этих сред также как с двоичными значениями стоимости (например, препятствием и пустой) чтобы уменьшить требования [15] памяти. Работа дорожная, чтобы интегрировать D* с off-road системой предотвращения препятствия [12] на наружном подвижном роботе. До настоящего времени, объединенная система показала способность найти цель после запуска отдельной сотни метров в cluttered среде без начальной карты. ПодтвержденияЭто исследование было субсидировано ARPA, согласно контрактам " Восприятие для Наружного Передвижения " (номер контракта DACA76-89-C-0014, контролировалось Армией США TEC) и " Беспилотная Наземная Система Транспортного средства " (чтобы dзаключить цифровой ber DAAE07-90-C-R059, контролируемый TACOM). Автор благодарит Alonzo Kelly и Пауля Келлер для графического программного обеспечения и идей для производства ландшафта фрактала. References[1] Goto, Y„ Stentz, A„ "Mobile Robot Navigation: The CMU System," IEEE Expert, Vol. 2, No. 4, Winter, 1987. [2] Jarvis, R. A„ "Collision-Free Trajectory Planning Using the Distance Transforms," Mechanical Engineering Trans. of the Institution of Engineers, Australia, Vol. MEIO, No. 3, September, 1985. [3] Korf, R. E., "Real-Time Heuristic Search: First Results," Proc. Sixth National Conference on Artificial Intelligence, July, 1987. [4] Latombe, J.-C., "Robot Motion Planning", Kluwer Academic Publishers, 1991. [5] Lozano-Perez, T, "Spatial Planning: A Configuration Space Approach", IEEE Transactions on Computers, Vol. C-32, No. 2, February, 1983. [6] Lumelsky, V. J., Mukhopadhyay, S„ Sun, K., "Dynamic Path Planning in Sensor-Based Terrain Acquisition", IEEE Transactions on Robotics and Automation, Vol. 6, No. 4, August, 1990. [7] Lumelsky, V. J„ Stepanov, A. A„ "Dynamic Path Planning for a Mobile Automaton with Limited Information on the Environment", IEEE Transactions on Automatic Control, Vol. AC-31, No. II, November, 1986. [8] Nilsson, N. J., "Principles of Artificial Intelligence", Tioga Publishing Company, 1980. [9] Pirzadeh, A., Snyder, W„ "A Unified Solution to Coverage and Search in Explored and Unexplored Terrains Using Indirect Control", Proc. of the IEEE International Conference on Robotics and Automation, May, 1990. [10] Rao, N. S. V„ "An Algorithmic Framework for Navigation in Unknown Terrains", IEEE Computer, June, 1989. [II] Rao, N.S.V, Stoltzfus, N., lyengar, S. S„ "A 'Retraction' Method for Learned Navigation in Unknown Terrains for a Circular Robot," IEEE Transactions on Robotics and Automation, Vol. 7, No. 5, October, 1991. [12] Rosenblatt, J. K., Langer, D., Hebert, M„ "An Integrated System for Autonomous Off-Road Navigation," Proc. of the IEEE International Conference on Robotics and Automation, May, 1994. [13] Samet, H„ "An Overview of Quadtrees, Octrees and Related Hierarchical Data Structures," in NATO ASI Series, Vol. F40, Theoretical Foundations of Computer Graphics, Berlin: Springer-Verlag, 1988. [14] Stentz, A., "Optima] and Efficient Path Planning for Unknown and Dynamic Environments," Carnegie Mellon Robotics Institute Technical Report CMU-RI-TR-93-20, August, 1993. [15] Zeiinsky, A„ "A Mobile Robot Exploration Algorithm", IEEE Transactions on Robotics and Automation, Vol. 8, No. 6, December, 1992. |
