Часть 5.

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

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

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

В работе [Williams и Nayak, 1996] управление автономной системой осуществляется с помощью реактивного диспетчера конфигурации и планировщика высокого уровня. Планировщик (раздел 7.4) генерирует последовательность целей по реконфигурации системы. Диспетчер конфигурации отслеживает переходы системы (в нашем случае - системы двигателей космического корабля) вдоль желаемой траектории. Таким образом, управление конфигурацией осуществляется посредством наблюдения и управления переходами между состояниями системы.

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

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

298 Часть III. Представление и разум в ракурсе искусственного интеллекта

В следующем разделе будут рассмотрены рассуждения на основе опыта - прием, позволяющий использовать прошлый опыт работы в данной предметной области в новых ситуациях. В разделе 7.4 представлены вопросы планирования и снова рассмотрен пример системы, разработанной NASA.

7.3.3. Введение в рассуждения на основе опыта

Эвристические правила и теоретические модели - вот два типа информации, которые человек-эксперт использует для решения проблем. Еще одной мощной стратегией, используемой экспертами, является рассуждение на основе опыта решения задач. В рассуждениях на основе опыта для решения новых проблем используется детальная база данных, содержащая известные решения задач. Эти решения могут быть собраны экспертами в области знаний или могут отображать результаты предыдущих успешных и неудачных попыток поиска решения. Например, медицинская диагностика основывается не только на теоретических моделях болезней, анатомии и физиологии, но и на изучении истории болезни и врачебного опыта, приобретенного при лечении других пациентов. Системы CASEY [Koton, 1988a, 19885] и PROTOS [Bareiss и др., 1988] являются примерами рассуждений на основе опыта в медицине.

Юристы тоже подыскивают прецеденты и пытаются убедить суд, что нужно действовать по аналогии с известной ситуацией. Хотя общие законы вырабатываются в рамках демократических процессов, их интерпретация обычно основана на прецедентах. Интерпретация закона в некоторой предыдущей ситуации определяет его текущую интерпретацию. Таким образом, важным компонентом правовых рассуждений является идентификация прецедента для принятия решения в конкретном случае. В работах [Rissland, 1983] и [Rissland и Ashly, 1987] предложены механизмы рассуждений на основе опыта, предназначенные для поддержки правовых споров.

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

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

Глава 7. Сильные методы решения задач 299

часто приходят на ум неудачи прошлого. Хорошим примером этого является также диагностика аппаратных средств. Эксперт в этой области для решения текущей проблемы помимо использования богатых теоретических знаний по электронике и механическим системам учитывает успехи и неудачи прошлого. Рассуждения на основе опыта составляют важный компонент многих диагностических систем, включая системы диагностики спутникового оборудования [Skinner и Luger, 1992] и анализа неисправностей полупроводниковых компонентов [Stern и Luger, 1997].

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

Подходы к таким рассуждениям позволяют экспертной системе учиться на своем опыте. После решения задачи путем поиска система может сохранить это решение, чтобы воспользоваться им при возникновении подобной ситуации (без привлечения поиска). Важно запоминать информацию как об успешных, так и о неудачных попытках решения. Таким образом, рассуждения на основе опыта являются мощным средством для обучения. Одним из первых примеров таких систем является программа для игры в шашки [Samuel, 1959] (см. подраздел 4.3.2), где важные позиции на доске, найденные посредством поиска или эксперимента, запоминались для последующего использования.

Механизм рассуждения на основе опыта функционирует следующим образом.

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

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

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

Сохраняет успешное или неудачное решение для дальнейшего использования.

Сохранение новых случаев требует адаптации индексной структуры. Существуют специальные методы поддержки индексов. К ним относятся алгоритмы кластеризации [Fisher, 1987] и другие приемы машинного обучения [Stubblefield и Luger, 1996].

300 Часть III. Представление и разум в ракурсе искусственного интеллекта

Дня реализации рассуждения на основе случая могут потребоваться специальные структуры данных. В простейшей ситуации случаи запоминаются как кортежи отношений, где одни аргументы описывают сопоставляемые признаки, а другие - этапы решения. Случаи могут представляться и более сложными структурами, такими как деревья вывода. Обычно случай запоминается как множество правил типа ситуация-действие. Факты, описывающие ситуацию, являются существенными признаками этого случая, а операторы, представляющие действия, описывают преобразования, используемые в новой ситуации. При использовании такого представления для организации и оптимизации поиска подходящих случаев могут применяться такие алгоритмы, как RETE [Forgy, 1982].

Наиболее трудным вопросом в решении проблем на основе опыта является выбор существенных признаков для индексирования и поиска ситуаций. В [Kolodner и др., 1993] при решении задач на основе случаев считается, что они должны быть организованы в соответствии с целями и потребностями решателя проблем. Это означает, что необходимо выполнить тщательный анализ дескрипторов ситуации в контексте того, как эти случаи должны быть использованы в процессе решения.

Например, рассмотрим проблему слабого коммуникационного сигнала на спутнике в момент времени 10:24:35 GMT. На основе анализа определяется, что, кроме всего прочего, система имеет низкую мощность. Низкая мощность может быть следствием того, что солнечные батареи неправильно ориентированы по отношению к Солнцу. Наземные контроллеры регулируют ориентацию спутника, мощность увеличивается, и коммуникационный сигнал снова становится сильным. Для записи этого случая можно использовать ряд существенных признаков. Наиболее важным из них является слабый коммуникационный сигнал или низкий ресурс мощности. Другой существенный признак - время возникновения проблемы (10:24:35). В соответствии с целями и потребностями решателя задач существенными признаками являются слабый коммуникационный сигнал и низкий ресурс мощности. Время события может не иметь никакого значения, за исключением случая, если поломка произошла именно после того, как Солнце скрылось за горизонтом [Skinner и Luger, 1995].

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

В работе [Kolodner, 1993] предлагается множество возможных эвристик для организации, хранения и поиска ситуаций. К ним относятся следующие.

Упорядочение на основе целей. Случаи систематизируются, по крайней мере частично, на основе описания цели. Выполняется поиск случаев, цель которых соответствует текущей ситуации.

Упорядочение по существенным признакам. Выбираются случаи, для которых

наиболее важные признаки (или большинство важных признаков) совпадают.

Предпочтение точных совпадений. Сначала рассматриваются все случаи точного

совпадения признаков, а затем более общие соответствия.

Частотное предпочтение. Сначала проверяются наиболее типичные случаи.

Предпочтение новизны. Предпочтение отдается случаям, которые использовались

последними.

Предпочтение легкости адаптации. Используются первые, наиболее легко адап

тируемые к текущей ситуации, случаи.

Глава 7. Сильные методы решения задач 301

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

Рассуждения на основе опыта поднимают ряд важных теоретических вопросов, относящихся к человеческому обучению и рассуждениям. Одним из наиболее острых и критических вопросов является определение степени подобия. Хотя меру подобия двух случаев можно описывать как функцию, зависящую от числа общих признаков, такое представление содержит ряд тонкостей. Например, большинство объектов и ситуаций имеют бесконечное число свойств. Однако механизм рассуждений на основе опыта, как правило, выбирает случаи из очень небольшого архива поиска, составляемого инженером по знаниям. Несмотря на некоторые исследования возможности решателя определять соответствующие признаки из своего собственного опыта [Stubblefield, 1995], определение информативности признаков остается сложной проблемой.

Другой важной проблемой, с которой сталкиваются специалисты при реализации рассуждений на основе опыта, является проблема компромисса между запоминанием и вычислением. По мере запоминания новых случаев механизм рассуждений становится все более интеллектуальным, способным лучше решать различные проблемы. Действительно по мере добавления в память новых случаев результаты рассуждений до некоторого момента будут улучшаться. Но по мере роста базы данных время, необходимое для поиска и обработки информации о прецедентах, тоже растет. Снижение эффективности для больших баз данных также может объясняться пересечением понятий и другими помехами. Одним из решений этой проблемы является хранение лишь "наилучших" или "прототипных" случаев и вычеркивание тех, которые являются избыточными или редко используемыми. Следовательно, система рассуждений должна забывать случаи, которые не доказали свою полезность. Примером ранних работ в этой области может служить алгоритм запоминания позиций на шашечной доске [Samuel, 1959]. Однако в общем случае не ясно, как можно автоматизировать такие решения. Это остается областью активного поиска [Kolodner, 1993].

Автоматизированные объяснения рекомендаций - еще один тип рассуждения на основе опыта. В ответ на вопрос, почему в данной ситуации рекомендуется принимать именно это лекарство, единственным объяснением системы является то, что именно это назначение было сделано в предыдущий период времени. Иногда используются объяснения, основанные на сходстве описаний текущей и предыдущей ситуаций. В примере задачи спутниковой коммуникации подходящий случай был выбран на основе слабого коммуникационного сигнала. Этот способ рассуждения тоже не обеспечивает более глубокого объяснения, чем то, которое было выработано ранее в подобной ситуации. Но зачастую этого может быть достаточно.

Однако многие исследователи убеждены, что простое повторение целей высокого уровня и используемых случаев является недостаточным объяснением [Leake, 1992], [Stern и Luger, 1992]. Вернемся к ситуации со спутником. Предположим, что переориентация солнечной батареи помогает улучшить качество сигнала, но через три часа сигнал снова становится слабым. Используя частотную эвристику и эвристику новизны, мы снова переориентируем солнечную батарею. Через три часа слабый сигнал повторяется. Каждые три часа мы используем одно и то же назначение. Этот пример основан на реальной ситуации, в которой была обнаружена более сложная причина, а именно: перегрелся гироскоп и давал искаженные данные об ориентации спутника. Окончательно решить

302 Часть III. Представление и разум в ракурсе искусственного интеллекта

проблему и определить причину слабого коммуникационного сигнала удалось лишь с помощью рассуждений на основе модели поведения спутника [Skinner и Luger, 1995].

Рассуждения на основе опыта обеспечивают обучение по аналогии. Для повторного использования прошлого опыта необходимо выделить существенные признаки прошлой ситуации и построить отображение, позволяющее применить этот опыт в текущей ситуации. Примером подхода к решению задач на основе опыта является трансформационная аналогия [Carbonell, 1983]. Новая задача решается путем модификации существующих решений до тех пор, пока их нельзя будет применить к данной ситуации. Операторы, которые модифицируют решение задачи, определяют абстракцию более высокого уровня, или Т-пространство, в котором состояниями служат решения задачи, подлежащие преобразованию (рис. 7.17). Целью является преобразование исходного решения в возможное решение поставленной проблемы. Для модификации решения можно его исключить, переупорядочить шаги в решении, соединить новые решения или изменить параметры в текущем решении. Трансформационная аналогия - типичный пример решения задач на основе опыта. Более поздние работы уточняют этот подход. В них рассматриваются такие вопросы, как представление случаев, стратегии организации памяти случаев, поиск подходящих ситуаций и использование их для решения новых задач. Более полная информация о рассуждениях на основе опыта содержится в [Hammond, 1989], [Kolodner, 1988a] и [Kolodner, 19886]. Исследования по аналогии рассматриваются далее в контексте машинного обучения на основе символов (см. подраздел 9.5.4).

7.3.4. Гибридные системы: достоинства и недостатки систем с сильными методами

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

Глава 7. Сильные методы решения задач 303

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

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

Рассуждения на основе правил

Преимущества этого подхода сводятся к следующему.

Возможность использовать знания экспертов в очень простой форме. Это важно в

областях, зависящих от эвристик управления сложной и/или отсутствующей ин

формацией.

Правила отображаются в пространство состояний поиска. Возможности объяснения облегчают отладку программ.

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

В ограниченных предметных областях возможны хорошие результаты. Поскольку

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

Хорошие возможности объяснения. Хотя системы на основе правил поддерживают

гибкие, проблемно-зависимые объяснения, необходимо отметить, что максимальное

качество этих объяснений зависит от структуры и содержания правил. Возможности

объяснения в системах, основанных на данных и на целях, сильно различаются.

Недостатки рассуждений, основанных на правилах.

Правила, полученные от экспертов, часто являются эвристическими по природе и

не охватывают функциональных знаний или знаний, основанных на моделях.

Эвристические правила обычно не являются робастными и не позволяют управлять

отсутствующей информацией или неожиданными значениями данных.

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

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

Знания являются проблемно-зависимыми. Формализованные знания о некоторой

предметной области, как правило, очень специфичны и применимы только к данной области. Современные языки представления знаний не обеспечивают гибкости, присущей человеку.

304 Часть III. Представление и разум в ракурсе искусственного интеллекта

Рассуждения на основе опыта

Преимущества рассуждений на основе опыта сводятся к следующему.

Возможность напрямую использовать исторический опыт. Во многих областях не

обходимую информацию можно получить из существующих исторических мате

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

Возможность сокращения рассуждений. Если известен аналогичный случай, новые

задачи решаются гораздо быстрее, чем при использовании правил или моделей.

Рассуждения на основе опыта позволяют избежать прошлых ошибок и использовать

прошлые успехи. Они обеспечивают модель обучения, как интересную с теоретической

точки зрения, так и достаточно практичную для применения в сложных ситуациях.

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

Соответствующие стратегии индексирования повышают эффективность решения

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

Рассмотрим недостатки рассуждений на основе опыта.

Описания случаев обычно не учитывают более глубокие знания о предметной области.

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

Большая база данных может привести к снижению производительности системы.

Трудно определить хороший критерий для индексирования и сравнения случаев.

Словари поиска и алгоритмы определения подобия необходимо тщательно отлаживать вручную. Это может нейтрализовать многие из преимуществ, присущих рассуждениям на основе опыта.

Рассуждения на основе моделей

Преимущества рассуждений на основе моделей сводятся к следующему.

Возможность использовать при решении задач функциональные и структурные

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

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

Некоторые знания можно использовать в разных задачах. Системы рассуждений на

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

Глава 7. Сильные методы решения задач 305

4. Обычно системы рассуждений, основанные на моделях, обеспечивают причинные объяснения. Таким образом пользователям можно передать более глубокое понимание причин неисправности, которое может сыграть важную образовательную роль (см. также раздел 16.2).

Недостатки рассуждений на основе моделей таковы.

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

важный класс экспертных оценок.

Необходимость точной модели предметной области. Знания из многих областей

имеют строгую научную основу, которую можно использовать в рассуждениях на

основе моделей. Однако во многих сферах, например, в некоторых медицинских

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

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

Исключительные ситуации. Необычные обстоятельства, например, замыкание или

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

Гибридные системы

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

Например, сочетание рассуждений на основе правил и опыта может обеспечить следующие преимущества.

Просмотр известных случаев до начала рассуждений на основе правил позволяет

снизить затраты на поиск.

Примеры и исключения можно сохранять в базе данных ситуаций.

Результаты поиска можно сохранить для будущего использования. При этом механизм рассуждений позволит избежать затрат на повторный поиск.

Комбинация рассуждений на основе правил и моделей открывает следующие возможности.

Объяснения дополняются функциональными знаниями. Это может быть полезно в

обучающих системах.

Повышается устойчивость системы при отказах. При отсутствии эвристических

правил, используемых в данном случае, механизм рассуждений может прибегнуть

к рассуждениям от исходных принципов.

Поиск на основе модели дополняется эвристическим поиском. Это может по

мочь в сложных рассуждениях, основанных на модели, и обеспечивает возможность выбора.

306 Часть III. Представление и разум в ракурсе искусственного интеллекта

Комбинация рассуждений на основе моделей и опыта дает следующие преимущества.

Более разумное объяснение ситуаций.

Проверка аналогичных случаев до начала более экстенсивного поиска посредством

рассуждений на основе моделей.

Обеспечение записи примеров и исключений в базу данных случаев, которые мо

гут быть использованы для управления выводом на основе модели.

Запись результатов вывода на основе моделей для будущего использования.

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

7.4. Планирование

7.4.1. Введение

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

В этом разделе будут использованы примеры из традиционной робототехники. (Современная робототехника, как указано в разделе 6.3, во многом основывается на реактивном управлении, а не на планировании.) Пункты плана определяют атомарные действия робота. Однако при описании плана нет необходимости опускаться до аппаратного уровня (или микроуровня) и говорить о таких деталях, как "поворот шестого шагового двигателя на один оборот". Планировщики описывают действия на более высоком уровне в терминах их воздействий на мир. Например, планировщик для робота из мира блоков может оперировать такими действиями, как "взять объект а" или "перейти в местоположение х". На таких планах высокого уровня строится управление действиями настоящего робота.

Например, для реализации пункта плана "принести блок а из комнаты б" требуется следующая последовательность действий.

Положить все, что есть в руке.

Пройти в комнату б.

Подойти к блоку а.

Взять блок а.

Выйти из комнаты б.

Вернуться в первоначальное местоположение.

Глава 7. Сильные методы решения задач 307

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

Задача планирования не зависит от существования реального робота. Изначально (в 1960-е годы) при решении задач компьютерного планирования полные планы формировались заранее, перед тем, как робот совершал свое первое действие. Таким образом, планы разрабатывались без наличия робота вообще! В последнее время благодаря реализации сложных механизмов восприятия и реагирования исследователи сфокусировались на более интегрированной последовательности план-действие.

Планирование зависит от методов поиска и поднимает ряд уникальных вопросов. Например, описание состояний мира может быть значительно сложнее, чем в предыдущих примерах поиска. Рассмотрим ряд предикатов, необходимых для описания комнат, коридоров и объектов в окружении робота. При этом необходимо представить не только мир робота, но и воздействие его атомарных действий на этот мир. Полное описание каждого состояния задачи может быть очень громоздким.

Другой отличительной особенностью планирования является необходимость характеризовать сложные неатомарные состояния и действия. Захват объекта означает изменение его местоположения и состояния руки робота (теперь она сжимает объект). При этом не изменяется местоположение дверей, комнат или других объектов. Описание того, что истинно в одном состоянии мира и изменяется при выполнении некоторого действия, называется проблемой границ [McCarthy, 1980], [McCarthy и Hayes, 1969]. По мере усложнения пространства состояний задачи вопрос поддержки истории изменений, связанных с каждым действием, и инвариантных признаков описания состояния становится все более важным. В этой главе будут представлены два подхода к проблеме границ, но, как показано ниже, ни один из них не является полностью удовлетворительным.

308 Часть III. Представление и разум в ракурсе искусственного интеллекта

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

В примерах этого раздела мы ограничим мир робота множеством блоков на поверхности стола и действиями руки робота, которая может поставить блоки один на другой, взять верхний блок и переместить блок в пределах стола. На рис. 7.18 показаны пять блоков а, Ь, с, d, е, установленных на верхней поверхности стола. Все блоки являются кубами одинакового размера. Некоторые блоки располагаются непосредственно друг на друге, образуя стеки. Рука робота имеет захват, который может схватить любой свободный блок (тот, который не имеет блоков на своей верхней грани) и переместить его в любое место на поверхности стола или на верхнюю грань любого другого свободного блока. Рука робота может выполнять следующие задания (U, V, W,X, Y и Z - переменные).

goto(X,Y,Z) Перейти в местоположение, описанное координатами X, Y и Z. Это

местоположение может быть неявно задано в команде pickup(W), где блок W имеет координаты X, У, Z.

pickup(W) Взять блок W из его текущего местоположения и держать его. Пред-

полагается, что блок является свободным, захват в это время пуст и компьютер знает текущее местоположение блока ИЛ

putdown(W) Опустить блок W в некоторой точке на столе. Записать новое местоположение для W. При выполнении данной задачи предполагается, что в данный момент блок W удерживается захватом.

stack(U,V) Поместить блок U на верхнюю грань блока V. При этом захват должен

держать блок U, и верхняя грань V должна быть свободна.

unstack(U,V) Убрать блок U с верхней грани V. Перед выполнением этой команды блок U должен быть свободен, располагаться на верхней поверхности блока V, и рука должна быть пустой.

Состояние мира описывается множеством предикатов и отношений между ними.

location(W,X,Y,Z) Блок W имеет координаты X, У, Z.

on(Х,Y) Блок X находится непосредственно на верхней поверхности блока Y.

clear(X) Верхняя грань блока X пуста.

gripping(X) Захват робота удерживает блок X.

gripping() Захват робота пуст.

ontable(W) Блок W находится на столе.

Запись ontable(W) является короткой формой предиката location(W,X,Y,Z), где Z - уровень стола. Предикат on(X,Y) указывает, что нижняя часть блока X находится на верхней грани блока Y. Если местоположение каждого блока и информация об их перемещении в новое место записаны в компьютере, то описание мира можно значительно упростить. При этом устраняется необходимость в команде, поскольку такие команды, как pickup(X) или stack(X), неявно содержат местоположение X.

Тогда мир блоков, показанный на рис. 7.18, может быть представлен множеством предикатов Состояние 1. Поскольку предикаты, описывающие состояние мира на рис. 7.18, являются истинными одновременно, полное описание состояния является конъюнкцией (л) всех этих предикатов. Состояние 1

ontable(a). on(b,a). clear(b).

Ontable(c). on(e,d). clear(c).

Ontable(d). gripping(). clear(e).

Глава 7. Сильные методы решения задач 309

Теперь для clear(b), ontable(a) и gripping() опишем ряд истинных отношений (в декларативном смысле) или правил выполнения (в процедурном смысле).

Согласно первому утверждению, если блок X свободен, то не существует блока Y, расположенного на верхней грани X. Процедурно его можно интерпретировать так: "Для освобождения блока X нужно убрать любой блок У, который может находиться на верхней грани X".

Теперь разработаем правила, воздействующие на состояния и приводящие к новым состояниям. С этой целью снова введем процедурную семантику для логического представления предикатов. Операторы (pickup, putdown, stack, unstack) определяются следующим образом.

Рассмотрим четвертое правило: для всех блоков X pickup(X) означает gripping(X), если рука пуста и блок X свободен. Отметим форму этого правила: А?(В?С). Это означает, что из А следует новый предикат В, если условие С истинно. Это правило можно использовать для генерации новых состояний в пространстве. Если предикат С является истинным, то в наследуемом состоянии В тоже является истинным. Другими словами, оператор А может быть использован для создания нового состояния, описываемого предикатом Б, если предикат С является истинным. Для создания этих операторов можно использовать и альтернативные подходы, описанные в подразделе 7.4.2, [Nilsson, 1980] и [Rich и Knight, 1991].

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

Эти правила означают, что предикат ontable инвариантен по отношению к операторам stack и unstack. Это истинно даже при идентичности X и Z; если же Y=Z, то одно из этих выражений не будет истинным.

Другие аксиомы границ сводятся к тому, что операторы stack и unstack изменяют значения предикатов on и clear лишь для некоторых параметров. Так, в нашем примере оператор unstack(c,d) не затрагивает значение on(b,a). Аналогично оператор

310 Часть III. Представление и разум в ракурсе искусственного интеллекта

gripping(Y) не затрагивает отношение clear(X), даже если X=Y или истинно выражение gripping(). Кроме того, оператор gripping затрагивает не отношение on(X,Y), a ontable(X), где X-удерживаемый блок. Таким образом, для нашего примера необходимо описать ряд аксиом границ.

Операторы и аксиомы границ определяют пространство состояний. Рассмотрим состояние, определяемое оператором unstack. Для выполнения оператора unstack(X,Y) должны выполняться три условия одновременно, а именно: on{X,Y), gripping() и clear(X). Когда эти условия выполняются, применение оператора unstack приводит к новым предикатам gripping(X) и clear(Y). Остальные предикаты, описывающие состояние 1, останутся истинными и в состоянии 2. Переход к состоянию 2 осуществляется посредством применения оператора unstack и аксиом границ к предикатам состояния 1.

Состояние 2

ontable(a). on(b,a). clear(b).

ontable(c). clear(c). clear{d).

ontable(d). gripping{e).clear(e).

Подведем итоги.

Планирование можно рассматривать как поиск в пространстве состояний.

Новые состояния определяются такими общими операторами, как stack и

unstack, и правилами границ.

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

На рис. 7.19 показан пример пространства состояний, в котором поиск выполняется с применением описанных выше операторов. Если к этому процессу решения задачи добавить описание цели, то план можно рассматривать как множество операторов, описывающих путь от текущего состояния этого графа к целевому (см. подраздел 3.1.2.).

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

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

7.4.2. Использование макросов планирования: STRIPS

Система STRIPS (современное название - SRI International) - это система планирования, разработанная в Стэндфордском исследовательском институте (Stanford Research Institute Planning System) [Fikes и Nilsson, 1971], [Fikes и др., 1972]. В

Глава 7. Сильные методы решения задач 311

начале 1970-х годов этот контроллер использовался для управления роботом SHAKEY. Система STRIPS решала проблему эффективного представления знаний и выполнения операций планировщика с учетом противоречивости подцелей и обеспечивала начальную модель обучения: успешные планы сохранялись и обобщались как макрооператоры, которые затем могли быть использованы в подобных ситуациях. В оставшейся части этого раздела описывается использованный в STRIPS подход к планированию и треугольные таблицы - структуры данных, используемые для организации и запоминания макроопераций.

В рассматриваемом примере с блоками четыре оператора pickup, putdown, stack и unstack описываются тройками элементов. Первым элементом тройки является множество предусловий (П), которым должен удовлетворять мир для применения оператора. Второй элемент тройки - список дополнений (Д) к описанию состояния, которые являются результатом применения оператора. И, наконец, список вычеркиваний (В) состоит из атомов, которые удаляются из описания состояния после применения оператора. Эти списки исключают необходимость использования отдельных аксиом границ. Рассматриваемые операторы можно представить следующим образом.

312 Часть III. Представление и разум в ракурсе искусственного интеллекта

Важной особенностью списков добавления и вычеркивания является то, что они описывают аксиомы границ. Подходу, основанному на списках добавления и вычеркивания, присуща некоторая избыточность. Например, в операторе unstack добавление gripping(X) может подразумевать вычеркивание gripping(). Однако эта избыточность имеет свои преимущества. Каждый дескриптор состояния, который не упоминается в списке добавления или вычеркивания, остается истинным в описании нового состояния.

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

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

Некоторые проблемы планирования не решает ни один из этих двух подходов. При решении задачи ее зачастую делят на подзадачи, например unstack(e,d) и unstack(b,a). Попытка независимого достижения этих подцелей может вызвать проблемы, если действия, необходимые для достижения одной цели, направлены на разрушение другой. Несовместимость подцелей может быть результатом неправильного предположения о линейности (независимости) подцелей. Нелинейность пространства план-действие может сделать поиск решений чрезмерно трудным или даже невозможным. Приведем простой пример несовместимых подцелей. Используем исходное состояние 1, показанное на рис. 7.18. Предположим, что целью планирования является состояние G, показанное на рис. 7.20, в котором оп(b,a)^оп(а,c), а блоки d и е остаются в том же положении, что и в состоянии 1. Можно отметить, что одна из частей конъюнктивной цели оп(b,a)^оп(а,c) - оп(b,а) - в состоянии 1 истинна. Для достижения второй подцели оп(а, с) это условие должно быть нарушено.

Представление данных в виде треугольной таблицы [Fikes и Nilsson, 1971], [Nilsson, 1980] позволяет смягчить некоторые последствия этих аномалий. Треугольная таблица является структурой данных для организации последовательности действий, включая потенциально несовместимые подцели. Она решает проблему противоречиво-