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

Различия и ключевые операторы

В заключение целесообразно обсудить ряд общих идей, на которых может быть основана редукция задач. К их числу прежде всего относится идея выделения так называемых ключевых операторов и различий состояний. Будем далее предполагать, что задачи и подзадачи описываются в пространстве состояний как тройки вида ( S­_I , O, S_G ), где S­_I и S_G – соответственно начальное и целевое состояния, или же как двойки (S­_I , S_G ), если предполагать неизменным при поиске множество O операторов преобразования состояний.

Часто при поиске в пространстве состояний нетрудно обнаружить один оператор, который обязательно должен входить в решение задачи (по сути, применение этого оператора есть необходимый шаг решения этой задачи). Такой оператор и называется ключевым оператором в пространстве состояний. К примеру, в задаче о пирамидке ключевым оператором был оператор переноса на нужный колышек самого большого диска 3.

Ключевой оператор может быть использован для следующего способа сведения исходной задачи к подзадачам. Пусть

Op – найденный в пространстве состояний задачи ключевой оператор (OpO) ;

S_Op – множество состояний, к которым применим ключевой оператор Op;

Op(s) – состояние, полученное в результате применения ключевого оператора Op к состоянию s (s S_Op).

Тогда исходную задачу можно свести к трем подзадачам:

1. первая задача (S­_I , S_Op) состоит в поиске пути от начального состояния исходной задачи к одному из состояний, к которому применим ключевой оператор Op;

2. вторая задача является элементарной, она заключается в применении этого ключевого оператора;

3. третья задача (Op(s) , S_G) состоит в поиске пути от состояния, полученного применением ключевого оператора, к целевому состоянию исходной задачи.

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

Для большинства задач не удается всегда однозначно выделить ключевой оператор, гораздо чаще удается найти множество операторов-кандидатов в ключевые (т.е. операторов, с большой вероятностью могущих стать ключевыми). Таким образом, в общем случае необходим процесс перебора операторов-кандидатов, каждый из которых образует свое множество результирующих задач (этот перебор и означает поиск на И/ИЛИ-графе задачи).

Самый важный вопрос при таком способе редукции задач состоит в том, как найти кандидаты в ключевые операторы. Один из способов, предложенных и опробованных впервые в одной из наиболее известных систем искусственного интеллекта “General Problem Solver” - GPS (А.Ньюэлл, Г.Саймон, Дж.Шоу – 1957 г.), заключается в выявлении различий для начального и целевого состояний задачи. Различие легче всего формализовать как несоответствие различных элементов описаний начального и целевого состояний.

К примеру, в задаче об обезьяне и банане различием можно считать неравенство соответствующих элементов списков, описывающих два состояния. Тогда при сравнении состояний (Т_О,П,Т_Я,0) и (Т_Я,П, Т_О,1) выявляются три различия – соответственно в первых, третьих и четвертых элементах списков.

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

В задаче об обезьяне и банане естественно связать различия и операторы-кандидаты в ключевые следующим образом:

1. Различие в первом элементе списка-описания состояния (положение обезьяны в плоскости пола) – операторы Перейти и Передвинуть.

2. Различие во втором элементе (положение обезьяны по вертикали) – оператор Взобраться.

3. Различие в третьем элементе (положение ящика) – оператор Передвинуть.

4. Различие в четвертом элементе (содержимое руки обезьяны) – оператор Схватить.

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

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

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

Подчеркнем, что основной механизм системы GPS не был проблемно-ориентированным: он представлял собой реализацию универсального эвристического метода решения задач, часто применяемого человеком, и известного как анализ целей и средств (means-ends analysis). Ключевая идея этой эвристики такова:

1. поиск различий между тем, что дано в поставленной задаче, и тем, что надо получить;

2. последовательное устранение найденных различий с помощью подходящих средств–операций.

Работая в соответствии с этой эвристикой, GPS применяла несколько схем редукции задач (Методов), и на основе выявления различий между объектами задачи и применения уменьшающих эти различия операторов рекурсивно формировала систему (дерево) задач-целей (подзадач).

Краткое описание схемы работы системы 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 в конкретной предметной области необходимо описать Объекты этой ПО и множество учитываемых Различий между Операторами, а также установить связи между Различиями и Операторами (для каждого Оператора указать, какие Различия он может устранить).

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

Операторы Различия	Op1	Op2	Op3	Op4	. . .	OpN
D1	+
D2	+		+
D3		+
D4		+
. . .
DM			+			+

Символ «+ » в позиции <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 }

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

Интеллектуальные роботы

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

В наши дни ведутся работы по «интеллектуализации» технических/промышленных роботов.

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

Иногда предполагается возможность передачи роботу (человеком-оператором) управляющих команд.

В свое время (70-е гг. XX века) задача создания интеллектуальных роботов рассматривалась как универсальная задача-рамка для исследований в области ИИ. Действительно, помимо таких проблем как представление знаний, планирование решения при создании роботов приходится ставить и решать задачи обработки изображений, управления эффекторами, не возникающие в случае более традиционных систем ИИ (решателей интеллектуальных задач).

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

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

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

HEMP, HOLD (x)

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

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

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