ОРДЕНА ЛЕНИНА
ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ им. М.В. КЕЛДЫША
РОССИЙСКОЙ АКАДЕМИИ НАУК
Программные средства реализации ассоциативного планирования
Корухова Л.С., Любимский Э.З., Малышко В.В.
Москва 2002
Аннотация
Работа посвящена исследованию средств программирования для решения задач планирования целенаправленной деятельности. Описана реализация ассоциативного планирования в решателе геометрических задач. Предложен алгоритм поиска близких ситуаций, основанный на компиляции описаний стереотипных ситуаций в сеть специального вида. Рассмотрены критерии отбора стереотипов для получения эффективного плана. Приведены решения интеллектуальных многошаговых задач, демонстрирующие метод ассоциативного планирования на основе стереотипов и близких ситуаций.
Ключевые слова и фразы: планирование решений, стереотип, решатель геометрических задач, граф решения, ситуация, ассоциативное планирование.
Abstract
This paper concerns research on new programming tools for solving some planning problems of goal-oriented activity. By example of geometric problem solver we describe the realization of the associative planning method for problem solving. We propose the algorithm of resembling situations searching, which is based on compiling of stereotype situation's descriptions to the special net. The criteria of stereotypes' selection for effective planning are discussed. The paper contains solutions of intellectual multi-step problems as examples of associative planning method's application.
Key words and phases: problem solving, stereotype, geometric problem solver, solution graph, situation, associative planning.
Введение
Настоящая работа является продолжением работ (см. [Корухова и Любимский, 1994], [Вакин, Корухова и др., 1997], [Корухова и др., 2000]), посвященных исследованию эффективных методов планирования для решения интеллектуальных задач. При разработке таких методов принципиальным является то, что процесс планирования должен основываться на тех приемах и методах, которые использует человек, решая сложную задачу. В работе рассматривается проблема реализации ассоциативного планирования.
Ассоциативное мышление и рассуждение по аналогии применяются человеком при составлении планов и решении задач наряду с логическим анализом и эвристическим поиском. Внимание разработчиков ранних систем искусственного интеллекта (ИИ) было сосредоточено на последних двух методах решения сложных задач. Многие системы базировались именно на этих методах, ставших классическими методами ИИ. С течением времени из-за недостатков, присущих логике и эвристическому поиску, часть исследователей занялась методами, основанными на аналогии. Привлекательность этих методов состоит в том, что при решении задач используется прежний опыт системы, а также система шире использует знания, содержащиеся в ее базе.
Основным направлением в этой области является исследование рассуждений на основе прецедентов (case-based reasoning). Этот метод рассуждений используется для автоматического планирования в различных предметных областях (доказательстве теорем, юриспруденции, поиске маршрутов по карте, программном управлении заводским станком). Суть метода состоит в том, что система хранит базу прецедентов (полученных ранее решений задач), приступая к работе над новой задачей, система просматривает базу в поисках решения похожей задачи и, обнаружив таковое, пытается адаптировать к новым условиям и применить для получения ответа. В случае успеха удается достаточно быстро получить результат, поскольку модификация готового решения зачастую оказывается проще, нежели его поиск «с нуля».
В качестве примера рассмотрим использующую прецеденты систему CLAM, которая осуществляет автоматическое доказательство теорем (см. [Melis and Whittle, 1997]). Прецедентами в системе являются планы доказательства теорем. Для построения плана целевой теоремы подыскивается подходящий прецедент (например, теорема sum(x)+sum(y)=sum(x+y) может быть доказана аналогично доказательству теоремы x<>(y<>z)=(x<>y)<>z), затем строится отображение исходной теоремы в целевую. На основании этого отображения осуществляется преобразование прецедента в план для целевой теоремы. При этом он может быть переформулирован, в доказательство могут быть добавлены новые шаги.
Процедура планирования системы CLAM представляет собой последовательность шагов:
1. Найти в базе прецедентов теорему, похожую на целевую (похожесть определяется по виду формул теоремы).
2. Построить отображение теоремы-прецедента в целевую.
3. Расширить отображение, сопоставляя правила исходного доказательства и правила для доказательства целевой теоремы.
4. Принять решение о переформулировании доказательства-прецедента (на основании образцов из отображения).
5. Применить для целевой теоремы шаги доказательства, следуя исходному плану.
Рассуждения на основе прецедентов не всегда успешны. Для ряда задач система CLAM стоит планы с изъянами - участками планов, которые невозможно уточнить полностью при помощи аналогии. Изъяны в планах могут быть устранены с помощью обычной техники доказательства (с привлечением дедуктивного метода доказательства).
Основные проблемы при реализации систем, основанных на прецедентах:
· сопоставление (поиск подходящих прецедентов в базе);
· адаптация прецедентов к условиям задачи;
· пополнение базы прецедентов;
· привлечение других методов планирования в случае неудачи рассуждений по аналогии.
В нашей работе предлагается метод планирования на основе аналогии - ассоциативное планирование, и рассматривается его реализация в решателе геометрических задач (РГЗ). Метод имеет некоторое сходство с рассуждениями на основе прецедентов, но ряд отличий между ними позволяет говорить о нем, как о новом методе планирования решений.
В первой главе дается описание идеи метода, вводятся основные понятия. Во второй главе описана структура и реализация сопоставителя, обеспечивающего полное и частичное сопоставление образцов. Реализация ассоциативного уточнения цели описана в третьей главе. Завершает работу описание процесса решения геометрической задачи при использовании метода ассоциативного планирования.
1. Ассоциативное планирование с использованием близких ситуаций
Мы рассматриваем систему планирования, основанную на стереотипах. Стереотипы - это непроцедурные конструкции для представления стереотипных приемов решения задач. Эффект применения стереотипов в системе похож на применение правил в системах продукций, но проблемно-ориентированная активация и назначение стереотипа существенно отличают его от правил продукционной системы. Используя термин стереотип, мы исходим из следующей модели планирования человеком своей деятельности. Человек, решая сложную задачу, анализирует сложившуюся ситуацию и предпринимает стереотипные действия, которые у него с данной ситуацией ассоциируются. Применение действий приводит к изменению состояния задачи. В новых условиях применяются другие стереотипные приемы решения. Процесс применения стереотипов является циклическим и довольно быстро (в сравнении с полным перебором вариантов) приводит к искомому решению, либо к убеждению, что такого решения нет.
Представление для стереотипного приема решения состоит из двух частей: ситуации и действия стереотипа. Ситуация стереотипа - это совокупность условий, накладываемых на состояние предметной области. Описание ситуации содержит переменные, оно является образцом, который сопоставляется с текущим состоянием предметной области. Действие стереотипа - это последовательность элементарных действий, которые можно применить, если выполняются условия ситуации. Мы исходим из того, что состояние предметной области описывается совокупностью фактов и хранится в базе знаний системы, а элементарными действиями являются запись фактов в базу, удаление фактов из базы, добавление новых целей и связей между целями. Таким образом, стереотип может представить знания о правилах вывода фактов и правилах разбиения целей на подцели.
Метод ассоциативного планирования сочетает в себе редукцию целей и рассуждения на основе прецедентов. Ассоциативное планирование предполагает итеративное разбиение целей на подцели и построение графа целей (который можно рассматривать как альтернативное представление И/ИЛИ-графа). Разбиение на подцели производится с привлечением аналогии. Идея метода такова: если при уточнении цели нельзя применить стереотип из-за нарушенных условий в его ситуации, то следует адаптировать стереотип к текущему состоянию задачи, и затем применить его действие.
1.1 Близкая ситуация
Базовым понятием ассоциативного планирования является близкая (частично-распознанная) ситуация. Ситуация стереотипа является близкой, если при ее сопоставлении с текущим состоянием задачи нарушается часть ее условий, причем только те условия, для которых есть потенциальная возможность вывода фактов, недостающих для полного сопоставления ситуации. Если ситуация стереотипа является близкой, то имеет смысл модифицировать стереотип в соответствии с текущим состоянием задачи. Адаптация стереотипа состоит в том, что для каждого нарушенного условия в действие стереотипа добавляется оператор, записывающий в граф цель, по достижении которой условие будет выполнено (например, если нарушено условие «длина стороны треугольника известна», то следует добавить оператор «запиши цель „найти длину стороны треугольника“»). В других случаях (когда ситуация не является близкой) попытка использования стереотипа при построении плана будет безуспешной, так как недостающие факты вывести невозможно, и этот путь решения ведет в тупик. Таким образом, близость ситуации показывает, имеет ли стереотип отношение к решению текущей задачи.
В РГЗ, как и в любой системе логического вывода можно выделить класс фактов, которые могут добавляться в ходе решения, и класс фактов, которые не могут быть получены путем вывода. В решателе, не реализовано добавление в ходе решения в базу задачи новых объектов, поскольку это может привести к неоправданному увеличению перебора. Новые отношения, отражающие конфигурацию объектов, тоже не могут возникать в ходе решения. Факты других типов, такие как значения величин геометрических объектов и проблемные отношения между объектами (например, равенство отрезков или углов и т. п.) составляют класс потенциально выводимых фактов в РГЗ. Следовательно, у близких ситуаций могут быть не выполнены при сопоставлении только условия на значения величин и условия на проблемные отношения. Заметим, что при расширении класса выводимых фактов должен соответственно меняться класс близких ситуаций. Например, если в решателе будут реализованы дополнительные построения, то отсутствие в текущем состоянии задачи геометрического объекта не будет означать, что ситуация не является близкой, поскольку недостающий факт будет относиться к выводимым.
Рассмотрим пример. Пусть в базе знаний есть такое описание стереотипа Замечания по синтаксису описаний: знак $ используется для отметки начала и конца строк; имена, начинающиеся с точки, - это имена переменных.:
Имя стереотипа: треугольник_и_окружность_4
Комментарий: Сторона треугольника является диаметром описанной окружности, если она равна диаметру окружности.
Ситуация:fsit242
Описание цели:[$диаметр окружности$, [$.s1$, $.o$]]
Действие:a([$доказательство$, 42, [$.s$, $.s1$, $.o$, $.tr$]], 0)
(записать факт, используя доказательство 42)
Трудность:0
Описание ситуации, в которой применимо действие стереотипа:
Ситуация:fsit242
Объекты:obj($.o$, $окружность$), obj($.s$, $отрезок$),
obj($.tr$, $треугольник$)
Элементы: elem($.s1$, $.tr$, $сторона$)
Условия на значения элементов: {в данной ситуации отсутствуют}
Отношения конфигурации: {в данной ситуации отсутствуют}
Проблемные отношения: prob($равны отрезки$, [$.s$, $.s1$]),
prob($диаметр окружности$, [$.s$, $.o$]),
prob($описана около треугольника$, [$.tr$,$.o$])
Допустим также, что состояние предметной области описано следующим набором фактов: объект ABC - треугольник, объект O1 - окружность, объект MN - отрезок, O1 описана около ABC, равны отрезки AB и MN. При сопоставлении ситуации fsit242 не выполнено условие, что MN является диаметром O1. Недостающий факт имеет тип проблемного отношения и относится к классу потенциально выводимых в РГЗ. Следовательно, ситуация fsit242 является близкой со строкой сопоставления <.tr-ABC,.s1-AB,.s-MN,.o O1>. Заметим, что ситуация fsit242 также является близкой со строкой сопоставления <.tr ABC,.s1-AC,.s-MN,.o-O1>. Недостающих фактов при таком сопоставлении будет два: равны отрезки AC и MN, отрезок MN является диаметром окружности O1. Еще один вариант сопоставления, при котором рассматриваемая ситуация является близкой - <.tr-ABC,.s1-BC,.s-MN,.o-O1>.
В зависимости от текущей цели рационально рассматривать применение стереотипа только с одним из трех возможных означиваний. Если стоит цель „доказать, что AB является диаметром окружности O1“, то только первый вариант сопоставления ситуации fsit242 может считаться подходящим для решения. Только в этом случае стереотип может быть адаптирован для его использования при планировании. Его действия могут быть расширены добавлением еще одного действия - «записать цель „доказать, что MN является диаметром окружности O1“», после чего адаптированный стереотип можно применять для редукции цели.
При ассоциативном планировании каждый используемый стереотип можно рассматривать как свого рода прецедент. Его действие нельзя применить в первоначальном виде, но после адаптации к текущему состоянию предметной области стереотип можно использовать при поиске плана решения. Общим у стереотипа и прецедента является то, что в отличие от правил, которые выбираются на основе точного сопоставления антецедента и данных из рабочей памяти, прецеденты и стереотипы выбираются на основе частичного сопоставления. Отметим сразу отличия нашего подхода от рассуждений на основе прецедентов: