Differences

This shows you the differences between two versions of the page.

--- courses:knowledge_representation_and_artificial_intelligence_systems:lab4 [2019/07/01 21:22]
andrey.suchkov created
+++ courses:knowledge_representation_and_artificial_intelligence_systems:lab4 [2022/12/10 09:08] (current)
@@ Line 2: / Line 2: @@
 ===== Цель работы =====
 Формирование умения реализации в среде CLIPS задачи поиска в пространстве состояний и освоение способов анализа ее решения.
+===== Основные теоретические положения =====
+==== Введение ====
+Одной из классических задач ИИ, рассматриваемых при построении и анализе алгоритмов поиска является известная головоломка о крестьянине, которому необходимо переправить на другой берег реки волка, козу и капусту. Он располагает двуместной лодкой, т.е. может перевозить только по одному объекту. При этом нельзя оставлять на берегу волка с козой и козу с капустой, т.к. в этом случае первый из них съест второго.
+==== Общие сведения ====
+Как известно, постановка задачи поиска в пространстве состояний в общем случае предполагает описание //исходного состояния//, //множества операторов// перехода в пространстве состояний и множества целевых состояний (процедуры определения целевого состояния). Рассмотрим эти компоненты для данной задачи.
+=== Представление состояний в пространстве состояний и вершин в дереве поиска ===
+Каждое //состояние// в пространстве состояний //определяется нахождением каждого персонажа/объекта// (крестьянина (''peasant''), волка (''wolf''), козы (''goat'') и капусты (''cabbage'')) на одном из двух берегов (''shore-1'' или ''shore-2''). Таким образом, состояние можно представить неупорядоченным фактом, содержащим слоты для задания местоположения каждого персонажа (объекта): ''peasant-location'', ''wolf-location'', ''goat-location'' и ''cabbage-location''. Эти слоты могут принимать символьные значения ''shore-1'' и ''shore-2''.
+Поскольку поиск выполняется по дереву поиска (ДП), при разработке программы необходимо представлять вершины ДП. Каждая вершина ДП, помимо описания некоторого состояния, должна содержать также дополнительную информацию: //ссылку на родительскую вершину//, //глубину вершины// и //последнее перемещение//. Последнее перемещение определяет с кем/чем переправлялся крестьянин последний раз и может принимать следующие символьные значения: ''no-move'', ''alone'', ''wolf'', ''goat'' и ''cabbage''.
+Таким образом, для представления вершин  ДП можно использовать неупорядоченный факт, определяемый следующим шаблоном:
+<code>
+(deftemplate status
+  (slot peasant-location (type SYMBOL) (allowed-symbols shore-1 shore-2))
+  (slot wolf-location (type SYMBOL) (allowed-symbols shore-1 shore-2))
+  (slot goat-location (type SYMBOL) (allowed-symbols shore-1 shore-2))
+  (slot cabbage-location (type SYMBOL) (allowed-symbols shore-1 shore-2))
+  (slot parent (type FACT-ADDRESS SYMBOL) (allowed-symbols no-parent))
+  (slot search-depth (type INTEGER) (range 1 ?VARIABLE))
+  (slot last-move (type SYMBOL) (allowed-symbols no-move alone wolf goat cabbage)))
+</code>
+Исходным является состояние, в котором все действующие лица (и лодка) находятся на первом берегу (''shore-1''). Соответствующая (корневая) вершина в ДП не имеет родительской вершины, имеет глубину 1 и не имеет последнего перемещения (''no-move''). Таким образом, исходное состояние может быть представлено следующим фактом:
+<code>
+(deffacts initial-positions
+  (status (search-depth 1)
+          (parent no-parent)
+          (peasant-location shore-1)
+          (wolf-location shore-1)
+          (goat-location shore-1)
+          (cabbage-location shore-1)
+          (last-move no-move)))
+</code>
+=== Операторы перехода в пространстве состояний ===
+//Множество операторов// перехода для данной задачи включает:
+  * перемещение с одного берега на другой одного крестьянина (''move-alone'');
+  * перемещение крестьянина с волком (''move-with-wolf'');
+  * перемещение крестьянина с козой (''move-with-goat'');
+  * перемещение крестьянина с капустой (''move-with-cabbage'').
+При реализации программы в среде CLIPS операторы удобно представлять правилами. При этом //в левой части правил// должны распознаваться условия применимости данного оператора и фиксироваваться (связываться) параметры конкретного состояния: указатель (адрес) на текущую вершину, местонахождение действующих лиц, затрагиваемых данным оператором, и глубина поиска.
+//В правой части// правила должна порождаться новая вершина, являющаяся потомком текущей в случае применения данного оператора и устанавливаться ее параметры: глубина, новое местонахождение действующих лиц, ссылка на родительскую вершину и последнее перемещение. Новую вершину удобно порождать путем дублирования текущей с изменением значений некоторых параметров. Пример правила для перемещения крестьянина с волком:
+<code>
+(defrule move-with-wolf "Правило перемещения с волком"
+  ?node <- (status (search-depth ?num)     ; фиксация адреса текущей вершины и ее глубины
+                   (peasant-location ?ps)  ; фиксация текущего местонахождения крестьянина
+                   (wolf-location ?ps))    ; волк на том же берегу, что и крестьянина
+  (opposite-of ?ps ?ns)  ; связывание значения противоположного берега
+=>
+  (duplicate ?node              ; создать новую вершину дублированием
+    (search-depth =(+ 1 ?num))  ; установить ее глубину инкрементом текущей
+    (parent ?node)              ; установить в качестве родительской вершины текущую
+    (peasant-location ?ns)      ; установить новое местонахождение крестьянина
+    (wolf-location ?ns)         ; установить новое местонахождение волка
+    (last-move wolf)))          ; установить тип последнего перемещения
+</code>
+Для фиксации (привязки) текущего берега и связывания переменной ''?ns'' значением противоположного берега в левой части правила используется условный элемент ''(opposite-of ?fs ?ns)''. Значение переменной ''?ns'' используется в правой части правила для установки нового местонахождения персонажей в результате выполнения оператора. Для использования такого элемента необходимо заранее определить отношение ''opposites-of'' между берегами с помощью конструкции:
+<code>
+(deffacts opposites
+  (opposite-of shore-1 shore-2)
+  (opposite-of shore-2 shore-1))
+</code>
+=== Ограничения на возможные состояния ===
+Процесс поиска может приводить в //запрещённые состояния//, в которых волк ест козу или коза ест капусту. При попадании в запрещенные состояния соответствующие вершины должны удаляться. Например, волк ест козу, если он находится с ней на одном берегу и на этом берегу нет крестьянина. Соответствующее правило можно записать так:
+<code>
+(defrule wolf-eats-goat
+  ?node <- (status (peasant-location ?s1)    ; фиксируется адрес вершины и положение крестьянин
+                   (wolf-location ?s2&~?s1)  ; волк и крестьянин на разных берегах
+                   (goat-location ?s2))      ; коза на том же берегу, что и волк
+=>
+  (retract ?node))  ; удалить вершину
+</code>
+Правило, определяющее состояние, в котором коза ест капусту, записывается аналогично.
+Необходимо также распознавать ситуации зацикливания процесса поиска, т.е. повторного попадания в уже пройденное состояние. Для этого новое состояние должно сравниваться с ранее достигнутыми. Если имеется состояние с меньшей глубиной и точно таким же местоположением всех персонажей, то новая вершина должна удаляться. Соответствующее правило представлено ниже:
+<code>
+(defrule circular-path
+  (status (search-depth ?sd1)
+          (peasant-location ?ps)
+          (wolf-location ?ws)
+          (goat-location ?gs)
+          (cabbage-location ?cs))
+  ?node <- (status (search-depth ?sd2&:(< ?sd1 ?sd2))
+                   (peasant-location ?ps)
+                   (wolf-location ?ws)
+                   (goat-location ?gs)
+                   (cabbage-location ?cs))
+=>
+  (retract ?node))
+</code>
+//Первая часть антецедента// этого правила сопоставляется с некоторой вершиной и фиксирует (в переменной ''?sd1'') ее глубину, а также местоположение всех персонажей -- крестьянина, волка, козы и капусты -- соответственно в переменных ''?ps'', ''?ws'', ''?gs'' и ''?cs''. //Вторая часть антецедента// сопоставляется с вершиной, имеющей большую глубину и точно такое же состояние (местоположение персонажей). Адрес этой вершины фиксируется в переменной ''?node'', чтобы в консеквенте правила можно было удалить данную вершину.
+=== Распознавание и вывод решения ===
+//Решением// задачи является последовательность перемещений на лодке с берега на берег, переводящая исходное состояние в целевое. В данной задаче целевым является состояние, когда все находятся на втором берегу. При достижении целевого состояния должно быть выведено решение -- последовательность перемещений. Однако каждая вершина в ДП (в том числе целевая) явно хранит лишь //последнее перемещение// и указатель на вершину-предка. Поэтому при обнаружении целевого состояния необходимо выполнить обратный проход от целевой вершины к корню ДП (исходному состоянию), чтобы восстановить полную последовательность перемещений. Таким образом, необходимо иметь //правило для распознавания целевого состояния// и //правило для построения решения// -- последовательности операторов (перемещений) переводящих исходное состояние в целевое.
+Для представления последовательности перемещений, приводящих в некоторое состояние, удобно использовать факт на основе следующего шаблона:
+<code>
+(deftemplate moves
+  (slot id (type FACT-ADDRESS SYMBOL) (allowed-symbols no-parent))
+  (multislot moves-list (type SYMBOL) (allowed-symbols no-move alone wolf goat cabbage))
+</code>
+Соответствующий факт содержит два слота:
+  - Слот для идентификации вершины-предка. Значением слота является адрес вершины-родителя рассматриваемой вершины, или символьное значение ''no-parent'' для корневой вершины (у нее отсутствует родитель).
+  - Мультислот ''moves-list'' для хранения последовательности перемещений, приводящих в данное состояние (вершину).
+//Правило распознавания целевого состояния// должно активироваться, если имеется вершина, в которой все действующие лица находятся на втором берегу (''shore-2''). Правая часть правила должна удалять эту вершину и добавлять в базу данных факт, представляющий путь в соответствии с шаблоном ''moves''. В этом факте слот идентификатора вершины должен указывать на вершину-предка целевой вершины, а мультислот ''moves-list'' содержать последнее перемещение из этой вершины-предка в целевую вершину. Тогда правило распознавания целевого состояния может быть записано следующим образом:
+<code>
+(defrule goal-test
+  ?node <- (status (parent ?parent)
+                   (peasant-location shore-2)
+                   (wolf-location shore-2)
+                   (goat-location shore-2)
+                   (cabbage-location shore-2)
+                   (last-move ?move))
+=>
+  (retract ?node)
+  (assert (moves (id ?parent) (moves-list ?move))))
+</code>
+Появление в базе данных факта ''moves'' инициирует процесс обратного движения по ДП к корневой вершине (исходному состоянию) с построением пути-решения. //Правило построения решения// при каждом срабатывании реализует переход к родительской вершине, добавляя в мультислот ''moves-list'' факта ''moves'' соответствующее перемещение. Пример правила построения решения:
+<code>
+(defrule build-solution
+  ?node <- (status (parent ?parent)    ; фиксация адреса некоторой вершины ?node в ДП,
+                   (last-move ?move))  ; ее вершины-родителя и последнего перемещения
+  ?mv <- (moves (id ?node) (moves-list $?rest))  ; проверка, есть ли вершина moves
+                                                 ; с адресом ?node и, если "да", фиксация адреса
+                                                 ; факта и значения его мультислота moves-list
+=>
+  (modify ?mv (id ?parent) (moves-list ?move ?rest)))  ; модификация факта moves путем
+                                                       ; расширения списка перемещений и
+                                                       ; обновления предка
+</code>
+После завершения построения пути-решения, его необходимо отобразить на экране. Соответствующее правило должно сработать, когда обнаружится факт ''moves'', не имеющий родителя (корневая вершина ДП). Правило вывода решения на экран может быть задано так:
+<code>
+(defrule SOLUTION::print-solution
+  ?mv <- (moves (id no-parent) (moves-list no-move $?m))  ; для факта moves, не имеющего
+                                                          ; предка фиксируется его адрес ?mv и значение ?m
+                                                          ; мультислота moves-list – список перемещений
+=>
+  (retract ?mv)                          ; факт ?mv удаляется
+  (printout t t "Solution found: " t t)  ; Печать сообщения "Решение найдено:"
+  (bind ?length (length ?m))             ; ?length = длина списка перемещений ( переменной ?m)
+  (bind ?i 1)            ; ?i = 1
+  (bind ?shore shore-2)  ; ?shore = shore-2
+  (while (<= ?i ?length) do         ; Пока ?i <= ?length
+    (bind ?thing (nth ?i ?m))       ; ?thing = значение i-го слота мультислота ?m (тип перемещения)
+    (if (eq ?thing alone)           ; Если ?thing = alone
+       then (printout t "Peasant moves alone to " ?shore "." t)
+       else (printout t "Peasant moves with " ?thing " to " ?shore "." t))
+    (if (eq ?shore shore-1)         ; Если ?shore = shore-1
+       then (bind ?shore shore-2)   ; ?shore = shore-2
+       else (bind ?shore shore-1))  ; ?shore = shore-1
+    (bind ?i (+ 1 ?i))))  ; ?i = ?i + 1
+</code>
+===== Постановка задачи =====
+Необходимо построить полное дерево поиска для задачи о крестьянине, которому необходимо переправить на другой берег реки волка, козу и капусту, разработать на продукционном языке CLIPS модульную программу решения данной задачи и проанализировать ход поиска решения, выполнив программу в пошаговом режиме.
+===== Порядок выполнения работы =====
+  - Построить полное дерево поиска для данной задачи.
+  - Разработать, используя среду CLIPS, программу решения данной головоломки. Программа должна быть построена по модульному принципу и состоять из трех модулей:
+    - основного (''MAIN'');
+    - контроля ограничений (''CONSTRAINTS'');
+    - вывода решения (''SOLUTION''). \\ Для объявления модуля используется конструкция ''defmodule'', в которой указываются экпортируемые в другие модули или экспортируемые из других модулей конструкции. Например модуль ''MAIN'' экспортирует шаблон ''status'': <code>
+(defmodule MAIN
+  (export deftemplate status))
+</code>
+  - Модуль MAIN должен содержать:
+    - объявление шаблона состояния ''status'';
+    - определение факта исходного состояния -- ''initial-positions'';
+    - определение факта отношения между берегами -- ''opposites'';
+    - определение правил генерации пути, соответствующих четырем операторам в пространстве состояний. \\ Имена всех конструкций модуля ''MAIN'' должны начинаться с префикса ''MAIN::''. Например: <code>
+(deftemplate MAIN::status
+  ...
+)
+</code>
+  - Модуль контроля ограничений ''CONSTRAINTS'' должен импортировать из модуля ''MAIN'' шаблон ''status'': <code>
+(defmodule CONSTRAINTS
+  (import MAIN deftemplate status))
+</code> и содержать:
+      - два правила для распознавания запрещенных ситуаций ''wolf-eats-goat'' и ''goat-eats-cabbage'';
+      - правило для распознавания зацикливания пути -- ''circular-path''. \\ Имена всех конструкций модуля ''CONSTRAINTS'' должны начинаться с префикса ''CONSTRAINTS::''. Например: <code>
+(defrule CONSTRAINTS::goat-eats-cabbage
+  ...
+)
+</code> У всех правил модуля ''CONSTRAINTS'' должно быть установлено свойство автофокусировки. Это делается так: <code>
+(defrule CONSTRAINTS::wolf-eats-goat
+  (declare (auto-focus TRUE))
+  ...
+)
+</code> Если свойство автофокусировки правила установлено, то всякий раз при активации правила автоматически выполняется команда фокусировки на модуле, в котором определено данное правило.
+  - Модуль вывода решения ''SOLUTION'' также должен импортировать из модуля ''MAIN'' шаблон ''status'': <code>
+(defmodule SOLUTION
+  (import MAIN deftemplate status))
+</code> и содержать:
+    - объявление шаблона факта-решения ''moves'';
+    - правило распознавания целевого состояния ''goal-test'';
+    - правило построения пути-решения -- ''build-solution'';
+    - правило вывода решения на экран -- ''print-solution''. \\ Имена всех конструкций модуля ''SOLUTION'' должны начинаться с префикса ''SOLUTION::''. Например: <code>
+(defrule SOLUTION::print-solution
+  ...
+)
+</code> У правила распознавания целевого состояния должно быть установлено свойство автофокусировки: <code>
+(defrule SOLUTION::goal-test
+  (declare (auto-focus TRUE))
+  ...
+)
+</code>
+  - Выполните программу в пошаговом режиме, проанализируйте и объясните ход поиска решения. В отчете необходимо привести трассу поиска решения.
+===== Содержание отчёта =====
+  * Цель работы.
+  * Краткое изложение основных теоретических понятий.
+  * Постановка задачи с кратким описанием порядка выполнения работы.
+  * Дерево решений.
+  * Трассировка решения, оформленная в виде таблицы, с краткими выводами.
+  * Результаты работы программы.
+  * Общий вывод по проделанной работе.
+  * Код программы.

se.moevm.info

User Tools

Site Tools

Differences

Page Tools