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

Искусственный интеллект – IV курс – День 05, лекции № 9, № 10 29.09.2009.

Язык ПЛЭНЕР

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

Вспомним «Особенности задач ИИ (с точки зрения программирования)»:

1. сложные и динамически меняющиеся структуры данных;

2. большие по объему хранилища данных (базы знаний) и средства эффективной работы с ними;

3. символьные (в основном) данные;

4. модели, отражающие состояние проблемной среды;

5. переборные алгоритмы;

6. алгоритмы поиска по образцу;

7. гибкие структуры управления.

Основные составляющие языка Плэнер:

• средства для работы со списками (лисповская часть, используется для работы со списками)

• плэнерская база данных (используется для моделирования ситуаций проблемной среды)

• встроенный режим возвратов (реализует один из основных методов перебора – бэктрекинг)

• аппарат работы с образцами (используется для анализа структуры списков)

• аппарат теорем (используется при планировании решения)

позволяют достаточно эффективно (и быстро) реализовать соответствующие возможности.

Три типа процедур языка Плэнер:

- функции;

- сопоставители (для работы с образцами);

- теоремы (процедуры, вызываемые по образцу).

Примеры конструкций и процедур Плэнера:

Обращение к функции:

[ELEM -2 (A B C D)] → C

Выдать второй (2), считая с конца списка (знак "минус" при 2), элемент списка (A B C D).

Сопоставление образца с выражением:

[IS (*X ПРИШЕЛ !*Y) (САША ПРИШЕЛ ИЗ МАГАЗИНА)] → T

Сопоставление успешно, то есть образец (*X ПРИШЕЛ !*Y) соответствует выражению (САША ПРИШЕЛ ИЗ МАГАЗИНА). Побочный эффект: переменная X получает значение САША, а переменная Y получает значение (ИЗ МАГАЗИНА)

Утверждение плэнерской базы данных:

(BOX A (3 7)) - ящик с названием А находится на плоском квадратном поле с пронумерованными клетками в третьей строке (по горизонтали) и в седьмом столбце (по вертикали).

Запись утверждения в плэнерскую базу данных:

[ASSERT (BOX A) (WITH COL RED)] – в базу данных записывается утверждение (BOX A), то есть "А является ящиком"; записывается также, что "цвет" (COL) этого ящика "красный" (RED).

Поиск утверждения в плэнерской базе данных:

[SEARCH (BOX [ ]) (TEST COL [NON GREEN])] – в базе данных ищется утверждение о некотором ящике, цвет которого не (NON) зеленый (GREEN); возможный ответ (результат поиска) – (BOX A).

Определение плэнерской теоремы:

[DEFINE ОСВОБОДИЛИ (ERASING (X)

(=ЗАНЯТ= *X)

[ASSERT (=СВОБОДЕН= .X)])]

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

Перейдем к более детальному рассмотрению основных составляющих Плэнера.

Основные объекты языка, средства для работы со списками

Выражения:

• атомарные:

- обращения к переменным

- атомы: идентификаторы, числа, строки

• списковые:

- L-списки (списки в круглых скобках: ( и ) )

- P-списки (списки в квадратных скобках: [ и ] )

- S-списки (списки в «уголках»: < и > )

Ограничители: <пробел>, ( , ) , [ , ] , < , >; цифры; буквы; специальные литеры + , - , . , * , : , ! .

Префиксы: . , * , : - простое обращение к переменным; !. , !* , !: - сегментное обращение к переменным.

Простые формы:

- атомы (значением атома является сам этот атом),

- обращения к переменным с префиксом . ,

- обращения к константам с префиксом : ,

- L-списки (значением L-списка является список из значений его элементов),

- P-списки (обращения к процедурам).

Сегментные формы:

- обращения к переменным с префиксом !. ,

- обращения к константам с префиксом !: ,

- S-списки (сегментные обращения к процедурам).

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

В языке имеется много встроенных (стандартных) функций.

Определение новых функций

Для определения новой функции следует обратиться к встроенной функции define:

[define f dexp]

Вычисление функции define в качестве побочного эффекта приводит к появлению в программе новой функции с именем f и т.н. определяющим выражением dexp, которое должно иметь вид

(lambda (v₁ v₂ … v_n) e) (n≥0)

где v_i - формальные параметры новой функции, а e - форма, зависящая от v_i.

При последующем обращении к этой новой функции

[f a₁ a₂ … a_n]

сначала вычисляются аргументы (фактические параметры) a_i, затем вводятся локальные переменные v_i, которым присваиваются значения соответствующих аргументов a_i, и далее вычисляется форма e при этих значениях переменных v_i, после чего эти переменные уничтожаются. Значение данной формы становится значением функции f при аргументах a_i.

Операции над списками

[elem n l]

Значением аргумента n должно быть ненулевое целое число (обозначим его N), а значением второго аргумента - список (L) с любыми скобками. Значением функции является N-й от начала элемент списка L, если N>0, или |N|-й от конца элемент этого списка, если N<0. В случае, когда в качестве n явно указано число, имя функции в обращении можно опустить; например, [1 .X] - это сокращение от [elem 1 .X], т.е. выделяется первый от начала элемент списка, являющего значением переменной X.

[rest n l]

Значением аргумента n должно быть ненулевое целое число (N), а значением второго аргумента - список (L) с любыми скобками. Значением функции является результат отбрасывания N первых элементов списка L, если N>0, или |N|-й последних его элементов, если N<0.

[head n l]

В такой же ситуации значением функции является список из N первых элементов списка L, если N>0, или |N|-й последних его элементов, если N<0.

Пример: [rest 2 [head 5 (1 2 3 4 5 6) ] ] (3 4 5)

Если требуется вычислить список в круглых скобках

(e₁ e₂ … e_n) (n≥0)

т.е. если он рассматривается как форма, то все его элементы должны быть формами. Значением такого списка является список (с круглыми скобками) из значений его элементов. Например, если переменная X имеет значение (a b), то значением списка (.X c [-1 .X]) является список ((a b) c b).

В таких списках можно использовать сегментные формы (сегментные обращения к переменным и сегментные обращения к процедурам, <elem 5 .X>). Сегментная форма вычисляется как обычная (простая) форма, но затем у ее значения, если это список, отбрасываются внешние скобки, и полученная таким образом последовательность элементов поставляется вместо сегментной формы. Например, если переменная X имеет значение (a (b c)), то:

(5 .X ( )) (5 (a (b c)) ( )), (5 !.X ( )) (5 a (b c) ( )), (!.X !.X) (a (b c) a (b c)).

Если переменная X имеет значение (1 2), а переменная Y – значение (3 4):

(.X !.Y) ((1 2) 3 4) – на Лиспе эти действия задаются так: (cons X Y)

(!.X !.Y) (1 2 3 4) – на Лиспе эти действия задаются так: (append X Y)

Арифметические функции

[+ n₁ n₂ … n_k] (k≥2)

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

[- n₁ n₂]

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

[max n₁ n₂ … n_k] (k≥2)

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

[min n₁ n₂ … n_k] (k≥2)

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

Предикаты

Предикатом называется форма, значение которой рассматривается как логическое значение «истина» или «ложь». При этом в Плэнере «ложью» считается пустой список ( ), а «истиной» – любое другое выражение (чаще всего в роли «истины» выступает атом T).

[num e]

Эта функция-предикат проверяет, является ли числом значение ее аргумента. Если да, то значение функции равно T («истина»), иначе – ( ) («ложь»).

[empty e]

Функция проверяет, является ли значение ее аргумента пустым списком (с любыми скобками). Если да, то значение функции равно T, иначе – ( ).

[eq e₁ e₂]

Функция сравнивает значения своих аргументов. Если они равны, то значение функции – T , иначе – ( ).

[neq e₁ e₂]

Аналог, но значения аргументов сравниваются на «не равно».

[memb e l]

Значением функции является номер первого вхождения формы E в список L.

[gt n₁ n₂], [ge n₁ n₂], [lt n₁ n₂] – сравнение, соответственно, на «больше», «больше или равно» и «меньше».

Предикаты, проверяющие состояние переменных

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

1) переменная не описана (в некоторой функции встретилась нелокальная переменная, которая не описана в динамически объемлющих процедурах/блоках),

2) переменная описана, но не имеет значения,

3) переменная описана и имеет некоторое значение.

Для анализа таких ситуаций используются предикаты: [bound v] и [hasval v].

Первый из этих предикатов проверяет, является ли значение его параметра описанной (в динамически объемлющих процедурах/блоках) переменной. Если да, возвращается значение T, иначе – ( ).

Значением аргумента предиката hasval должно быть имя переменной, существующей в данный момент. Функция проверяет, имеет ли сейчас эта переменная какое-либо значение или нет. Если имеет, то функция возвращает результат T, а иначе - результат ( ).

Функции для работы со списками свойств идентификаторов

Идентификаторы (и некоторые другие объекты) Плэнера могут иметь т.н. списки свойств – списки пар: свойство-значение. Если идентификатор является именем некоторого объекта проблемной среды (например, ящика, который может перемещаться роботом), в списке свойств могут быть указаны цвет этого ящика, его вес, линейные размеры и т.п.

Для задания списка свойств используется функция [plist i pl]. При выполнении обращения к ней идентификатор I получает список свойств PL = (ind₁ val₁ … ind_n val_n). Отметим, что отсутствие некоторого свойства эквивалентно тому, что это свойство присутствует в списке со значением ( ).

Функция [put i ind val] позволяет изменить значение указанного свойства IND идентификатора I, а функция [get i ind?] – получить весь список свойств I (если параметр ind не задан), или же узнать значение указанного свойства.

Логические функции

Функции «отрицание», «конъюнкция», «дизъюнкция» и «условное выражение» аналогичны соответствующим лисп-функциям:

[not e]