Адаптивное Исследование Широкой Области Мультиробота и Картография
Киэн Хсиэнг Лоу †, Джон М. Долан, и Прадеп Хосла
Департамент Электрического и Компьютерного Инжениринга, Робототехники Институт Карнеги Мелон Университета 5000 Форбс Авеню Питтсбург ПА 15213 США {bryanlow, jmd} @cs.cmu.edu, pkk@ece.cmu.edu
Резюме.
Проблема исследования - основной вопрос в мобильной робототехнике. Полное освещение ландшафта не практично если окружающая среда является большим только с несколькими небольшими горячими точками. Эта бумага представляет адаптивную стратегию исследования мультиробота что ново в выполнении и освещения широкой области и осуществлении образца горячей точки использования неблизорукого планирования пути. В результате экологические явления могут быть точно нанесены на карту. Это основанный на динамической программной формулировке, которую мы зовем Мультиробота Адаптивной Проблемой Осуществления Выборки (MASP). Главная особенность MASP находится в покрытии всего адаптивного спектра, таким образом позволяя стратегии изменения адаптивности быть сформированной и теоретически проанализированной в их выступлении; более адаптивная стратегия улучшает точность картографии. Мы применяем MASP к осуществлению выборки Гауссовского и лог- Гауссовские процессы, и анализируем если получающиеся стратегии адаптивны и максимизируют освещение широкой области и горячую точку осуществления выборки. MASP решение нетривиально, поскольку он включает непрерывные государственные компоненты. Так, это повторно сформулировано для выпуклого анализа, который позволяет ограничения монотонности дискретного состояния приближение, которое будет развито. Мы обеспечиваем теоретическое гарантии на стратегическом качестве приблизительного MASP(a MASP) для того, чтобы использовать в MASP. Хотя aMASP может быть решен точно, его государственный размер растет по экспоненте с числом стадий. Облегчить эту вычислительную трудность, в любое время алгоритмы предложены основанные на aMASP , один из которых может гарантировать его стратегическое качество для MASP в режиме реального времени.
Категории и Подчиненные Описатели
G 1.6 [Оптимизация]: выпуклое программирование; G 3 [Вероятность и Статистика]: вероятностные процессы; I 2.8 [проблема Решения, Способы управления, и Поиск]: динамическое программирование; I 2.9 [Робототехника]: автономные транспортные средства
Общие термины
Алгоритмы, Выполнение, Дизайн, Экспериментирование, Теория
Ключевые слова
исследование мультиробота и картография, адаптивное осуществление выборки, активное изучение, Гауссовский процесс, лог-Гауссовский процесс, не- близорукое планирование пути
Процитируйте как: Адаптивное Исследование Широкой Области Мультиробота и Картография, Киэн Хсиэнг Лоу, Джон М. Долан, и Прадип Хосла, Proc. 7-ых
Международная Конференция по Автономным Агентам и Системам Мультиагента (ААМАС 2008), Padgham, Паркс, Мюллер и Пасторы (редакторы)., май, 12-16., 2008, Эшторил, Португалия, стр. XXX-XXX.
Copyright c 2008, Международный Фонд для Автономных Агентов и Системы мультиагента (www.ifaamas.org). Все права защищены.
1. ВВЕДЕНИЕ
Проблемой исследования неизвестной окружающей среды является основной вопрос в мобильной робототехнике. Как правило, это требует осуществления выборки всего ландшафта. Однако, полное освещение ландшафта не практично с точки зрения затрат ресурса если окружающая среда является большой только с несколькими небольшими, динамическими "горячими точками", и диапазон ощущения робота ограничен. Такая окружающая среда возникает в двух важных приложениях реального мира: (a) исследование планет, такое как геологическая разведка и минерал, исследующий [9], и (b) окружающая среда и экологический контроль, такой как контроль океанских явлений (например, цветение воды) [7], лесные экосистемы [13], грязь, и загрязнение. В этих приложениях часто необходимо для проб горячих точек для подробного анализа и извлечения. В то же самое время, окружающая среда должна быть соответственно покрыта определить местонахождение этих горячих точек так же как нанести на карту явления точно. Чтобы уменьшить человеческиe усилия и риск, желательно построить команды робота, которые могут выполнить эти задачи.
Важная проблема в проектировании такой команды робота стратегия исследования: как роботы решают, где открыть следующее? Эта работа представляет адаптивную основанную на модели стратегию исследования, которая нова в выполнении освещения широкой области и осуществление выборки горячей точки, и покрытие всего спектра адаптивности. Напротив, все другие основанные на модели стратегии неадаптивны и достигают только освещения широкой области. Наша стратегия может также запланировать неблизорукие мультиробота пути, которые более желательны чем жадный или единственного робота пути. Эти характеристики отличают наш подход от существующих стратегий исследования робота и обсуждены более подробно со связанной работой ниже:
Освещение широкой области против Осуществления выборки Горячей точки Исследования стратегий [7, 12, 13, 16, 17, 18], которые подчеркивают цель освещения широкой области улучшить точность картографии экологических явлений. С другой стороны, стратегии что сосредотачиваются на том, чтобы определять местонахождение и пробовать горячие точки [9], возможно, не скроенны, чтобы удовлетворить эту цель. Напротив, наш предложенный подход может заняться обеими задачами одновременно.
Модель - против Основанных на дизайне Стратегий В основанных на дизайне стратегиях [9, 13, 18], выбор осуществления выборки местоположений для исследования ограниченых дизайном осуществления выборки, которая является не разработанной, чтобы рассмотреть затраты ресурса. В результате местоположения должны быть выбраны стратегией сначала перед уменьшением
ресурса затраты, чтобы пробовать их. Это влечет за собой "погруженные" затраты в движении; пути исследования должны пересечь ландшафт что не требует, чтобы осуществление выборки достигло отобранных местоположений.
Кроме того, некоторые стратегии [13, 18] требуют многие "проходы" через область интереса, таким образом что новые местоположения адаптивно отобраны и выбраны в каждом проходе. Изменение стратегии вовлечь затраты ресурса может лишить законной силы оценщиков связанных со стратегией.
Мы вместо этого используем основанную на модели стратегию [7, 12, 16, 17], которая предполагает определенную модель окружающей среды и выбирает осуществление выборки местоположений, чтобы уменьшить его неуверенность. Ресурса стоимости минимизация или ограничения могут быть применены к выбора процессу и получающаяся стратегия оптимальна в этих ограничениях. В отличие от стратегий [7, 12, 16] что используют параметрическую модель, наш подход использует непараметрическую модель, которая не требует никаких предположений на распределении лежащих в основе данных об осуществлении выборки. В частности мы моделируем явления окружающей среды как Гауссовские [17] и лог-Гауссовские процессы.
Адаптивный против Неадаптивных Адаптивных Стратегий Осуществления выборки Адаптивное осуществление выборки ссылается на стратегии [9, 13, 18] в которых процедура для выбора местоположения, которые будут включены в пути робота зависит от данных об осуществлении выборки, наблюдаемых во время исследования. С другой стороны, неадаптивные стратегии осуществления выборки [7, 12, 16, 17] не имеют такой зависимости. Когда явления окружающей среды гладко изменяются, неадаптивные стратегии как известно, выступают хорошо [18]. Обычно, если окружающая среда содержит горячие точки, адаптивное осуществление выборки может эксплуатировать явления объединения в кластеры, чтобы нанести на карту окружающей среды поле более точно чем неадаптивное осуществление выборки. В отличие от выше схем может адаптивность нашей предложенной стратегии быть различной (Раздел 2.3); увеличивая адаптивность, его картографии точность может быть улучшена.
Жадный против Неблизоруких Стратегий Планирования Пути В отличие от жадных стратегий [12, 17], которые стоят перед проблемой локальных минимумов, наша стратегия производит неблизорукие робота пути [16]. Неблизорукие пути обычно приближают оптимальное траектории лучше, но подвергаются более высокой вычислительной стоимости.
Одинокий - против Стратегий Мультиробота В отличие от одинокого робота стратегий исследования [12, 13, 16], наша стратегия должна координировать исследование многократных роботов как те в [7, 9, 17, 18]. Команда робота может потенциально закончить задача быстрее чем отдельный робот и является также здравой к неудачам обеспечивая избыточность.
2. МУЛЬТИРОБОТА АДАПТИВНОЙ ВЫБОРКИ ПРОБЛЕМА (МАВП MASP)
2.1 Терминология и Примечание
Позвольте X быть областью явлений окружающей среды соответствуя конечному, дискретизированному набору местоположений клетки сетки (то есть, центры клетки). Позвольте Zx быть случайным переменным представлением ненаблюдаемого количества в произвольном местоположении ; его реализованное наблюдаемое/пробованое количество будет обозначено zx. Пусть данные m выбранных местоположений d0 будут заказанным списком пар , для i = 1,..., m. Так, добавление данных n новых выбранных местоположений к результатам d0 в . Пусть и обозначают векторы, включающие x и zx компоненты данных dn соответственно (то есть, и ). Путь робота P соответствует последовательности l местоположений. Когда робот едет между двумя местоположениями x и y, это подвергается стоимости движения C(x,y). Стоимость C(P) пути робота определен как сумма движения стоимости вдоль пути, то есть, .
Мы определим более ясно понятие адаптивности в стратегии исследования, которая крайне важна для понимания MASP. Предположим, что данные d0 были выбраны ранее и n новые местоположения должны быть отобраны для выборки проб образцов. Формально, стратегия исследования ограниченно адаптивна, если ее процедура, чтобы выбрать каждое новое местоположение выборки xm+i+1 для i = 0...,n-1, зависит только от ранее выбранных данных di. Стратегия неадаптивна [7, 12, 16, 17] если ее процедура, чтобы выбрать каждое новое местоположение осуществления выборки xm+i+1 для i = 0,...,n-1 независимо от . Следовательно, все n новые местоположения могут быть отобраны до исследования не будучи должны наблюдать любые новые данные об осуществлении выборки. Гибридизацией эти две, частично адаптивной [9, 13, 18] стратегии дают результаты, то есть, его процедура, чтобы выбрать каждую партию нового j местоположения xm+1j+1,…., xm+1j+j, для i = 0,..., n/j-11 зависят только на ранее выбранных данных dij. Когда j=1(n), эта стратегия становится строго адаптивной (неадаптивный). Так, увеличивая число новых местоположений в каждой партии, адаптивность гибридной стратегии уменьшится.
2.2 Проблемная Формулировка
Цель исследования состоит в том, чтобы собрать "лучшие" выборки данные от запланированных путей робота, которые максимизируют точность картографии поля окружающей среды. Достигнуть это, мы используем среднеквадратический критерий ошибки в качестве меры из пространственной неуверенности картографии. Дав ранее выбранные данные d0, предсказатель ненаблюдаемого количества в местоположении x0 достигает среднеквадратической ошибки . Тогда, неуверенность в картографии поля окружающей среды области X с предсказателем может быть представлена суммой среднеквадратических ошибок над всеми местоположениями в X (то есть, . Используя лучший непредубежденный предсказатель (то есть, достигает самой низкой среднеквадратической ошибки среди всех непредубежденных предсказателей), среднеквадратическая ошибка в каждом местоположении x0 может быть уменьшена до условного различия . Это приводит к пространственной неуверенности картографии , которая будет использоваться в формулировке исследования проблемы ниже.
В особенности, проблема исследования мультиробота вовлекает отбор новых местоположений осуществления выборки для робота исследования путей, которые обеспечивают наименьшее количество пространственной неуверенности картографии. Один типичный способ сделать это был бы выбором всех новых местоположений, которые будут добавлены к существующему образцу (скажем, d0), который минимизирует ожидание суммы следующих различий над всеми местоположениями в X:
(1)
подвергните ограничению движения C(Pi) для робота i=1,...,k, где - заказанный список пар построенный из пути Pi. Интерпретировать (1), выбор из новых местоположений быть включенным в робота пути P1..., Pk не зависит от ранее выбранных данных вдоль путей. Следовательно, эта проблемная формулировка неадаптивна.
С другой стороны, новые местоположения могут также быть отобраны последовательно таким образом, что выбор последующих местоположений быть включенным в пути робота зависит от ранее выбранных данных вдоль путей. Эта форма исследования
1 для упрощения выставки, мы предполагаем, что n является делимым j.
может быть достигнута моделируя MASP используя Динамичное Программирование (DP ДП) со следующими функциями переменной, которое представляет количество пространственной неуверенности картографии:
(2)
для i = 0,….,n-1 где реализованные данные dki - заказанный список последних k пар - вектор k местоположений робота, обозначающих текущее состояние команды робота, - пространство действия команды робота (то есть, конечный набор совместных действий) данные его текущим состоянием , ненаблюдаемые данные Dki+1 - заказанный список пар для l=m+ki+1,...,m + ki +k, и - следующее состояние, произведенное детерминированной функцией перехода команде робота основанная на его текущем действии ai и состоянии . Интерпретировать (2), выбор последующих местоположений быть включенным в путях робота P1,.., Pk зависит от ранее выбранных данных dki вдоль путей, которые делают эту проблемную формулировку адаптивной. Следовательно, случайные данные Dk1,..,Dkn соответствуют образцу, который является чтобы быть реализованным путями робота P1,..., Pk. Вышеупомянутые ограничения движения на роботы также применяются в этой проблеме.
Пусть обозначает действия политики команды робота таким образом что . Решая (2), оптимальная переменная V0(d0) может получиться вместе с соответствующей оптимальной политикой действия ;* где
(3)
Из (3), оптимальное действие ;*0(d0) может быть определено предшествующим к исследованию начиная с данных d0, что известны. Обычно, каждое действия правило ;*i(dki), i = 1,...,n-1 определяет действия, чтобы взять в отклике к данным dki, части которых (то есть, ), будут только наблюдаться во время исследования. Учитывая стартовые местоположения (говоря, ) роботов, их пути P1,.., Pk могут также быть получены, применяя перехода функцию T(..) к оптимальной политике действия ;*.
В некоторых задачах исследования запрет торговли может последовать между адаптивностью и выполнением задачи стоимости: например, первая окружающей среды измеряемая быть нанесеной на карту - иногда связывается с высоко коррелироваными вспомогательными изменяемыми, которые могут быть более дешевыми к образцу в более высоком пространственном разрешении или более надежным для того, чтобы запланировать пути исследования. Так, если вспомогательная изменяемая используется в MASP для планирования пути вместо этого, адаптивная стратегия должна подвергнуться добавочной плате осуществления выборки вспомогательной переменной во время исследования, которое не требуется неадаптивным исследованием.
2.3 Преимущество Адаптивного Исследования
Увеличение адаптивности может улучшить точность картографии (то есть, понизить пространственную неуверенность картографии), как показано ниже:
ТЕОРЕМА 2.1. Определим значение функций j-MASP как (4) для i = 0,..., n/j-1 , где j - число действий команде робота за стадию, для l =1,...,j таким образом, что Dijk:=dijk, и предполагают, что n является делимым переменной j. Тогда,V0j (d0) монотонно увеличивается в j.
Чтобы уточнить, каждая стадия j-MASP в (4) состоит из минимума следующим ожиданием. Как номер j из действий команды робота за уменьшения стадии, число местоположений опробованных за уменьшения стадии, который подразумевает увеличение в адаптивности (Раздел 2.1). В то же самое время, оптимальная переменная (то есть, пространственная неуверенность картографии) уменьшается с увеличением адаптивности. Отметьте, что 1-MASP переписывается к MASP в (2), в то время как n-MASP имеет ту же самую форму как неадаптивная проблема исследования в (1).
Вычислительная эффективность j-MASP не исправляется с уменьшением адаптивности (то есть, увеличивая j): для постоянного числа новых местоположений (то есть, n), чтобы быть выбранным, необходимое число стадий уменьшается с уменьшением адаптивности. Но, это связано с увеличивающейся размерностью из пространства действия под каждым минимумом и также, распределение вероятности для каждого ожидания. Если эти ожидания должны быть оценены в цифровой форме, число переменной функции оценок, требуемой для каждого ожидания, должно вырасти по экспоненте с числом местоположений опробованных за стадию для числового приближения, чтобы быть эффeктивными. Так как пространство действия под каждым минимумом также растет по экспоненте с числом действий команды робота за стадию, нет никакой вычислительной выгоды, уменьшая адаптивность.
2.4 Альтернативная Формулировка
В этом подразделе мы обеспечиваем альтернативную формулировку к MASP в (2), который предоставляет себя различным интерпретациям. Что еще более важно, эта переформулировка может подвергнуться выпуклым анализам (Раздел 2.6), который позволяет ограничение монотонности приближение MASP, который будет развит (Раздел 3.1).
Повторно сформулированный MASP включает функции переменные
(5)
для i = 0,...,t-1 с t=n-1 и функции награды
(6)
где . Аналог к Теореме 2.1 может быть получен для повторно сформулированного MASP кроме того, что оптимальная переменная увеличивается, а не уменьшается, с увеличением адаптивности.
ТЕОРЕМА 2.2. Переменные функции MASP в (2) и (5) связаны
(7) для i = 0,...,n-1 и их соответствующее оптимальное действие политики совпадают.
Теорема 2.2 может быть обобщена, чтобы угодить j-MASPs.
Переформулированный MASP в (5) интерпретируется различно от оригинального MASP в (2): от известного различия разложения формулы
,
член измеряет сокращение неуверенности в местоположении x0 от предшествующего различия к ожидаемому последующему различию , пробуя новые местоположения . Так, исследуя новые местоположения на каждой стадии, которые достигают большего сокращения в неуверенности по всем местоположениям в X (то есть, максимизируя награды в (5)), мы передвигаем самое большое количество неуверенности от начальной пространственной неуверенности картографии (то есть, (7)). Это в отличие от оригинала MASP в (2), посредством чего стоимость, которая будет минимизирована, появляется только на последней стадии (то есть, заключительная пространственная неуверенность картографии .
В следующих двух подразделах мы покажем как повторно сформулированный MASP в (5) может быть применен к Гауссовскому и лог -Гауссовскому процессу. В частности мы проанализируем адаптивен ли MASP для этих процессов и выпуклого свойства MASP для лог-Гауссовского процесса.
2.5 MASP для Гауссовского Процесса (GP)
Пусть обозначает GP определенное на области X, то есть, объединенное распределение по любому конечному подмножеству есть Гауссиан. GP может быть полностью определен его значением функции и ковариацией функции для . В этой работе предположено что значение функции и структура ковариации Zx известны. Учитывая ранее выбранные данные dkn, распределение Zx0 - Гауссовское с условным предложением и вариацией
(8)
(9)
где вектор колонки со значения компонентами для i = 1,..., m+kn, вектор ковариации с компонентами , для i= 1,...,m+kn, перемещение , и матрица ковариации с компонентами , для i,j = 1,..., m+kn.
Для GP, MASP может быть уменьшен, чтобы быть неадаптивным. Это прямое следствие следующей леммы:
Лемма 2.3. в (6) независимы от для i = 0,...,t. Следующая теорема следует из Леммы 2.3 и (5):
Теорема 2.4. Ui(dki) и ;*i (dki) независимы от , для i = 0,...,t. Следовательно, выбор новых местоположений выборки независим , для i = 0,...,t. В результате MASP для GP может быть уменьшен до детерминированной проблемы планирования
, (10)
которая стремится предоставлять достаточное покрытие для картирования поля окружающей среды точно. Однако, это не учитывается для максимизации осуществления выборки в горячих точках (Лемма 2.3).
2.6 MASP для лог-Гауссовского Процесса (lGP)
Пусть обозначают lGP, определенный на области X. Таким образом, если мы позволяем , тогда - GP (Секция 2.5). Так, и lGP имеет значение функции и функция ковариации для . Из Раздела 2.5 мы знаем что распределение из , данного dkn, является Гауссовским. Начиная с преобразования от к является обратимым, распределение , данное dkn является лог-Гауссовским с условным значением и вариацией:
(11)
(12)
где и определены, используя (8) и (9) соответственно.
Для lGP MASP адаптивен. Это - прямое следствие из следующей леммы:
Лемма 2.5. в (6) зависит от dkn для i =0,...,t.
Следующая теорема следует из Леммы 2.5 и (5):
Теорема 2.6. Ui(dki) и ;*i (dki) зависят от dki для i =0,...,t. Следовательно, выбор новых местоположений выборки зависит по ранее выбранным данным dki, для i = 0,...,t.
Помимо предоставления покрытия, чтобы изучить точное пространственное нанесение на карту, MASP в (5) для lGP также максимизирует осуществление выборки горячей точки: можно показать что большой награды в (6) связан с высоким ожидаемым количеством. Так, если x0 - одно из новых местоположений осуществления выборки в , MASP в (5) имеет тенденцию выбирать местоположение x0 с большой наградой . Следовательно, x0 ожидали верхний уровень количества, таким образом максимизируя осуществление выборки горячих точек (то есть, области из высоких взвешенных количеств).
Функции переменной MASP в (5), возможно, не выпуклы в выбранном ярде количеств yd входных данных d. Однако, MASP может быть преобразован, чтобы быть выпуклым заменой переменных Zx=logYx, как показано ниже:
Лемма 2.7. в (6) выпукло в (то есть, ()), дляi = 0,...,t. Следующая теорема следует из Леммы 2.7 и (5):
Теорема 2.8. Ui (dki) выпуклы в (то есть, (), для i = 0,...,t.
3. ПРИБЛИЖЕНИЯ ФУНКЦИИ ПЕРЕМЕННОЙ
Техника решения представленая в этой секции фокусируется на занятии строго адаптивным MASP в (5) (Раздел 2.1), который подразумевает, что только одно новое местоположение должно быть отобрано в каждой стадии. Функции переменной могут тогда быть упрощены в следующие два способа приведенные в (13): (a), более чем выбор совместных действий (.), чтобы переместить все роботы одновременно в каждой стадии, только один робот должен быть выбран на каждой стадии к пробе нового местоположения, в то время как остальная часть роботов остается помещенной. Этот запрет торговли между одновременными действиями и строгими адаптивности результатами в уменьшенном наборе A`(.) совместных действий для команды робота, которая растет линейно, а не по экспоненте (Раздел 2.3), с числом роботов; (b) следовательно, ненаблюдаемые данные Dki+1 могут быть сокращены до одиночной пары соответствующей новому местоположению x`, чтобы быть опробованным выбранным роботом. Так как другие отменявшие роботы стационарны на той стадии, остающихся парах в Dki+1 переписываются к местоположениям, отобранным на предыдущих стадиях и, может быть найденный в известных данных di. Распределение вероятности для условное ожидание в MASP может поэтому быть упрощено к унивариату Zx` , который уменьшает вычислительное бремя решения проблемы в цифровой форме (Раздел 2.3).
(13)
для i = 0,...,t-1, где xi – вектор k местоположений робота обозначающие текущее состояние команды робота, которая может быть получена из выбранных местоположений , и следующее состояние произведеное детерминированной функцией перехода T(ai,xi). Отметьте, что x` компонент в xi+1 с тот же самый индекс как компонент отличный от нуля в xi+1-xi.
Так как случайная переменная Zx` непрерывна, точное решение вышеупомянутого MASP не будет в вычислительном отношении выполнимо, если условное ожидание оценено, вычисляя Ui+1 (di, ‹х`,Zx`›) бесконечно часто по поддержке Zx`. Для MASP с t = 1 в (13), можно показать что условное ожидание может быть оценено в закрытой форме, которая делает проблему в вычислительном отношении выполнимой. В этот момент, мы не знаем ни о ком в вычислительном отношении выполнимом методы, чтобы решить MASP с t> 1 точно. Следовательно, мы будем обращаться к приближению MASP как описано ниже. Для легкой выставки мы вернемся к использованию изменяемой Zx для lGP (то есть, преобразовывая Zx =log Yx) в остальной части этой бумаги.
Трудности в решении многоступенчатого MASP находится в оценке условного ожидания относительно непрерывного параметра состояния Zx`. Эта запутанная проблема обработки с непрерывными состояниями обращена следующим связанным стохастическим теоретического решения проблемы планирования, которые решили это строя приблизительные проблемы:
Процессы принятия решений Маркова (MDPs) Традиционный подход из обобщения в непрерывные состояния в MDP к приближению значения функции с параметризованной моделью; получающееся решение обычно трудно проанализировать, и может отклониться. Сделать проблему в вычислительном отношении выполнимой решить, недавние подходы такие как с временной зависимостью [8] и фактора MDPs [6] приближают его, ограничивая переход, награду, и значение функции определенным семьям функции. Однако, MDPs с временной зависимостью страдает от показательного увеличенного снимка с увеличивающимся числом стадий, в то время как факторный MDPs вызывают бесконечно много ограничений в своей линейной программировании формулировке.
Напротив, MASP принимает более сложную, но реалистическую структуру не-Маркова; функция перехода обусловлена на всей истории действий и непрерывных состояний. Больше значительно, предполагая награду и значение функций будет выпукло (Раздел 2.6), кусочно-линейные функции могут быть построенны к монотонно полосе и приблизить значения функции (Раздел 3.1). Отметьте что форма перехода функции не ограничена.
Проблемы Не-Маркова Байеса (Bayes) последовательные проблемы проектирования [11] и стохастические программы [4, 15] могут быть смоделированы как проблемы не - Маркова DP. В отличие от MASP, у них есть простая структура: (a) их функции перехода не зависят от прошлых действий, (b) для Байеса последовательный дизайн, вся история непрерывных состояний может быть сокращена до резюме статистики, и (c) для стохастических программ, награды функция, как часто предполагается, линейна в переменной действия [4]. Сделать их в вычислительном отношении выполнимыми решить, условное ожидание приближено, используя Монте-Карло осуществление выборки для обеих проблем [11, 15] и ограничивая методы [4] для стохастических программ. Последняя техника далее предполагает значения функции, чтобы быть линейным или выпуклым в непрерывном состоянии и переменные действия. Получающееся приблизительные проблемы страдают от показательного увеличенного снимка. Наша ограниченная техника приближения (Раздел 3.1) использует результаты по обобщенным Дженсена ограничениям для выпуклых функций [5] от поля стохастического программирования.
3.1 Приблизительный MASP
В этой секции мы сформулируем приблизительный MASP (aMASP), чьи оптимальные более низкие границы ценности тот из MASP в (13). Получить aMASP и его связанное ограничение, следующий результат требуется, который использует неравенство Дженсена к более низкой-полосе ожидания выпуклой функции:
Теорема 3.1 ([5]). Пусть W(;) будет выпуклой функцией ; с поддержкой [a,b], который подразделен в произвольных точках b0,...,b;. (то есть, a:=b0 <b1<…<b; =:b). Пусть ;-кратная обобщенная Дженсена полоса, боунд обозначена
, v=1,2,…, (14)
где
, , j=1,…,v
Если разделение, соответствующее k+ 1, по крайней мере, столь же прекрасно как то соответствие k для k = 1,.....,v- 1, J1;....;Jv ;E [W(;.)].
Пусть поддержка Zx`, данных выбранных данных di будет Svx`i =[a,b], который разделен в v непустые, несвязные интервалы Svx`ij =[bj-1,bj] для j = 1,....,v. Используя Теорему 3.1, aMASP может быть получен из (13) со структурой:
(15)
для i = 0,...,t- 1, где , и , который является ожиданием Zx` кондиционируемого на di и . Отметьте что параметры из aMASP соответствуют тем из Дженсена полосы в (14). Что еще более важно, структура aMASP в (15) может быть рассматриваема как приближение непрерывной изменяемой состояния Zx` в (13) использованием дискретного с распределением в пунктах zx`ij вероятности px`ij> 0 для j = 1,...,v где .
Оптимальная политика действия ;v* =‹ ;0v*(d0),…, ;tv*(dt) › определенная подобным образом как тот из (3). В отличии от (3), дополнительные количества наблюдаемые во время исследования, как ожидают, будут реализованы от дискретных, а не непрерывных, распределений как объяснено выше. Если перепланирование не позволено во время исследования, то мы должны выбрать правило наиболее соответствующих мер применить к наблюдаемым непрерывным количествам. Это решено в форвард этапа- подобной манере: когда выбран во время исследования, следующего действия отобран таким образом что . Когда выбран, следующее действие отобрано таким образом что . Это продолжается для i = 3,...,t таким образом, что когда выбран, следующее действие отобрано с .
Доказать монотонные границы, значение функции MASP обязаны быть выпуклыми, которые показали для lGP (Раздел 2.6). Вместе с Теоремой 3.1 и следующей леммой, мы можем получить границы в Теореме 3.3:
Лемма 3.2. выпукла в для i =0,..., t.
Теорема 3.3. Если получен, раскалывая один из интервалов в , для i = 0,...,t.
Что еще более важно, Теорема 3.3 указывает что aMASP дает урожаи более низкой полосы к оптимальной переменной U0(d0) MASP в (13). Кроме того, совершенствуя разделение (то есть, увеличивая ;), границы могут быть улучшены; оптимальное значение aMASP монотонно увеличивается до того из MASP. Обычно, это увеличивает вычислительное бремя решения aMASP. Следующее заключение - прямой результат Теорем 2.2 и 3.3:
Заключение 3.4. Пусть .Тогда, .
Теорема 3.5. Пусть для i = 0,...,t-1, где является новым местоположением, чтобы быть выбранным, предпринимая текущие меры ;i(di). Если ;v* оптимальная политика действия для aMASP, , для i = 0,...,t.
Теорема 3.5 указывает что если оптимальная политика действия ;v* полученная, решая aMASP используется в оригинальном MASP, нижняя граница улучшена (то есть, политика ;v* гарантируется достигнуть не хуже чем для MASP).
4. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ В РЕАЛЬНОМ ВРЕМЕНИ
Для нашей схемы ограничивающей аппроксимации размер статуса растет по экспоненте с числом стадий. Это должное по природе DP проблем, которая принимает во внимание все возможные состояния. Облегчить эту вычислительную трудность, мы предлагаем алгоритмы любого времени, основанные на aMASP, один из которых может гарантировать свое стратегическое качество для оригинала MASP в режиме реального времени.
Наши предложенные в любое время алгоритмы приспособлены техникой Динамического Программирования Реального Времени (ДПРВ RTDP) [1], которая является известным эвристическим алгоритмом поиска для дискретного статуса MDPs. RTDP по существу симулирует пути жадного исследования через большое пространство состояний. Это приводит к следующим желательным свойствам: (a) поиск сосредоточен, то есть, это не должно оценить все пространство состояний, чтобы получить оптимальную политику, и (b) у нее есть полезное поведение в любое время, то есть, это производит хорошую политику быстро и эта политика улучшается в течение долгого времени. Неудобство RTDP - своя медленная конвергенция из-за сосредоточенного поиска.
Нетривиальный выпуск возникает с обобщением RTDP, чтобы обращаться с не-Маркова структурой aMASP: пространство состояний из MDP, как часто предполагается, послушен. Основываясь на этом предположении, RTDP был увеличен в [2, 3] с дополнительной процедурой, чтобы улучшить конвергенцию, которая требует сложность времени линейную в размере статуса. Что еще более важно, усовершенствования RTDP [2, 3, 10, 19] подчеркивают использование информированных эвристических границ, которые предварительно обработаны со временем сложностью линейной в размере состояния. Это чисто недопустимо для нашего алгоритма любого времени пока размер состояния aMASP растет по экспоненте с числом стадий. В следующей секции, мы получим информированные эвристические границы что в вычислительном отношении эффективно.
4.1 Предварительная обработка Эвристических Границ
Жадное исследование в RTDP управляется эвристическими границами, которые используются, чтобы сократить ненужные, плохие поиски из пространства состояний, все еще гарантируя политику оптимальности. В частности когда начальным границам более сообщают или более трудяги (в противоположность неинформированным, свободным границам, используемым в [1]), выполнение в любое время и выполнение конвергенции может быть улучшено [2, 3, 10]. Однако, это делает предварительную обработку границ более в вычислительном отношении дорогими как описано ранее.
Чтобы получить в вычислительном отношении эффективно информированные более низкие границы, мы можем расслабить aMASP v = 1, выбирая лучшее действие максимизировать непосредственную награду на каждой стадии:
(16)
для i= 0,...,t-1, где . Легко видеть что и для чего нижние границы aMASP (Теорема 3.3). Это можно показать что
Тогда, мы говорим, что более низкая эвристическая граница является монотонной. Как обычно, пространство состояний только растет линейно с числом t стадий для вычисления эту нижнюю границу.
Получить в вычислительном отношении эффективные информированные верхние границы, Теорема 2.2 может эксплуатироваться, чтобы дать
, (17)
для i= 0,...,t- 1. Из Теоремы 2.2, верхняя граница Ui(di) начиная с Vi(di); 0. Для чего это есть верхние границы aMASP (Теорема 3.3). Эта верхняя граница может быть вычисленна с временной сложности константой в ряде стадий. Можно показать что
Тогда, мы говорим, что верхняя эвристическая граница является монотонной.
4.2 Алгоритмы любого времени
Первый алгоритм (Алгоритм 1) любого времени приспособлен непосредственно от RTDP. Уточнить, каждая симулируемая тропа исследования вовлекает альтернативный выбор действий и их соответствующие выходы до последней стадии достигнуты; каждое действие отобрано на основе верхней границы (линия 3) и соответствующее следующее состояние/выход для исследования выбрано на базе дискретного распределения aMASP (линия 4). Тогда, алгоритм обратных следов до тропы, чтобы обновить верхние эвристические границы (линии 8-10) использующие , где
Мы предполагаем это всякий раз, когда с новым состоянием сталкиваемся, оно инициализируется с верхней границей, полученной в Разделе 4.1. Когда политику действия требуют в любое время во время выполнения алгоритма, мы обеспечиваем жадную политику вызванную верхней границей. Но, его качество не гарантируется.
Алгоритм 1: RDTP.
Второе алгоритм (Алгоритм 2) любого времени вдохновлен основанными на неуверенности RDTP (URDTP) методами [10, 19]. В отличии от Алгоритма 1, это поддерживает обе нижнюю и верхнюю границы для каждого сталкиваемого состояния, которые используемы, чтобы получить неуверенность в его соответствующем оптимальном значении функции. Алгоритм эксплуатирует их, чтобы вести будущие поиски в более информированной манере; это исследует следующее состояние/результат с самым большим количеством неуверенности
(линии 4-5). Помимо обновления верхних границ, нижние эвристические границы также обновлены во время обратного следования через (линии 10-13), где
. Когда политику действия требуют, мы обеспечиваем жадную политику, вызванную нижней границей. Качество этой политики имеет подобную гарантию к Теореме 3.5 посредством чего алгоритм любого времени для решения aMASP обеспечивает жадную политику что достигает не хуже чем для того, чтобы использовать в MASP.
5. ЭКСПЕРИМЕНТЫ И ОБСУЖДЕНИЕ
Эта секция представляет эмпирические оценки aMASP на набор данных реального мира, то есть, ежемесячное соединение в июне 2006 данные о плотности планктона Чесапикского залива от НОУА CoastWatch, ограниченный в пределах 38.481-38.591 N широты и 76.487-76.335W долготы. Областью залива (Рис. 1) является дискретизированная в 14. 12 сетку осуществления выборки единиц. Каждая единица x связана с плотностью планктона Yx измеренной в хлорофилле-a (chl-a). Область исследования (то есть, море) включает |X | =148 таких единиц приложеных темно-синей границей (Рис. 1). Флоту из двух роботизированных лодок задают работу, чтобы исследовать 18 осуществлений выборки единицы в этой залива области с их стартовыми обозначенными местоположениями в Рис. 1; каждый робот ограничен к типа смежным 9 единицам в его пути включая единицу его старт включен. Если только один робот используется для исследования, он помещен в высшую стартующую единицу (Рис. 1) и должен пробовать все 18 единиц. Действия из каждого робота ограничены перемещению во фронт, левую или правую единицу. Вместо того, чтобы предположить значения функции и ковариации структуру GP и lGP, что будет известна, мы используем данные 20 беспорядочно отобранных единиц, чтобы изучить их гиперпараметры через максимальную оценку вероятности [14]. Так, известные данные d0 включают беспорядочно отобранные единицы и стартовые единицы роботов.
Алгоритм 2: URTDP (; определеная пользователем граница).
Стратегическое исполнение строго адаптивного aMASP сравнивается с той из стратегий исследования вроде искусства, а именно, жадные и неадаптивные стратегии. Жадные стратегии применены к осуществлению выборки GP и lGP; жадная стратегия неоднократно выбирает максимизирующее награду действие (то есть, неоднократно решая MASP с t = 0 в (13)) получить тропы робота. Неадаптивная стратегия GP соответствует детерминированной проблеме планирования в (10). Подобно aMASP, его состояния размер растет по экспоненте с числом стадий. Для чего он приближен детерминированной версией RTDP под названием LRTA*.
Две исполнительных метрики используются, чтобы оценить политику из вышеупомянутых стратегий исследования: (a) Среднеквадратическая Относительная Ошибка (MSRE) меры пространственной неуверенности картографии при использовании в (11) предсказать поле плотности планктона где , и t = 16 (17) для случая 2 (1) роботы. Маленький MSRE подразумевает более низкую неуверенность и таким образом, лучшее освещение широкой области; (b) урожай чл-а измеряет количество выбранного планктона путями робота; высокий урожай планктона означает большую выборку в горячих точках.
Таблица 1 показывает результаты различных стратегий исследования с различными предполагаемыми моделями и размером команды робота. Для адаптивный aMASP и неадаптивный MASP, результаты получены, используя политику действия, полученную после пробега 100000 симулируемых путей. Результаты показывают что стратегии для lGP получают более высокий урожай планктона чем это для GP.
Рисунок 1: Плотности планктона (chl-а) поле Чеса- пик залива: 20 единиц (черные точки) беспорядочно отобранные как известные данные. Роботы запускаются в местоположениях отмеченных ‘;'с. Черные и серые пути робота
произведены адаптивным aMASP для lGP и не - адаптивным MASP для GP соответственно.
Таблица 1: Исполнительное сравнение робота исследований стратегий: 1R и 2R обозначают 1 и 2 робота соответственно.
В частности адаптивный aMASP с URTDP достигает самый низкий MSRE и очень высокий урожай планктона как сравнено с неадаптивным и жадным стратегиями. Кроме того, это может наблюдаться от Рис. 1 что политика действия адаптивных aMASP с URDTP перемещает роботы в образец горячих точек, но тот из неадаптивных MASP для GP не делают. Для того адаптивный aMASP с URTDP способен к выполнению превосходящего освещения широкой области (самый низкий MSRE) и осуществлению выборки горячей точки (очень высокий урожай планктона).
6. ЗАКЛЮЧЕНИЯ
Эта бумага описывает адаптивную исследования мультиробота стратегию, основанную на MASP, которая нова в выполнении как освещения широкой области так и осуществления выборки горячей точки. Главная особенность MASP находится в покрытии всей адаптивности спектра; теоретический анализ MASP с изменением адаптивности раскрывает то, что более адаптивная стратегия сокращает пространственную неуверенность картографии. Мы демонстрируем ее применимость для осуществления выборки GP и lGP, которые приводят к неадаптивному и адаптивному исследованию стратегии соответственно. Мы также показываем что MASP для lGP угождает и освещению широкой области и осуществлению выборки горячей точки в то время как это для GP только достигает прежнего. С тех пор это нетривиально, чтобы решить MASP из-за его непрерывных состояния компонент, это приближено дискретным состоянием монотонного ограничения aMASP. Мы обеспечиваем теоретическую гарантию на стратегическое качество aMASP для того, чтобы использовать в оригинальном MASP. К облегчению вычислительной трудности решения aMASP для lGP, любого времени алгоритмы предложены основанные на aMASP: Алгоритм URTDP может гарантировать свое стратегическое качество для оригинальной MASP в реальном времени и демонстрирует опытным путем достигнуть превосходящего освещения широкой области и осуществления выборки горячей точки по сравнению со стратегиями вроде искуства.
7. ССЫЛКИ