С 1991 года этот подход называется Лингвистической Геометрией (LG) из-за геометрической природы обнаруженных эвристик и теории формальных языков, применённой для их формализации. Полная разработка двух уровней иерархии языков была представлена в (Штильман, 1993a, 1993b и 1994d).

В 70-х и 80-х годах цели исследования были связаны с открытием наиболее глубоких особенностей экспертных эвристик перебора и разработкой математических инструментов, которые формализуют эти особенности. В 90-х годах с установлением LG как отдельной области цели изменились. На третьем этапе развития LG научные цели связаны с исследованием пределов эффективности, общности, вычислительной сложности и точности LG.

Частичный список вопросов для исследований в области LG в 90-х годах приведен ниже. Какой должна быть наиболее эффективная общая структура программных реализаций LG? Существуют ли задачи высокой размерности, решаемые с использованием LG? Как повлияет на время расчётов переход от двумерных задач к трехмерным задачам? Как изменится время расчётов, если мы увеличим число агентов и обеспечим их более развитыми средствами перемещения? Сможем ли мы решать задачи с частично или даже полностью параллельными ходами, используя аналогичные формальные инструменты? Какова вычислительная сложность этих задач?

К счастью, неожиданно для нас, в этот период мы получили ответы не только на эти, но и на другие дополнительные вопросы. Насколько точны решения LG? Можем ли мы строго оценить (и доказать) определённый уровень точности? Если наше доказательство конструктивно, можно ли использовать ту же самую технику для получения решения (а не только для оценки точности)?

Все программы, разработанные в 70-х и 80-х годах в рамках проекта ПИОНЕР, были в высшей степени проблемно-ориентированными. Они служили реализацией эвристических иерархий подсистем для специфических проблемных областей. В 90-х годах мы начинали исследование различных подходов и программных инструментов для реализации общей иерархии формальных языков и их приложений.

Несколько общих LG-грамматик были впервые реализованы в Университете Колорадо в Денвере в 1993 году Д.Кингом и Р.Матьюсом с использованием языка CLIPS и языка C, соответственно (Кинг, 1993) и (Матьюс, 1993). В то время как Р.Матьюс реализовал только два уровня иерархии — Траектории и Зоны (на C), Д.Кинг разработал прототип полномасштабной иерархии грамматик, используя среду программирования CLIPS. Он показал также, что инструменты программирования CLIPS (Гиарратано и Рилей, 1998), предназначенные первоначально для разработки экспертных систем, продемонстрировали высокую эффективность для быстрой реализации LG-грамматик. Конечно, эффективность на этапе разработки была достигнута за счёт снижения эффективности на этапе исполнения. Однако эти инструменты могут послужить основой для разработки прототипов.

Другое направление исследований было связано с выяснением фактической актуальности применимости общих LG-инструментов к различным проблемным областям. В 1995 году C.Флечер реализовал Грамматики кратчайших и допустимых Траекторий с обобщенными отношениями достижимости, используя C++ (Флечер, 1996; Флечер и Штильман, 1997). Он применил этот инструмент для разработки программного прототипа для моделирования управления навигацией робота в индустриальной среде. Интерпретация различных движений робота через отношения достижимости позволила этой системе планировать близкие к оптимальным пути роботов и избегать столкновений с неподвижными и подвижными препятствиями. Различные версии этого прототипа демонстрировались в Сандийской Национальной Лаборатории, Научном Центре Рокуэлла и на множестве конференций.

Проблемно-ориентированная версия LG-инструментов была разработана Р.Тюреком (Тюрек, 1996 и 1997). Он разработал очень эффективное коммерческое программное обеспечение, работающее в реальном времени, для прокладки маршрутов для машин экстренной помощи. Эти машины (полиция, пожарные и санитарные машины) направлялись к месту происшествия в ответ на телефонные звонки по номеру 911. LG-грамматики использовали отношения достижимости, которые формально представляли планы улиц и заторы движения на улицах города Авроры (часть Денвера), штат Колорадо. Планы улиц были введены при помощи географической информационной системы (GIS), в то время как информация о заторах обновлялась в реальном времени по данным от приборов, которыми комплектуются транспортные средства автодорожной полиции. Варианты этой программы демонстрировались в NASA в Центре Космических Полетов в Гринбелте, MD, и на нескольких конференциях.

В 1996 году Д.Вуд разработал BGF — универсальную программную среду для настольных игр в виде апплетов на языке Java (Вуд, 1996). Этот инструмент был предназначен для разработки перспективных интерфейсов для приложений LG в различных проблемных областях. В 1997-98 годах Э.Скисов использовал BGF для дальнейшего совершенствования своего инструмента моделирования военных игр (Скисов, 1997).

Этот инструмент моделирования военных игр (пока что наиболее полная реализация LG-алгоритмов) был разработан Э.Скисовым в 1997 году в рамках совместного проекта Университета Колорадо в Денвере и Университета Денвера (Скисов, 1997; Скисов и Б.Штильман, 1997, 1998a и 1998b). Его инструмент генерировал полномасштабную иерархию языков, включая предварительную версию Грамматики Переводов, основанную на беспереборном подходе (глава 13). Эта реализация была предназначена для исследования новых подходов в LG. В частности это был первый LG-инструмент, применённый к задачам с параллельным движением агентов. Также, это было первой реализацией LG для параллельной вычислительной среды на основе сети компьютеров. В этой среде вычисление траекторий с помощью Грамматики Траекторий происходило параллельно. Инструмент моделирования военных игр был реализован на C++ и на Java. Новая версия инструмента разрабатывается исключительно на языке Java.

В 1998 году класс задач, в которых применима LG, был расширен путём включения задач для локальных агентов, перемещающихся с переменной скоростью. Это расширение приближает модели LG к задачам из реальной жизни. Михаил Штильман обобщил отношения достижимости и изменил Грамматику Кратчайших Траекторий для этого случая (М.Штильман, А.Яхнис и В.Яхнис, 1998), (ОПРЕДЕЛЕНИЕ 2.4 и разд.9.10). Его реализация этой грамматики (на C++) вычисляет все кратчайшие пути для самолёта, который должен избежать пролёта над некоторыми территориями. Вначале самолёт ускоряется, затем идёт по курсу с постоянной скоростью и в конце полёта он замедляется, чтобы приземлиться.

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

По мере того, как общая структура и детали реализаций LG становятся более понятными, мы приближаемся к осуществлению нового проекта. Универсальный LG-testbad будет служить структурной средой для разработки приложений LG путём настройки на определенную проблемную область. Также, LG-testbad будет использоваться для быстрой проверки новых идей и подходов в LG.

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

В 1993 году, реализованная на основе CLIPS, иерархия грамматик была применена к задаче оптимального управления четырьмя роботами в двумерном пространстве, участвующими в игре 2-х игроков. Задача была представлена как двумерная дискретная игра уклонения от преследования с 4 агентами — задача 2D/4A (Штильман, 1996a, 1997a и глава 3). В сущности, это была версия этюда Рети. Традиционные подходы требуют, чтобы дерево игры для решения этой задачи содержало миллион ходов. LG-инструменты позволили нам найти решение в виде LG-дерева, которое включало только 46 ходов с показателем ветвления 1,65. Интересный результат был получен в 1994 году, когда задача 2D/4A была обобщена для трёхмерного случая — задача 3D/4A (Штильман, 1994b, 1994c, 1996a и глава 4). Задача была представлена как игра уклонения от преследования космических станций, которые должны достигнуть определённых областей в пространстве, и космических кораблей, которые могут перехватить эти станции или предотвратить перехват. Традиционные подходы требуют, чтобы дерево игры для решения этой задачи содержало триллион ходов, в то время как дерево, сгенерированное LG-инструментами, содержало всего около 50 ходов с коэффициентом ветвления близким к 1. Очевидно, что LG-инструменты позволили нам устранить экспоненциальный рост времени исполнения (относительно входных данных) для этого класса задач (разд.4.4).

Другой существенный тест для LG-инструментов в задачах со значительно большим пространством состояний проводился для двумерных и трёхмерных игр уклонения от преследования, в которых использовались 8 космических кораблей с необычайно сложными и развитыми возможностями перемещения (Штильман, 1995a, 1995b, 1997d и глава 5). Это была версия этюда Г.Надареишвили. Глубина решения и, соответственно, глубина перебора были чрезвычайно большими, по крайней мере, 25 ходов. Теоретические оценки показали, что для нахождения решения этих задач требуется генерация деревьев игры, которые бы включали приблизительно 1525 и 3025 ходов для задач 2D/8A и 3D/8A соответственно. Генерация дерева такого размера выходит за пределы разумных временных ограничений для любого компьютера. Однако, LG-деревья, сгенерированные LG-инструментами, состояли приблизительно из 150 ходов при коэффициенте ветвления 1,12.

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

В вышеупомянутых примерах подвижные объекты — самолёты, космические корабли и т.д. — перемещаются последовательно, т.е. один объект за один ход. Кроме того, движения объектов противоположных сторон чередуются. Нам было важно расширить применимость LG, охватив задачи с параллельным перемещением. На разных этапах развития LG формальное определение класса многоагентных систем, в которых применима LG, никогда не включало требования последовательных или чередующихся ходов, однако все примеры включали только последовательные перемещения. Новое направление, связанное с применением LG к многоагентным системам с высокой степенью параллелизма, определилось в 1994 году (Штильман, 1995c, 1995d, 1997a, 1997b и глава 6). Новый класс игр, называемый многоагентными играми на графе с одновременными ходами, был разработан В.Яхнисом и автором (1995). Эти новые игры разрешают одновременные (параллельные) ходы нескольких кооперирующих и конкурирующих агентов; кроме того, каждая сторона (суперагент) может пропустить ход или сделать ход путём одновременного перемещения одного или нескольких локальных агентов.

Несколько примеров было разработано в 1994-95 годах. Мы постепенно увеличивали степень параллелизма, выясняя его воздействие на эффективность LG-инструментов (глава 6). Применение LG к задачам с полностью параллельными движениями первоначально финансировалось американскими ВВС в 1995 году в рамках летней программы для профессоров на базе Лаборатории Филипса, расположенной на Военно-Воздушной Базе Кэртланд (Штильман, 1997a). Прототип программы для генерации сценария воздушного боя в режиме реального времени был разработан в Лаборатории Филипса в 1995 году. Эта программа была предназначена для управления пилотируемыми и беспилотными самолётами, наводимыми датчиками, установленными на спутниках, для обнаружения и уничтожения подвижных вражеских пусковых установок ракет. В 1996 году эти исследования финансировались грантом от Сандийской Национальной Лаборатории. В этих задачах самолеты — свои и противника — могли летать одновременно. Разработанные задачи включали две противостоящих группы, по два самолёта в каждой группе. Введение параллелизма привело к существенному росту коэффициента ветвления, до 324 (если применять перебор по методу «брут форс»). Это число — основание степени при экспоненциальном законе роста размера дерева игры, которое должно быть построено. Однако, LG-дерево для этой полностью параллельной модели содержит только 40 ходов с коэффициентом ветвления примерно 1,5. Позже эти результаты были обобщены для n×n области (Штильман и Флечер, 1998; и главы 6, 13 и 14).

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

Одно из последних достижений в LG — математическое доказательство оптимальности решений, полученных для некоторого класса задач, содержащего так называемые Рети-подобные задачи моделирования военных игр (Штильман, 1996b, 1997c, 1997d). Эти исследования финансировались грантом от Сандийской Национальной Лаборатории. Результат, полученный в 1996 году и позднее улучшенный, всё ещё выглядит удивительным для тех, кто вовлечён в исследования по LG. На протяжении всей истории развития LG значительные трудности виделись в том, как продемонстрировать качество приближённых решений, т.е. хороших или почти выигрышных стратегий, например, как измерить их точность. Как уже обсуждалось выше, это были решения одобренные экспертами. Существование ошибки даже не вызывало сомнений, потому что эвристические алгоритмы обычно не гарантируют оптимум. В течение многих лет мы пытались понять, как оценить степень этой ошибки. Удивительно, что эти исследования привели к доказательству отсутствия ошибки для Рети-подобных задач (разд.13.9). Этот новый результат свидетельствует о том, что LG-инструменты генерируют оптимальные решения для подкласса переборных задач. Оптимальность означает, что результат совпадает с решением, которое могло бы быть получено при использовании полного перебора по методу «брут форс».

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

В этой связи возникла мысль о конверсии доказательства в прямое построение LG-решений. Это было достигнуто в 1998 году (Штильман, 1998a, 1998b; и глава 13). Новый метод был назван беспереборным подходом. Беспереборной подход был расширен для охвата задач с параллельным движением агентов. Инструмент моделирования военных игр, разработанный Э.Скисовым, был впервые применён для экспериментов с параллельными задачами на основе беспереборного подхода (Скисов и Штильман, 1998a и 1998b). Задачи были решены с коэффициентом ветвления, равным точно 1, т.е. без ветвления в других направлениях.

В настоящее время разработаны две версии верхнего уровня LG-алгоритма: Грамматика Переводов и Беспереборной Алгоритм. Первый является универсальным инструментом, применимым к различным задачам. Генерируя маленькое LG-дерево перебора, он не даёт формальных оснований для заключения о точности решения; обычно, он генерирует решения, которые являются лучшими среди известных. С другой стороны, Беспереборной Алгоритм генерирует доказуемо оптимальное решение — выигрышную стратегию без перебора на дереве, но в настоящее время он применим только к подклассу Рети-подобных задач. Обратите внимание, что термин "беспереборной подход" означает, что перебор на дереве устранён, но Алгоритм всё ещё может включать некоторые другие типы перебора, например, полиномиальные по времени переборы. Вероятно, будущие исследования, основанные на развитии беспереборного подхода, приведут к перестройке верхнего уровня иерархии языков — Языка Переводов.

Помимо задач с подвижными объектами и противоположными сторонами (типа моделирования навигации робота), LG-инструменты могут быть эффективно применены к задачам без явного конфликта и противоположных сторон, например, к задаче составления расписаний с распределением ресурсов. Основы этого подхода были заложены применениями проекта ПИОНЕР к составлению графиков ремонтов и планированию на 1-м этапе развития LG (разд.1.7). Чтобы применить LG-инструменты, мы вводим искусственную игру двух игроков, т.е. искусственный конфликт, операционную область, подвижные объекты и противоборствующие стороны (Штильман и Флетчер, 1998, и глава 7). Эта формулировка позволила нам решить задачи высокой размерности, которые были неразрешимы при использовании традиционных подходов.