Лингвистическая геометрия
Dec. 25th, 2012 02:50 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
kaipaПросматривая историю проекта "Пионер" Михаила Ботивинника, обнаружил, что разработанные тогда идеи живы, и не просто живы, а активно развиваются под новым названием лингвистическая геометрия. По сути это метод в рамках теории игр, применимый для мульти-агентных дискретных игр с большим числом переборных вариантов. Метод ЛГ позволяет радикально сократить число вариантов, а в некоторых случаях даже найти оптимальную стратегию без перебора. Если Ботвинник свои идеи обкатывал прежде всего в шахматах, но разрабатывал приложения управления электроэнергетикой (он сам был энергетиком) и планирования народного хозяйства СССР, то попав с США вместе с ведущим математиком группы Ботвинника, эти идеи мигом обросли сугубо военной тематикой: бой роботов, управление ракетами, система ПРО и т.д, хотя есть и гражданские приложения, например, оптимальная траектория скорой. Судя по прочитанным мной материалам, исследования спонсировались DARPA и, вероятно, ЛГ реально применяется в боевых системах. Сразу вспомнился недавний Russian AI Cup, где такая технология была бы очень в тему.
Суть метода в том, что строится иерархия формальных языков (отсюда -- лингвистическая), описывающих состояние агентов и их возможные траектории (отсюда -- геометрия). Лингвистический аппарат оказался наиболее удобным для описания иерархических систем. Агенты тоже объединяются в иерархии, на каждом уровне иерархии свои локальные цели. Самое сложное, это построить иерархии и описать их на математическом языке (на языке формальных грамматик, насколько я понял). Все это математически обосновано, исследуются классы задач, где и каким образом такой подход применим, вычислительная сложность и т.д. Результаты революционные. По сравнению с прямым перебором сокращение в степенные порядки.
Это основное, что я понял из введения к книге Штильмана, которое доступно открыто на сайте автора, или в переводе на сайте какого-то энтузиаста из Харькова. По ЛГ Штильман читает курс в Денверском университете. На русском информации практически ноль.
Суть метода в том, что строится иерархия формальных языков (отсюда -- лингвистическая), описывающих состояние агентов и их возможные траектории (отсюда -- геометрия). Лингвистический аппарат оказался наиболее удобным для описания иерархических систем. Агенты тоже объединяются в иерархии, на каждом уровне иерархии свои локальные цели. Самое сложное, это построить иерархии и описать их на математическом языке (на языке формальных грамматик, насколько я понял). Все это математически обосновано, исследуются классы задач, где и каким образом такой подход применим, вычислительная сложность и т.д. Результаты революционные. По сравнению с прямым перебором сокращение в степенные порядки.
Это основное, что я понял из введения к книге Штильмана, которое доступно открыто на сайте автора, или в переводе на сайте какого-то энтузиаста из Харькова. По ЛГ Штильман читает курс в Денверском университете. На русском информации практически ноль.
