Назад в библиотеку

---

Автоматический вывод конечных автоматов для управления поведением

Авторы: B. Bonet, H. Palacios. H. Geffner.

Перевод: В.О. Изюк
Источник: B. Bonet, H. Palacios. H. Geffner. Proc. AAAI-10. Atlanta, USA. 7/2010. Источник оригинальной статьи

Аннотация

B. Bonet, H. Palacios. H. Geffner. Автоматический вывод конечных автоматов для управления поведением. Конечные контроллеры представляют эффективные механизмы отбора действия широко используются в таких областях, как видео-игр и мобильных роботов. В отличие от политики, полученных от МДП и POMDPs, конечные контроллеры имеют два преимущества: они часто чрезвычайно компактный, и они вообще, применяя к множеству проблем, а не только один. Ограничение конечных контроллеров, с другой стороны, является то, что они написаны от руки. В этой статье, мы обращаемся это ограничение, представляя метод получения контроллеры автоматически модели. Модели представляют собой класс задач, где условные действия детерминированы и некоторые флюэнты являющиеся наблюдаемыми. Проблема получения контроллер превращается в совместимой проблемы, которая решается с помощью классических планировщиков, воспользовавшись полного перевода в классической планирования, введенного в последнее время. Контроллеры, полученные в «общее» в том смысле, что они не только решить исходную задачу, но много вариантов, а также, в том числе изменения размера задачи или в неопределенности исходной ситуации и действий эффектов. Несколько экспериментов, иллюстрирующие автоматическое дифференцирование контроллеров представлены.

Введение

Рисунок 1 (a) показывает простой 1 × 5 сетка, где робот, первоначально в одном из двух крайних левых позиций, должны посетить правую позицию, отмеченные B, и вернуться к А. Если предположить, что робот может наблюдать след в текущей ячейки, если таковые имеются, и что действия левой и правой детерминировано перемещения робота один блок слева и справа, соответственно, проблема может быть решена с помощью условного планировщик или POMDP решающего, в результате чего в первом случае в условном дерева, и функция отображение убеждения в действиях в секунду (Levesque 1996; Kaelbling, Littman и Кассандра, 1999).Решение проблемы, однако, также может быть выражена в более простой форме, как конечным числом состояний контроллера, показанного на фиг. 1 (б). Начиная с государственной q0 контроллера, этот контроллер выбирает действии прямо, будь не наблюдается или нет знак ('-'), до тех пор, наблюдая В. Затем контроллер переключается на состоянии q1, где он выбирает Left тех пор, как не наблюдается никаких следов.

Конечный контроллер отображается на рисунке имеет две особенности, которые делают его более привлекательным, чем условных планов и политики POMDP: он очень компактный (она включает в себя только два состояния), и это является очень общим. Действительно, эта проблема может быть изменена в несколькими способами, и контроллер будет продолжать работать. Например, размер сетки может быть изменен от 1 × 5 до 1 × N, агент может быть помещен в любом месте первоначально в сетке (за исключением B), и действия могут быть выполнены недетерминированным добавлением ' шум ". Эта общность хорошо за власть условных планов или точных политики POMDP, которые привязаны к конкретной государственной пространстве. По этим причинам, конечные контроллеры широко используются в практике, из управления неиграющий символов в видеоиграх (Бакленд 2004) мобильных роботов (Мерфи, 2000; Mataric 2007 г.). Без памяти контроллеров или политика (Littman 1994) широко используются в качестве хорошо, и они не что иное, как конечно-контроллеров с единого государства. Дополнительные штаты предоставляют контроллеры с памятью, что позволяет различные действия, которые будут приняты с учетом же наблюдение.

Преимущества конечных контроллеров прийти в цене: в отличие от условных деревьев и политики POMDP, они, как правило, не происходит автоматически из модели, но написаны от руки; задача, которая не является тривиальной даже в простейших случаях. Там были попытки для получения конечных Госконтролеры для POMDPs с заданным числом состояний (Meuleau др. 1999; Пупар и Boutilier 2003; Бернштейн и др 2009)., Но проблема решается затем примерно с не корректности гарантий.

Модель, язык и управления

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

Точнее, мы рассмотрим класс задач управления вида P = (F, I, A, G, R, O, D), где F, I, G и обозначим множество (примитивных) флюент, начальная и цель ситуаций, и набор действий, соответственно, как в классической задаче планирования, кроме того, что я не набор литералов, но набор положений, которые приспосабливают неопределенности. Кроме того, R обозначает набор непримитивных флюент, определенных в терминах примитивных флюент с помощью сбора D аксиом или правил ветвления и вывода подмножество R, которые представляют наблюдаемые флюент. Точно так же.

1. Cостояние s это правда оценка по примитивные флюент F, который определяет значения для всех не-примитивных флюент R через аксиомы r ⇐ C в D (Thiebaux, Hoffmann, и Nebel 2005).

2. I задается набором F-положений, так что возможные исходные ситуации нормирования правды над F, удовлетворяющие I.

3. Действия пустые предпосылки и условные последствия форма C → C’, где С является множество литералов над F ∪ R и С’ является набор литералов более всего F.

4. Наблюдаемые флюэнты О ⊆ R обозначим информации воспринимается агентом: наблюдение о является набор O-литералов, истинных в данном состоянии. Наблюдение, что соответствует состоянии обозначается как O (S), и множества всех наблюдений, как O *.

В то время как решение задач управления может быть выражено в различных формах, в том числе отображение политики верований состояний в действия, условные планы и деревьев, мы рассмотрим решения, которые представлены конечным числом состояний контроллеров (FSCS) вида C = (Q, А, O*, δ, q0), где Q является множество состояний или узлов,A и O* наборы действий и наблюдений, δ: О * × Q → A × Q является (частичное) переходная функция, которая отображает наблюдения и узел пары в действии и пар узлов и q0 ∈ Q является начальная вершина. Узлы служить контроллер памяти, позволяющий выбирать различные действия, при том же наблюдение. FSC с одним узлом является без памяти.

Контроллеры представлены двумя способами: графически, используя круги представляют узлы и ребра с метками, чтобы представлять переходы, и, как множества кортежей t = (o,q,a,q0), которые выражают что δ определяется по (рис. 1) (O, Q) и отображает его на (а, q0).

Контроллер С обеспечивает спецификация действий ai+1, что делать дальше после последовательности данного наблюдения, действия (o0, a0, . . . , ai , oi+1).Действие сделать во время i = 0, если t = (o0, q0, a, q’) в С и o(s0) = а0, и q' является контроллер узла, который приводит во время i = 1. Точно так же, действия, чтобы сделать во время i в состояние s если t = (o, q, a, q’) в C, O(S) = о, и контроллер узла во время i это q.

Контроллер решает проблему, если все фазовые траектории, что она производит, начиная от начального состояние s0 ∈ I, достичь состояния цели. Это слабая форма раствора, поскольку это не требует, что все такие траектории оканчиваются целевого состояния. Это различие не имеет значения, когда цели наблюдаются, но имеет отношение иное.

Формулировка

Ключевым результатом нашей работы является то, что проблема получения контроллер C_N с N узлами для проблемной управления P могут быть переведены в задаче решения совместимые задачи планирования P_N (Бонет, Паласиос, и Geffner 2009 года). Этот перевод выполняет в основном следующие задачи:

1. он переводит наблюдения o ∈ O * и узлы контроллер q ∈ Q в флюент в P_N,

2. он устанавливает свободно (в соответствии с) q0, чтобы верно в исходной ситуации, и устанавливает все флюент q, c q 6 = q0, и все флюэнты вывода ложь,

3. это делает воздействие своих действиях в P условных на каждой наблюдательной о и свободно q определяя ‘контроллер действий’ b(t), для каждого кортежа t = (o, q, a, q’), которые ведут себя каккогда о и q верны, и заменить q на q ',

4. он захватывает эффекты действия на непримитивных флюент с помощью одного ‘ветвления действий’, и

5. уверяет, что все действия контроллера, используемые в растворе попарно согласуются; т.е., что никакой план не содержит действия b(o, q, a, q’) и b(o, q, a’ , q’’) с (a, q’) 6= (a’ , q’’).

Проблема P_N совместимую потому неопределенность в начальном положении P передается в неуверенности в исходной ситуации P_N, в то время как наблюдения O ∈ O * составляются далеко в условных эффектов действия P_N.

Для решения P_N, звук и полный K_S0 перевода, который преобразует P_N в классической задаче планирования K_S0 (P_N) используется (Паласиос и Geffner 2009).В результате классическая проблема планирования, K_S0 (P_N), решается либо с последовательным неоптимальным эвристического поиска планировщик, или оптимального параллельного планировщик C_N основе. За недостатком места мы опускаем подробности. Отметим, однако, что перевод звука и полное, это означает, что есть контроллер C_N с N узлами для решения P тогда и только тогда есть план для классической задачи планирования K_S0 (P_N). В этом случае, контроллер может быть считана план. Там нет бесплатный обед, хотя, и оба перевод Р в P_N, и P_N перевод в K_S0 (P_N) будут экспоненты в худшем случае. Эксперименты ниже, однако, показать, что это наихудший поведение не обязательно является практичным препятствием.

Эксперименты

Мы рассчитали контроллеры для нескольких проблем, как описано в следующем; дальнейшие подробности можно найти в Бонет, Паласиос, и Geffner (2009).

Холл. Проблема на рис. 1 версия 1 × 5 домена залы.N × N версии, включает в себя четыре 1 × N-залы, расположенные в квадрате, и наблюдаемые следы, B, C, D в четырех углах. Начиная с А, робот должен посетить все отмеченные позиции и вернуться к А. Рассмотрим два представления для задачи: в зале-А, есть четыре действия, которые движутся робота вдоль каждого направления компаса, в зале-R, есть это действия, чтобы двигаться вперед и повернуть 90° влево или вправо, и присутствие стене в передней части робота могут быть обнаружены (W).

4-Состояние контроллера получены для экземпляра Hall-A 4 × 4, и контроллер без памяти, полученные для экземпляра Холла-R 4 × 4, показаны на рис. 2. Стрелки в клетках показать выполнение, что приводит при контроллер применяется в исходное состояние, где агент находится на А. Оба контроллера обобщения в залах любого размера, и работа также в присутствии шумов как в исходной ситуации и в эффектов действий. Это обобщение осуществляется в несмотря на то, вывод контроллер от заданного начального состояние, а результаты изменения представления: последовательные планов не обобщать, поскольку они не представляют конечных Госконтролеры, пока мы не связываем узлы контроллер с показателями времени. Удалив зависимость от показателей времени, обобщение достигается. Еще один способ взглянуть на контроллерах, как условные планы на языке, где циклические конструкции разрешенных (Levesque 2005 г.).

Блоки. Блоки является проблема поднимая зеленый блок из башни с n блоков различных цветов. Мы кодировать домен с тремя действиями, разборки стопки, Drop, и собирать, что не принимают аргументов и имеют условные эффекты. Первое, что разборки стопки х очищает Y и помещает х в захвате, если х ясно и на Y; Второй блок, который может быть отброшен, когда состоится в захвате; в-третьих, цель достигнута, если собирать действие сделано в то время зеленый блок проходит (оплаченный действия с блоком из разные результаты цвета в тупик). Наблюдаемые флюэнты ли сверху блок в башне зеленый («G»), и является ли блок проходит («H»). Таким образом, условие, что блок проходит зеленый не наблюдается, и контроллер без памяти не решит проблему.2-состояние контроллер, который обобщает на любое количество блоков показана на рис. 3 (слева).

Захват. В этой задаче, робот должен выполнять шары от комнатной до комнатной В А. робот может двигаться между комнатами, и это может забрать и шары, используя свои захваты. Наблюдения включают ли шары остаются в B ('B'), есть ли свободного места в захватами ('S'), и робот держит ли некоторый шар ('H'). Робот не может непосредственно наблюдать его местоположение пока это первоначально при комнатной А с уверенностью. Экземпляр (n, m) относится к проблеме с n захватов и неопределенной количества шаров в комнатной В, которые могут варьироваться от 1 до m. Инжир. 3 (справа) показывает контроллер, полученной для экземпляра (3, 5), который также работает для задач (N, M) для любого n и n. Робот идет первым B, и поднимает шарики, пока нет места осталось в захватами, то он перемещается в А, где он падает все шары, по одному, повторяя цикл, пока не шары не оставляют в B и Робот не держит любой мяч. В этом случае, цель наблюдается и верно, когда ни В, ни Н верны.

Сбор мусора. Рисунок 4 показывает контроллер для мусора-может собирать робота (Коннелл 1990; Murphy, 2000; Mataric 2007), которые могут блуждать в течение целевого объекта, пока объект не находится рядом, можно перейти к объекту, если объект находится рядом, может захватить возражать, если находится там, где объект, и может упасть объект, если объект проходит.Задача передвигаться, блуждая по мусор, и когда кусок мусора проводится, бродить корзины уронить его. При кодировании, наблюдаемые флюэнты являются трэш-состоялось, далеко от-X, почти X и X на-где Х это мусор или мусорка. Наблюдения соответствуют векторы ABC, где означает, как далеко мусор (Дальний, близко, при), В обозначает, насколько это мусорное ведро (Дальний, близко, при), В и С относится ли проводится мусора (Held, несостоявшегося).

Визуальное перемещение маркера Вторая проблема blocksworld о размещении визуальный маркер на зеленом блоке, местоположение которого неизвестно (рис 5)., И вдохновляется использования указательных представлений (Чепмен 1989; Баллард и др 1997).. Визуальный маркер, первоначально в нижнем левом углу, можно перемещать вдоль четырех направлений компаса между клетками сцены, одной ячейки в то время. Наблюдения ли ячейка под маркер пустой («C»), является не-зеленый блок («B»), или зеленый блок («G»), и является ли это на столе («Т») или нет («–»). Мы получили контроллеры для разных экземпляров пока никто обобщенных над произвольными конфигурациями. Экземпляр (п, т) содержит т горизонтальные клетки и п блоков в какой-то распоряжения. Благодаря ограничению влево / вправо движений визуального маркера на уровне таблицы (т.е. при «Т» наблюдается, чтобы быть правдой), мы получили контроллер, который работает для любого количества блоков и элементов. Контроллер показано в правой части фиг. 5; это в основном ищет башни с зеленым блока слева направо, пройдя весь путь до вершины в каждой башне, а затем пройдя весь путь вниз к столу, и двигаться вправо, и не повторяя таким образом до тех пор, визуальный маркер достигает зеленой блока.

Заключение

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

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

Литература

1. Ballard, D.; Hayhoe, M.; Pook, P.; and Rao, R. 1997. Deictic codes for the embodiment of cognition. Behavioral and Brain Sciences 20(04):723–742.
2. Bernstein, D.; Amato, C.; Hansen, E. A.; and Zilberstein, S. 2009. Policy iteration for decentralized control of Markov decision processes. Journal of Artificial Intelligence Research 34:89–132.
3. Bonet, B.; Palacios, H.; and Geffner, H. 2009. Automatic derivation of memoryless policies and finite-state controllers using classical planners. In Proc. ICAPS, 34–41.
4. Buckland, M. 2004. Programming Game AI by Example. Wordware Publishing, Inc. Chapman, D. 1989. Penguins can make cake. AI magazine 10(4):45–50.
5. Connell, J. H. 1990. Minimalist Mobile Robotics. Morgan Kaufmann.
6. Kaelbling, L. P.; Littman, M.; and Cassandra, A. R. 1999.
7. Planning and acting in partially observable stochastic domains. Artificial Intelligence 101:99–134.
8. Levesque, H. 1996. What is planning in the presence of sensing In Proc. AAAI, 1139–1146.
9. Levesque, H. 2005. Planning with loops. In Proc. IJCAI, 509–515.
10. Littman, M. L. 1994. Memoryless policies: Theoretical limitations and practical results. In Cliff, D., ed., From Animals to Animats 3. MIT Press.
11. Mataric, M. J. 2007. The Robotics Primer. MIT Press.
12. Meuleau, N.; Peshkin, L.; Kim, K.; and Kaelbling, L. P. 1999. Learning finite-state controllers for partially observable environments. In Proc. UAI, 427–436.
13. Murphy, R. R. 2000. An Introduction to AI Robotics. MIT Press.
14. Palacios, H., and Geffner, H. 2009. Compiling Uncertainty Away in Conformant Planning Problems with Bounded Width. Journal of Artificial Intelligence Research 35:623– 675.
15. Poupart, P., and Boutilier, C. 2003. Bounded finite state controllers. In Proc. NIPS, 823–830.
16. Thiebaux, S.; Hoffmann, J.; and Nebel, B. 2005. In defense of PDDL axioms. Artificial Intelligence 168(1–2):38–69.