Исследователь решает дилемму теории игр почти 60-летней давности

  • Пользователь Алексей Коровин опубликовал
  • 15 марта 2023 г., 14:06:02 MSK
  • 0 комментариев
  • 49 просмотров
Исследователь решил дилемму теории игр почти 60-летней давности под названием "игра в погоню за стеной", что позволяет лучше рассуждать об автономных системах, таких как транспортные средства без водителя.

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

Деян Милутинович, профессор электротехники и вычислительной техники Калифорнийского университета в Санта-Крус, долгое время работал с коллегами над сложным подразделом теории игр, называемым дифференциальными играми, которые имеют отношение к игрокам в движении. Одна из таких игр называется the wall pursuit game, относительно простая модель для ситуации, в которой более быстрый преследователь преследует цель поймать более медленного уклоняющегося, который ограничен перемещением вдоль стены.

С тех пор как эта игра была впервые описана почти 60 лет назад, в игре возникла дилемма - набор позиций, в которых считалось, что оптимального решения для игры не существует. Но теперь Милутинович и его коллеги доказали это в новой статье, опубликованной в журнале Транзакции IEEE по автоматическому управлению что этой давней дилеммы на самом деле не существует, и ввел новый метод анализа, который доказывает, что в игре "погоня за стеной" всегда существует детерминированное решение. Это открытие открывает двери для решения других подобных проблем, существующих в области дифференциальных игр, и позволяет лучше рассуждать об автономных системах, таких как беспилотные транспортные средства.

Теория игр используется для рассуждений о поведении в широком спектре областей, таких как экономика, политология, информатика и инженерное дело. В рамках теории игр равновесие Нэша является одной из наиболее общепризнанных концепций. Концепция была введена математиком Джоном Нэшем, и она определяет оптимальные стратегии игры для всех игроков в игре, чтобы закончить игру с наименьшим сожалением. Любой игрок, который решит не использовать свою оптимальную стратегию игры, в конечном итоге будет еще больше сожалеть, поэтому все рациональные игроки мотивированы играть по своей стратегии равновесия.

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

Но Милутинович и его соавторы не пожелали с этим согласиться.

"Это обеспокоило нас, потому что мы подумали, что если уклоняющийся знает о существовании единственной поверхности, существует угроза того, что уклоняющийся может перейти на единственную поверхность и злоупотребить ею", - сказал Милутинович. "Уклоняющийся может заставить вас выйти на единственную поверхность, где вы не знаете, как действовать оптимально - и тогда мы просто не знаем, как это повлияет на гораздо более сложные игры".

Таким образом, Милутинович и его соавторы придумали новый подход к решению проблемы, используя математическую концепцию, которой не существовало, когда изначально задумывалась игра wall pursuit. Используя решение вязкости уравнения Гамильтона-Якоби-Айзекса и введя анализ скорости потерь для решения сингулярной поверхности, они смогли обнаружить, что оптимальное для игры решение может быть определено при любых обстоятельствах игры и разрешить дилемму.

Решение уравнений с частными производными по вязкости - это математическая концепция, которая не существовала до 1980-х годов и предлагает уникальную линию рассуждений о решении уравнения Гамильтона-Якоби-Айзекса. Теперь хорошо известно, что эта концепция актуальна для рассуждений об оптимальном управлении и задачах теории игр.

Использование решений вязкости, которые являются функциями, для решения задач теории игр предполагает использование математического анализа для нахождения производных этих функций. Относительно легко найти оптимальные решения для игры, когда решение по вязкости, связанное с игрой, имеет четко определенные производные. Это не относится к игре в погоню за стеной, и это отсутствие четко определенных производных создает дилемму.

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

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

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

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

Милутинович и его соавторы заинтересованы в изучении других задач теории игр с сингулярными поверхностями, где мог бы быть применен их новый метод. Эта статья также является открытым призывом к исследовательскому сообществу аналогичным образом изучить другие дилеммы.

"Теперь вопрос в том, какие еще дилеммы мы можем решить?" Сказал Милутинович.

Комментарии

0 комментариев