Искусственный интеллект – IV курс – День 12, лекция № 23 30.11.2010.

Краткое описание схемы работы системы GPS

Проблемная среда в системе GPS описывается с использованием таких понятий/терминов:

Объекты (элементы проблемной среды)

Различия (между Объектами)

Операторы (способы преобразования Объектов)

Цель

При планировании решения задачи в системе GPS используются:

Три основных Метода (не зависящих от конкретной предметной области):

1. Преобразовать один Объект в другой: A → B

а) Сравнить A с B, найти D = (A - B)

если D = 0, то FIN (успех)

б) ПОДЦЕЛЬ: Уменьшить Различие D

если это не удается, то FIN (неудача), иначе: найдется A’ (нет Различия D с B)

в) ПОДЦЕЛЬ: Преобразовать A’ → B

если это не удается, то FIN (неудача), иначе FIN (успех)

2. Уменьшить Различие между двумя Объектами: D = (A - B)

а) Найти оператор Q, подходящий для уменьшения Различия D

если это не удается, то FIN (неудача)

б) Предварительная проверка применимости Оператора

если Оператор эту проверку не прошел, то FIN (неудача)

в) ПОДЦЕЛЬ: Применить Оператор Q (A), результат A’, FIN (успех)

3. Применить Оператор к Объекту: Q (A)

а) Найти D = (prec (Q) - A)

если D = 0, то результат A’’, FIN (успех)

б) ПОДЦЕЛЬ: Уменьшить Различие D

если это не удается, то FIN (неудача), иначе: найдется A’ (нет Различия D с prec(Q))

в) ПОДЦЕЛЬ: Применить Оператор Q (A’), результат A’’,

если это не удается, то FIN (неудача), иначе FIN (успех)

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

Эти связи можно задать с помощью таблицы (демонстрационный пример):

Символ «+ » в позиции <i, j>, что Op_j может устранить различие D_i.

Предметная область (в которой реально проводились эксперименты с системой GPS) – «Преобразование логических выражений»:

Примеры Различий:

D₁ – в формуле не хватает символов (добавить символ)

D₂ – в формуле есть лишние символы (вычеркнуть символ)

D₃ – в формуле другая связка (изменить связку)

D₄ – в формуле другой знак выражения (изменить знак)

Примеры Операторов:

Op₁ : A & A → A; A V A ↔ A

Op₂ : A V B ↔ (~A & ~B)

Op₃ : A & B → A; A & B ↔ B [относится только к основному выражению]

Правила предварительной проверки применимости оператора:

• Одинакова ли главная связка?

• Не слишком ли «велик» Оператор? { (A V B) & (A V C) → A V (B & C) }

• Не слишком ли «прост»/неспецифичен Оператор? { A → A & A }

• Удовлетворены ли побочные условия? { [относится только к основному выражению] }

Пример: ПЛАНИРОВАНИЕ ДЕЙСТВИЙ РОБОТА В «МИРЕ КУБИКОВ»

Начальное состояние:

CL (C), CL (B), ON (C, A), ONT (A), ONT (B),

HEMP, HOLD (x)

Целевое состояние:

ON (C, B) & ON (A, C) [ & ONT (B) ]

Сложность достижения «целей»:

HEMP 1

CL (x) 2

ONT (x) 2

HOLD (x) 2

ON (x, y) 3

Операторы:

Pickup (x)

prec: ONT (x), CL (x), HEMP

res–: ONT (x), CL (x), HEMP

res+: HOLD (x)

Putdown (x)

prec: HOLD (x)

res–: HOLD (x)

res+: ONT (x), CL (x), HEMP

Stack (x, y)

prec: HOLD (x), CL (y)

res–: HOLD (x), CL (y)

res+: ON (x, y), CL (x), HEMP

Unstack (x, y)

prec: ON (x, y), CL (x), HEMP

res–: ON (x, y), CL (x), HEMP

res+: HOLD (x), CL (y)

Планирование способов достижения целевого состояния: ON (C, B) & ON (A, C)

Иерархическое планирование:

1.Планированине на высшем (3) уровне сложности:

{ Stack (C, B), Stack (A, C) } – предусловия пока не рассматриваем

2.Учет предусловий (планирование на других уровнях сложности):

HOLD (C), CL (A) – res+ оператора Unstack (C, A), CL (B) – выполняется [начальное состояние]

Stack (C, B)

HOLD (A) – res+ оператора Pickup (A), CL (C) – выполняется [res+ оператора Stack (C, B)]

Stack (A, C)

3.Окончательный план: { Unstack (C, A), Stack (C, B), Pickup (A), Stack (A, C) }

6