АГЕНТЫ, ДЕЙСТВУЮЩИЕ НА ОСНОВЕ ТЕОРИИ РЕШЕНИЙ

Динамические сети принятия решений позволяют получить краткое представление крупных задач POMDP, поэтому могут использоваться в качестве входных данных для любого алгоритма POMDP, включая те из них, которые относятся к методам итерации по значениям и итерации по стратегиям. В этом разделе мы сосредоточимся на прогностических методах, которые проектируют последовательности действий в прямом направлении от текущего доверительного состояния во многом таким же образом, как и алгоритмы ведения игр, описанные в главе 6. Сеть, приведенная на рис. 17.7, спроектирована в будущее на три этапа; неизвестными являются все текущие и будущие решения, а также будущие наблюдения и вознаграждения. Обратите внимание на то, что сеть включает узлы вознаграждений для xt+1 и Xt+2, но для Xt+3 — только узел полезности. Это связано с тем, что агент должен максимизировать (обесцениваемую) сумму всех будущих вознаграждений, а полезность U{xt+3) представляет и вознаграждение, относящееся к Xt+3, и все будущие вознаграждения. Как и в главе 6, предполагается, что значение полезности и доступно только в некоторой приближенной форме, поскольку, если бы были известны точные значения полезности, то не было бы необходимости заглядывать вперед на глубину больше 1.
На рис. 17.8 показана часть дерева поиска, соответствующего приведенной на рис. 17.7 сети DDN, развернутой в будущее на три этапа. Каждый из узлов, обозначенных треугольником, представляет собой доверительное состояние, в котором агент принимает решение At+i для i = 0,l,2,.... Узлы, обозначенные кружками, соответствуют выборам, сделанным средой, а именно тому, какие получены результаты наблюдений Et+i. Обратите внимание на то, что в этой сети нет узлов жеребьевки, соответствующих результатам действий; это связано с тем, что обновление доверительного состояния для любого действия является детерминированным, независимо от фактического результата.
Доверительное состояние каждого обозначенного треугольником узла можно вычислить, применив алгоритм фильтрации к ведущей к нему последовательности наблюдений и действий. Таким образом, в алгоритме учитывается тот факт, что для принятия решения о выполнении действия At+i агент должен иметь доступные результаты восприятия Et+i,..., Et+i, даже несмотря на то, что во время t он не знает, какими будут эти результаты восприятия. Благодаря этому агент, действующий на основе теории принятия решений, автоматически учитывает стоимость информации и выполняет действия по сбору информации, когда это потребуется.
Из данного дерева поиска можно извлечь информацию о решении, резервируя значения полезности, взятые из листовых узлов, вычисляя среднее в узлах жеребьевки и определяя максимальные значения в узлах принятия решений. Такая организация работы аналогична применяемой в алгоритме Expectiminimax для деревьев игр с узлами жеребьевки, за исключением того, что, во-первых, вознаграждения могут быть предусмотрены и в состояниях, отличных от листовых, и, во-вторых, узлы принятия решений соответствуют доверительным состояниям, а не фактическим состояниям. Временная сложность исчерпывающего поиска до глубины d выражается как О ( I DId-1ЕId), где I D I — количество доступных действий; Е — количество возможных наблюдений. Для получения решений, близких к оптимальным, при решении таких задач, в которых коэффициент обесценивания у не слишком близок к 1, часто бывает вполне приемлемым поверхностный поиск. Существует также возможность аппроксимировать этап усреднения в узлах жеребьевки, осуществляя выборку из множества возможных наблюдений вместо суммирования по всем возможным наблюдениям. Могут также применяться некоторые другие способы быстрого поиска качественных приближенных решений, но мы отложим их описание до главы 21.
Действующие по принципам теории решений агенты, основанные на динамических сетях принятия решений, имеют целый ряд преимуществ по сравнению с другими, более простыми агентами, проекты которых представлены в предыдущих главах. В частности, они способны функционировать в частично наблюдаемых неопределенных вариантах среды и могут легко пересматривать свои "планы" с учетом непредвиденных результатов наблюдений. При использовании подходящих моделей восприятия эти агенты могут справиться с ситуациями наподобие отказа датчиков и способны составлять планы по сбору информации. Под давлением жестких требований ко времени и в сложных вариантах среды эти агенты проявляют способность осуществлять "корректный переход к более примитивному поведению" (graceful degradation) с использованием различных методов вычисления приближенных решений. Так чего же в них недостает? Наиболее важным недостатком агентов, основанных на использовании алгоритмов динамической сети принятия решений, является то, что в них используется прямой поиск, полностью аналогичный тому, который предусмотрен в алгоритмах поиска в пространстве состояний, описанных в части II. В части IV было показано, что способность рассматривать частично упорядоченные, абстрактные планы с использованием целенаправленного поиска обеспечивает существенное расширение возможностей решения задач, особенно если при этом применяются библиотеки планов. Кроме того, были предприняты попытки распространить эти методы на вероятностную проблемную область, но до сих пор они оказывались неэффективными. Еще одной связанной с этим проблемой является слишком простой язык динамических сетей принятия решений, который по сути является пропозициональным. Было бы желательно распространить на задачи принятия решений некоторые идеи вероятностных языков первого порядка, описанные в разделе 14.6. Современные исследования показали, что такое расширение возможно и что оно позволяет получить существенные преимущества, как описано в заметках в конце данной главы.







Материалы

Яндекс.Метрика