Оригинал LG01.pdf на английском языке доступен в Интернете на web-сайте Бориса Штильмана по адресу:

Лингвистическая Геометрия: от Перебора к Построению, 1999, 395 стр.

LG — математическая дисциплина, которая занимается поиском лучших стратегий в переборных задачах, относящихся к классу игр на абстрактной доске. LG выросла из проекта шахматной программы ПИОНЕР М.Ботвинника, в котором Борис Штильман был ключевым математиком и программистом. Удивительно то, что сейчас приложения LG — это управление навигацией роботов и беспилотных транспортных средств, моделирование боевых операций, составление расписаний, а не только шахматы или другие настольные игры. В отличие от традиционных подходов к поиску стратегий на дереве перебора, LG позволяет за разумное время вычислять лучшие и даже теоретически оптимальные стратегии в реальных боевых задачах.

Прошло ровно 4 года с тех пор, как рукопись книги "Лингвистическая Геометрия: от Перебора к Построению" была сдана в печать. По случайному совпадению, ровно столько же времени прошло с тех пор, как была основана компания STILMAN Advanced Strategies (далее STILMAN). В книге я писал о возможном начале четвёртого этапа развития LG — и он действительно начался в 1999 году в связи с открытием этой компании. В сущности, STILMAN — это пока ещё небольшое, но весьма эффективное научно-производственное объединение ("НПО" в советской терминологии), которое лидирует в разработке теории и приложений LG на четвёртом этапе.

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

Шахматы, как известно, родились около полутора тысяч лет назад путём абстрагирования реальных военных действий. Наверное, пришла пора платить по счетам — передать военным выигрышные стратегии, разработанные за много веков поколениями выдающихся шахматистов.

Борис Штильман Денвер, США октябрь, 2003

Эта книга не о лингвистике и не о геометрии. Она — о переборных задачах. Лингвистическая Геометрия (LG) — это подход к построению математических моделей для представления знаний и логического вывода в крупномасштабных многоагентных системах. Множество таких систем (формально определяемых здесь как Сложные Системы), включая воздушный бой, роботизированное производство, конверсию программного обеспечения, кибервойну в Интернете и т.д., образуют все те системы, которые могут быть смоделированы как абстрактные настольные игры (ABG). Сложные Системы — это игры многих игроков, ходы которых могут быть представлены передвижениями абстрактных фигур по полям абстрактной доски. Размерность (пространства) абстрактной доски (2D, nD и даже его нелинейность), его форма и размер, подвижность фигур, очерёдность ходов (включая одновременные ходы) — всё это может быть использовано для моделирования разнообразных многоагентных систем. Таким образом, абстрактные настольные игры понимаются здесь как класс Сложных Систем. Цель LG состоит в том, чтобы обеспечить участников игры стратегиями, необходимыми для достижения их целей. Традиционно, чтобы найти такие стратегии нужно перебрать все ветви в гигантском дереве игры (ДИ). Такой перебор часто превышает (по ресурсам времени и памяти) возможности современных и даже мыслимых компьютеров будущего.

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

Это первая книга по предмету. Я не намеревался представить здесь полную теорию LG, поскольку она ещё не закончена. Однако, эта книга включает основы теории LG.

LG имеет длинную и поучительную историю. Шахматы — дрозофила искусственного интеллекта (ИИ) — наибольшим образом способствовали созданию LG. Они и теперь остаются постоянным источником идей и движущей силой, подталкивающей развитие LG. Начавшись с компьютерных экспериментов в 1972 году, продолженных уже с развитием теоретических идей в 80-х и формально определившаяся в 1991, LG развивалась по многим направлениям. Некоторые из них основаны на строгих теоретических построениях, другие — на сложных и утонченных экспериментах. Цель этой книги состоит в том, чтобы представить читателю разнообразие подходов, идей и экспериментов. Каждая глава написана как эссе на одну тему в LG, теоретическую или экспериментальную, хотя все главы связаны вместе и поддерживают друг друга.

Глава 1 включает введение в предмет и краткую историю исследований. Глава 2 включает основные определения и обзор формализмов LG, т.е. иерархию формальных языков. Главы 3-7 охватывают несколько экспериментов с инструментами LG. Они демонстрируют, как алгоритмы LG решают задачи постепенно возрастающей сложности. Помимо интересных фактических результатов, детальное описание экспериментов предназначено развить интуитивное понимание алгоритмов LG и их общей структуры. Вооруженный этой интуицией, читатель будет способен воспринять формальное описание инструментов LG, приведенное в главах 8-12. В главе 13 основы LG рассмотрены более глубоко. Пересматривая эксперименты из главы 3, мы вводим новое направление в LG: решение переборных задач путём построения стратегий (без какого-либо перебора на дереве). В главе 14 мы обсуждаем некоторые вопросы вычислительной сложности. В этой книге высказывается предположение, что инструменты LG позволяют выделить широкий подкласс легко решаемых задач (т.е. полиномиально сложных) среди тех, которые обычно считались трудноразрешимыми (т.е. экспоненциально сложными). Алгоритмы LG обеспечивают эффективное решение задач из этого подкласса.

Книга может использоваться как учебник для дипломированного специалиста или старшекурсника по курсу LG в течение одного-двух семестров или в качестве приложения к курсу по ИИ. Часть этого материала преподавалась в курсе Представление Знаний для Интеллектуальных Систем и в курсе Сложных Интеллектуальных Систем в Университете Колорадо в Денвере. Также, многие из тем, включенных в эту книгу, ранее преподавались в качестве отдельных лекций и кратких курсов по LG, проводимых по всему миру.

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

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

Эта книга была вдохновлена результатами долгого и плодотворного сотрудничества в 70-х и 80-х годах с профессором Михаилом Ботвинником, моим научным руководителем и лидером проекта ПИОНЕР. В самом начале работы он формировал мои взгляды на сложные переборные задачи. Один ученый как-то сказал, что эта невообразимо трудная работа, возможно, началась только потому, что Ботвинник-шахматист не представлял себе трудностей программирования, в то время как Штильман-математик и программист не представлял себе трудностей игры в шахматы. Каждый раз, когда у группы исследователей возникали серьёзные проблемы в работе над проектом ПИОНЕР, доктор Ботвинник имел обыкновение говорить: “Если человек, шахматный мастер, может это делать, то и компьютер тоже сможет это сделать”. Он верил в существование общего алгоритма или небольшого набора общих алгоритмов, интуитивно используемых всеми шахматными мастерами и гроссмейстерами при игре в шахматы. В сущности, разработка, моделирование и обобщение этих алгоритмов и было целью проекта ПИОНЕР. Попытка разработки и исследования математической модели, основанной на этих алгоритмах — цель этой книги.

Александр Юдин, Александр Резницкий, Михаил Цфасман, Михаил Чудаков работали со мной в 70-х и 80-х годах над проектом ПИОНЕР. Мой друг и коллега, Вадим Мирный, с которым мы работали в 80-х, проявил глубокую научную проницательность и продвинул наши исследования и программные реализации на значительно более высокий уровень. Также, в 70-х годах неоценимая помощь в разработке программного обеспечения была оказана Дмитрием Лозинским, Лидией Полтавец и Анатолием Кострюковым.

Четверо знаменитых ученых, основателей информатики и разработки компьютеров в прежнем Советском Союзе, академик Виктор Глушков, профессора Башир Рамеев, Вячеслав Мясников и Николай Криницкий помогали организации работы, обеспечению финансирования и доступа к современным компьютерам в рамках проекта ПИОНЕР.

Проект ПИОНЕР и первые теоретические обобщения, связанные с созданием LG, не увенчались бы успехом без постоянной поддержки многочисленных советских ученых. Я благодарен им всем. Я хотел бы выразить признательность тем, чья решительная поддержка приходила в самые трудные времена. Это академик Николай Красовский, член-корреспондент, лауреат Ленинской премии Яков Цыпкин, члены-корреспонденты Юрий Руденко и Гермоген Поспелов, профессора Дмитрий Поспелов, Давид Юдин, Владимир Якубович, Георгий Адельсон-Вельский, Юрий Шакарян, Гавриил Шалыт, Лев Мамиконянц и доктор Михаил Донской.

Научный обмен с исследователями всего мира позволил нашей группе преодолевать изоляцию прежнего Советского Союза. Список основных участников этого сотрудничества включает профессора Монти Ньюборна (Monty Newborn) из Мак-Гилльского Университета, Канада; профессоров Тони Марсланда (Tony Marsland) и Рэнди Гобеля (Randy Goebel) из Университета Альберты, Канада; профессора Япа ван ден Херика (Jaap van den Herik) из Университета Лимбурга, Нидерланды; профессора Бена Миттмана (Ben Mittman) из Северо-западного Университета, США; доктора Дэвида Каландера (David Cahlander) из CDC Corp., США; Кена Томпсона (Ken Thompson) из Лабораторий Белла (Bell Labs), США; доктора Ханса Мойера (Hans Meuer) из Университета Мангейма, Германия; доктора Х.Дж.Аппелрата (H.J.Appelrath) из Университета Дортмунда, Германия; Дэвида Леви (David Levy) из Лондона, Великобритания.

Я особо признателен профессору Ньюборну, который пригласил меня для проведения исследований в Мак-Гилльском Университете в 1990 году. Уверен, что без этого приглашения я не смог бы продолжить исследования по LG.

В 1992 году профессор Эрвин Родин (Ervin Rodin) из Вашингтонского Университета в Сент-Луисе, Миссури, проявил интерес к дальнейшему развитию и расширению исследований по LG. В качестве главного редактора международного журнала "Компьютеры и Математика с Приложениями" (Computers and Mathematics with Applications), он писал: “... Я был бы очень заинтересован в публикации Ваших работ на эту тему [по LG — Б.Ш.]” (Родин, 1992). Некоторые из основных результатов, представленных в этой книге были впервые опубликованы в этом журнале. Центр профессора Родина "Оптимизация и Семантическое Управление" в Вашингтонском Университете внес вклад в успех 1-го Симпозиума по LG и Семантическому Управлению в 1995 году. В 1994, в связи с применением LG к моделированию и управлению боем, он писал: “Я знаком с работами профессора Штильмана по Лингвистической Геометрии и полагаю, что LG — это может быть наиболее заслуживающий внимания инструмент для выше названного предмета [интеллектуальное планирование и управление боем — Б.Ш.]” (Родин, 1994).

В 1993 году доктор Раймонд Луззана (Raymond Lauzzana), главный редактор международного журнала "Языки Проектирования" (Languages of Design) заинтересовался расширением круга специалистов знакомых с возможностями LG. Он приложил значительные личные усилия, осуществлял руководство и поддержку при переработке мною статей по LG для публикации в его журнале, чтобы сделать LG доступной для самого широкого круга специалистов. Он писал: “... Я хотел бы сказать, что доктор Штильман продемонстрировал увлекательный, впечатляющий новизной подход к научным исследованиям. Ему удалось превратить свои исследования по моделированию игр двух игроков в разработку общей модели иерархических систем. Это значительно расширило применимость его работ по LG... Я лично высоко оцениваю строгость, с которой он подошёл к предмету. Я уверен, что его работа окажет существенное влияние в будущем” (Луззана, 1993).

Джим Раш (Jim Rash), ученый из Центра Космических Полётов им. Годдарда (NASA), Гринбелт, MD, оказал поддержку, стимулировал и поощрял дальнейшее развитие LG. В качестве приглашённого редактора специального выпуска международного журнала "Телематика и Информатика" (Telematics and Informatics), включающего лучшие статьи Конференции по Космическим Приложениям ИИ 1994 года, он упомянул мою статью "Эвристические Сети для Исследования Космоса" (1994c), “... как пример особенно увлекательного приложения ИИ... Эта статья представляет Лингвистическую Геометрию как эффективный метод для поиска решений в больших пространствах состояний для классов задач, которые известны как особенно трудные, и применяет LG к задаче автономного планирования навигацией робота” (Раш, 1994).

Я благодарен профессору Алексу Майстелу (Alex Meystel) из Дрексельского (Drexel) Университета, за его конструктивный интерес к LG и постоянную поддержку. Как главный редактор серии книг по Интеллектуальным Системам, публикуемых издательством Вайли (Wile Series in Intelligent Systems), он не только поощрял меня к быстрому завершению работы над этой книгой, когда я находился ещё в самом начале работы над ней, но даже убеждал написать новую книгу по LG, возможно, с другим акцентом. Профессор Майстел писал: “... Я ожидаю, что многочисленные новые результаты по LG будут включены в Инженерию Знаний ИИ. Любое дальнейшее продвижение в области ИИ невозможно себе представить без использования концептуальных систем подобных Лингвистической Геометрии” (Майстел, 1998).

Схему этой книги мне неявно подсказал профессор Норман Фу (Norman Foo) из Университета Нового Южного Уэльса, Сидней, Австралия, который писал: “Не может быть никакой панацеи для методов перебора, поскольку доказано, что в худшем случае перебор экспоненциально сложен или даже ещё сложнее. Так, для любой идеи перебора найдутся такие классы задач, в которых она потерпит поражение. Однако вполне возможно, что существуют большие подклассы задач, которые могут быть хорошо описаны и окажутся поддающимися эффективной атаке. Это как раз то место, где идеи Бориса в области Лингвистической Геометрии представляют интерес. Он по существу нашел интересный и полезный подкласс, для которого его идеи и представления обещают эффективные решения. Это — значительный вклад в область ИИ” (Фу, 1996).

Когда работа над этой книгой была почти закончена, я узнал о следующем заявлении профессора Джона Маккарти (John McCarthy) из Стэнфордского Университета. В своих комментариях о решении шахматного этюда Рети компьютерами он писал: “Обратите внимание, что идея Рети может быть реализована на доске размером 100x100, и люди всё ещё смогут решать эту задачу, но современные программы [традиционные, т.е. работающие по методу «брут форс» — Б.Ш.] уже не смогут... Шахматы по-прежнему будут служить дрозофилой для ИИ, если исследователи попробуют создать программу, которая сможет решать задачи на доске произвольного размера. Однако, ИИ не будет продвигаться к человеческому уровню, если исследователи ИИ удовлетворятся методом «брут форс» как заменой интеллекта... Будет ли кто-нибудь серьёзно утверждать, что компьютер не сможет решить этюд Рети методом, отличным от «брут форс»?” (Маккарти,1998). Конечно, LG была разработана независимо и за длительный период времени. Однако, удивительно, что исследования по LG вдохновлялись аналогичными идеями.

LG значительно обогатилась при использовании уникальной экспертизы двух учёных, моих друзей доктора Владимира Яхниса (Vlad Yakhnis) из Научного Центра фирмы Рокуэлл (Rockwell Science Center), CA и доктора Александра Яхниса (Alex Yakhnis) из фирмы Пионерские Технологии (Pioneer Technologies), TX. Они внесли существенный вклад в построение выигрышных стратегий для игр двух игроков с полной информацией. Их работа повлияла на определение абстрактных настольных игр, используемых в LG. Я пользуюсь случаем, чтобы выразить особую благодарность доктору Владимиру Яхнису, который способствовал перестройке оснований LG. Я высоко оцениваю рецензию предварительного варианта этой книги, подготовленную доктором Александром Яхнисом, и, особенно, его конструктивные комментарии.

Я благодарю моего студента Дэвида Нокса (David Knox), который прочитал черновик этой книги, за его ценные комментарии и за высказывание, что эта книга — ...всё же читабельна.

Я пользуюсь случаем поблагодарить моего друга профессора Тома Альтмана (Tom Altman) из Университета Колорадо в Денвере, вдохновляющие идеи и практические советы которого помогли мне значительно продвинуть теорию и приложения LG. Очень важно иметь друга, на которого Вы могли бы положиться в самых трудных ситуациях на работе и в жизни.

Я благодарен моему сыну Мише, в настоящее время студенту 1-го курса Стэнфордского Университета, который внёс вклад в развитие LG для агентов с переменной скоростью и разработал удивительную обложку для этой книги.

Ещё один человек, которого я хотел бы поблагодарить — это Гарри Фолвен (Gary Folven), мой издатель. Его энтузиазм в связи с изданием этой книги и невероятное терпение помогли мне успешно закончить эту работу.

В этом кратком обзоре невозможно перечислить всех, кто внёс вклад в развитие LG. Я хотел бы выразить мою благодарность многочисленным исследователям, инженерам и студентам, интерес и усилия которых помогли прояснить и развить различные аспекты LG.

В СССР эти исследования поддерживались грантами от Государственного Комитета по Науке и Технике (ГКНТ) и от Министерства Энергетики (МинЭнерго). Доступ к наиболее современным компьютерам был обеспечен Вычислительным Центром Госплана СССР (ГВЦ Госплана), Всесоюзным Научно-Техническим Информационным Центром (ВНТИЦ) и Вычислительным Центром Коллективного Пользования "Здравоохранение" при Правительстве Москвы (ВЦКП "Здравоохранение"). Много лет дружественная атмосфера интереса и поддержки Всесоюзного Научно-Исследовательского Института Электроэнергетики (ВНИИЭ) помогала мне в развитии LG.

В Канаде и затем в США эти исследования на различных этапах поддерживались Национальным Научно-Исследовательским Советом Канады (NSERC) и Мак-Гилльским Университетом, Канада, Офисом Научных Исследований ВВС США (AFOSR), Летней Профессорской Стипендией Лаборатории Военно-Воздушных Сил им. Филипса (Air Force Phillips Laboratory), грантами от Министерства Энергетики через Сандийскую Национальную Лабораторию (Sandia National Laboratories), а также Исследовательскими Стипендиями Университета Колорадо в Денвере.

В настоящее время, эти исследования поддерживаются значительным грантом от Агентства Перспективных Исследований Министерства Обороны США (Defense Advanced Research Projects Agency — DARPA).

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

Что мы знаем о методах шахматного эксперта? Конечно, компьютер — это совершенный инструмент для распознавания и моделирования таких методов. История компьютерных шахмат началась со статьи профессора Клода Шеннона (1950), в которой он предложил общую схему для последующих разработок. Используя, главным образом, поиск решения по методу полного перебора (англ. «брут форс» — грубая сила), т.е. полагаясь, в конечном счёте, на быстродействие компьютеров, шахматные программы постепенно улучшили свой уровень игры (Ньюборн, 1996). В середине 90-х годов, они достигли уровня гроссмейстера. После исторического события в мае 1997 года, когда Дип Блю (Deep Blue — компьютерная шахматная система фирмы IBM) победила чемпиона мира по шахматам Гарри Каспарова, компьютерные шахматы потеряли свою захватывающую привлекательность. В июне 1997 года, профессор Джон Маккарти писал: “В 1965 году российский математик Александр Кронрод сказал, что «шахматы — дрозофила ИИ». Однако компьютерные шахматы разрабатывались так, как могло бы случиться с генетикой, если бы усилия учёных концентрировались, начиная с 1910 года, только на выведении быстрой дрозофилы. Но тогда мы всё же имели бы немного науки, хотя главным образом, мы получили бы очень быстрых плодовых мушек” (Маккарти, 1997).

Все самые большие успехи в компьютерных шахматах, включая триумф Дип Блю, были связаны с методом решения «брут форс». Сможем ли мы использовать какие-либо из этих результатов для решения других задач, особенно для задач, имеющих намного большую размерность? Вряд ли. Даже на суперкомпьютерах будущего, мы не сможем решать такие задачи по методу «брут форс». Метод гроссмейстера (т.е. почти без перебора ходов) пока ещё не раскрыт. После события 1997 года стало яснее, чем когда-либо прежде, что шахматы предназначены быть научной дрозофилой ИИ, а не только тестом для проверки скорости компьютеров (Маккарти, 1990, 1997).

Однако, не все исследования в компьютерных шахматах проводились в направлении поиска решений по методу «брут форс». В 70-х и 80-х годах в Москве (Россия) разрабатывался проект ПИОНЕР во главе с экс-чемпионом мира по шахматам профессором Михаилом Ботвинником. В своей книге (1984) Ботвинник писал, что метод решения «брут форс» “едва ли способен к дальнейшему прогрессу. Настала очередь принять компьютеру более плодотворный метод, возможно, ПИОНЕР. И, если ПИОНЕР неудачен, то мы должны быть уверены, что другой метод всё же будет найден. Задача должна быть и будет решена”.

LG — прямой преемник проекта ПИОНЕР. Дрозофила ИИ “летит через эту книгу, оплодотворяя различные эксперименты и генерируя новые идеи”.

Среди других примеров в этой книге мы рассматриваем ряд задач моделирования боя. Это — Рети-подобные задачи, т.е. обобщения знаменитого этюда Рети (Ботвинник, 1979, 1984). Здесь они — называются задачами 2D/4A, 3D/4A, с частично и полностью параллельным моделированием боя. Эти задачи достаточно просты, чтобы использоваться для демонстрации LG-подхода. С другой стороны, они всё-таки не тривиальны и требуют существенного перебора, если их решать с использованием традиционных подходов. Важно общее понимание того, что Рети-подобные задачи являются P-SPACE-полными или, по крайней мере, относятся к группе (или подклассу), так называемых, NP-сложных задач, т.е. таких, для которых не существует алгоритмов, приводящих к решению за полиномиальное время (Гэри и Джонсон, 1991).

Инструменты LG позволяют нам решать задачи из этого подкласса и многие другие задачи, используя алгоритмы полиномиальной сложности. Поэтому можно предположить, что Рети-подобные задачи являются представителями более широкого класса задач с низкой (полиномиальной) вычислительной сложностью (т.е. их можно рассматривать и как новый подкласс в группе P-TIME задач). Вероятно, многие важные задачи из реальной жизни, рассмотренные ниже, входят в этот подкласс (Рети-подобных задач).

Разработка новых технологий необходима для моделирования различных параллельных многоагентных систем типа операций наземного и воздушного боя, отслеживания и возможного перехвата ракет и спутников, разведывательных операций наблюдения и т.д. Беспилотные самолеты или танки могут участвовать в разведывательных миссиях или в полномасштабной боевой операции. Подобные отряды интеллектуальных транспортных средств могут участвовать и на стороне противника. Управление этими действиями требует постоянной адаптации к промежуточным результатам и динамическому пересчёту в режиме реального времени.

Ещё один пример — это задача управления в режиме реального времени воздушным боем, в котором группа самолётов (пилотируемых или беспилотных), оснащённых защитными средствами, уклоняется от группы преследователей, оснащённых ракетами. Другой пример — это задача оптимального управления беспилотными самолётами (UAV), которые барражируют в разведывательном полёте, чтобы определить местонахождение подвижных пусковых установок ракет. Фактические точки запуска ракет обычно обнаруживаются датчиками при помощи спутника. UAV используются для того, чтобы, зная координаты этих точек, найти подвижные установки и, по возможности, уничтожить их. В сценарии из реальной жизни управление UAV нужно рассматривать вместе с воздушным боем, когда UAV уклоняются от преследующих их самолетов врага и, в свою очередь, продолжают поиск подвижных пусковых установок противника. Подобные задачи генерации и перепланирования боевых сценариев в режиме реального времени существенны также для морских и наземных операций.

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

Задачи моделирования космического боя, в общем-то, подобны другим задачам боевого моделирования. Однако, астродинамика космического корабля делает эти задачи значительно более сложными. Другой фактор — автономность транспортного средства. В то время как автономность наземных, морских и воздушных транспортных средств очень желательна, она просто необходима для космического корабля, особенно если он далеко от Земли. Моделирование и управление боем двух-трёх космических кораблей требует огромного количества вычислений. Задачи с ещё большим числом транспортных средств в вычислительном отношении неразрешимы (Шинар, 1990; Гарсия-Ортиз и др., 1993).

Другой класс задач связан с организацией работы интеллектуальных автоматов в индустриальной среде. Группы роботов перемещаются по заводу, комплектуют сборочные детали, подают их на сборочный конвейер и собирают изделие. В результате намеренно локализованного управления, роботы сотрудничают только в пределах своих групп. Различные группы конкурируют друг с другом за общие ресурсы, включая детали, пути движения, очерёдность сборки и т.д. Планирование этих действий требует огромного количества вычислений при использовании традиционных подходов.

Задачи конверсии программного обеспечения (ПО) требуют преобразования неструктурированных программ в объектно-ориентированное ПО, причём, иногда требуется, чтобы конечный результат такого преобразования был доказуемо правильной программой. Цель этой конверсии состоит в преобразовании неструктурированного оригинала, так называемого наследуемого ПО, в изделие, которое можно сопровождать (т.е. вносить в него изменения) в течение его жизненного цикла. Этот класс задач может быть сведен к задачам преобразования графа, где первоначальный граф представляет ПО, которое нужно конвертировать. Как правило, для этого используются системы переделки графов (graph-rewriting systems). В то время как ПО небольшого размера конвертируемо, попытка перейти к конверсии реального полномасштабного ПО сталкиваются с непреодолимыми вычислительными трудностями.

Задачи безопасности и целостности компьютерных сетей и проблемы кибервойны в Интернете недавно привлекли всеобщее внимание. Вопрос состоит в том, как защитить национальную компьютерную сеть от нападения миллиардов компьютерных вирусов и червей? Какие узлы и даже ветви должны быть отключены ("пожертвованы"), какие из них следует заново подключить ("оживить") путём активизации дубликатов, какие контрмеры должны быть приняты? Традиционный ответ на эту угрозу — локальная защита. Очевидно, что количество вычислений, необходимых для генерации стратегии для глобальной защиты делает эту задачу неразрешимой.

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

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

Задачи планирования ближних и дальних миссий, особенно для автономной навигации, управления космическим роботом (типа UAV), управления операциями космического боя, глобальной и локальной разведки и т.д. обычно описываются математически в форме дифференциальных игр уклонения от преследования. Классический подход, основанный на традиционной теории Дифференциальных Игр (Айзекс, 1965) недостаточен, особенно в случае динамических, многоагентных моделей (Лиров, Родин и др., 1988; Гарсия-Ортиз и др., 1993). Известно, что при классическом подходе существует небольшое количество дифференциальных игр, для которых построены точные аналитические решения. Есть ещё несколько классов дифференциальных игр, для которых численные решения могут быть получены за разумное время при весьма ограничивающих условиях. Однако каждая из этих игр должна быть типа "один против одного", что, естественно, далеко от реальных боевых сценариев. Кроме того, эти игры являются играми с "нулевой суммой", что не позволяют новому агенту "войти" в игру или некоторым агентам обеих сторон быть исключёнными. Другие трудности связаны с потребностью в трёхмерном (пространственном) моделировании с ограничениями на время жизни агентов или с одновременным участием разнотипных агентов, например, поверхностных, подводных или космических транспортных средств.

Следуя профессору Родину (Родин и др., 1987, 1988; Родин, 1988; Шинар, 1990) — это может быть реализовано с помощью дискретно-событийного моделирования Сложных Систем управления. Эти методы могут быть основаны на генерации состояний, имеющих геометрический смысл. Конечное дерево игры (ДИ) может быть получено путём дискретизации времени. Узлы дерева будут представлять состояния игры, в которых игроки смогут выбирать своё управление для каждого временного интервала. Также, можно будет определить ходы, соответствующие противоборствующим сторонам (включая одновременные действия). Таким образом, ветви дерева будут представлять последовательности ходов в пространстве игры, а сами задачи могли бы рассматриваться как проблемы планирования в ИИ. Главная трудность — комбинаторный взрыв дерева перебора (ДП). Согласно (Лиров, Родин и др., 1988) “...в случае игры с двумя самолетами задача оптимального выбора не является слишком трудной, так что исчерпывающий перебор в поисках лучшей модели может быть выполнен за разумное время. Однако проблема перебора начинает вызывать особое беспокойство, если вдруг все самолёты примут участие в игре одновременно или, в более сложном примере, когда другие объекты, например препятствия, могут быть введены в игру в будущем”.

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

Пусть коэффициент ветвления B — параметр, представляющий среднюю ширину ДП в каждом узле. Он показывает, сколько ветвей (ходов) в среднем должно выходить из каждого узла ДП. Например, в шахматных программах, использующих алгоритмы перебора по методу «брут форс», в каждом узле рассматриваются все возможные ходы (т.е. разрешённые в позиции шахматными правилами). Это означает, что мы должны генерировать ДП с числом узлов T, которое может быть рассчитано по формуле (1.2.1). В этом уравнении B — среднее число ходов из каждой позиции, L — глубина перебора (предполагается, что все ветви усечены до глубины L) и T — общее количество построенных позиций (узлов). Вычисление B основано на рассмотрении гипотетического ДП с глубиной всех ветвей равной L, общим количеством узлов равным T при постоянном числе потомков у каждого узла.

По определению (Нильсон, 1980; Рич и Найт, 1991) это постоянное число равно коэффициенту эффективного ветвления B и определяется как решение уравнения (1.2.1) для заданных L и T относительно B. Большие значения B соответствуют неизбирательному перебору. Очевидно, что большое значение B указывает на рост ДП по экспоненциальному закону с большим основанием степени. Алгоритмы, которые уменьшают B, особенно те алгоритмы, которые делают B близким к 1, нужно рассматривать как наилучшие, направленные "прямо" к цели, с минимальным ветвлением в других направлениях.

Используя уравнение (1.2.1) для значения T — общего количества узлов, которые фактически построены в процессе перебора и значение L — требуемой глубины перебора, мы можем вычислить коэффициент ветвления B для произвольного переборного алгоритма. Коэффициент эффективного ветвления B можно найти как аппроксимацию решения уравнения (1.2.2) относительно B. Это нелинейное уравнение и его можно решить различными методами, включая метод проб и ошибок.

Для уменьшения коэффициента ветвления были разработаны различные переборные алгоритмы типа динамического программирования и метода ветвей и границ. Для антагонистических игр двух игроков (типа шахмат) самые популярные алгоритмы — это различные алгоритмы перебора с формальным альфа-бета отсечением (Нильсон, 1980; Рич и Найт, 1991). Они реализованы в самых сильных шахматных программах, включая действующих и экс-чемпионов мира по компьютерным шахматам. Было доказано, что в лучшем случае алгоритм альфа-бета перебора может уменьшить число терминальных узлов в дереве перебора следующим образом (Слэйгл и Диксон, 1969; Кнут и Мур, 1975):

	2B L / 2 - 1 ,	если L — чётно,
	B( L+1) / 2 + B( L-1) / 2 - 1 ,	если L — нечётно.

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

Предположим, что произвольная шахматная позиция в среднем содержит примерно 40 ходов по правилам, тогда альфа-бета отсечение может уменьшить это число примерно до 6 (≈√40). Однако мы всё ещё имеем рост по экспоненциальному закону с очень большим основанием степени B=6 (т.е. коэффициентом ветвления). В результате, шахматные задачи, которые требуют глубокого перебора, например до глубины L=20 или больше ходов, требуют и огромного количества времени для получения решения. Даже специализированная программно-аппаратная система Дип Блю не способна преодолеть это препятствие (Хсу и др., 1990; Ньюборн, 1996, 1997). Эта массово-параллельная система из шахматных чипов специального назначения со скоростью вычислений до двухсот миллионов позиций в секунду не способна противостоять росту ДП по экспоненциальному закону с большим коэффициентом ветвления. В задачах из реальной жизни число альтернатив намного больше 40, в то время как требуемая глубина перебора может превышать сотни ходов. Даже суперкомпьютеры будущего не смогут произвести такое количество вычислений при использовании традиционных процедур перебора по методу «брут форс».

Один из основных подходов к сокращению перебора — это метод уменьшения размерности Сложной Системы путём её декомпозиции на меньшие подсистемы, используемый экспертами в различных областях. Процесс декомпозиции может быть применён рекурсивно, пока мы не получим группу базовых подзадач, которые можно рассматривать (в некотором смысле) независимо друг от друга. Всё это сродни планированию в присутствии подцелей, макрооператоров и абстракций (Корф, 1987; Тэйт, Хендлер и Драммонд, 1990). На каждом уровне декомпозиции мы можем применять абстракцию, т.е. первоначально игнорировать детали низкого уровня и сконцентрироваться на существенных особенностях задачи, а к деталям мы сможем вернуться позже. В некотором смысле, эксперты обычно устанавливают подцели (и достигают их), потому что они знают какую последовательность операторов (т.е. макрооператор) применить, чтобы дойти до следующей подцели. Идея абстракции при решении задач человеком была указана в работе (Пойа, 1945), позже она использовалась в версии Универсального Решателя Задач (GPS), предназначенной для планирования (Ньюэлл и Саймон, 1972). С тех пор подобные идеи были применены во многих системах в рамках формальных теорий линейного и нелинейного планирования (например, Сакердоти, 1974, 1975; Штефик, 1981; Чэпман, 1987; Кноблок, 1990; Георгев, 1990; Мак-Аллистер и Розенблит, 1991) или в рамках других подходов (Месарович и Такахара, 1989; Эльбас, 1991).

Реальные Сложные Системы обычно включают динамические процессы, которые не подконтрольны одиночному агенту. Решатель задач должен учитывать действия, неподконтрольные данному агенту, которые могут производиться последовательно или параллельно с его действиями. Различные теории планирования для многоагентных систем были предложены в работах (Аллен, 1984; Георгев, 1983, 1990; Мак-Дермот, 1985; Пелевин и Аллен, 1986). В частности, можно рассмотреть обобщённый тип события как множество последовательностей состояний, представляющее все варианты появления этого события во всех возможных ситуациях, которые могли бы включать и параллельные действия многих агентов. Один из возможных подходов — это аппроксимация параллельных действий с использованием взаимного чередования (одновременных ходов) или интерливинг-приближения (Георгев, 1983; Педнаулт, 1987). Мы используем аналогичное приближение в наших примерах в главах 3, 4, 5 и 6. Конечно, в рамках этого подхода нельзя моделировать одновременные события; для этого мы вводим истинный параллелизм (Штильман, 1995d, 1997a; Скисов и Штильман, 1997, 1998a, 1998b; и глава 6).

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

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

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

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

Лингвистическая Геометрия (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-сетей. Результат вывода — существенно уменьшенный перебор, который и приводит к решению задачи.

Классы задач, которые будут изучены — это задачи оптимального управления 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).

Рассмотрим связь между стратегиями Теории Игр и LG-стратегиями (в LG-системе из двух взаимодействующих суперагентов). Теория Игр появилась в 1930-х годах, например (Дж. фон Нейман и Моргенштерн, 1944; Оуэн, 1982) и описана в обширной литературе. Хороший обзор сделан в (Льюс и Райфа, 1957). Важный раздел Теории Игр посвящён моделированию экономического поведения. В этом разделе цели игроков сформированы с помощью функции выигрыша и требования максимизировать вознаграждение игрока. Хотя LG использует оценочную функцию, которая является формой вознаграждения, по духу LG всё же ближе к другому разделу Теории Игр, который был основан в работах (Гэйл и Стюарт, 1953) и называется теорией (бесконечных) игр 2-х лиц с полной информацией.

Цели игроков в играх 2-х лиц формулируются посредством множеств желательных вариантов действий, называемых победительными множествами. Выигрышная стратегия для игрока — это такое поведения, которое приводит игрока к победе независимо от того, как ведёт себя противник. Методы построения таких стратегий отличаются от методов Теории Игр, в которых моделируется экономика, тем, что они используют методы логики, алгебры и топологии в отличие от методов математического или функционального анализа и/или вариационного исчисления, применяемых в классической Теории Игр. Методы, подобные вариационному исчислению также используются в другом разделе Теории Игр, который называется Дифференциальными Играми (Айзекс, 1965) — раздел 1.2.

Игры Гэйла-Стьюарта (2-х лиц с полной информацией) были расширены до игр на графах в работах (А.Яхнис и В.Яхнис, 1993; Зейтман, 1994). Самая ранняя ссылка на игры на графах содержится в классических статьях по Теории Игр (Кун, 1953; Берж, 1957). В 1993-94 годах было сделано следующее расширение класса игр на графах, позволившее включить параллельные ходы, а также игры с более чем двумя игроками (В.Яхнис и Б.Штильман, 1995b). Введенный класс игр наиболее близок к абстрактным настольным играм (ABG) или Сложным Системам, которые моделируются LG-системой.

Цели игр на графах и цели в LG не идентичны, так как в рамках LG-подхода класс полезных стратегий шире, чем класс выигрышных стратегий. Интуитивно, специфические LG-стратегии можно рассматривать как стратегии типа "лучшие из возможных", а не как исключительно выигрышные стратегии. Действительно, часто LG-игры не имеют "детерминированной" выигрышной стратегии из-за параллельных ходов. В результате методы LG приводят к новым способам построения выигрышных стратегий. LG генерирует выигрышные стратегии на основе математических конструкций, которые были впервые введены в LG и приспособлены для формализации стратегий экспертов.

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

Как и в Теории Игр Гэйла-Стюарта, LG занимается поиском стратегии для обеих сторон (игроков), но вводит соответствующие определения на основе состояний LG-системы (или игры), а не на основе ДИ. В фокусе LG, тем не менее, оказываются эффективно вычисляемые стратегии. Это соответствует конструктивному подходу к обнаружению выигрышных стратегий в Теории Игр 2-х игроков Гэйла-Стюарта, впервые введенному Бухи и Ландвебером (1969) и продолженному Гуревичем и Харрингтоном (1982), А.Яхнисом и В.Яхнисом (1990, 1993), Мак-Нотоном (1993) и Зейтманом (1994). Близость целей последнего подхода к LG иногда проявляется в полном совпадении: речь идёт о тех случаях, когда в LG вычисляется доказуемо победная (ничейная) стратегия для игрока (глава 13). В других случаях, LG вычисляет стратегию, которая является хорошей, но может быть сложно или практически невозможно проверить, действительно ли эта стратегия является выигрышной для данного игрока. Алгоритмы Теории Игр, строящие выигрышные стратегии обычно практически неприменимы из-за экспоненциального (или ещё худшего) времени исполнения, в то время как LG-алгоритмы являются практическими и даже полиномиальными по времени (для подклассов задач).

Немного перефразируя, данное в Теории Игр, определение стратегии для игрока на ДИ, мы получим определение LG-стратегии, основанной на состояниях игры. Стратегия — это частичная функция на состояниях игры, которая генерирует ходы для этого игрока. Выигрышная стратегия игрока — это такая стратегия, которая удовлетворяет двум свойствам. Во-первых, стратегия определена в каждом состоянии, в которое игрок должен попасть, следуя ей, а также в состояниях, которые уже были сгенерированы с использованием этой стратегии, включая начальное состояние. Во-вторых, любые конечные последовательности ходов обеих сторон, сгенерированные выигрышной стратегией, приведут систему из начального состояния в целевые состояния для данного игрока, в то время как противоположная сторона может делать любые ходы, разрешённые правилами игры. Дальнейшие подробности об LG-стратегиях приведены в главе 13.

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

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

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

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

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

LG-стратегия должна заново построить LG-дерево в каждом состоянии, для которого вычисляется ход игрока. Если LG-стратегия вычисляет ход для игрока в состоянии S1, а следующий ход противника ведёт в состояние S2, то оба состояния будут содержать много общих структурных компонентов, потому что они отделены только двумя ходами: ход игрока и ответный ход противника, если мы рассматриваем последовательные игры. Для параллельных игр эти состояния разделены одним (параллельным) ходом. Таким образом, LG-алгоритм пытается построить LG-дерево для состояния S2, преобразовывая его из LG-дерева для состояния S1.

Можно считать, что LG-стратегия вычисляет ход для игрока, находящегося в состоянии S системы, построением подмножества графа всех переходов из одного состояния LG-системы в другое. Фактически, LG-алгоритм существенным образом использует информацию о порядке ходов. Вышеупомянутый граф, представляет все варианты, построенные LG-алгоритмом, при выборе очередного хода для игрока.

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

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

Также как в физике 17-го столетия, в области ИИ и, в частности в LG, важнейшие обобщения и крупнейшие достижения всё ещё впереди. Однако, весьма возможно, что их первые признаки уже рядом с нами. В этом отношении, было бы полезно оглянуться назад, обратившись к истории развития LG. Эта история может быть разделена на три этапа.

В конце 50-х годов в Москве Михаил Ботвинник, доктор электротехники и чемпион мира по шахматам, начал проводить научные исследования методологии лучших шахматистов. Десять лет спустя, эти исследования привели к революционным идеям в построении шахматных программ, которые моделируют игру гроссмейстеров. В начале 70-х, доктор Ботвинник организовал и возглавил исследования по проекту ПИОНЕР с автором этой книги, как ключевым разработчиком. Эти исследования проводились в Москве во Всесоюзном Научно-Исследовательском Институте Электроэнергетики (ВНИИЭ). Они финансировались ГКНТ СССР и Министерством Энергетики СССР. Цель исследования состояла в том, чтобы изучить и реализовать в виде компьютерных программ методологию лучших шахматистов, а так же экспертов в других областях, в решении переборных задач почти без перебора, и применить этот подход к широкому спектру сложных практических задач. Ряд эффективных алгоритмов был разработан в рамках проекта ПИОНЕР (Ботвинник, 1979, 1984). Были проведены многочисленные эксперименты для сравнения систем, основанных на начальной модели (ПИОНЕР) с системами, использующими другие подходы. Эксперименты показали, что многие из задач, которые были вовсе не разрешимы при других подходах, успешно решались прототипами будущих LG-систем. Кроме того, на тех задачах (где сравнение было возможно), новые системы работали значительно быстрее, чем системы при других подходах. Проект ПИОНЕР продолжался до конца 80-х годов. Период времени 1958-1988 годов, заполненный предварительными разработками и обширными экспериментами в рамках проекта ПИОНЕР, можно рассматривать как первый этап развития LG (разд.1.7).

Многократные попытки формализовать и, по возможности, обобщить эвристики, обнаруженные в ходе проекта ПИОНЕР, столкнулись с огромными трудностями. Эти попытки, начавшиеся в середине 70-х годов, были вызваны настоятельными требованиями многих учёных, которые хотели, чтобы результаты этого проекта оказались применимы в других проблемных областях. Другая цель состояла в том, чтобы понять фундаментальную природу результатов, применить формальный подход и теоретически оценить качество, полноту и вычислительную сложность алгоритмов, разрабатываемых в ходе проекта ПИОНЕР. Трудности были связаны с необычной природой эвристик, присущих построенной модели. В частности, математические средства, которые следовало применить для формализации, должны были отразить иерархическую и динамическую структуру модели, существенную гибкость подсистем, должны были допускать глобальное и эффективное управление как отдельно взятой подсистемой, так и всей иерархией подсистем. Разработку Иерархии Формальных Языков, как основу математической модели эвристических алгоритмов проекта ПИОНЕР, выполненную автором этой книги, можно рассматривать как второй этап истории развития LG (разд.1.8). Первые результаты были получены в 1979 году, но разработка продолжалась вплоть до 1990 года в Москве во ВНИИЭ, а позже во Всесоюзном Научно-Исследовательском Геологоразведочном Нефтяном Институте (ВНИГНИ). Эти исследования финансировались в рамках проекта ПИОНЕР и из других источников.

1990-й год — это начало третьего этапа развития (разд.1.9), когда LG определилась как самостоятельная область исследований в ИИ. Этот этап начался в Мак-Гилльском Университете, в Монреале, Канада. С сентября 1991 года и до настоящего времени, он продолжается в Университете Колорадо в Денвере, США. В 90-х годах, предварительная математическая модель была унифицирована и обобщена (Штильман, 1992-1998). Поскольку формальная лингвистика и геометрия операционной области и подсистем, были использованы совместно, новая перспективная модель была названа Лингвистической Геометрией (LG) в 1991 году. Ретроспективно, мы будем использовать название LG при ссылках на предварительные исследования и результаты (этапы 1-й и 2-й). Цели исследований на 3-м этапе включали разработку прочного теоретического фундамента, оценку вычислительной сложности классов задач, допускающих LG-подход, оценку точности решений, получаемых при использовании LG-инструментов, расширение применимости LG к новым проблемным областям для разработки эффективных LG-приложений, а также создание программного прототипа универсального LG-testbed (испытательного стенда) — среды для разработки и отладки приложений LG в разнообразных проблемных областях.

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

Вероятно, несколько важных событий, имевших место в 1999 году, включая публикацию этой книги и значительный грант от Агентства Перспективных Исследований Министерства Обороны США, помогут в развитии теории и разработке программных приложений LG для решения задач из реальной жизни. Возможно, эти события знаменуют начало нового четвертого этапа в развитии LG.

Первые десять лет исследований, начиная с 1958 года, закончились публикацией книги "Алгоритм игры в Шахматы" (Ботвинник, 1968, 1970). В то время как математическое описание алгоритма было ещё недостаточным для программирования (и, возможно, несколько сомнительным), основные принципы сокращения перебора заложили прочный фундамент для дальнейшего развития. Другая публикация "Блок-схема Алгоритма игры в Шахматы" (Ботвинник, 1972) уже может рассматриваться как официальное начало проекта ПИОНЕР. К сожалению, обе вышеупомянутые публикации не включали ничего кроме идей и набора блок-схем для низкоуровневых процедур алгоритма. Собственно алгоритм и программу шахматный игры ещё только предстояло разработать.

Группа исследователей, занятых в этом проекте, имела два предмета научных исследований: выдающихся экспертов (подобно самому Ботвиннику) и компьютерные программы (после того как они были разработаны). Эти программы включали шахматную программу ПИОНЕР 1.x и множество программ ПИОНЕР 2.x — 4.x для планирования народного хозяйства СССР и составления графика ремонтов. Взаимосвязи между этими предметами исследований приводили к постоянному пересмотру наших взглядов и к многократной перестройке алгоритмов и программ. Много старых и новых идей были проверены в ходе проекта ПИОНЕР. Например, идея Траекторий, ограниченных горизонтом, и идея о декомпозиции Сложной Системы в динамическую иерархию подсистем доказали свою важность с самого начала. Этого не произошло с подсистемой второго уровня — Сетью Траекторий. Определенная первоначально, как ключевая область боя, а позже как Зона (в многочисленных версиях) и как Цепочка фигур, эта подсистема прошла множество существенных и менее значительных изменений. Эвристические алгоритмы для генерации подсистем первого и второго уровня — Траекторий и Зон — были представлены в (Штильман, 1975, 1977, 1979, 1984a). Подобные проблемы возникали и с подсистемами высокого уровня, и с алгоритмом глобального управления, позже формализованным как Грамматика Переводов.

К концу 1976 года первая версия шахматной программы ПИОНЕР был закончена. Она была проверена на решении шахматных этюдов. Конечно, цель состояла не только в том, чтобы решить эти этюды. При решении нужно было получить дерево перебора, близкое к тому, которое строит шахматный мастер. Что касается точности, то получаемые решения никогда не рассматривались как оптимальные. Кроме того, для огромного большинства этюдов оптимальные решения до сих пор неизвестны. Доказательство оптимальности при использовании традиционных алгоритмов типа «брут форс» требует огромного перебора, который часто превышает возможности любых компьютеров (разд.1.2). То, что обычно называют решением — это вариант (или несколько вариантов), которые признаны экспертами. Более глубокое понимание оптимальности и его роли в LG пришло намного позже на 3-м этапе развития LG (разд.1.9 и глава 13).

Первые два этюда, отобранные для тестирования программы ПИОНЕР — этюд Рети и этюд М.Ботвинника-С.Каминера, считаются простыми для шахматиста. Однако эта простота скрыта за миллионами ходов в дереве перебора, которые должны быть проанализированы при поиске решения по методу «брут форс». Конечно, шахматный эксперт способен избежать этого множества вычислений. Во время экспериментов с ПИОНЕРом оценивалось множество параметров, включая коэффициент ветвления (разд.1.2), а также некоторые другие параметры перебора (Ботвинник, 1979, 1984). Дерево перебора, построенное ПИОНЕРом в январе 1977 года при решении этюда Рети, содержало 54 хода (T=54). Следовательно, принимая во внимание, что глубина перебора, необходимого для решения этой задачи должна быть не меньше L=6, мы получили коэффициент ветвления B≈1,68 (1.2.2). Деревья перебора, построенные традиционными шахматными программами для этого этюда, включают приблизительно 106 ходов. В этюде Ботвинника и Каминера (Ботвинник, 1979, 1984), общее количество ходов, включённых в перебор, было равно 145, максимальная глубина L=12 и B≈1,35. Хотя оба этюда могут быть решены традиционными шахматными программами, эти результаты были очень интересны из-за существенного уменьшения коэффициента ветвления. Одна из этих задач, этюд Рети, продолжает служить моделью для далеко идущих обобщений в LG (главы 3, 4, 6, 13 и 14).

Среди разнообразных сложных задач, решённых ПИОНЕРом, мы обсудим ещё две. Обе задачи до сих пор не могут быть решены традиционными шахматными программами. Алгоритмы перебора с альфа-бета отсечением (разд.1.2) не в состоянии обеспечить существенное уменьшение коэффициента ветвления. Поэтому время, требуемое для расчёта, оказывается немыслимым.

Первая задача — этюд Г.Надареишвили (Надареишвили, 1976; Ботвинник, 1979, 1984). Он был решён ПИОНЕРом в августе 1977 года. Общее количество построенных узлов было T=200, в то время как глубина перебора, требуемого для нахождения решения L=25. Следовательно, B≈1,14. Неуменьшенный коэффициент ветвления для алгоритмов типа «брут форс» здесь можно оценить как B≈15. Решение этого этюда продемонстрировало мощь эвристической модели, на которой основан ПИОНЕР. Динамическая иерархия подсистем, Траекторий и Сетей, позволила нам найти очень глубокое решение почти без ветвления. Конечно, это было всего лишь решение, одобренное экспертами. Тогда никто не поднимал вопроса об оптимальности или хотя бы о точности этого решения. Теперь, 20 лет спустя, мы можем предположить, что это — математический оптимум. Разумно ожидать, что это будет доказано при использовании идей беспереборного подхода в LG (глава 13) в ближайшем будущем. Этюд Надареишвили также послужил образцом для множества обобщений, включенных в эту книгу (глава 5).

Вторая сложная задача — это позиция в середине игры из легендарной партии М.Ботвинник и Х.Р.Капабланка, сыгранной в 1938 году на АВРО-турнире (Голландия)(Ботвинник, 1984a). Эту шахматную комбинацию обычно рассматривают как бессмертный пример выдающегося шахматного мастерства. Начальная позиция содержит 19 фигур, а неуменьшенный коэффициент ветвления можно оценить как B≈20. Глубина перебора для этой задачи не должна быть меньше, чем 23. В апреле 1980 года программа ПИОНЕР построила дерево перебора из 40 узлов с коэффициентом ветвления B≈1,05 (Ботвинник, 1980a, 1980b, 1982, 1987). Решение, найденное ПИОНЕРом, было точно таким же, как и вариант в той партии 1938 года. Вероятно, это решение является доказуемо оптимальным.

В 1981-1988 годах, все исследования и программные разработки по проекту ПИОНЕР проводились при помощи системы поддержки разработки программ, называвшейся РАБОЧИМ МЕСТОМ ПРОГРАММИСТА (PROGRAMMER'S WORKBENCH — PW), (Штильман, 1994f). Система PW была разработана Мирным, Ройзнером, Чудаковым и Штильманом (1986), и позже переработана и расширена Мирным, Чудаковым и Штильманом (1988). PW была предназначена для того, чтобы поддержать параллельную разработку и конфигурацию программного обеспечения (ПО) для крупномасштабных научно-исследовательских работ. ПИОНЕР и другие сложные проекты включали расширенный период опытной эксплуатации образцов (прототипов) ПО. В основном, компьютерные программы использовались как инструменты для научных исследований и перестройки сложных алгоритмов. Полный цикл жизни компьютерных программ рассматривался как последовательность прототипов. Каждый прототип должен был быть чрезвычайно гибким, чтобы обеспечить многократное перепроектирование. PW поддерживала многократные итерации при перестройке изменяющихся прототипов благодаря жесткому универсальному каркасу версий ПО. Дополнительно, PW эффективно автоматически поддерживала взаимодействие разработчиков в проекте ПИОНЕР, обеспечивая независимость проектировщиков PW от остальных сотрудников (пользователей PW) и одновременно поддерживая строгую дисциплину коллективных разработок. Хотя язык Dijkstra (Дейкстра, 1976; Грис, 1983; Штильман, 1994f) был входным языком (транслятора), полностью реализованным в PW, фактическая разработка (включая отладку) проводилась с использованием проблемно-ориентированного языка очень высокого уровня. PW позволила нам создавать, расширять и поддерживать различные версии этого языка и для других проблемных областей. PW была реализована на IBM 370/144 — оригинальном американском компьютере, на котором в эти годы и велась разработка ПИОНЕРа. Позже, PW инструменты использовались в нескольких НИИ на советских ЭВМ для разработки и поддержки крупномасштабных проектов в области Искусственного Интеллекта. Инструменты PW были подготовлены к модернизации для поддержки объектно-ориентированного программирования.

Проект ПИОНЕР закончился разработкой одной из самых интересных и мощных эвристических моделей, основанной на эвристических сетях. Применение разработанной модели к шахматной игре было полностью реализовано в виде программы ПИОНЕР 1.x (Ботвинник, 1979, 1982, 1984, 1987, 1989). Аналогичная эвристическая модель была также реализована для долгосрочного календарного планирования в виде набора программ ПИОНЕР 2.x, 3.x, 4.x. Они использовались для составления графика ремонтов электроагрегатов, для сглаживания графика потребления мощности и для планирования народного хозяйства в прежнем СССР (Штильман, 1985a, 1993a). Эти модели (Штильман, 1976c, 1977, 1979, 1994a; Ботвинник, 1968, 1972, 1975, 1979, 1989), (Резницкий и Штильман, 1983; Резницкий, Бордюгов и Штильман, 1983), (Ботвинник и др., 1983; Ботвинник, 1989), (Штильман, 1978, 1985b, 1985c, 1993d) были представлены в форме идей, правдоподобных рассуждений и работающих программ.

Эксперименты с программами составления графика ремонтов ПИОНЕР 2.x продемонстрировали преимущества нового подхода. Программа ПИОНЕР 2.1 для составления месячного графика ремонтов электроагрегатов генерировала различные графики с коэффициентом ветвления, не превышающим 1,06, что составляло 50..100-кратное уменьшение этого коэффициента по сравнению с методом «брут форс» (Резницкий и Штильман, 1983; Штильман, 1985a). Эксперименты с программой ПИОНЕР 2.2 по составлению годового (на период в 365 дней) графика ремонтов электроагрегатов также продемонстрировали уменьшение коэффициента ветвления до величины близкой к 1. В отличие от ПИОНЕРа 2.1, эта программа была способна максимизировать число электроагрегатов, включённых в график ремонтов, регулируя продолжительность ремонта этих агрегатов. Особые качества были продемонстрированы программой ПИОНЕР 2.3, которая генерировала годовые графики ремонта агрегатов, регулируя значения резерва мощности. Небольшие вариации резерва мощности (в пределах диапазона 6%) позволяли этой программе включать в план ремонта все электростанции, которые подали заявки. Самые интересные результаты в составлении графика ремонтов были получены программой ПИОНЕР 2.4 для составления годового графика с распределением многочисленных ресурсов, включая различные типы ремонтного персонала. Такая постановка задачи приводила к существенному росту коэффициента ветвления; программа сумела уменьшить этот коэффициент до 1,005. Это позволило генерировать высококачественные годовые графики ремонтов для Единой Энергосистемы бывшего СССР. Применение LG к календарному планированию и дополнительная информация о программах составления графиков ремонта представлены в главе 7.

Программы ПИОНЕР 3.1 и 3.2 позволяли сглаживать еженедельные графики потребления мощности, сдвигая выходные дни для различных потребителей. Они уменьшили максимумы потребления мощности на 3,5% при уменьшении числа потребителей со сдвинутыми выходными (Ботвинник и Мирный, 1983).

Главным достижением модели ПИОНЕР в применении к не шахматным областям была разработка программ ПИОНЕР 4.1 и 4.2 для планирования народного хозяйства СССР на периоды в 15 и 25 лет соответственно. Эти программы балансировали продукцию государственной промышленности и бюджет, основываясь на агрегированной модели, включавшей 18 отраслей народного хозяйства (Резницкий, 1987; Ботвинник, 1989).

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

Что было общего в этих иерархиях? Какие формальные средства могли бы быть использованы, чтобы отразить эту общность и применить её в других проблемных областях?

В 1979-1990 годах была разработана первая версия формальных инструментов для LG (рис.1.5). История получения этих результатов — поучительна. Было ясно, что математические инструменты должны быть дискретными, символическими и должны отражать динамическую иерархию подсистем. Более точно эти требования описаны ниже.

Математические инструменты должны отражать постановку задачи как системы локальных агентов и их местоположений. Агенты разделяются на две стороны с противоположными интересами. Агенты могут перемещаться, изменяя свои местоположения — пункты. Некоторые из пунктов остаются свободными от агентов, но могут быть заняты ими позже. Ход делается в течение одного временного интервала. Все интервалы должны быть равны по времени. Также, агенты должны иметь чёткие правила, ограничивающие их движения. Функционирование системы можно представить как вариант, состоящий из последовательности ходов. Каждый вариант может сравниваться с другими возможными вариантами. Решение задачи — это вариант, выбранный среди всех по некоторому критерию оптимальности. Типичная трудность такого выбора связана с числом возможных вариантов и, следовательно, с продолжительностью требуемого перебора. Весьма часто, для задач из реальной жизни, время перебора возрастает так сильно, что они становятся практически неразрешимыми.

Формализация постановки задачи в том виде, как она описана выше, не представляла трудности. Этот класс задач мог быть формально представлен с использованием многочисленных уже существующих методов, причём все они эквивалентны. Однако, важно, чтобы выбранное формальное представление постановки для класса задач соответствовало формальному представлению метода, который использовался при решении этих задач, т.е. LG-подходу. Это представление должно было стать основой и математической средой для формального представления динамической иерархии подсистем. Формальная постановка задачи (глава 2) была разработана, следуя известным теориям формального решения задач и планирования, разработанным в статьях (Маккарти и Хайеса, 1969; Файкса и Нильсона, 1971; Сакердоти, 1975; Маккарти, 1980; Нильсона, 1980 и в других), которые основаны на исчислении предикатов 1-го порядка. Основная идея этой формализации была заимствована из системы STRIPS, разработанной Файксом и Нильсоном (1971).

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

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

Более высокие уровни иерархии — это Сети Траекторий (вместе с их агентами). Каждая Сеть Траекторий должна иметь конечную цель с определенным местоположением, т.е. конечным пунктом назначения. Множество сетей должно включать Зоны нападения, Зоны доминирования, Зоны отступления и т.д. Каждая сеть должна включать агентов, участвующих в достижении конечной цели. Это участие является двойным. Агенты одной стороны преследуют свою цель, перемещаясь, защищая друг друга и уничтожая врагов. Агенты другой стороны подобными же действиями стараются препятствовать противнику в достижении его цели. Агент может участвовать во многих сетях одновременно. Движения агентов организованы с учётом времени. Например, если агент имеет достаточно времени, чтобы пройти по траектории и перехватить агента противоположной стороны, то эта траектория включается в сеть и движение по ней разрешается. Если дело обстоит не так, то траектория отбрасывается. При перемещении агентов в другие пункты часть траекторий и пучков траекторий сети застывает, когда движение агентов по ним уже не имеет смысла относительно конечной цели. Это может быть связано с недостатком времени, конфигурацией состояния (позицией) или с другими причинами. Вычисление времени и других параметров, связанных с построением и реконструкцией сети, производится для каждой сети независимо друг от друга. Связи с другими сетями при этом игнорируются. Сети могут быть связаны друг с другом, если конечная цель одной из них становится главной целью объединенной сети, тогда цели других сетей-компонентов подчиняются главной цели.

В 70-х годах многие из известных математических инструментов были пересмотрены и отброшены. Обычно, они не отражали явно иерархию подсистем или не обеспечивали достаточную гибкость для представления их динамичности. Например, эти недостатки свойственны представлению траекторий и сетей в виде графов. В этой связи лингвистическое представление также рассматривалось в качестве кандидата. Действительно, траектория — это конечная последовательность запланированных ходов агента, в то время как слово — это конечная последовательность символов. Кажется, разумным представить траектории как формальные слова, составленные из символов. В этом случае множество траекторий можно представить как формальный язык. Но как с помощью языков представить иерархии? К нашему удивлению мы поняли, что лингвистическое представление иерархий является и наиболее естественным. Действительно, множество динамических подсистем можно представить как иерархию формальных языков, в которой каждое предложение — группа слов языка более низкого уровня — соответствует слову в высокоуровневом языке. Это стандартная процедура на нашем естественном языке. Например, фраза: "Человек, который преподаёт студентам", вводит иерархию языков. Символы языка низкого уровня могут включать все слова кроме слова "профессор". Высокоуровневый язык мог бы быть тем же самым языком, но дополненным ещё одним словом "профессор", которое является просто кратким обозначением для фразы "человек, который преподаёт студентам". Следует отметить, что иерархическая архитектура естественных языков и аналогичный подход, принятый в LG, — это примеры общего семиотического механизма мультирезолюций (иерархии моделей разного разрешения), введенного позже А.Майстелом (Майстел, 1996a, 1996b).

Оставался ключевой вопрос о том, какие языки следует использовать для этой модели? В течение 50-70-х годов, формально-синтаксический подход к исследованию свойств естественного языка привёл к быстрому развитию теории формальных языков (Хомский, 1963; Гинсбург, 1966; Хопкрофт и Ульман, 1979 и другие). Это развитие предоставило интересную возможность для распространения лингвистического подхода в другие области. В частности, возникла идея об аналогичном лингвистическом представлении физических образов (рис.1.5). Эта идея была успешно разработана и воплощена в синтаксических методах распознавания образов (Нарасимхан, 1966; Фу, 1974, 1982; Павлидис, 1977) и языках описания изображений (Шоу, 1969; Федер, 1971; Розенфельд, 1979). Плекс-языки, введеные в (Федер, 1971), продемонстрировали значительную описательную мощь. В обычной строке символов каждый символ связан только с двумя соседями — левым и правым. Поэтому он имеет две точки сцепления. В Плекс-языке символ называется NAPE (n Attaching-Point Entity, т.е. n-связанный объект) и может иметь произвольное число n-точек сцепления для соединения с другими символами. Результирующие слова представляют общие многомерные образы, которые позволяют генерировать образы, представляющие деревья, сложные химические формулы, электрические схемы и т.д. Нечто аналогичное можно было бы сделать в LG с Траекториями и Сетями.

В поисках адекватных математических инструментов, формализующих эвристику, мы преобразовали идею лингвистического представления сложных естественных и искусственных образов в идею аналогичного представления сложных иерархических систем (Штильман, 1981, 1984b, 1985a, 1985b, 1985c, 1992). Однако соответствующие языки должны были бы иметь более изощрённые и гибкие атрибуты, чем языки, обычно используемые для описания образов. Происхождение таких формальных языков можно проследить ретроспективно, начиная с исследований программируемых и атрибутных грамматик (Кнут, 1968; Розенкранц, 1969 и прочие). В этом отношении, особого внимания заслуживают результаты Н.Волченкова (1979) и Л.Кузина (1979). Волченков разработал исключительно мощные порождающие (генерирующие) грамматики, которые он называет БУППГ. Модификация и обобщение этих грамматик (Штильман, 1993a, 1993b) позволили нам построить языки, которые удовлетворяли всем требованиям для представления динамических иерархий. Эта модификация, названная управляемыми грамматиками (глава 8), позволила использовать их как универсальный инструмент на всех уровнях LG, формально доказывать правильность и полноту построенных языков, оценивать вычислительную сложность их порождения (главы 8-12 и 14). Новая версия управляемых грамматик рассмотрена в (В.Яхнис, А.Яхнис и Б.Штильман, 1996, 1997).

До третьего этапа развития LG, в начале 90-х годов, формальные инструменты ещё не были организованы в полномасштабную математическую модель. Развитие программ ПИОНЕР на втором этапе было основано на наборе эвристических алгоритмов. Многократные эксперименты с этими программами позволили сделать далеко идущие обобщения и позднее построить математическую модель.

С 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). Эта формулировка позволила нам решить задачи высокой размерности, которые были неразрешимы при использовании традиционных подходов.