Данная задача также относится к задачам поиска в простран-
стве состояний. Она широко известна в литературе по искусствен-
ному интеллекту и часто используется для иллюстрации задач
моделирования поведения объектов. Впервые задача "об обезьяне
и бананах" была предложена Дж.Маккарти в 1963 году и звучит
она следующим образом. Обезьяна вместе с ящиком находится в комнате, на потолке
которой подвешены бананы. Обезьяна может достать бананы только
в том случае, если залезет на ящик. Ящик расположен в углу ко-
мнаты, бананы - в центре. Обезьяна может подойти к ящику, пере-
двинуть его и залезть на него. Бананы она сможет достать только
в том случае, если будут стоять на ящике, а ящик будет находить-
ся под бананами. Что должна сделать обезьяна?
В более общем случае эта задача может быть рассмотрена
как задача определения поведением самоуправляющегося объекта,
перед которым поставлена задача и описана текущая ситуация
(управление роботом). Задача "об обезьяне и бананах" была
одной из первых задач, использованых в качестве тестовых при
испытаниях универсального решателя задач GPS (General Problem
Solver). Для диска с данной программой вам может потребоваться
оригинальная упаковка заказать которую
можно тут: http://cdmaker.ru.
Программа LOGTASK2 для решения данной задачи выглядит сле-
дующим образом.
database
is_at(symbol, integer)
monkey_is_off_box
predicates
solve_the_problem
request_position(integer, integer, integer)
go_and_get_bananas(integer, integer, integer)
monkey_works(integer, integer, integer)
move_to(symbol, integer, integer)
go_to(integer, integer)
push_box(integer, integer)
climb_box
grasp_bananas
goal
solve_the_problem.
clauses
/*----- База данных разрешенных состояний -------*/
monkey_is_off_box.
/* Разрешенные состояния для банана */
is_at(bananas,1). is_at(bananas,2).
is_at(bananas,3). is_at(bananas,4).
is_at(bananas,5). is_at(bananas,6).
is_at(bananas,7). is_at(bananas,8).
is_at(bananas,9). is_at(bananas,10).
/* Разрешенные состояния для ящика */
is_at(box,1). is_at(box,2).
is_at(box,3). is_at(box,4).
is_at(box,5). is_at(box,6).
is_at(box,7). is_at(box,8).
is_at(box,9). is_at(box,10).
/* Разрешенные состояния для обезьяны */
is_at(monkey,1). is_at(monkey,2).
is_at(monkey,3). is_at(monkey,4).
is_at(monkey,5). is_at(monkey,6).
is_at(monkey,7). is_at(monkey,8).
is_at(monkey,9). is_at(monkey,10).
/*----------- Правила поиска бананов -------------- */
solve_the_problem :-
makewindow(1,$A,$A,"",0,0,25,80),
makewindow(2,$1E,$1A," ОБЕЗЬЯНА И БАНАНЫ ",
1,10,23,60),
request_position(B,Bo,M),
nl, write(" Обезьяна думает:"),
nl, write(" 'Я хочу взять эти бананы !'"),
go_and_get_bananas(B,Bo,M),
write(" Обезьяна добралась до бананов !"), nl, nl,
write(" ЗАДАНИЕ ВЫПОЛНЕНО !!!"), nl, nl,
write(" Нажмите любую клавишу ..."),
readchar(_).
/* Предикат запроса начального расположения объектов */
request_position(B,Bo,M) :-
nl, nl,
write(" Введите местоположение банана (1-10) : "),
readint(B),
write(" Введите местоположение ящика (1-10) : "),
readint(Bo),
write(" Введите местоположение обезьяны (1-10): "),
readint(M).
/* Основной предикат цели */
go_and_get_bananas(B,Bo,M) :-
is_at(bananas,B), % Проверки
is_at(box,Bo), % допустимости
is_at(monkey,M), % позиций
monkey_works(B,Bo,M).
/* Управление поведением обезьяны */
monkey_works(B,Bo,M) :-
nl, write(" Обезьяна оглядывается и замечает бананы."),
move_to(monkey,Bo,M),
nl, write(" Обезьяна переходит из позиции ",M,
" в позицию ",Bo,"."),
move_to(box,B,Bo),
nl, write(" Обезьяна передвигает ящик из позиции ",Bo,
" в позицию ",B,"."), nl,
climb_box,
grasp_bananas.
move_to(monkey,B,M) :- % Передвижение
is_at(monkey,B), % обезьяны
is_at(monkey,M),
go_to(M,B).
move_to(box,B,C) :- % Перемещение
is_at(box,B), % ящика
is_at(box,C),
push_box(C,B).
go_to(B,C) :- % Передвижение обезьяны
monkey_is_off_box, % Коррекция базы
retract(is_at(monkey,B)),% данных положений
assert(is_at(monkey,C)). % обезьяны
push_box(B,C) :- % Передвинуть ящик
monkey_is_off_box, % Перемещение обезьяны
move_to(monkey,C,B), % вместе с ящиком
retract(is_at(monkey,B)),% Коррекция
retract(is_at(box,B)), % базы данных
assert(is_at(monkey,C)), % положений обезьяны
assert(is_at(box,C)). % и ящика
climb_box :- % Забраться на ящик
monkey_is_off_box,
retract(monkey_is_off_box),
write(" Обезьяна забирается на ящик."), nl.
grasp_bananas :- % Схватить бананы
write(" Обезьяна достает бананы."), nl.
Совокупность фактов, описанных в разделе clauses, опреде-
ляет допустимые местоположения обезьяны, ящика, бананов и
информацию о том, забралась обезьяна на ящик или нет. Для
этих целей используются предикаты is_at и monkey_is_off_box.
Начальная позиция объектов определяется пользователем.
Процедуру диалога реализуется предикатом request_position.
Если обезьяна успешно справится с поставленной задачей, то
конечное состояние будет описываться следующим образом:
1) бананы в начальной позиции;
2) ящик в той же позиции, в которой находятся бананы;
3) обезьяна на ящике;
4) обезьяна схватила бананы.
Для организации перехода из начального в конечное состоя-
ния используются следующие предикаты.
Предикат go_and_get_bananas организует начало перемещения
обезьяны из стартовой позиции.
Предикат monkey_works служит для организации последователь-
ности перемещений обезьяны и ящика (предикат move_to) до дости-
жения конечного состояния, фиксируемого предикатами climb_box и
grasp_bananas.
Комбинация правил move_to и go_to служат для перемещения
обезьяны из одного положения в другое. При этом в предикате
move_to выполняется предварительная проверка допустимости
позиций (по фактам is_at), а предикат go_to удаляет из базы
данных (фактов) старое положение обезьяны и добавляет в нее те-
кущее положение.
Cовместное применение правил move_to и push_box обеспе-
чивают перемещение ящика из одного положения в другое. Предикат
push_box вызывает правило move_to для того, чтобы объединить
передвижение обезьяны и передвижение ящика. При этом происходит
удаление из базы данных старых положений ящика и обезьяны.
Предикаты climb_box и grasp_bananas соответствуют перемеще-
нию обезьяны на коробку и захват бананов. В правиле для преди-
ката climb_box происходит удаление факта monkey_is_off_box
(обезьяна не на ящике), т.к. обезьяна уже находится на ящике.
Для изменения состояния базы данных используются стандар-
тные предикаты Турбо Пролога retract и assert, выполныющие со-
ответственно удаление и занесение фактов в базу данных.
Метод решения логической задачи, используемый в программе
"обезьяна и бананы", называется обратным выводом. Программа
начинает работу с фиксации цели и движется в обратном направле-
нии при помощи унификации предикатов, определяющих промежуточ-
ные подцели. Поэтому программные системы, использующие обратный
вывод, называются системами, управляемыми целью. |
Главная
Каталог файлов
