Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 234
Текст из файла (страница 234)
Модифицированный алгоритм итерации по стратегиям описан в [1245] и [1534). Алгоритм асинхронной итерации по стратегиям был проанализирован Уильямсом и Бердом [1598), которые также доказали свойство граничной убыточности стратегии, рассматриваемое в уравнении 17.9. Результаты анализа обесценивания с точки зрения стационарных предпочтений приведены в [834).
В [120), [121) и [1244) дано строгое введение в проблематику задач последовательного принятия решений. В [1170) описаны результаты исследования вычислительной сложности задач М)3Р. Важную роль в ознакомлении сообшества разработчиков в области искусственного интеллекта с задачами МОР сыграли оригинальные работы Саттона [1477] и Уоткинса [1558] по применению методов обучения с подкреплением для решения задач МОР, а также вышедший немного позже обзор [74). (В более ранней работе Глава 17.
Принятие сложных решений 857 [1580] содержались во многом аналогичные идеи, но они не были развиты до такой же степени.) Связь между задачами МОР и задачами планирования в искусственном интеллекте была впервые показана Свеном Кенигом [817], который также продемонстрировал, что вероятностные операторы 8гг[рз позволяют создавать компактные представления для моделей перехода (см. также [1575]). В [359] и [1492] сделана попытка преодолеть комбинаторную сложность больших пространств состояний с использованием ограниченного горизонта поиска и абстрактных состояний. Эвристики, основанные на стоимости информации, могут использоваться для определения в пространстве состояний таких областей, где локальное расширение горизонта приводит к значительному повышению качества решения.
Агенты, применяющие такой подход, могут соразмерять свои усилия под давлением дефицита времени и вырабатывать некоторые варианты поведения (такие как использование знакомых "проторенных тропинок") для быстрого поиска путей через пространство состояний без необходимости повторно вычислять в каждой точке оптимальные решения. В опубликованных недавно работах Бутильера и др. [158], [159] основные усилия сосредоточены на динамическом программировании с использованием символических представлений моделей перехода и функций стоимости на основе формул пропозициональной логики и логики первого порядка.
В [47] впервые было показано, что задачи М!)Р в частично наблюдаемой среде могут быть преобразованы в обычные задачи МОР с использованием доверительных состояний. Первый полный алгоритм точного решения для марковских процессов принятия решений в частично наблюдаемой среде (Рап!а1!у-ОЬзепаб!е Маг[соч Оес1гйоп Ргосезв — РОМОР) был предложен Эдвардом Сондиком [1446] в его докторской диссертации (опубликованная позднее журнальная статья Смоллвуда и Сондика [1433] содержит некоторые ошибки, но является более доступной).
В [946] приведен обзор состояния разработок в области решения задач РОМПР. Первым значительным вкладом в рамках искусственного интеллекта был алгоритм %!гпезз [227], [758] — усовершенствованная версия алгоритма итерации по значениям, применяемого для решения задач РОМРР. Вслед за ним вскоре были разработаны другие алгоритмы, в том числе основанные на подходе, предложенном Хансеном [6!2], который предусматривает инкрементное определение стратегии с помощью конечного автомата. В представлении стратегии с помощью конечного автомата доверительные состояния непосредственно соответствуют конкретным состояниям автомата.
Приближенно оптимальные стратегии для задач РОМРР могут формироваться с помощью прямого поиска, применяемого в сочетании с формированием выборок из возможных результатов наблюдений и действий [784], [! 134]. Другие результаты исследований в области алгоритмов РОМ(3Р описаны в главе 21. Основные идеи по созданию архитектуры агента с использованием динамических сетей принятия решений были предложены в [360].
В книге Р!алтпх апг( Озшго! Дина и Уэллмана [363] этот подход развит намного глубже и установлена связь между моделями ОВХ!РГЗМ и классической литературой теории управления, посвященной вопросам фильтрации. Татмен и Шахтер [1497] показали, как применять алгоритмы динамического программирования к моделям (30Б[. В [1325] описаны различные способы обеспечения применения таких агентов в более широких масштабах и указан ряд нерешенных исследовательских проблем. Корни теории игр можно проследить до предложений по изучению конкурентных и кооперативных взаимодействий людей с помощью научного и математиче- 858 Часть Ч. Неопределенные знания и рассуждения в условиях неопределенности ского подхода, которые были выдвинуты еше в ХЪП столетии Христианом Гюйгенсом и Готфридом Лейбницем. На протяжении Х1Х столетия некоторые ведущие экономисты создавали простые математические модели для анализа конкретных примеров конкурентных ситуаций.
Первые формальные результаты в области теории игр принадлежат Цермело [1641], который за год до этого предложил некоторую форму минимаксного поиска для игр, хотя и неправильную. Эмиль Борель [152] ввел понятие смешанной стратегии. Джон фон Нейман [1545] доказал, что любая игра с двумя участниками и нулевой суммой имеет максиминное равновесие в смешанных стратегиях и полностью определенное значение. Сотрудничество Джона фон Неймана с экономистом Оскаром Моргенштерном привело к публикации в 1944 голу книги 7пеогу оГСашез апВ Есопогп(с Вейатог (Теория игр и экономического поведения) [1546], которая сыграла решаюшую роль в создании теории игр. Публикация этой книги задерживалась из-за нехватки бумаги во время войны до тех пор, пока один из членов семейства Рокфеллеров не субсидировал публикацию.
В 1950 году в возрасте 21 года Джон Нэш опубликовал свои идеи, касающиеся достижения равновесия в играх общего типа [1! 12). Его определение равновесного решения получило известность под названием равповесия Нэша (хотя впервые появилось в работе Курно [297)). После длительной задержки из-за шизофрении, которой он страдал с !959 года, Нэш получил Нобелевскую премию по экономике (наряду с Рейнхартом Селтеном и Джоном Харсаньи) в! 994 году.
Равновесие Байеса — Нэша описано в [622) и обсуждается в [757]. Некоторые проблемы использования теории игр для управления агентами рассматриваются в [129]. Дилемма заключенного была разработана для использования в качестве учебного упражнения Альбертом В.
Такером в 1950 году и тшательно исследована в [50]. Понятие повторяюшихся игр было представлено в [963], а игры с частичной информацией — в [862]. Первый практически применимый алгоритм для игр с частичной информацией был разработан в рамках искусственного интеллекта Коллером идр.[821); в статье [822] дано удобное для чтения введение в эту общую область и описана действуюшая система представления и решения последовательных игр. Теория игр и задач МОР объединена в теорию марковских игр ]937].
Шепли ]1398] фактически описал алгоритм итерации по значениям до Беллмана, но его результаты не получили широкого признания, вероятно, потому, что были представлены в контексте марковских игр. К числу основных учебников по теории игр относятся ]5!0], [1109] и [1161]. Задача, послужившая стимулом к созданию области проектирования механизма, трагическая деградация общих пастбищ, была представлена в [619).
Гурвич [709] создал математические основы для проектирования механизма. Милгром [1048) описал разработанный им механизм аукциона, который охватывает диапазон сделок в несколько миллиардов долларов. Понятие аукционов может также использоваться в планировании [706] и составлении расписаний [1267].
В [1539] приведен краткий обзор тематики аукционов в связи с публикациями по компьютерным наукам, а в [1307] представлено описание способов применения этого подхода для решения распределенных задач искусственного интеллекта, занявшее целую книгу. Родственные работы по проблематике распределенных задач искусственного интеллекта публикуются также под другими названиями, включая коллективный интеллект [1516] н управление на основе рынка [269).
Статьи по вычислительным проблемам, связанным с аукционами, часто публикуются в трудах конференции АСМ Сап/егепсеэ оп Е(ес(гоп(с Сопопегсс. 859 Глава ]7. Принятие сложных решений УП РАЖН ЕНИЯ !7.1. 17.2. 17.3. 17.4. Для мира 4х3 (см. рис. [7. !) рассчитайте, какие квадраты могут быть достигнуты из квадрата (1, 1] с помощью последовательности действий [ггр, [гр, л1дпс, Идпс, Ид]зс] и с какими вероятностями. Объясните, как эти вычисления связаны с задачей проектирования скрытой марковской модели. Предположим, что в качестве полезности последовательности состояний определено максимальное вознаграждение, полученное в любом из состояний этой последовательности. Покажите, что данная функция полезности не приводит к формированию стационарных предпочтений между последовательностями состояний. Остается ли возможным определение на состояниях такой функции полезности, что принятие решений на основе полезности МЕ(] позволит сформировать оптимальное поведение? Может ли любая задача конечного поиска быть точно преобразована в марковскую задачу принятия решений, такую, что оптимальное решение последней является также оптимальным решением первой? Если да, то объясните, как преобразовать эту задачу и как выполнить обратное преобразование решения, а если нет, объясните, почему ваш ответ отрицателен (в частности, приведите контрпример).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
