Помощь поисковым алгоритмам в решении проблем, не зависящих от предметной области.
Эвристика: резюме
В предыдущем посте мы обсуждали эвристику, которая представляет собой оценку минимальной стоимости от состояния до целевого состояния, чтобы помочь поисковому алгоритму уменьшить количество узлов, которые он должен исследовать, чтобы найти план решения, в надежде, что это сократит время выполнения алгоритма поиска и найдет оптимальный план.
Другими словами, без эвристики алгоритмы поиска исследуют вслепую, чтобы найти решение. С помощью эвристики алгоритмы поиска информируются.
В предыдущем посте мы рассмотрели примеры для конкретной предметной области, чтобы показать, как эвристика помогает визуализировать исследованные и выбранные узлы. Вы можете прочитать сообщение здесь:
В этом посте мы рассмотрим независимую от предметной области эвристику, которую можно использовать для задач планирования, не зависящих от предметной области, которые нас интересуют.
Расслабление
В предыдущем посте мы немного обсудили расслабление, которое является наиболее известным способом написания эвристической функции, путем ослабления некоторых ограничений, которые мы используем в нашей области планирования. В следующих разделах мы увидим конкретные примеры релаксации.
В этом посте мы рассмотрим два связанных алгоритма:
- Макс-стоимость
- Добавка
Эвристика максимальной стоимости
Чтобы понять эту эвристику и эвристику аддитивной стоимости, мы начнем с заимствования термина из логики предикатов, буквального.
литерал - это атомарная формула или ее отрицание.
и атомная формула, или атом
Атомарная формула - это логическое выражение
Определения взяты отсюда.
По сути, мы разбиваем состояние нашей цели на литералы. В нашем примере Pacman, показанном на рисунке ниже, цель - съесть все три продукта.
Мы можем разбить состояние нашей цели на 3 литерала:
- food (a, b) = Ложь
- food (c, d) = Ложь
- food (e, f) = Ложь
Оттуда мы можем двигаться назад от состояния цели к состоянию, которое нас интересует. Это лучше визуализировать с помощью дерева И / ИЛИ.
И / или Дерево
Определение And / Or Tree:
Дерево, узлы которого помечены И или ИЛИ.
Хорошо визуализировать сокращение проблем до подцелей, например, что мы делаем с нашим состоянием цели Pacman.
Визуализация
Цель разбита на три литерала, и все они должны иметь значение Истина, чтобы узел цели имел значение Истина (узел цели - это узел И, показанный дугой соединяя все три его края).
Узел food (a, b) = F является узлом OR, у него 3 дочерних элемента (допустим, для этого примера), ему нужно, чтобы только один из его дочерних элементов был True . Этот узел является узлом действия.
Чтобы развернуть узел, мы используем предварительные условия действия:
- нет стены между ними, то есть движение возможно
- Pacman находится на локации
Этот процесс продолжается до тех пор, пока мы не достигнем состояния, которое оцениваем.
У действия есть соответствующая стоимость, после того, как мы завершили построение дерева, мы можем рассчитать стоимость.
Узлы, выделенные красным, показывают состояние, которое мы оцениваем, общая стоимость этой ветви составляет 2. Предположим, что общая стоимость следующей ветви равна 1, а последняя - 10.
Эвристическая функция максимальной стоимости возвращает 10, поскольку это максимальная стоимость из трех ветвей.
Расслабление в этом подходе состоит в том, что он использует только максимальную стоимость всех литералов. Проблема планирования смягчается тем, что предполагает, что цель может быть достигнута, просто используя один литерал в цели.
Чтобы увидеть разницу, мы используем алгоритм GBFS без эвристической функции и с эвристической функцией максимальной стоимости для решения нашей проблемы.
Без эвристики Pacman исследует все возможные области, как показано ниже.
Используя эвристику максимальной стоимости, Pacman может уменьшить исследуемые области, как показано красными точками ниже.
Понятно, что эвристика максимальной стоимости помогает уменьшить количество узлов, исследуемых Pacman.
В следующем разделе мы рассмотрим немного другой подход - эвристику аддитивной стоимости.
Эвристика аддитивной стоимости
Эвристика аддитивной стоимости тесно связана с эвристикой максимальной стоимости. Это недопустимо, потому что стоимость часто превышает оптимальную.
Напомним, что 0 ≤ h (s) ≤ h * (s).
Эвристика аддитивной стоимости использует тот же подход, что и эвристика максимальной стоимости, но вместо того, чтобы выбирать наибольшую стоимость среди всех литералов, складывает их все. Этот подход обычно лучше на практике, потому что он учитывает все литералы, а не только один из них.
Используя дерево И / или со стоимостью на рисунке выше, эвристика дает в сумме 2 + 1 + 10 = 13.
Давайте посмотрим, как он работает с нашей проблемой:
Мы видим, что это работает лучше, чем эвристика максимальной стоимости и без эвристики, и решения другие. Смотрите видео ниже, чтобы увидеть выполнение планов.
Рассмотрение
Хотя количество исследуемых узлов уменьшается при использовании этих двух эвристик, мы всегда должны учитывать компромисс между временем вычисления эвристической функции и количеством сокращенных узлов.
Эвристика полезна только в том случае, если она сокращает общее время, необходимое алгоритму поиска, в противном случае, даже если она помогает уменьшить количество исследуемых узлов, она не имеет смысла, если общее время больше, чем без эвристики.
В нашем примере доступные действия для Pacman довольно низкоуровневые, поскольку он перемещает Pacman только на один шаг, они не связаны напрямую с другими литералами в состояниях, таких как еда, капсулы и т. Д. Поэтому, используя эти две эвристики, общее время больше, чем без эвристики. Потому что эвристика - это, по сути, обратный поиск от цели к состоянию, которое мы хотим исследовать.
Эвристика удаления-релаксации
В следующем посте мы обсудим другой подход - эвристику удаления-релаксации.
