PDF-лекции, страница 8

Если этот список пуст, функция вырабатывает неуспех,который автоматически возвращает программу к предыдущей ее развилке. Иначе функция запоминаетразвилку, альтернативами которой является то, что функция в качестве своего значения может выдатьлюбой элемент из этого списка. Вначале функция выдает как свое значение первый элемент списка,завершает на этом работу, и программа продолжает свои вычисления. Но если позже в программевозникнет неуспех, который вернет ее к данной развилке, то функция возобновит свою работу и теперькак свое значение выдаст второй элемент списка, после чего программа снова «идет вперед». И такдалее, пока в списке остаются нерассмотренные элементы. После выдачи в качестве своего значенияпоследнего элемента списка, функция уничтожает свою развилку и потому последующий неуспех ужене будет здесь остановлен.[alt e1 e2 … en]Функция ставит развилку, i-я альтернатива которой – вычисление формы ei.

Если вычислить значениеудалось, функция заканчивает работу со значением Ei. Перед вычислением en развилка уничтожается.[fail]Эта функция вырабатывает неуспех, по которому программа автоматически возвращается к последней(по времени) развилке. (Если развилок нет, то вычисление всего выражения самого верхнего уровняпрограммы считается окончившимся неуспешно.)[pset v e]Это аналог функции set, т.е. переменной, имя которой является значением аргумента v, присваиваетсяновое значение – значение аргумента e. Однако, если присваивание, осуществленное функцией set,отменяется при неуспехе, то действие функции pset при неуспехе не будет отменено. Функция pset (и ейподобные) применяется, когда надо сохранить информацию, полученную на неуспешном путивычисления программы, для последующих путей.Для управления режимом возвратов помимо использования процедур, результаты которых неотменяются при неуспехе, в Плэнере есть и другие средства:- уничтожение развилок и/или обратных операторов,- использование именованных развилок.Пример плэнер-программы, решающей переборную задачу на основе бэктрекинга:Пусть задан список L положительных целых чисел.

Нужно подобрать набор чисел из L (они могутповторяться), сумма которых равна заданному числу N.[define sum (lambda (L N) [prog ( K (M ( )) (S 0))A[set K [among .L]] [set M ( .K !.M)] [set s [+ .K .S]][cond ([eq .S .N] .M]([lt .S .N] [go A])(T [fail])] ])]Трассировка выполнения программы при L = (6 3 2 1) и N = 5:Вход: K – без значения, M = ( ), S = 025[among (6 3 2 1)]  6[among (6 3 2 1)]  3[set K 6]обр.оператор [unassign K][set K 3][set M (6)]обр.оператор [set M ( )][set M (3)][set S 6]обр.оператор [set S 0][set S 3]S > 5  неуспехS < 5  переход по метке A и новый вызов among:[among (6 3 2 1)]  6[among (6 3 2 1)]  3[among (6 3 2 1)]  2неуспехнеуспехS = 5, выход со значением M.Отметим, что развилки в первом и втором обращениях к функции among остаются. Если в описанноеобращение к функции sum откуда-то извне «придет» неуспех, вычисление может возобновиться (приэтом будут выбираться не исследованные ранее альтернативы).

Например:[prog (X) [set X [sum (6 3 2 1) 5]] [cond ([neq [length .X 3]] [fail])] .X]  (1 1 3).Напечатать (поочередно) все решения рассматриваемой задачи можно с помощью такой конструкции:[prog ( ) [alt ( ) [return T]][print [sum (6 3 2 1) 5]] [fail]]А собрать все решения (в списке Y) и затем выдать этот результат на печать можно так:[prog (X (Y ( )) ) [alt ( ) [return .Y]][set X [sum (6 3 2 1) 5]][pset Y (!.Y .X)] [fail]]ТеоремыТеорема Плэнера – процедура, вызываемая по образцу.В языке существуют три типа теорем: «целевые» (типа conseq), «при записи» (типа antec), «при вычеркивании» (типа erasing).Целевые теоремы используются при планировании решения задач.Если плэнерская база данных может рассматриваться как модель проблемной ситуации, то наборцелевых теорем – как набор средств решения соответствующей задачи.

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

Автоматически выбираются такие теоремы, которые приводят к достижению цели,описываемой в образце этой теоремы. Вызов теорем происходит в сочетании с режимом возвратов;распространение неуспеха может влиять на процесс планирования решения.Все теоремы – любого из трех указанных типов – пользователь должен определять сам (встроенныхтеорем в языке нет).Пример определения целевой теоремы:[define TRAN-R (conseq (x y)(at R *y)[search1 (AT R *x)][erase (AT R .x)][assert (AT R .y)] )]Эта теорема (с именем TRAN-R) описывает перемещение робота (R) из точки x в точку y. Теоремаможет быть вызвана по образцу – (at R *y) – в ситуации, когда ставится цель «робот R должен попастьв некоторую точку проблемной среды», скажем в точку G (такая целевая ситуация описываетсявыражением (at R G), которое соответствует образцу теоремы).

Добиться этого можно, применивданную теорему (выполнив соответствующее ей действие в предметном мире) или, возможно, какие-тодругие теоремы из числа описанных в программе.Тело этой теоремы предписывает:- найти точку, в которой находится R,- вычеркнуть из базы данных утверждение о том, что R находится в этой точке,- записать в базу данных утверждение о новом местонахождении R.Вызов целевых теорем осуществляется с помощью функции achive (или goal):26[achive pat rec?]- pat – образец, rec? – факультативная рекомендация;[goal pat test? rec?] - pat – образец, test? – факультативный набор требований к списку свойствутверждения, rec? – факультативная рекомендация;Функция goal перед тем, как начать вызов теорем, проверяет, не представлена ли целевая ситуация вбазе данных в виде утверждения (это означает, что цель на самом деле достигнута, никакого вызоватеорем, никакого планирования решения не нужно).Факультативный параметр rec (рекомендации) позволяет влиять на процесс перебора теорем, отдаватьприоритет некоторым теоремам, учитывать их «стоимость» и т.п.

Более того, можно "редактировать"(динамически менять) рекомендации с учетом попыток вызова других теорем.Примеры рекомендаций:(use T1 [ ])- вызвать теорему с именем T1, а если вызов неуспешен, вызывать все остальные,(try [NOT T3]) - вызывать все теоремы кроме T3,(use1)- если найдена одна успешная теорема, отменить все развилки.Пример определения теоремы типа «при вычеркивании»:[define КУБИК_ОСВ (erasing (X)(=ЗАНЯТ= *X)[assert (=СВОБОДЕН= .X)])]Если из базы данных вычеркивается утверждение о том, что "поверхность некоторого кубика X занята"(если так, то на него нельзя поставить другой кубик), то автоматически будет вызвана и выполнена этатеорема. Она запишет в базу данных утверждение: "поверхность этого кубика X освободилась" (теперьна него можно поставить другой кубик).Вызов теорем типа «при вычеркивании» осуществляется с помощью функции change – либо явно:[change pat rec?], либо неявно (из функции erase).Пример определения теоремы типа «при записи»:[define ПРИШЕЛ (antec (X Y Z)(*X =ПРИШЕЛ= *Y)[search1 (.X =НАХОДИТСЯ_В= *Z)][erase (.X =НАХОДИТСЯ_В= .Z)][assert (.X =НАХОДИТСЯ_В= .Y)])]Если в базу данных записывается утверждение о том, что "X пришел в Y (из Z)", то автоматически будетвызвана и выполнена эта теорема.

Она найдет в базе данных утверждение о прежнем местонахожденииX, вычеркнет это утверждение и запишет, что "X находится вY".Вызов теорем типа «при записи» осуществляется с помощью функции draw – опять же либоявно: [draw pat rec?], либо неявно (из функции assert).День 7. Проблема знаний - центральная проблема ИИВ данном разделе курса речь идет о проблемах формирования, хранения и использования «знаний»(пока мы считаем, что «знания» – любая информация о системе и ее окружении) на всех этапахжизненного цикла системы искусственного интеллекта (системы ИИ)/интеллектуальной системы (ИС).1.Терминологические замечания:а) Предметная область (ПО) – «срез» действительности, со своими объектами, отношениями.Проблемная область (ПО) – Предметная область + характерные задачи.Примеры:Предметная область – Лисп как язык для обработки списковПроблемные области: автоматический синтез программ на Лиспе,автоматизированное обучение приемам программирования на Лиспе.б)Из психологии и педагогики нам известна триада: знания – умения – навыки.Знания – усвоенные Понятия.Умения – способность выполнять новые действия в новых условиях.Навыки – действия, автоматизировавшиеся в процессе их усвоения и выполнения.В работах по ИИ знаниями обычно называют и собственно знания, и умения, и навыки.Поэтому говорят о: базах понятий, базах фактов, базах правил и т.п.27Вот, например, два определения из Интернет-ресурса «Тематическая служба толковых словарей» –http://www.glossary.ru.Знания (в информатике) – вид информации, отражающей опыт специалиста (эксперта) вопределенной ПО, его понимание множества текущих ситуаций и способы перехода от одногоописания объекта к другому.Знания о ПО подразделяются на:-факты, относящиеся к ПО;-закономерности, характерные для ПО;-гипотезы о возможных связях между явлениями, процессами и фактами;-процедуры для решения типовых задач в данной ПО.Чтобы не вступать в противоречие с литературными источниками, мы согласимся с такой трактовкой(расширенной) термина знания.в)Базы знаний (БЗ) в работах по ИИ часто не совсем корректно противопоставляются базам данных(утверждается, например, что базы знаний в отличие от баз данных имеют встроенный дедуктивныймеханизм вывода следствий из известных фактов и т.п.).Для нас это феномены разноплановых уровней:База знаний – (у нас) – совокупность «знаний» системы ИИ в компьютерном представлении.