courses:knowledge_representation_and_artificial_intelligence_systems:lab4
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
|
courses:knowledge_representation_and_artificial_intelligence_systems:lab4 [2019/07/12 13:19] andrey.suchkov [Общие сведения] |
courses:knowledge_representation_and_artificial_intelligence_systems:lab4 [2020/08/27 09:51] 127.0.0.1 external edit |
||
|---|---|---|---|
| Line 4: | Line 4: | ||
| ===== Основные теоретические положения ===== | ===== Основные теоретические положения ===== | ||
| ==== Введение ==== | ==== Введение ==== | ||
| - | Одной из классических задач ИИ, рассматриваемых при построении и анализе алгоритмов поиска является известная головоломка о фермере, которому необходимо переправить на другой берег реки волка, козу и капусту. Он располагает двуместной лодкой, т.е. может перевозить только по одному объекту. При этом нельзя оставлять на берегу волка с козой и козу с капустой, т.к. в этом случае первый из них съест второго. | + | Одной из классических задач ИИ, рассматриваемых при построении и анализе алгоритмов поиска является известная головоломка о крестьянине, которому необходимо переправить на другой берег реки волка, козу и капусту. Он располагает двуместной лодкой, т.е. может перевозить только по одному объекту. При этом нельзя оставлять на берегу волка с козой и козу с капустой, т.к. в этом случае первый из них съест второго. |
| ==== Общие сведения ==== | ==== Общие сведения ==== | ||
| Как известно, постановка задачи поиска в пространстве состояний в общем случае предполагает описание //исходного состояния//, //множества операторов// перехода в пространстве состояний и множества целевых состояний (процедуры определения целевого состояния). Рассмотрим эти компоненты для данной задачи. | Как известно, постановка задачи поиска в пространстве состояний в общем случае предполагает описание //исходного состояния//, //множества операторов// перехода в пространстве состояний и множества целевых состояний (процедуры определения целевого состояния). Рассмотрим эти компоненты для данной задачи. | ||
| === Представление состояний в пространстве состояний и вершин в дереве поиска === | === Представление состояний в пространстве состояний и вершин в дереве поиска === | ||
| - | Каждое //состояние// в пространстве состояний //определяется нахождением каждого персонажа/объекта// (фермера (''farmer''), волка (''wolf''), козы (''goat'') и капусты (''cabbage'')) на одном из двух берегов (''shore-1'' или ''shore-2''). Таким образом, состояние можно представить неупорядоченным фактом, содержащим слоты для задания местоположения каждого персонажа (объекта): ''farmer-location'', ''wolf-location'', ''goat-location'' и ''cabbage-location''. Эти слоты могут принимать символьные значения ''shore-1'' и ''shore-2''. | + | Каждое //состояние// в пространстве состояний //определяется нахождением каждого персонажа/объекта// (крестьянина (''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''. | + | Поскольку поиск выполняется по дереву поиска (ДП), при разработке программы необходимо представлять вершины ДП. Каждая вершина ДП, помимо описания некоторого состояния, должна содержать также дополнительную информацию: //ссылку на родительскую вершину//, //глубину вершины// и //последнее перемещение//. Последнее перемещение определяет с кем/чем переправлялся крестьянин последний раз и может принимать следующие символьные значения: ''no-move'', ''alone'', ''wolf'', ''goat'' и ''cabbage''. |
| Таким образом, для представления вершин ДП можно использовать неупорядоченный факт, определяемый следующим шаблоном: | Таким образом, для представления вершин ДП можно использовать неупорядоченный факт, определяемый следующим шаблоном: | ||
| <code> | <code> | ||
| (deftemplate status | (deftemplate status | ||
| - | (slot farmer-location (type SYMBOL) (allowed-symbols shore-1 shore-2)) | + | (slot peasant-location (type SYMBOL) (allowed-symbols shore-1 shore-2)) |
| - | (slot wolf-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 goat-location (type SYMBOL) (allowed-symbols shore-1 shore-2)) |
| - | (slot cabbage-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 parent (type FACT-ADDRESS SYMBOL) (allowed-symbols no-parent)) |
| - | (slot search-depth (type INTEGER) (range 1 ?VARIABLE)) | + | (slot search-depth (type INTEGER) (range 1 ?VARIABLE)) |
| - | (slot last-move (type SYMBOL) (allowed-symbols no-move alone wolf goat cabbage))) | + | (slot last-move (type SYMBOL) (allowed-symbols no-move alone wolf goat cabbage))) |
| </code> | </code> | ||
| Исходным является состояние, в котором все действующие лица (и лодка) находятся на первом берегу (''shore-1''). Соответствующая (корневая) вершина в ДП не имеет родительской вершины, имеет глубину 1 и не имеет последнего перемещения (''no-move''). Таким образом, исходное состояние может быть представлено следующим фактом: | Исходным является состояние, в котором все действующие лица (и лодка) находятся на первом берегу (''shore-1''). Соответствующая (корневая) вершина в ДП не имеет родительской вершины, имеет глубину 1 и не имеет последнего перемещения (''no-move''). Таким образом, исходное состояние может быть представлено следующим фактом: | ||
| Line 27: | Line 27: | ||
| (deffacts initial-positions | (deffacts initial-positions | ||
| (status (search-depth 1) | (status (search-depth 1) | ||
| - | (parent no-parent) | + | (parent no-parent) |
| - | (farmer-location shore-1) | + | (peasant-location shore-1) |
| - | (wolf-location shore-1) | + | (wolf-location shore-1) |
| - | (goat-location shore-1) | + | (goat-location shore-1) |
| - | (cabbage-location shore-1) | + | (cabbage-location shore-1) |
| - | (last-move no-move))) | + | (last-move no-move))) |
| </code> | </code> | ||
| === Операторы перехода в пространстве состояний === | === Операторы перехода в пространстве состояний === | ||
| //Множество операторов// перехода для данной задачи включает: | //Множество операторов// перехода для данной задачи включает: | ||
| - | * перемещение с одного берега на другой одного фермера (''move-alone''); | + | * перемещение с одного берега на другой одного крестьянина (''move-alone''); |
| - | * перемещение фермера с волком (''move-with-wolf''); | + | * перемещение крестьянина с волком (''move-with-wolf''); |
| - | * перемещение фермера с козой (''move-with-goat''); | + | * перемещение крестьянина с козой (''move-with-goat''); |
| - | * перемещение фермера с капустой (''move-with-cabbage''). | + | * перемещение крестьянина с капустой (''move-with-cabbage''). |
| При реализации программы в среде CLIPS операторы удобно представлять правилами. При этом //в левой части правил// должны распознаваться условия применимости данного оператора и фиксироваваться (связываться) параметры конкретного состояния: указатель (адрес) на текущую вершину, местонахождение действующих лиц, затрагиваемых данным оператором, и глубина поиска. | При реализации программы в среде CLIPS операторы удобно представлять правилами. При этом //в левой части правил// должны распознаваться условия применимости данного оператора и фиксироваваться (связываться) параметры конкретного состояния: указатель (адрес) на текущую вершину, местонахождение действующих лиц, затрагиваемых данным оператором, и глубина поиска. | ||
| - | //В правой части// правила должна порождаться новая вершина, являющаяся потомком текущей в случае применения данного оператора и устанавливаться ее параметры: глубина, новое местонахождение действующих лиц, ссылка на родительскую вершину и последнее перемещение. Новую вершину удобно порождать путем дублирования текущей с изменением значений некоторых параметров. Пример правила для перемещения фермера с волком: | + | //В правой части// правила должна порождаться новая вершина, являющаяся потомком текущей в случае применения данного оператора и устанавливаться ее параметры: глубина, новое местонахождение действующих лиц, ссылка на родительскую вершину и последнее перемещение. Новую вершину удобно порождать путем дублирования текущей с изменением значений некоторых параметров. Пример правила для перемещения крестьянина с волком: |
| <code> | <code> | ||
| - | (defrule move-with-wolf "Правило 'перемещение с волком'" | + | (defrule move-with-wolf "Правило перемещения с волком" |
| - | ?node <- (status (search-depth ?num) ; фиксация адреса текущей вершины и ее глубины | + | ?node <- (status (search-depth ?num) ; фиксация адреса текущей вершины и ее глубины |
| - | (farmer-location ?fs) ; фиксация текущего местонахождения фермера | + | (peasant-location ?fs) ; фиксация текущего местонахождения крестьянина |
| - | (wolf-location ?fs)) ; волк на том же берегу, что и фермер | + | (wolf-location ?fs)) ; волк на том же берегу, что и крестьянина |
| (opposite-of ?fs ?ns) ; связывание значения противоположного берега | (opposite-of ?fs ?ns) ; связывание значения противоположного берега | ||
| => | => | ||
| Line 53: | Line 53: | ||
| (search-depth =(+ 1 ?num)) ; установить ее глубину инкрементом текущей | (search-depth =(+ 1 ?num)) ; установить ее глубину инкрементом текущей | ||
| (parent ?node) ; установить в качестве родительской вершины текущую | (parent ?node) ; установить в качестве родительской вершины текущую | ||
| - | (farmer-location ?ns) ; установить новое местонахождение фермера | + | (peasant-location ?ns) ; установить новое местонахождение крестьянина |
| (wolf-location ?ns) ; установить новое местонахождение волка | (wolf-location ?ns) ; установить новое местонахождение волка | ||
| (last-move wolf))) ; установить тип последнего перемещения | (last-move wolf))) ; установить тип последнего перемещения | ||
| Line 64: | Line 64: | ||
| </code> | </code> | ||
| === Ограничения на возможные состояния === | === Ограничения на возможные состояния === | ||
| - | Процесс поиска может приводить в //запрещённые состояния//, в которых волк ест козу или коза ест капусту. При попадании в запрещенные состояния соответствующие вершины должны удаляться. Например, волк ест козу, если он находится с ней на одном берегу и на этом берегу нет фермера. Соответствующее правило можно записать так: | + | Процесс поиска может приводить в //запрещённые состояния//, в которых волк ест козу или коза ест капусту. При попадании в запрещенные состояния соответствующие вершины должны удаляться. Например, волк ест козу, если он находится с ней на одном берегу и на этом берегу нет крестьянина. Соответствующее правило можно записать так: |
| <code> | <code> | ||
| (defrule wolf-eats-goat | (defrule wolf-eats-goat | ||
| - | ?node <- (status (farmer-location ?s1) ; фиксируется адрес вершины и положение фермера | + | ?node <- (status (peasant-location ?s1) ; фиксируется адрес вершины и положение крестьянин |
| - | (wolf-location ?s2&~?s1) ; волк и фермер на разных берегах | + | (wolf-location ?s2&~?s1) ; волк и крестьянин на разных берегах |
| (goat-location ?s2)) ; коза на том же берегу, что и волк | (goat-location ?s2)) ; коза на том же берегу, что и волк | ||
| => | => | ||
| Line 79: | Line 79: | ||
| (defrule circular-path | (defrule circular-path | ||
| (status (search-depth ?sd1) | (status (search-depth ?sd1) | ||
| - | (farmer-location ?fs) | + | (peasant-location ?ps) |
| (wolf-location ?ws) | (wolf-location ?ws) | ||
| (goat-location ?gs) | (goat-location ?gs) | ||
| (cabbage-location ?cs)) | (cabbage-location ?cs)) | ||
| ?node <- (status (search-depth ?sd2&:(< ?sd1 ?sd2)) | ?node <- (status (search-depth ?sd2&:(< ?sd1 ?sd2)) | ||
| - | (farmer-location ?fs) | + | (peasant-location ?ps) |
| (wolf-location ?ws) | (wolf-location ?ws) | ||
| (goat-location ?gs) | (goat-location ?gs) | ||
| Line 91: | Line 91: | ||
| (retract ?node)) | (retract ?node)) | ||
| </code> | </code> | ||
| - | //Первая часть антецедента// этого правила сопоставляется с некоторой вершиной и фиксирует (в переменной ''?sd1'') ее глубину, а также местоположение всех персонажей -- фермера, волка, козы и капусты -- соответственно в переменных ''?fs'', ''?ws'', ''?gs'' и ''?cs''. //Вторая часть антецедента// сопоставляется с вершиной, имеющей большую глубину и точно такое же состояние (местоположение персонажей). Адрес этой вершины фиксируется в переменной ''?node'', чтобы в консеквенте правила можно было удалить данную вершину. | + | //Первая часть антецедента// этого правила сопоставляется с некоторой вершиной и фиксирует (в переменной ''?sd1'') ее глубину, а также местоположение всех персонажей -- крестьянина, волка, козы и капусты -- соответственно в переменных ''?ps'', ''?ws'', ''?gs'' и ''?cs''. //Вторая часть антецедента// сопоставляется с вершиной, имеющей большую глубину и точно такое же состояние (местоположение персонажей). Адрес этой вершины фиксируется в переменной ''?node'', чтобы в консеквенте правила можно было удалить данную вершину. |
| === Распознавание и вывод решения === | === Распознавание и вывод решения === | ||
| //Решением// задачи является последовательность перемещений на лодке с берега на берег, переводящая исходное состояние в целевое. В данной задаче целевым является состояние, когда все находятся на втором берегу. При достижении целевого состояния должно быть выведено решение -- последовательность перемещений. Однако каждая вершина в ДП (в том числе целевая) явно хранит лишь //последнее перемещение// и указатель на вершину-предка. Поэтому при обнаружении целевого состояния необходимо выполнить обратный проход от целевой вершины к корню ДП (исходному состоянию), чтобы восстановить полную последовательность перемещений. Таким образом, необходимо иметь //правило для распознавания целевого состояния// и //правило для построения решения// -- последовательности операторов (перемещений) переводящих исходное состояние в целевое. | //Решением// задачи является последовательность перемещений на лодке с берега на берег, переводящая исходное состояние в целевое. В данной задаче целевым является состояние, когда все находятся на втором берегу. При достижении целевого состояния должно быть выведено решение -- последовательность перемещений. Однако каждая вершина в ДП (в том числе целевая) явно хранит лишь //последнее перемещение// и указатель на вершину-предка. Поэтому при обнаружении целевого состояния необходимо выполнить обратный проход от целевой вершины к корню ДП (исходному состоянию), чтобы восстановить полную последовательность перемещений. Таким образом, необходимо иметь //правило для распознавания целевого состояния// и //правило для построения решения// -- последовательности операторов (перемещений) переводящих исходное состояние в целевое. | ||
| Line 108: | Line 108: | ||
| (defrule goal-test | (defrule goal-test | ||
| ?node <- (status (parent ?parent) | ?node <- (status (parent ?parent) | ||
| - | (farmer-location shore-2) | + | (peasant-location shore-2) |
| (wolf-location shore-2) | (wolf-location shore-2) | ||
| (goat-location shore-2) | (goat-location shore-2) | ||
| Line 138: | Line 138: | ||
| => | => | ||
| (retract ?mv) ; факт ?mv удаляется | (retract ?mv) ; факт ?mv удаляется | ||
| - | (printout t t "Solution found: " t t) ; Печать сообщения «Решение найдено:» | + | (printout t t "Solution found: " t t) ; Печать сообщения "Решение найдено:" |
| (bind ?length (length ?m)) ; ?length = длина списка перемещений ( переменной ?m) | (bind ?length (length ?m)) ; ?length = длина списка перемещений ( переменной ?m) | ||
| (bind ?i 1) ; ?i = 1 | (bind ?i 1) ; ?i = 1 | ||
| Line 145: | Line 145: | ||
| (bind ?thing (nth ?i ?m)) ; ?thing = значение i-го слота мультислота ?m (тип перемещения) | (bind ?thing (nth ?i ?m)) ; ?thing = значение i-го слота мультислота ?m (тип перемещения) | ||
| (if (eq ?thing alone) ; Если ?thing = alone | (if (eq ?thing alone) ; Если ?thing = alone | ||
| - | then (printout t "Farmer moves alone to " ?shore "." t) | + | then (printout t "Peasant moves alone to " ?shore "." t) |
| - | else (printout t "Farmer moves with " ?thing " to " ?shore "." t)) | + | else (printout t "Peasant moves with " ?thing " to " ?shore "." t)) |
| (if (eq ?shore shore-1) ; Если ?shore = shore-1 | (if (eq ?shore shore-1) ; Если ?shore = shore-1 | ||
| - | then (bind ?shore shore-2) ;?shore = shore-2 | + | then (bind ?shore shore-2) ; ?shore = shore-2 |
| - | else (bind ?shore shore-1)) ;?shore = shore-1 | + | else (bind ?shore shore-1)) ; ?shore = shore-1 |
| (bind ?i (+ 1 ?i)))) ; ?i = ?i + 1 | (bind ?i (+ 1 ?i)))) ; ?i = ?i + 1 | ||
| </code> | </code> | ||
| ===== Постановка задачи ===== | ===== Постановка задачи ===== | ||
| - | Необходимо построить полное дерево поиска для задачи о фермере, которому необходимо переправить на другой берег реки волка, козу и капусту, разработать на продукционном языке CLIPS модульную программу решения данной задачи и проанализировать ход поиска решения, выполнив программу в пошаговом режиме. | + | Необходимо построить полное дерево поиска для задачи о крестьянине, которому необходимо переправить на другой берег реки волка, козу и капусту, разработать на продукционном языке CLIPS модульную программу решения данной задачи и проанализировать ход поиска решения, выполнив программу в пошаговом режиме. |
| ===== Порядок выполнения работы ===== | ===== Порядок выполнения работы ===== | ||
| - Построить полное дерево поиска для данной задачи. | - Построить полное дерево поиска для данной задачи. | ||
| Line 164: | Line 164: | ||
| </code> | </code> | ||
| - Модуль MAIN должен содержать: | - Модуль 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> | ||
| + | - Выполните программу в пошаговом режиме, проанализируйте и объясните ход поиска решения. В отчете необходимо привести трассу поиска решения. | ||
| + | ===== Содержание отчёта ===== | ||
| + | * Цель работы. | ||
| + | * Краткое изложение основных теоретических понятий. | ||
| + | * Постановка задачи с кратким описанием порядка выполнения работы. | ||
| + | * Дерево решений. | ||
| + | * Трассировка решения, оформленная в виде таблицы, с краткими выводами. | ||
| + | * Результаты работы программы. | ||
| + | * Общий вывод по проделанной работе. | ||
| + | * Код программы. | ||
courses/knowledge_representation_and_artificial_intelligence_systems/lab4.txt · Last modified: 2022/12/10 09:08 (external edit)
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
