Человеческий фактор. Том 3. Часть 1 - Сальвенди Г.
ISBN 5-03-001815-8
Скачать (прямая ссылка):
Если MOVE единственный оператор или действие робота, та формируется граф (или дерево) поиска (рис. 2.2).
Рассмотрим более конкретный пример с исходной базой данных, показанной на рис. 2.1, и следующими четырьмя действия-
Глава 2
ми или операциями робота, представленными в формате системы STRIPS.
1. PICKUP (X)
Предусловие и список удалений: ONTABLE(X), CLEAR(Z), HANDEMPTY.
Список добавлений: HOLDING (X).
2. PUTDOWN(X)
Предусловие и список удалений: HOLDING(X). Список добавлений: ONTABLE(X), CLEAR {X), HANDEMPTY.
3. STACK (X, У)
Предусловие и список удалений: HOLDING (X), CLEAR (У). Список добавлений: HANDEMPTY, ON(X, У), CLEAR(X).
4. UNSTACK {X, У)
Предусловие и список удалений: HANDEMPTY, CLEAR(X), ON(X, У).
Список добавлений: HOLDING (X), CLEAR (У). Предположим, что наша цель — ON (В, С) AON (Л, В). Осуществляя поиск в прямом направлении от описания исходного состояния (рис. 2.1), мы получаем все пространство состояний для данной задачи, как показано на рис. 2.8 (на этом рисунке путь решения между исходным и целевым состояниями отображен штриховыми линиями). Последовательность действий, приводящая к решению, имеет вид: {ONSTACK(C, Л), PUTDOWN(C), PICKUP(S), STACKS, С), PICKUP^), STACKS, ?)}. Она называется «планом» достижения цели.
Если решатель задач знает, как каждый оператор изменяет состояние мира или базы данных, а также предусловия выполнения операторов, то он способен решать задачи путем анализа средств и результатов. Вкратце, этот метод предполагает выявление невязки между текущим и целевым состояниями и последующий поиск оператора, который мог бы уменьшить эту обнаруженную невязку. Это будет оператор, для которого список добавлений содержит формулы, способные частично устранять невязку. Процесс рекурсивно продолжается до тех пор, пока не будет достигнуто целевое состояние. Метод анализа •средств и результатов используется не только в системе STRIPS, но и в большинстве других планировщиков.
Мы только что показали, как система STRIPS определяет план решения конкретной задачи, поставленной перед роботом. Следующий этап заключается в обобщении этого конкретного плана путем замены констант новыми параметрами. Иными словами, мы хотим обобщить конкретный план до уровня пла-«а-схемы. Необходимость в обобщении планов очевидна для самообучающейся системы. Для того что*, г можно было сохранять планы с целью использования их чтс~г,й в последующих ^процессах планирования, необходимо з а - предусловия и дей-
PUTDOWN
CLEAR (A) CLEAR (C) HOLDING (5) ONTABLE (A) DNTABIEIC'J
CLEAR (A) ONTABLE (A) CLEAR № ONTABLEW CLEAR (C) ONTABLE ГС) HANDEMPTY
PICKUP^) PICKUP(C)
V P1CKUP(A PUTDOWN 1C)
PUTDOWN (A)
CLEAR (C) CLEAR (B) HOLDING (C) ONTABLE(A) ONTABLE Ш
CLEAR (B) CLEAR (C) HOLDING (A) ONTABLE IB) ONTABLE (C)
CLEAR (A) ON (5,0 CLEAfc (B) ONTABLE (A)
ONTABLE(C) HANDEMPTY
PICKUP (a) I
J
CLEAR (C) ON (BA) CLEAR (Я) ONTABLE (A) ONTABLE (C) HANDEMPTY
PICKUP (C) PUT DOWN (A)
ON (BtC) CLEAR IB) HOLDING (A) ONTABLE (C)
STACK (4^!
I
CLEAR (A)
ON (C,5) CLEAR (C) ONTABLE (A) ONTABLE (B) HANDEMPTY
PICKUP (А) ?
PUTDOWN(С)
un |«.л/ CLEAR (B) HOLDING (С) ONTABLE (A)
STACKS) UNSTACK (A, B)
CLEAR (A) 0Nf.4.?i
on где;
ONTABLE (C) HANDEMPTY
so
CLEAR lb) ON (CA) CLEAR (C) ONTABLE (A) ONTABLE(B) HANDEMPTY
PICKUP (B) PUTDOWN (A)
ON (C,B) CLEAR (C) HOLDING^} ONTABLE (3)
STACK(A,C)
UMSTACK
iC,B)
CLEAR (C)
ON (C,B)
ON (8,A) ONTABLE (A) HANDEMPTY
CLEAR lb)
ON (A.C) CLEAR (A) ONTABLE IB) ONTABLE (C) HANDEMPTY
PICKUP (B) PUTDOWN (5)
ON (C,A) CLEAR (C) HOLDING ^ ONTABLE (A)
STACK(B,C) UNSTACK (A,C)
CLEARS)
0 H(A,CJ ON (C,B) ONTABLE (3) HANDEMPTY
CLEAR(С)
ON (A,B) CLEAR ГА} ONTABLE (B) ONTABLE(O HANDEMPTY
PICKUPS PUTDOWN (B)
ON (A.C) CLEAR (A) HOLDING (B) ONTABLE (C)
STACK(0,A) UNSTACK
(V)
CLEAR (8)
ON (Д C)
ON (C.A) ONTABLE (A) HANDEMPTY
PUTDOWN 1C)
ON (AtB) CLEAR (A) HOLDING (C) ONTABLE (B)
STACK(C^) UNSTACK IB,A)
CLEAR (Bf W(8.A)
ON (A.C) ONTABLE 1C) HANDEMPTY
UNSTACK
(C,A)
CLEAR (Cl ON (C,A)
ON (AJB) ONTABLE (B) HANDEMPTY
Рис. 2.8. Пространство состояний задачи об укладке кубиков роботом.
118 Глава 2
ствия любой части плана. С этой целью планы хранятся в треугольной таблице, строки и столбцы которой соответствуют операторам плана. Треугольная таблица раскрывает структуру плана таким образом, что его части можно позднее выделить и использовать для решения смежных задач.
Пример треугольной таблицы показан на рис. 2.9. Назовем крайний левый столбец нулевым; тогда заголовком каждого /-го столбца будет /-й оператор. Пусть верхняя строка называется первой. Если в последовательности плана N операторов, то последняя строка будет (iV+l)-ft. Записи в ячейке (г, /) таблицы (при />0 и г'<ЛЦ-1)—это те утверждения, которые добавляются к описанию состояния у'-м оператором, выживающим в
о
HANOEMPTY CLEAR (С) ON (С, А) 1 UNSTACK (С, А)
HOLDING (С) г
PUT DOWN (С)
0NTABLE(в) CLEAR fSJ HANDEMPTY 3 PICKUP (В)
CLEAR (С) HOLDING (В) 4 STACK (В, С)
qntAble(А) CLEAR (А) HANDEMPTY 5 PICKUP (А)
