Децентрализованные частично наблюдаемые Марковские процессы принятия решений (decentralized partially observable Markov decision processes, далее в тексте Dec-POMDPs) легли в основу моделирования поведения автономно действующих роботов в условиях отсутствия связи с другими роботами и элементами системы и когда их собственных знаний об окружающей обстановке недостаточно. Этот подход к планированию сотрудничества роботов, как отмечают исследователи, делает сложные модели применимыми и эффективными на практике.

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

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

В этом году на Международной конференции по робототехнике и автоматизации (International Conference on Robotics and Automation, IEEE ICRA) другая команда исследователей MIT продемонстрировала дальнейшее развитие этого подхода. Их новая система может фактически генерировать системы управления нижнего уровня с нуля, при этом еще и создавая модели на основе Dec-POMDP в разумные сроки.

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

На этапе планирования в режиме оффлайн агенты могут вместе создавать правила для каких-то ситуаций: «Если я совершу такие-то действия, принимая во внимание сведения, полученные мной во время полетов в режиме онлайн, и если ты совершаешь такие-то действия, основываясь на сведениях, полученных тобой во время полета, то все к тому, что оптимальным вариантом будет следующее...» – говорит Шайеган Омидшафи (Shayegan Omidshafiei), магистр MIT по астронавтике и аэронавтике и первый в списке авторов новой статьи. – «В режиме онлайн уже нет смысла тратить время на разборки вроде «окей, это мое мнение, это твое мнение, давай договоримся, как будет лучше, и спланируем, что дальше». Тут уже пусть каждый просто делает, что считает нужным».

Откуда в данном случае берется неопределенность? Автономно действующий робот ориентируется в окружающей среде по показаниям датчиков. Но велика вероятность, что эти показания будут неточны или ошибочны, так что любые показания должны трактоваться как вероятностное распределение вокруг данного показателя. Даже точное измерение может потребовать интерпретаций. Затем, построив данные вероятностные распределения, робот должен выбрать курс действий, но все его возможные действия будут также иметь свои вероятности успеха. И если речь идет о совместной работе многих роботов, в эту схему должны быть включены вероятные местоположения других роботов и их последующие возможные действия.

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

Чтобы облегчить эту задачу, Омидшафи и его соавторы (его научный руководитель, профессор аэронавтики и астронавтики Джонатан Хау (Jonathan How), бывший постдок Лаборатории информационных систем и систем принятия решений MIT, а ныне работник корпорации Qualcomm Али-акбар Ага-мохаммади (Ali-akbar Agha-mohammadi) и Кристофер Амато (Christopher Amato), который вел первые работы в этой области в качестве постдока Лаборатории информатики и искусственного интеллекта MIT, ныне сотрудник Университета Нью-Гэмпшира) разбили ее на две составляющие, обе связанные с графами.

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

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

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

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

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

Наконец, алгоритм отбирает те «макродействия» и связи между ними, значение которых оказалось наибольшим. Что уже дает определенный план действий отдельным агентам – в условиях А, выполнив макродействие Б, переходи к макродействию С.

Дата публикации: 3 июня 2015 года
Источник: ScienceDaily