Пространство состояний

Представление задачи ИИ в виде пространства состояний. Поиск в глубину

Задачи искуственного интеллекта

Задачи ИИ, как правило, имеют специфическую организацию. Имеется начальное состояние задачи и целевое условие, по которому определяется множество конечных состояний. От состояния к состоянию можно переходить по определенным правилам или ходам. Ход оценивается некоторым числом. Таким образом, программа, решающая такую задачу, переводит ее из состояния в состояние, распознавая ситуацию тупика или конечного состояния.

Опр. 1. Пространство состояний — формализм для представления задачи ИИ — орграф, вершины которого соответствуют состояниям задачи, дуги — возможным переходам из состояния в состояние. Имеется выделенная начальная вершина и целевое условие, по которому определяется множество конечных вершин. Решению задачи соответствует путь в графе от начальной до любой конечной вершины.

Задача о кубиках

При всей своей простоте эта задача является модельной для решения одной из центральных задач робототехники — задачи о составлении упорядоченного плана операций.

Итак, у нас имеется некоторое количество кубиков, поставленных друг на друга. На каждом шаге можно переставить только один верхний кубик. Разрешается образовывать число столбиков не более заданного. Кубик можно ставить на стол или на другой кубик.

Для определенности будем считать, что у нас имеется 3 кубика A, B, C и разрешено образовывать не более трех столбиков. Требуется составить план переупорядочивания кубиков таким образом, чтобы из начальной конфигурации получить конечную.

Проблемная ситуация — положение и состав всех трех столбиков. Разрешенные ходы — перемещения верхнего кубика. Будем задавать состояния как список столбиков, столбики — как список символов, голова списка — верхний кубик.

Начальное состояние: [[‘c’,’a’,’b’]],[],[]].

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

end(Prob):-

member([’a’,’b’,’c’],Prob).

Теперь можно определить правила возможных переходов из состояния в состояние.

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

В Prob1 имеются два столбика Stolb1 и Stolb2 такие, что верхний кубик из Stolb1 можно поставить на Stolb2 (рис. 1):

Рисунок 1. Правило перекладывания верхнего кубика

Удалить из Prob1 непустой столбик Stolb1. Оставшиеся обозначить Tprob1.

Удалить из Tprob1 столбик Stolb2. Оставшиеся обозначить TTProb1.

Голову списка Stolb1 сделать головой списка Stolb2.

go(Prob1,[Stolb1,[H|Stolb2]|TTProb1]):-

del([H|Stolb1],Prob1,TProb1),

del(Stolb2,TProb1,TTProb1).

del(X,[X|L],L).

del(X,[Y|L],[Y|L1]):-

del(X,L,L1).

Теперь пространство состояний задано полностью. Осталось найти путь. Путь на графе можно найти поиском в глубину или ширину. Откажемся пока от однократного просмотра каждой вершины.

Рекурсивная процедура поиска в глубину depth

depth(Way,Sol), где Way — текущий путь;

Sol — окончательное решение;

Z — целевая вершина.

depth([Z|Was],[Z|Was]):-

end(Z).

% рекурсивное правило продолжения пути

depth([X|Was],Sol):-

go(X,Y),

not(member(Y,Was),

depth([Y,X|Was],Sol).

% Запуск глубины с начальной путем из одной вершины

solve:-

A=[[c,a,b],[],[]],

depth([A],Sol), write(Sol), nl.

Sol — список состояний, соответствующий сделанным ходам.

Задание. Написать программу, реализующую составление упорядоченного плана перестановок кубиков поиском в глубину в пространстве состояний.

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

Дата добавления: 2015-06-27