Эта функция вырабатывает неуспех, по которому программа автоматически возвращается к последней (по времени) развилке. (Если развилок нет, то вычисление всего выражения самого верхнего уровня программы считается окончившимся неуспешно.)

[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 = 0

[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):

[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).

Проблема знаний

В данном разделе курса речь идет о проблемах формирования, хранения и использования «знаний» (пока мы считаем, что «знания» – любая информация о системе и ее окружении) на всех этапах жизненного цикла системы искусственного интеллекта (системы ИИ)/интеллектуальной системы (ИС).

1.Терминологические замечания:

а) Предметная область (ПО) – «срез» действительности, со своими объектами, отношениями.

Проблемная область (ПО) – Предметная область + характерные задачи.

Примеры:

Предметная область – Лисп как язык для обработки списков

Проблемные области: автоматический синтез программ на Лиспе,

автоматизированное обучение приемам программирования на Лиспе.

б)Из психологии и педагогики нам известна триада: знания – умения – навыки.

Знания – усвоенные Понятия.

Умения – способность выполнять новые действия в новых условиях.

Навыки – действия, автоматизировавшиеся в процессе их усвоения и выполнения.

В работах по ИИ знаниями обычно называют и собственно знания, и умения, и навыки.

Поэтому говорят о: базах понятий, базах фактов, базах правил и т.п.

Вот, например, два определения из Интернет-ресурса «Тематическая служба толковых словарей» – http://www.glossary.ru.

Знания (в информатике) – вид информации, отражающей опыт специалиста (эксперта) в определенной ПО, его понимание множества текущих ситуаций и способы перехода от одного описания объекта к другому.

Знания о ПО подразделяются на:

-факты, относящиеся к ПО;

-закономерности, характерные для ПО;

-гипотезы о возможных связях между явлениями, процессами и фактами;

-процедуры для решения типовых задач в данной ПО.

Чтобы не вступать в противоречие с литературными источниками, мы согласимся с такой трактовкой (расширенной) термина знания.

в)Базы знаний (БЗ) в работах по ИИ часто не совсем корректно противопоставляются базам данных (утверждается, например, что базы знаний в отличие от баз данных имеют встроенный дедуктивный механизм вывода следствий из известных фактов и т.п.).

Для нас это феномены разноплановых уровней:

База знаний – (у нас) – совокупность «знаний» системы ИИ в компьютерном представлении. Средством представления «знаний» может быть, в частности, та или иная штатная база данных (в обычном смысле).

2.Некоторые острые аспекты проблемы знаний:

Проблема извлечения знаний

Извлечение знаний – процесс взаимодействия инженера по знаниям с источником знаний (экспертом), в результате которого становятся явными процесс рассуждений специалистов при принятии решения и структура их представлений о предметной области.

Проблема приобретения знаний

Приобретение знаний – автоматизированное построение базы знаний посредством диалога эксперта и/или инженера знаний со специальной программой формирования БЗ.

Экспертные знания – знания, которыми располагает специалист в некоторой проблемной области.

Эксперт – специалист в некоторой проблемной области.

Инженер знаний/Инженер по знаниям/Когнитолог – специалист по искусственному интеллекту, проектирующий и создающий базу знаний системы ИИ. Обычно инженер по знаниям выступает в роли «посредника» между экспертом и базой знаний

Проблема открытости знаний

Совокупность «знаний» системы ИИ неизбежно должна быть открыта для включения в нее новой информации, отражающей динамику проблемной среды и динамику поручаемых системе ИИ заданий.

Открытость может быть реализована по-разному:

- пополнение БЗ «хирургическим путем» (программист/администратор вносят изменения в тексты БЗ),

- обучение системы пользователем в рабочем режиме,

- самообучение системы (приспособление ее к новым условиям/задачам).

3.Базовые методы представления знаний:

Метод представления знаний – совокупность взаимосвязанных средств формального описания знаний и оперирования (манипулирования) этими описаниями.

(аналог модели данных в теории Баз Данных – понятие концептуального уровня)

Логические методы (язык предикатов)

Знания, необходимые для решения задач и организации взаимодействия с пользователем, – факты (утверждения).

Факт – формула в некоторой логике.

Система знаний – совокупность формул.

База знаний – система знаний в компьютерном представлении.

Основные операции: логический вывод (доказательство теорем)

Примеры:

иметь (Саша, книга) «Саша имеет книгу»

иметь (Саша, книги)  иметь (Саша, книга) «Если Саша имеет книги, то он имеет книгу»

(x) [человек (x)  иметь (x, книга)] «Каждый человек имеет книгу»

(x) [свободен (x)  (y) (на (y,x))] «Если кубик x свободен, то нет такого кубика y,

который находится на кубике x»

Достоинства:

• формальный аппарат вывода (новых фактов/знаний из известных фактов/знаний),

• возможность контроля целостности,

• простая и ясная нотация.

Недостатки:

• знания трудно структурировать,

• при большом количестве формул вывод идет очень долго,

• при большом количестве формул их совокупность трудно обозрима.

Семантические сети

Знания, необходимые для решения задач и организации взаимодействия с пользователем, – объекты/события и связи между ними.

Статические семантические сети - сети с объектами.

Динамические семантические сети (сценарии) - сети с событиями.

Система знаний – совокупность сетей (или одна общая сеть).

База знаний – система знаний в компьютерном представлении.

Для представления семантических сетей используются графы:

вершина - атомарный объект (событие),

подграф - структурно сложный объект (событие),

дуга - отношение или действие.