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

Цель LG состоит в том, чтобы решать разнообразные задачи с огромными пространствами состояний при условии, что мы ищем "по возможности оптимальное или лучшее" поведение агентов, которые генерируют целенаправленные переходы из одного состояния в другое. К таким задачам относятся сотрудничество или противоборство команд интеллектуальных (или управляемых человеком) роботов (т.е. сухопутных или морских транспортных средств, самолётов или космических кораблей); критичные к безопасности системы управления удалёнными автоматическими объектами, подобные тем, что используются для исследования других планет; проектирование VLSI; долгосрочное планирование, составление расписаний и распределение ресурсов; шахматы и т.д. Традиционно, поиск оптимального или почти оптимального поведения объектов для вышеупомянутых систем требует полного перебора ветвей в гигантском дереве перебора (ДП). Такой перебор часто превышает (по ресурсам времени и памяти) возможности современных и даже мыслимых компьютеров будущего. LG-подход существенно уменьшает размер ДП, делая задачи решаемыми. Хотя дискретность заложена в природе LG, этот подход может быть применён и к управлению непрерывными процессами, которые описываются обыкновенными дифференциальными уравнениями или уравнениями в частных производных после их дискретизации.

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

Результаты сравнения LG-подхода с другими методами приведены на рис.1.1. Показаны три различных ДП. Верхний треугольник обозначает дерево, которое будет построено при использовании перебора по методу «брут форс». Широта этого дерева отражает высокий коэффициент ветвления. Однако, поскольку время ограничено, все ветви должны быть прерваны на небольшой глубине (например, на одной и той же). Дерево, построенное с применением алгоритма альфа-бета перебора, является более глубоким и более узким. Это — результат отсечений, которые позволяют уменьшить коэффициент ветвления и строить более глубокие ветви за то же самое время. Доказано, что оптимальная ветвь не будет отсечена, она будет той же, как в случае перебора по методу «брут форс» с такой же самой глубиной (Кнут и Мур, 1975). Однако, даже в этом случае рост перебора по экспоненциальному закону с большим основанием степени (коэффициентом ветвления) не позволяет нам решать большинство задач из реальной жизни. Третье, очень узкое и глубокое дерево отражает то, что при переборе на основе LG коэффициент ветвления равен точно 1 или близок к 1. Было также доказано, что для некоторого класса задач LG-алгоритм — это оптимальная (выигрышная или ничейная) стратегия (глава 13).

Подход на основе LG применим к параллельным многоагентным системам. Что это за агенты? Введём агентов двух типов. Агенты высшего уровня — это суперагенты, способные к действию посредством некоторого числа подвижных объектов, т.н. локальных агентов. Окружающая среда может оказывать существенное воздействие на движение агентов. Одни пункты операционной области могут быть достижимы за некоторое число ходов, другие могут быть вовсе не достижимы. Рассмотрим системы с двумя суперагентами, которые действуют друг против друга. Они называются противоположными сторонами. Обычно эти суперагенты преследуют противоположные цели. Каждый из них управляет командой локальных агентов, чья свобода действий существенно ограничена. В конечном счете, в примерах, рассмотренных в этой книге, локальные агенты вовсе не имеют свободы и полностью контролируются суперагентом. Однако, инструменты LG применимы и к тем моделям, в которых локальные агенты менее ограничены и работают независимо по своему разумению. Каждый суперагент разрабатывает модель своего оппонента, предполагая, что тот будет действовать наилучшим образом в рамках этой модели. Модель используется, чтобы планировать действия суперагента и выбирать оптимальные. Модель устанавливает локальные цели для локальных агентов. Эти локальные цели скоординированы с глобальной целью соответствующего суперагента. Движения, направленные к локальным целям, связаны со стремлением суперагента достигнуть своей глобальной цели. Модель является динамической, т.е. после каждого действия, которое может включать и одновременные передвижения агентов обеих сторон, она обновляется с учётом новой ситуации.

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

Иерархия подсистем в LG представлена как иерархия формальных языков. Чтобы ввести формальные языки, следуя (Хопкрофт и Ульман, 1979), мы должны использовать символы. Символ — это абстрактный объект, который мы не будем сейчас определять формально. Примеры символов включают

Диаграмма Иерархии Формальных Языков показана на рис.1.2 в виде множества треугольников трёх типов. Любое состояние из пространства состояний (т.е. из множества всех позиций или из всех возможных конфигураций агентов на абстрактной доске) представлено иерархией из двух вложенных треугольников (Языка Траекторий и Языка Сетей Траекторий). Несколько треугольников, которые представляют состояния (вместе с их двойной иерархией и дополнительными атрибутами), вложены в один большой треугольник — слово Языка Переводов. Этот высокоуровневый язык собственно и включает в себя решение задачи. Детальное описание Иерархии Языков в LG начинается в главе 2 и продолжается в главах 8-12. Более точная (но сложная) версия этой диаграммы показана на рис.1.4. Ниже, мы даём предварительное, краткое введение в эту Иерархию.

Подсистемы первого уровня в LG представлены Языком Траекторий, который является множеством "траекторий", т.е. слов типа:

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

где xi — называются параметрами. Значения параметров определяются семантикой проблемной области. Слова этого типа представляют пути (траектории) локальных агентов. Например, для модели роботов xi — координаты планируемого пути робота.

Подсистемы второго уровня в LG представлены Языком Сетей Траекторий, который является множеством Web-сетей, т.е. слов типа:

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

где pi, ti, τi — называются параметрами; pi — это локальный агент системы (робот или программный агент), ti — это траектория агента pi, а τi является списком параметров, зависящих от конкретной задачи. Эти Web-сети представляют рабочую схему для локального динамического планирования. Агенты перемещаются по траекториям, стремясь к достижению своих локальных целей, в то время как суперагент продвигается к глобальной цели, типа победы в бою или лучшего графика ремонтов электрогенераторов. Наша система может иметь несколько уровней для языков Web-сетей, представляющих иерархию подсистем.

Полная система функционирует, переходя из одного состояния в другое, т.е. движение локального агента из одного пункта в другой вызывает изменение иерархии языков. Это изменение можно представить как отображение, т.е. перевод из одной иерархии языков в другую или, более точно, в новое состояние той же самой иерархии. При переборе ходов в поисках оптимальной стратегии мы генерируем множество путей (последовательностей ходов) в пространстве состояний; таким образом, этот перебор можно рассматривать как последовательность переводов иерархии языков.

В LG в формальном языке высшего уровня — Языке Переводов — любой перебор представлен словом:

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

где ik — называются параметрами. Каждый символ π(ik) соответствует ходу локального агента по Web-сети. Перебор (вывод слова) на Языке Переводов представляется фактически как поиск оптимальной или близкой к оптимальной стратегии типа выигрышной стратегии для боя, лучшего графика ремонтов и т.д. Вывод слова в этом языке управляется взаимодействием всех Web-сетей. Результат вывода — существенно уменьшенный перебор, который и приводит к решению задачи.