18:231 Эвристический поиск Вывод знаний 2. © Муромцев Д.И. Лекция 8 18:232 Понятие эвристики Эвристика (eurisco, греч. исследовать) - «изучение методов. - презентация

1 18:231 Эвристический поиск Вывод знаний 2

2 © Муромцев Д.И. Лекция 8 18:232 Понятие эвристики Эвристика (eurisco, греч. исследовать) - «изучение методов и правил открытий и изобретений». В задачах искусственного интеллекта эвристику используют в двух ситуациях: Проблема может не иметь точного решения из- за неопределённости в постановке задачи и/или в исходных данных. Проблема может иметь точное решение, но стоимость его поиска может быть слишком высокой.

3 © Муромцев Д.И. Лекция 8 18:233 Эвристические функции оценки состояний Начальное и целевое состояния игры в восемь. Подходы, учитывающие функцию оценки расстояния от текущего состояния до цели, называют поиск по первому наилучшему совпадению (Greedy best-first search).

4 © Муромцев Д.И. Лекция 8 18:234 Оценка пространства поиска для игры в 8 Размеры пространства поиска можно оценить исходя из следующих соображений: средне количество шагов решения для случайно расположенных фишек составляет равно 22, средний коэффициент ветвления равен трем, так как при нахождении пустой клетки в центре возможно 4 различных хода, на одной из сторон по центру – 3 хода, и при пустой угловой клетке – 2 хода. То есть при полном переборе на глубину 22 придется рассмотреть состояний. Для аналогичной «игры в пятнадцать» пространство поиска будет оцениваться уже в 1013 состояний.

5 © Муромцев Д.И. Лекция 8 18:235 Подходы к вычислению эвристической функции Эвристическая функция h1 подсчитывает количество фишек, стоящих не на своих местах. Эвристическая функция h2, равная сумме расстояний всех фишек от их целевых позиций. Поскольку рассчитываемое расстояние представляет собой сумму горизонтальных и вертикальных перемещений, эту величину называют также манхэттенским расстоянием (Manhattan distances) или расстоянием, измеряемым в городских кварталах.

6 © Муромцев Д.И. Лекция 8 18:236 Ограниченность эвристических функций Пример состояния с хорошей эвристической оценкой, но до достижения цели еще далеко

7 © Муромцев Д.И. Лекция 8 18:237 Сравнение эвристических функций

8 © Муромцев Д.И. Лекция 8 18:238 Поиск А* Суммарная оценка А* выглядит следующим образом: f(n) = g(n) + h(n), где g(n) – это фактическая длина пути от произвольного состояния n к начальному, а h(n) – эвристическая оценка расстояния от состояния n до цели. Поскольку функция g(n) позволяет определить стоимость пройденного пути от начального состояния, а функция h(n) определяет оценку стоимости до цели, то можно утверждать, что функция f(n) есть оценка наименее дорогостоящего пути, проходящего через состояние n.

9 © Муромцев Д.И. Лекция 8 18:239 Сравнение значений стоимости поиска dIDSA*(h1)A*(h2) Для формирования оценок использовались 1200 случайным образом сформированных примеров состояний игры «в восемь» с длиной решения от 2 до 24 (по 100 экземпляров для каждого значения длины).

10 © Муромцев Д.И. Лекция 8 18:2310 Свойства эвристических функций Если алгоритм гарантирует нахождение кратчайшего пути к решению, то такой алгоритм называют допустимым или приемлемым (admissible). Класс допустимых эвристических алгоритмов поиска можно охарактеризовать с помощью функции f(n) = g(n) + h(n), Примечательно, что стратегия поиска в ширину может рассматриваться как разновидность алгоритма А*, в котором f(n) = g(n) + 0. Свойство, позволяющее находить кратчайший путь к каждому состоянию, которое встречается в процессе поиска, называется монотонностью (monotonicity). Формально свойство монотонности можно описать с помощью неравенства треугольника: h(n) = c(n, a, n) + h(n). где n - вершина текущего состояния, n - ее потомок, соответствующий следующему состоянию, a - вершина целевого состояния. Оценка стоимости достижения цели из состояния n не больше чем стоимость перехода из n в n + оценка стоимости достижения цели из n. Если для всех состояний n верно неравенство h1(n) h2(n), то говорят, что эвристика h2 более информирована, чем h1.

11 © Муромцев Д.И. Лекция 8 18:2311 Примеры алгоритмов интеллектуального поиска Алгоритм «восхождение на гору» «Жадный» алгоритм Процедура минимакса Альфа-бета-усечение

12 © Муромцев Д.И. Лекция 8 18:2312 Интеллектуальное планирование Задача планирования заключается в поиске последовательности действий, применение которой к начальному состоянию модели мира, приводит к достижению целевого состояния.

13 © Муромцев Д.И. Лекция 8 18:2313 Среда планирования (planning environment) Частично или полностью наблюдаемая среда. В полностью наблюдаемой среде алгоритму планирования доступна вся информация о состоянии модели мира в каждый момент времени. Детерминированная или стохастическая среда. В детерминированной среде всегда точно известно, каким будет результат выполнения того или иного действия. Конечная или бесконечная среда. Для конечной среды можно привести описание всех возможных состояний: объектов, их свойств и отношений. Следовательно, бесконечная среда не может быть полностью наблюдаемой. Статическая или динамическая модель мира. В статической модели мира изменение состояний происходит только в результате работы планировщика. В динамической модели допускаются изменения мира по своим внутренним законам, не зависимо от воздействия со стороны. Дискретные или непрерывные действия во времени. Если действия дискретны, то они не имеют длительности, и свойства мира во время выполнения действий не определены. Изменения в модель мира вносятся, только после завершения действия.

14 © Муромцев Д.И. Лекция 8 18:2314 Классическое планирование Классическое планирование осуществляется в средах, являющихся полностью наблюдаемыми, детерминированными, конечными, статическими и дискретными. Для представления состояний модели мира используются конъюнкции означенных (ground) положительных литералов исчисления предикатов первого порядка (то есть не содержащих свободных переменных). Также для описания состояний не допускается использование функций.

15 © Муромцев Д.И. Лекция 8 18:2315 Аномалия Зюссмана и нелинейное планирование В линейных планировщиках STRIPS-подобных систем используется предположение, что подцели всегда можно достигать последовательно. Очевидное решение заключается в том, чтобы сначала установить кубик B на кубик C, а затем кубик A на кубик B. Но после установки кубика B на C, для выполнения следующего действия (установки A на B), необходимо чтобы кубик А был свободен. Для обеспечения этого условия необходимо снять кубик C с A. А до этого потребуется снять B с C. Но это приведет к противоречию c результатом предыдущего шага – глобальная цель не должна нарушаться на интервале от точки ее достижения до конца выполнения плана.

16 © Муромцев Д.И. Лекция 8 18:2316 Нелинейное планирование Для формирования плана состоящего из зависимых действий может потребоваться их чередование (interleaving), подразумевающее выбор нового действия исходя из его вклада (commit) в выполнение другого действия. Стратегия, в которой в процессе поиска выбор шагов откладывается на более позднее время, получила название планирование с наименьшим вкладом (Least Commitment Planning). Для задач, аналогичных аномалии Зюссмана, отложенные (deferred) действия – это то, что может упорядочить процесс выполнение плана. Таким образом, обеспечивается вклад в общее решение на любом этапе поиска, так как в первую очередь выбираются те действия, которые безотлагательно должны быть выполнены для продолжения процесса поиска решения.

17 © Муромцев Д.И. Лекция 8 18:2317 Этапы планирования решения для аномалии Зюссмана (1)

18 © Муромцев Д.И. Лекция 8 18:2318 Этапы планирования решения для аномалии Зюссмана (2)