courses:knowledge_representation_and_artificial_intelligence_systems:lab5
Differences
This shows you the differences between two versions of the page.
|
courses:knowledge_representation_and_artificial_intelligence_systems:lab5 [2019/07/12 14:24] andrey.suchkov [Headline] |
courses:knowledge_representation_and_artificial_intelligence_systems:lab5 [2022/12/10 09:08] |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Лабораторная работа №5: Исследование моделей планирования действий в системах искусственного интеллекта ====== | ||
| - | ===== Цель работы ===== | ||
| - | Изучение принципов описания и решения задачи планирования на основе продукционной модели с использованием механизма поиска в пространстве состояний. | ||
| - | ===== Основные теоретические положения ===== | ||
| - | Задача построения башни из блоков (кубиков) заключается в последовательном выборе из неупорядоченной кучи блоков и постановки их друг на друга. План решения задачи представляет собой чередование двух фаз: выбора блока из кучи и установки его в башню. При этом больший по размерам блок не может ставиться на меньший по размерам и, следовательно, на каждом шаге решения задачи необходимо выбирать из кучи самый большой блок. | ||
| - | Каждый блок характеризуется //размером//, //цветом// и //положением//, поэтому для его описания можно использовать следующий шаблон: | ||
| - | <code> | ||
| - | (deftemplate block | ||
| - | (slot size (type INTEGER)) | ||
| - | (slot place (type SYMBOL)) | ||
| - | (slot color (type SYMBOL)) | ||
| - | ) | ||
| - | </code> | ||
| - | Каждый блок может находиться либо в куче (''heap''), либо в руке (''hand''), когда он выбран из кучи, либо в башне (''tower''). | ||
| - | |||
| - | В результате решения задачи необходимо последовательно вывести информацию о действиях, составляющих план её решения и взаимное положение блоков в построенной по данному плану башне с указанием их цвета. С этой целью для блоков, находящихся в башне, необходимо определить отношение, указывающее, какой блок (''upper'') на каком (''lower'') стоит: | ||
| - | <code> | ||
| - | (deftemplate on | ||
| - | (slot upper (type SYMBOL)) | ||
| - | (slot lower (type SYMBOL)) | ||
| - | (slot place (type SYMBOL)(default heap)) | ||
| - | ) | ||
| - | </code> | ||
| - | Если блок ставится в основание башни, слоту ''place'' присваивается значение ''tower'', а слоты ''upper'' и ''lower'' остаются неопределенными. Если блок ставится на другой блок, слотам ''upper'' и ''lower'' должны присваиваться значения цветов соответствующих блоков. | ||
| - | |||
| - | Поскольку план решения задачи представляет собой чередование фаз поиска в компоненте пространства состояний (<<куче>>) самого большого блока (''find'') и его установки в башню (''build''), необходимо иметь факт, определяющий текущую задачу. Его можно определить с помощью следующего шаблона: | ||
| - | <code> | ||
| - | (deftemplate goal | ||
| - | (slot current-task (type SYMBOL)) | ||
| - | ) | ||
| - | </code> | ||
| - | Для решения задачи необходимы правила для следующих действий: | ||
| - | * установки начального значения текущей задачи; | ||
| - | * выбора из кучи самого большого блока; | ||
| - | * установки первого блока в основание башни; | ||
| - | * установки в башню всех последующих блоков; | ||
| - | * определения окончания процесса, когда в куче нет больше блоков. | ||
| - | //Правило установки начального значения текущей задачи// должно активироваться исходным фактом (''initial-fact'') и устанавливать в качестве текущей задачи ''find''. | ||
| - | |||
| - | **Правило выбора из кучи самого большого блока** должно активироваться следующими условиями: | ||
| - | * текущая задача -- ''find''; | ||
| - | * наличие в куче блока, для которого не существует большего по размерам. | ||
| - | Действия правила: | ||
| - | * взять найденный блок в руку (изменить его местоположение на ''hand''); | ||
| - | * изменить текущую задачу на ''build''. | ||
| - | **Правило установки блока в основание башни** (первого блока) имеет следующие условия активации: | ||
| - | * текущая задача -- ''build''; | ||
| - | * имеется блок в руке; | ||
| - | * отсутствуют блоки в башне -- нет блока, у которого значение слота ''place'' равно ''tower''. | ||
| - | Действия правила: | ||
| - | * изменить местоположение блока в руке на ''tower''; | ||
| - | * изменить текущую задачу на ''find''. | ||
| - | **Правило установки в башню последующих блоков** имеет условия активации: | ||
| - | * текущая задача -- ''build''; | ||
| - | * имеется блок в руке (для него надо запомнить цвет); | ||
| - | * имеется блок в башне, на котором не стоит другой блок (для него также надо запомнить цвет). | ||
| - | Действия правила: | ||
| - | * модифицировать местоположение блока в руке на ''tower''; | ||
| - | * установить факт, что новый блок находится на блоке, который был до этого верхним; | ||
| - | * изменить текущую задачу на ''find''. | ||
| - | **Правило определения окончания процесса** должно активироваться, когда в куче больше нет блоков и удалять из рабочей памяти факт текущей задачи. | ||
| - | ===== Постановка задачи ===== | ||
| - | Разработать и отладить на языке CLIPS программу решения задачи планирования постройки башни из блоков с пошаговым отображением плана построения башни. | ||
| - | ==== Варианты заданий ==== | ||
| - | <note important>Для каждого блока в таблице через слеш указаны параметры: цвет/размер.</note> | ||
| - | ^ № варианта ^ Блок-1 ^ Блок-2 ^ Блок-3 ^ Блок-4 ^ | ||
| - | | 1 | синий/10 | зелёный/8 | красный/18 | жёлтый/15 | | ||
| - | | 2 | красный/20 | коричневый/5 | жёлтый/12 | зелёный/8 | | ||
| - | | 3 | жёлтый/15 | красный/10 | белый/25 | коричневый/5 | | ||
| - | | 4 | зелёный/10 | жёлтый/14 | чёрный/18 | красный/11 | | ||
| - | | 5 | коричневый/5 | белый/25 | синий/14 | жёлтый/12 | | ||
| - | | 6 | красный/10 | чёрный/18 | жёлтый/15 | белый/25 | | ||
| - | | 7 | жёлтый/12 | синий/10 | зелёный/8 | чёрный/18 | | ||
| - | | 8 | белый/16 | красный/5 | коричневый/15 | синий/10 | | ||
| - | ===== Порядок выполнения работы ===== | ||
| - | - Разработать программу решения задачи планирования на языке CLIPS, реализующую описанные выше правила, в соответствии с вариантом задания, указанным в таблице. \\ Исходное состояние должно описываться конструкцией ''deffacts'', содержащей четыре факта, соответствующих блокам в куче. | ||
| - | - Вывод результатов на экран должен обеспечивать пошаговое отображение плана построения башни. | ||
| - | ===== Содержание отчёта ===== | ||
| - | ===== Пример решения задачи ===== | ||
| - | ==== Решение задачи в среде CLIPS ==== | ||
| - | <code text lab5.CLP> | ||
| - | ;;//Шаблон для блока, хранит размер , цвет, положение - в куче, в руке или помещен в башню | ||
| - | (deftemplate block | ||
| - | (slot size (type INTEGER)) | ||
| - | (slot place (type SYMBOL)(default heap)) | ||
| - | (slot color (type SYMBOL)) | ||
| - | ) | ||
| - | ;;//------------------------------------------------------------------------------------------------------- | ||
| - | ;;//Шаблон для отношения, задающего порядок расположения кубиков в башне (для основания значения полей upper,lower не определено | ||
| - | (deftemplate on | ||
| - | (slot upper (type SYMBOL)) | ||
| - | (slot upper-size (type INTEGER)) | ||
| - | (slot lower (type SYMBOL)) | ||
| - | (slot lower-size (type INTEGER)) | ||
| - | (slot place (type SYMBOL)(default heap)) | ||
| - | ) | ||
| - | ;;//------------------------------------------------------------------------------------------------------- | ||
| - | ;;//Действие, выполняемое в настоящий момент времени: поиск подходящего кубика или установка найденного на вершину башни | ||
| - | (deftemplate goal | ||
| - | (slot current-task (type SYMBOL)) | ||
| - | ) | ||
| - | ;;//------------------------------------------------------------------------------------------------------- | ||
| - | ;;//задаем начальное состояние кучи блоков с кубиками | ||
| - | (deffacts bloxx | ||
| - | (block (size 10)(color blue)) | ||
| - | (block (size 20)(color red)) | ||
| - | (block (size 15)(color yellow)) | ||
| - | (block (size 10)(color green)) | ||
| - | (block (size 5)(color brown)) | ||
| - | (block (size 10)(color red)) | ||
| - | (block (size 12)(color yellow)) | ||
| - | (block (size 16)(color white)) | ||
| - | (block (size 18)(color black)) | ||
| - | ) | ||
| - | ;;//------------------------------------------------------------------------------------------------------- | ||
| - | ;;//вывобит на экран информацию о блоке | ||
| - | (deffunction print-block(?color ?size) | ||
| - | (printout t " <[block] [color] = '" ?color "' [size] = '" ?size "'/>" crlf) | ||
| - | );;//конец deffunction print-block | ||
| - | ;;//------------------------------------------------------------------------------------------------------- | ||
| - | ;;//вывобит на экран информацию о наибольшем блоке | ||
| - | (deffunction print-biggest-block(?color ?size) | ||
| - | (printout t crlf "Biggest block: ") | ||
| - | (print-block ?color ?size) | ||
| - | (printout t crlf ) | ||
| - | );;//конец deffunction print-biggest-block | ||
| - | ;;//------------------------------------------------------------------------------------------------------- | ||
| - | ;;//Инициирует процесс поиска решения - устанавливает состояние системы "поиск кубика" | ||
| - | (defrule init-system | ||
| - | (initial-fact) | ||
| - | => | ||
| - | (assert (goal(current-task find))) | ||
| - | );;//конец defrule init-system | ||
| - | ;;//------------------------------------------------------------------------------------------------------- | ||
| - | ;;//Ищет наибольший блок в куче | ||
| - | (defrule find-biggest | ||
| - | ?goal-ptr <- (goal (current-task find)) | ||
| - | ?block-ptr <- (block (size ?s1)(color ?cl1)(place heap)) | ||
| - | (not | ||
| - | (block | ||
| - | (size ?s2&: (> ?s2 ?s1)) | ||
| - | (place heap) | ||
| - | );;//end block | ||
| - | );;//end (not): нет блока большего по размеру чем данный | ||
| - | => | ||
| - | (modify ?block-ptr (place hand)) | ||
| - | (modify ?goal-ptr (current-task build)) | ||
| - | (print-biggest-block ?cl1 ?s1);;//вывести информацию о блоке | ||
| - | );;//конец defrule find-biggest | ||
| - | ;;//------------------------------------------------------------------------------------------------------- | ||
| - | ;;//выводит блоки, находящиеся в куче | ||
| - | (defrule show-in-heap | ||
| - | (declare (salience 2000)) | ||
| - | (goal (current-task find));;//текущ задача - "поиск" | ||
| - | (block | ||
| - | (place heap) | ||
| - | (size ?sz) | ||
| - | (color ?cl) | ||
| - | );;//end block | ||
| - | => | ||
| - | (printout t "Block in the heap: ") | ||
| - | (print-block ?cl ?sz);;//вывести информацию о блоке | ||
| - | );;//конец defrule show-in-heap | ||
| - | ;;//------------------------------------------------------------------------------------------------------- | ||
| - | ;;//Устанавливает блок в основание башни | ||
| - | (defrule set-basis | ||
| - | (declare (salience 1000)) | ||
| - | ?goal-ptr <- (goal (current-task build) );;//текущ задача - "строить" | ||
| - | ?block-ptr <- (block (place hand)(color ?col)(size ?sz) );;// есть блок в руке | ||
| - | (not | ||
| - | (block | ||
| - | (place tower) | ||
| - | );;//end block | ||
| - | );;//end (not): нет блока, находящегося в башне | ||
| - | => | ||
| - | (modify ?goal-ptr (current-task find) );;// перейти к поиску следующего | ||
| - | (modify ?block-ptr (place tower));;// установить блок в башню | ||
| - | (assert | ||
| - | (on | ||
| - | (place tower) | ||
| - | (upper ?col) | ||
| - | (upper-size ?sz) | ||
| - | (lower nil) | ||
| - | (lower-size 0) | ||
| - | );//end on | ||
| - | );;//добавить новый факт, соотвествующий помещениб выбранного блока на верх башни | ||
| - | );;//конец defrule set-basis | ||
| - | ;;//------------------------------------------------------------------------------------------------------- | ||
| - | ;;//Устанавливает все последующие (после заложенного в основание) блоки | ||
| - | (defrule set-next | ||
| - | (declare (salience 1000)) | ||
| - | ?goal-ptr <- (goal (current-task build) );;//текущ задача - "строить" | ||
| - | ?block-ptr <- (block (place hand) (color ?color-up) (size ?sz-up));;// есть блок в руке | ||
| - | (block (place tower) (color ?color-t) (size ?sz-t) );;//сохранили цвет некоторого блока | ||
| - | (not (on (place tower)(lower ?color-t)(lower-size ?sz-t)));;//нет такого блока, который находится над данным | ||
| - | (on (place tower)(upper ?color-t)(upper-size ?sz-t)) | ||
| - | ?on-ptr <- (on | ||
| - | (place tower) | ||
| - | (upper ?color-t) | ||
| - | (upper-size ?sz-t) | ||
| - | );;//выберем блок в башне, на котором нет блока сверху, т.е. верхний блок | ||
| - | => | ||
| - | (modify ?goal-ptr (current-task find) );;// перейти к поиску следующего | ||
| - | (modify ?block-ptr (place tower));;// установить блок в башню | ||
| - | (assert | ||
| - | (on | ||
| - | (place tower) | ||
| - | (upper ?color-up) | ||
| - | (upper-size ?sz-up) | ||
| - | (lower ?color-t) | ||
| - | (lower-size ?sz-t) | ||
| - | );//end on | ||
| - | );;//добавить новый факт, соотвествующий помещениб выбранного блока на верх башни | ||
| - | );;//конец defrule set-next: | ||
| - | ;;//------------------------------------------------------------------------------------------------------- | ||
| - | ;;//останавливает процесс поиска, когда в куче ничего не осталось | ||
| - | (defrule finish-process | ||
| - | (not (block (place heap)));;//нет ни одного блока в куче | ||
| - | ?goal-ptr <- ( goal (current-task ?task)) | ||
| - | => | ||
| - | (retract ?goal-ptr) | ||
| - | (printout t "Solution found" crlf "Order of the blocks from the lowest to the highest" crlf) | ||
| - | );;//конец defrule finish-process | ||
| - | ;;//------------------------------------------------------------------------------------------------------- | ||
| - | ;;//выводит решение после окончания поиска | ||
| - | (defrule show-build-process | ||
| - | (not (goal (current-task ?task) ));;//цель - показать решение | ||
| - | (on (place tower)(upper ?color-up)(upper-size ?sz-up) );;//находим блок на котором ничего не находится сверху | ||
| - | (not (on (place tower)(lower ?color-up)(lower-size ?sz-up) )) | ||
| - | ?on-ptr <- (on (place tower) (upper ?color-up)(upper-size ?sz-up) );;//возьмем адрес отношения, соотв. данному блоку | ||
| - | => | ||
| - | ;;//(printout t "Block: color = " ?color-up " size = " ?sz-up crlf) | ||
| - | (print-block ?color-up ?sz-up) | ||
| - | (retract ?on-ptr );;//удалим отношение, соотв. данному блоку, чтобы продолжить процесс вывода решения | ||
| - | );;//конец defrule | ||
| - | </code> | ||
| - | ==== Headline ==== | ||
| - | <code batch lab5.BAT> | ||
| - | (load lab5.CLP) | ||
| - | (reset) | ||
| - | (run) | ||
| - | </code> | ||
courses/knowledge_representation_and_artificial_intelligence_systems/lab5.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
