ПРИНЯТИЕ СЛОЖНЫХ РЕШЕНИЙ
В данной главе рассматриваются методы принятия решений о том, что следует делать в настоящее время, при условии, что в дальнейшем может быть принято другое решение.
В этой главе описано, какие расчеты связаны с принятием решений. В главе 16 речь шла о задачах принятия единоразовых или эпизодических решений, в которых полезность результата каждого действия была вполне известна, а в настоящей главе рассматриваются задачи последовательного принятия решений, в которых полезность действий агента зависит от последовательности решений. Задачи последовательного принятия решений, в которых рассматриваются полезности, степени неопределенности и результаты восприятия, являются обобщением задач поиска и планирования, описанных в частях II и IV. В разделе 17.1 описано, как должны быть определены задачи последовательного принятия решений, а в разделах 17.2 и 17.3 показано, как их следует решать, чтобы выработать оптимальные правила поведения, в которых уравновешиваются риски и вознаграждения, связанные с осуществлением действий в неопределенной среде. В разделе 17.4 эти идеи распространяются на случай частично наблюдаемых вариантов среды, а в разделе 17.5 разрабатывается полный проект для агентов, действующих на основе теории принятия решений в частично наблюдаемых вариантах среды; в этом проекте объединяются динамические байесовские сети, описанные в главе 15, и сети принятия решений, описанные в главе 16.
Во второй части данной главы рассматриваются варианты среды с многочисленными агентами. В таких вариантах среды понятие оптимального поведения становится гораздо более сложным из-за взаимодействия агентов. В разделе 17.6 представлены основные идеи теории игр, включая ту идею, что рациональным агентам может потребоваться вести себя случайным образом. В разделе 17.7 показано, как следует проектировать мультиагентные системы для того, чтобы несколько агентов могли достичь общей цели.
ЗАДАЧИ ПОСЛЕДОВАТЕЛЬНОГО ПРИНЯТИЯ РЕШЕНИЙ
Пример
Предположим, что агент находится в среде с размерами 4x3, показанной на рис. 17.1, я. Начиная с начального состояния, он должен выбирать какое-то действие в каждом временном интервале. Взаимодействие со средой оканчивается после того, как агент достигает одного из целевых состояний, обозначенных +1 и -1. В каждом местонахождении в распоряжении агента имеются действия Up (Вверх), Down (Вниз), Left (Влево) и Right (Вправо). На данный момент предполагается, что эта среда является полностью наблюдаемой, поэтому агент всегда знает, где он находится.
Если бы эта среда была полностью детерминированной, то достижение требуемого решения было бы несложным: [Up, Up, Right, Right, Right]. К сожалению, среда не всегда реагирует правильно на осуществление этого решения, поскольку действия выполняются ненадежно. Конкретная принятая нами модель стохастического движения показана на рис. 17.1, б. Каждое действие достигает намеченной цели с вероятностью 0.8, но в течение всего остального времени в результате выполнения действия агент движется под прямыми углами к выбранному направлению. Более того, если агент ударяется в стену, то остается в том же квадрате. Например, выполняемое из начального квадрата (1,1) действие Up перемещает агента в квадрат (1,2) с вероятностью 0 . 8, но с вероятностью 0 .1 агент движется вправо, в квадрат (2,1), а с вероятностью 0 .1 он движется влево, ударяется в стену и остается в квадрате (1,1). В такой среде последовательность действий [Up, Up, Right, Right, Right] позволяет обойти барьер и достичь целевого состояния, квадрата (4,3), с вероятностью 0.85=0. 32768. Существует также небольшой шанс случайно достичь цели, обойдя барьер с другой стороны с вероятностью 0 .14х0 . 8, поэтому суммарная вероятность достижения цели равна 0.32776 (см. также упр. 17.1).
Спецификацию вероятностей результатов каждого действия в каждом возможном состоянии принято называть моделью перехода (или просто "моделью", если не может возникнуть путаница). Для обозначения вероятности достижения состояния s1, если в состоянии s было выполнено действие а, будет применяться запись Т( s, a, s1 ). Предполагается, что эти переходы являются марковскими в том смысле, какой указан в главе 15, т.е. что вероятность достижения состояния s1 из s зависит только от s, а не от истории пребывания в предыдущих состояниях. На данный момент запись т {s, а, s' ) может рассматриваться как большая трехмерная таблица, содержащая вероятности. В дальнейшем, в разделе 17.5, будет показано, что модель перехода может быть представлена как динамическая байесовская сеть, точно так же, как и в главе 15.
В завершение этого определения среды задачи необходимо сформулировать функцию полезности для агента. Поскольку эта задача принятия решений является последовательной, функция полезности должна зависеть от последовательности состояний (от истории пребывания в среде), а не от отдельного состояния. Ниже в этом разделе будет приведено описание того, как такие функции полезности могут быть определены в целом, а на данный момент просто примем предположение, что в каждом состоянии s агент получает вознаграждение R( s), которое может быть положительным или отрицательным, но должно быть ограниченным. В данном конкретном примере вознаграждение равно -0.04 во всех состояниях, кроме конечных (с которыми связаны вознаграждения +1 и -1). Полезность, связанная с историей пребывания в среде (на данный момент), рассматривается как сумма полученных вознаграждений. Например, если агент достиг состояния +1 после 10 шагов, суммарная полезность его действий будет равна 0.6. Отрицательное вознаграждение -0.04 побуждает агента быстрее достичь квадрата (4,3), поэтому данная среда представляет собой стохастическое обобщение вариантов среды, которые рассматривались в задачах поиска в главе 3. Еще один способ описать эту игровую ситуацию состоит в том, что агенту "не нравится" находиться в этой среде, поэтому он стремится выйти из игры как можно быстрее.
Такая спецификация задачи последовательного принятия решений для полностью наблюдаемой среды с марковской моделью перехода и дополнительными вознаграждениями называется спецификацией марковского процесса принятия решений, или сокращенно MDP (Markov Decision Process). Любая задача MDP определяется тремя перечисленными ниже компонентами.
• Начальное состояние — S0.
• Модель перехода — т (s, а, s1 ).
• Функция вознаграждения1 — R(s).
Следующий вопрос состоит в том, как должно выглядеть решение этой задачи. Выше в данной главе было показано, что какая-либо фиксированная последовательность действий не может служить решением этой задачи, поскольку в конечном итоге после ее выполнения агент может оказаться в состоянии, отличном от целевого. Поэтому в решении должно быть указано, что следует делать агенту в любом состоянии, которого он может достичь. Решение такого рода — это так называемая стратегия. Для обозначения стратегии обычно принято использовать я; а я( s) — это действие, рекомендованное в соответствии со стратегией я для состояния s. Если агент имеет полное описание стратегии, то всегда знает, что делать дальше, независимо от результата любого действия.
Каждый раз, когда осуществляется данная конкретная стратегия, начиная с начального состояния, стохастический характер среды приводит к формированию другой истории пребывания в среде. Поэтому качество определения стратегии измеряется по ожидаемой полезности возможных историй пребывания в среде, создаваемых с помощью этой стратегии. Оптимальной стратегией называется такая стратегия, которая позволяет достичь максимальной ожидаемой полезности. Для обозначения оптимальной стратегии принято использовать запись я*. Если агенту указана стратегия я*, он принимает решение, что делать, проверяя свои текущие результаты восприятия, которые сообщают ему, что он находится в текущем состоянии s, а затем выполняя действие я* (s). В любой стратегии функция агента представлена явно, поэтому стратегия является описанием простого рефлексного агента, сформированным с учетом информации, которая используется агентом, действующим на основе полезности.
Оптимальная стратегия для мира, приведенного на рис. 17.1, показана на рис. 17.2, я. Обратите внимание на то, что стоимость выполнения одного шага довольно мала по сравнению со штрафом, который связан со случайным попаданием в квадрат (4,2), поэтому оптимальная стратегия для состояния (3,1) является предельно осторожной. Этот стратегия рекомендует, что нужно совершить дальний обход препятствия, а не пытаться пройти по короткому пути и тем самым подвергнуться риску попасть в квадрат (4,2).
Равновесие между риском и вознаграждением изменяется в зависимости от значения функции R{s) для нетерминальных состояний. На рис. 17.2, б показаны оптимальные стратегии для четырех различных диапазонов изменения значения R(s). Если R{s)<-1.6284, жизнь настолько мучительна, что агент направляется прямо к ближайшему выходу, даже если стоимость этого выхода равна -1. Если -0 .4278
Тщательное уравновешивание риска и вознаграждения является характерной особенностью задач MDP, которая не возникает в детерминированных задачах поиска; более того, такое уравновешивание характерно для многих реальных задач принятия решений. По этой причине задачи MDP изучаются в нескольких научных областях, включая искусственный интеллект, исследование операций, экономику и теорию управления. Для вычисления оптимальных стратегий были предложены десятки алгоритмов. В разделах 17.2 и 17.3 описываются два наиболее важных семейства алгоритмов. Но вначале мы должны завершить начатое исследование полезностей и стратегий для задач последовательного принятия решений.