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

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

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