Классы задач, которые будут изучены — это задачи оптимального управления LG-системой, т.н. Сложной Системой. Эта система определена (ОПРЕДЕЛЕНИЯ 2.1-2.4) как пара множеств: множество точек (пунктов) и множество локальных агентов, которые перемещаются, двигаются из одной точки в другую. Это — очень общее представление. Например, в задачах управления навигацией робота локальные агенты — это автономные роботы, перемещающиеся по траектории (построенной из точек) в сложной и опасной двумерной или трёхмерной окружающей среде. Агенты могут быть разделены на две или более противоположные стороны (т.е. на суперагентов), хотя в этой книге мы рассматриваем только системы с двумя сторонами. Каждая сторона может атаковать, уничтожать агентов противника и защищать своих агентов. Уничтоженный агент должен быть удален из системы, но он может появиться вновь в другой ситуации. Удаление происходит, когда атакующий агент перемещается в точку, где уже стоит агент противника. Каждая сторона стремится достичь множества определённых позиций — конфигураций агентов. Например, подобная конфигурация может представлять множество точек, в которых расположены агенты обеих сторон, с максимальным выигрышем, т.е. величина алгебраической суммы стоимостей своих и чужих агентов, которые уничтожены (и удалены из системы) достигла максимума.

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

Иерархия структур была построена на основе иерархии подсистем, введенных высококвалифицированными экспертами. Иерархия подсистем была введена следующим образом: одноуровневая LG-система с глобальными целями (по одной для каждой стороны) была заменена многоцелевой, многоуровневой системой путём введения промежуточных целей и разбиения (декомпозиции) полной системы на подсистемы, которые стремятся их достичь. Цели для подсистем различны, но подчинены общей главной цели. Например, каждая подсистема второго уровня, называемая Зоной, включает элементы двух противоположных сторон. Цель одной стороны состоит в том, чтобы напасть и уничтожить мишень, в то время как другая сторона пытается её защитить. В задачах управления навигацией робота это означает, что выбирается пара роботов противоположных сторон: один — как атакующий агент, а другой — как локальная мишень, затем генерируется путь, ведущий к мишени, а так же пути других роботов, поддерживающих атаку или защищающих мишень.

Иерархия структур представлена в LG как Иерархия Формальных Языков, где каждое слово языка низкого уровня соответствует одному символу в слове языка более высокого уровня (разд.1.3).

При LG-подходе каждая подсистема первого уровня представлена как слово или цепочка символов:

a(x1) a(x2) ... a(xn) ,

(1.4.1)

где символы a(xi) взяты из алфавита символов { a(xi) }. Символ a не несёт смысловой нагрузки. Он предназначен для связи параметров xi в одно слово и указания, что это слово — траектория. Значения параметров xi определяются семантикой проблемной области. Слова типа (1.4.1) образуют Язык Траекторий (ОПРЕДЕЛЕНИЕ 2.8). Например, для задачи управления навигацией робота xi — это координаты пунктов остановки в планируемом пути робота. Для задачи составления графика ремонтов аналогичное слово представляет собой вариант графика ремонта для определенного агрегата, причём x1, x2, ... , xn соответствуют определённым дням в составленном графике. Различные типы траекторий определены в разделе 2.4.

Подсистема второго уровня представлена также как слово или цепочка символов с параметрами, т.е. в виде Web-сети:

t(p1, t1, τ1) t(p2, t2, τ2) ... t(pk, tk, τk) ,

(1.4.2)

где символ t подобно a в (1.4.1) не несёт смысловой нагрузки. Он предназначен для связи параметров в одно слово и указания, что это слово — Web-сеть. Значения параметров (pi, ti, τi) определяются семантикой проблемной области и подсистем более низкого уровня. Символы pi обозначают агентов нашей LG-системы (роботы, агрегаты и т.д.); символы ti — обозначают Траектории (подсистемы низшего уровня) агентов pi, т.е. слова вида

a(x1pi) a(x2pi) ... a(xnpi) ,

включённые в эти подсистемы; а символы τi — обозначают время, выделенное для движения по траектории ti.

Используя слова (1.4.1), мы можем представить пути агентов LG-системы, а слова (1.4.2) — это Web-сети из некоторых путей, объединенных общей целью. Например, в управлении навигацией робота подобная сеть планируемых путей может моделировать набросок оперативного плана для достижения локальной цели в опасной окружающей среде (с подвижными и неподвижными препятствиями). В задаче составления расписаний это соответствует графику ремонта некоторого агрегата, включая график доставки ресурсов. Множество слов (1.4.2) — называют Языком Web-сетей (ОПРЕДЕЛЕНИЕ 2.18). Различные типы Web-сетей, так называемых Зон, определены в разделе 2.6.

Переход к другому состоянию LG-системы приводит к перестройке иерархии структур. Эта перестройка может быть представлена как отображение (перевод) в иерархию структур другого состояния. Фактически, мы можем представить изменение иерархии при переходе LG-системы из одного состояния в другое так, как будто сама иерархия структур изменяет своё состояние. Это означает, что структуры Траекторий и Зон для соответствующих состояний LG-системы образуют состояния иерархии структур. Направленный граф переходов состояний LG-системы порождает граф переходов состояний у иерархии структур.

В LG введен ещё более высокий уровень иерархии структур, который является общим для всех состояний. Эта структура высокого уровня представляет поддерево игры (с узлами, соответствующими состояниям LG-системы), которое порождается LG-стратегией игрока при поиске очередного хода в игре. Эту структуру называют деревом LG перебора (или LG-деревом). LG-дерево включает все варианты игры, которые LG-алгоритм генерирует в том состоянии игры, в котором игрок должен сделать ход. LG-дерево включает очень маленькое подмножество вариантов в противоположность полному дереву игры (ДИ). Ограничим употребление термина LG-дерево обозначением поддерева ДИ, представляющего варианты, рассмотренные при вычислении хода игрока в исходном состоянии LG-системы. LG-дерево включает последовательности ходов, т.е. переходов между состояниями LG-системы. Поэтому, мы можем ввести другое дерево — соответствующих последовательностей отображений или переводов Иерархии Языков (которые представляют эти состояния). Существует взаимно однозначное соответствие между этими деревьями. Таким образом, мы будем говорить об одном и том же дереве, называя его деревом ходов или деревом переводов. Это дерево представлено как слово, символы которого соответствуют рёбрам дерева, занумерованным, например, в соответствии с порядком обхода дерева по методу сначала вглубь: π(i1) π(i2) ... π(in) в (1.4.3). Это дерево, в свою очередь может быть записано как пара, состоящая из слова, упомянутого выше, и кортежа функций, которые генерируют потомков в любом узле дерева. Кортеж функций включает тройку функций, которые генерируют крайнего левого потомка, родного брата крайнего левого потомка и их родителя для любого узла дерева. Мы предполагаем, что генерация (обход) дерева происходит слева направо. Этот кортеж описывает сигнатуру, которая задаёт алгебраическую структуру дерева посредством функций, генерирующих потомков (ОПРЕДЕЛЕНИЕ 2.26).

Рассмотрим следующие слова:

( π(i1) π(i2) ... π(in), functions ),

(1.4.3)

где каждый символ π(ik) представляет одновременно следующие три понятия:
- ребро (дуга) LG-дерева;
- ход;
- соответствующий перевод.

Слово (1.4.3) — это элемент формального языка высшего уровня — Языка Переводов (разд.2.8 и глава 12). Как и ранее, символ π не несёт смысловой нагрузки. Он предназначен для связи параметров в одно слово и указания, что это слово — дерево переводов. Параметры ik идентифицируют рёбра дерева. Список функций, называемый functions, отражает связи между рёбрами. Эти связи предназначены для поддержки структуры данных дерева, которая представлена здесь линейно как слово или цепочка символов. Построение LG-дерева (1.4.3) управляется генерацией и взаимодействием Web-сетей (1.4.2) и Траекторий (1.4.1).

Если LG-алгоритм используется обоими игроками, то вариант (или варианты) ходов, порождаемый применением LG-стратегии для обоих игроков, является некоторой ветвью LG-дерева. Однако этот вариант не обязан быть подсловом (1.4.3) в Языке Переводов, состоящим из непрерывной подцепочки символов. Например, рассмотрим дерево с 4 узлами π(1) π(2) π(3) (рис.1.3). Ребро π(1) ведёт от корня R к единственному потомку, который обозначен как X, ребро π(2) ведёт к левому потомку X и ребро π(3) ведёт к правому потомку X. При обходе сначала вглубь (слева направо) рёбра будут занумерованы в виде списка π(1) π(2) π(3). Подслово π(1) π(2) представляет левую ветвь дерева. Есть ещё одна ветвь, состоящая из последовательности рёбер π(1) и π(3), т.е. подслово π(1) π(3). Однако это подслово π(1) π(3) не является непрерывным подсловом для π(1) π(2) π(3).

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

Диаграмма Иерархии Формальных Языков в LG показана на рис.1.4. Эта диаграмма является детализацией диаграммы, показанной на рис.1.2. Язык Переводов — это язык деревьев перебора. Слово этого языка может быть иллюстрировано деревом. Одно из таких деревьев с 5 рёбрами и узлами (1-6) показано на рис.1.4. Узел этого дерева соответствует состоянию сложной системы (1-6). Декомпозиция системы на подсистемы представлена в LG как Иерархия Формальных Языков. В каждом состоянии декомпозиция представлена иерархией двух языков — Языка Web-сетей и Языка Траекторий. Слово Языка Траекторий соответствует символу в слове Языка Web-сетей. Эта двойная иерархия иллюстрируется двумя вложенными треугольниками, присоединёнными к каждому узлу LG-дерева. Связь между этой иерархией и вышестоящим Языком Переводов (показанным как один большой треугольник) отличается от связи между языками внутри двойной иерархии. Слово Языка Переводов, т.е. перебор, представляет LG-дерево с узлами-состояниями, за которыми закреплены двойные иерархии. Поэтому, двойные иерархии соответствуют каждому символу слова Языка Переводов. Это иллюстрируется на рис.1.4. LG-перебор может быть представлен как логический вывод слова (генерация LG-дерева) в Языке Переводов.

Преимущества представления декомпозиции LG-системы в виде Иерархии Формальных Языков станут более очевидными, когда мы рассмотрим формальный механизм для генерации этой Иерархии. В задачах распознавания образов формально-лингвистический подход был предложен для представления иерархически структурированной информации, содержащейся в каждом образе, т.е. для описания образов посредством более простых подобразов. Этот подход обнаруживает аналогию между иерархической структурой образов и синтаксисом формальных языков. Правила, управляющие слиянием подобразов в образы, обычно задаются грамматиками описания образа, а мощь такого описания объясняется рекурсивной природой грамматик. Используя подобный подход для генерации Траекторий и Сетей Траекторий, мы используем раздел теории формальных грамматик, который был разработан Кнутом (1968), Розенкранцем (1969), Волченковым (1979), Штильманом (1985) и называется теорией управляемых грамматик. Детальный анализ управляемых грамматик и их приложений к LG приведен в главах 8-12, 14.

Недавнее исследование точности решений, полученных с помощью LG-алгоритмов, привело к более глубокому пониманию мощи этого подхода. Как выяснилось, инструменты LG способны реализовать конструктивную декомпозицию пространства состояний (глава 13). LG-инструменты позволяют нам формально описывать существенные подмножества пространства состояний и формулировать потенциально выигрышные стратегии, т.е. классы путей в пространстве состояний, ведущие из начального состояния в подмножества состояний, которые мы хотим достичь. Некоторые из этих стратегий могут быть забракованы, как нереализуемые. Следующий шаг — это попытка формальной реализации незабракованых стратегий для каждой из противоположных сторон. Это доказуемо лучшее поведение из того, что каждая сторона в принципе может сделать. Применение потенциально выигрышной стратегии для каждой стороны кончается генерацией LG-дерева, которое является оптимальным решением переборной задачи.

Подобные идеи работают для различных классов игр. Оптимальность доказана для классов многоагентных последовательных и параллельных военных игр с d-мерной операционной областью действий — подмножеством Zd. Это исследование привело к новому направлению в LG: решение переборных задач путём построения стратегий без какого-либо перебора на дереве (глава 13).