AI-2009 Day 06 (Лекции 2009 года)

Искусственный интеллект – IV курс – День 06, лекции № 11, № 12 06.10.2009.

Образцы и сопоставители

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

- функцию is, реализующую сопоставление образца с выражением,

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

Соответствующие возможности Плэнера мы рассмотрим кратко и в основном на примерах.

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

Если выражение удовлетворяет требованиям шаблона, то говорят, что оно соответствует образцу, если нет, то не соответствует. В первом случае сопоставление образца с выражением удачно, во втором – неудачно.

Обращение к функции is выглядит так:

[is pat e], где pat – образец, e – выражение (сопоставление производится с E – значением e).

Алгоритм сопоставления в общем случае сложен, он предполагает возвраты. Важно, что удачное сопоставление может сопровождаться побочными эффектами – переменным, входящим в состав образца могут присваиваться в качестве значений соответствующие фрагменты выражения. Это позволяет резко сократить запись сложных действий по анализу данных и выделению важных для работы фрагментов.

Примеры (считаем, что используемые переменные описаны вне обращений к is, например, в каком- то объемлющем блоке):

[is (*X .X) (b b)] T - сопоставление удачно, X (побочный эффект) получает значение b

отметим, что при сопоставлении первого элемента образца (*X) с

первым элементом выражения (b) переменная X получила значение b;

второй элемент образца (.X) требует, чтобы рассматривалось текущее

значение переменной X (префикс точка), т.е. как раз b; поэтому

удачным будет и сопоставление второго элемента образца со вторым

элементом выражения.

[is (*X .X) (b (b))] ( ) - сопоставление неудачно;

[is (*X !*Y) (1 2 3)] T - сопоставление удачно; X:= 1, Y:= (2 3)

[is (*X *Y) (1 2 3)] T - сопоставление неудачно (образец описывает список длиной два).

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

Пример: [list n] - сопоставитель, соответствующий списку из N элементов

[is [list 2] (a b)] T - сопоставление удачно;

[is [list 2] (a b c)] ( ) - сопоставление неудачно;

[is (a <list 2> a) (a b b a)] T - сопоставление удачно (сегмент b b соответствует сегментному

обращению к сопоставителю list;

[is (a [list 2] a) (a (b b) a)] T - сопоставление удачно.

В Плэнере есть около 30 встроенных сопоставителей, в том числе: логические (типа and и or), типа сond, типа prog (вводят локальные переменные).

Сопоставитель [ ] соответствует любому выражению, сопоставитель < > - любому сегменту.

Некоторые встроенные сопоставители

Сопоставители (без параметров): id (идентификатор), num (число), var. (обращение к переменной с префиксом "."), var*, var:, var!., var!*, var!:, atomic (атомарное выражение) – проверяют тип выражения.

[aut  pat₁ … pat_n] – сопоставитель "ИЛИ"; сопоставление с некоторым выражением успешно, если выражение соответствует одному из указанных образцов.

[et  pat₁ … pat_n] – сопоставитель "И"; сопоставление с некоторым выражением успешно, если выражение соответствует каждому из указанных образцов.

[when  pat₁ pat_1,1 pat_1,2 … pat_1,k1) … (pat_n pat_n,1 pat_n,2 … pat_n,kn)] – "УСЛОВНЫЙ" сопоставитель; если выражение соответствует образцу pat_i, то применяется сопоставитель [et pat_i,1 pat_i,2 … pat_i,ki].

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

Определение новых сопоставителей

[define <имя> (kappa <список параметров> pat)]

Пример:

[define pal (kappa ( )

[aut ( ) [list 1] [same (X) (*X <pal> .X)]])]

- рекурсивный сопоставитель pal соответствует любому списку-палиндрому; в нем использованы: логический сопоставитель aut (аналог or), известный нам сопоставитель list, сопоставитель-блок same (вводящий локальную переменную X). Сопоставитель pal проверяет (последовательно): не является ли выражение пустым списком; списком длиной 1; списком, первый и последний элементы которого совпадают, а «середина» удовлетворяет требованиям pal.

Плэнерская база данных

База данных Плэнера не имеет никакого отношения к базам данных как объекту традиционного программного обеспечения (реляционным или сетевым, СУБД). Она похожа на т.н. доску объявлений.

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

Основные операции над базой данных: запись утверждения, вычеркивание утверждение (по образцу), поиск утверждения (по образцу).

Запись

[assert asrt with? rec? else?] – функция assert служит для записи явно заданного (в виде L-списка) утверждения asrt в базу данных. Факультативный параметр with задает список свойств записываемого утверждения (он имеет такую же структуру, что и список свойств идентификатора, но связан с утверждением в целом). Факультативный параметр rec указывает, какие теоремы следует вызвать при записи данного утверждения (некоторые теоремы могут вызываться в этот момент автоматически). Факультативный параметр else содержит рекомендации по поводу того, что следует делать, если записать указанное утверждение в базу данных не удалось (например, потому, что такое утверждение в базе данных уже хранится).

Пример: пусть переменная X имеет значение green

[assert (box A) (with col .X) (else)] - параметр rec в этом примере опущен

При выполнении этого обращения к функции assert происходит следующее:

1) в базу данных записывается утверждение (box A) - имеется ящик A,

2) с ним связывается список свойств (col green) - его цвет – зеленый,

3) если утверждение записать не удалось, то (в соответствии с конкретным видом последнего параметра – else – вырабатывается неуспех.

Поиск

[search pat test?] – основная функция для поиска в базе данных утверждений по образцу pat. Параметр test (факультативный) позволяет задать требования, предъявляемые к списку свойств утверждения.

Функция search ставит развилку; ищет утверждение, соответствующее образцу; проверяет его список свойств (если он не удовлетворяет требованиям параметра test, ищется другое утверждение соответствующее образцу). Если подходящее (соответствует образцу, удовлетворяет требованиям test, параметр test не задан) утверждение найдено, оно является результатом обращения к search; развилка не уничтожается, следовательно, если в динамике до этого обращения к search «доберется» неуспех, начнется поиск новых утверждений, соответствующих pat. Если найти утверждение, соответствующее pat и удовлетворяющее test, не удалось, развилка отменяется и вырабатывается неуспех.

Пример: пусть после выполнения обращения к assert из предыдущего примера мы задаем:

[search (box [ ]) (test col [non red])]

Результат поиска – утверждение (box A).

Поиск утверждений можно вести поэтапно – находить утверждения, «частично соответствующие» образцу (функция candidates, обращение к которой имеет вид [candidates pat type?]), а затем более детально анализировать полученный «список кандидатов». Можно искать только одно подходящее утверждение (функция search1).

Вычеркивание

[erase pat test?] – функция для удаления из базы данных утверждений, соответствующих образцу pat и удовлетворяющих требованиям параметра test (если он задан).

Пример: стереть утверждение (box A) со списком свойств (col green) можно так:

[erase (box [ ]) (test col [non red])]

Плэнерская база данных, отображающая состояние проблемной среды:

( room R1)

(room R2)

(conn R1 R2 D)

(door D) (at ROBBY R1)

(box A) – (col green) (at A R2)

(box B) – (col red) (at B R2)

В этой ситуации можно выполнять операции поиска:

[search (at ROBBY R1)] → T

[search (at ROBBY R2)] → ( )

[search (at ROBBY *X)] → T, X:= R1

[find all (Y) .Y [search (room *Y)]] → (R1 R2)

Режим возвратов

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

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

Ниже перечислены некоторые из встроенных функций языка Плэнер, позволяющих реализовать режим возвратов.

[among e]

Значением аргумента должен быть список. Если этот список пуст, функция вырабатывает неуспех, который автоматически возвращает программу к предыдущей ее развилке. Иначе функция запоминает развилку, альтернативами которой является то, что функция в качестве своего значения может выдать любой элемент из этого списка. Вначале функция выдает как свое значение первый элемент списка, завершает на этом работу, и программа продолжает свои вычисления. Но если позже в программе возникнет неуспех, который вернет ее к данной развилке, то функция возобновит свою работу и теперь как свое значение выдаст второй элемент списка, после чего программа снова «идет вперед». И так далее, пока в списке остаются нерассмотренные элементы. После выдачи в качестве своего значения последнего элемента списка, функция уничтожает свою развилку и потому последующий неуспех уже не будет здесь остановлен.

[alt e₁ e₂ … e_n]

Функция ставит развилку, i-я альтернатива которой – вычисление формы e_i. Если вычислить значение удалось, функция заканчивает работу со значением E_i. Перед вычислением e_n развилка уничтожается.

[fail]

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

[pset v e]