Правильный эвристический механизм для восхождения на холм

Question

Следующая проблема - это экзаменационное упражнение, которое я нашел на курсе искусственного интеллекта.

"Предложите эвристический механизм, который позволяет решить эту проблему, используя алгоритм Hill-Climbing. (S= Начальная точка, F= Конечная точка / цель). Диагональное перемещение не допускается".

Поскольку очевидно, что Манхэттенское расстояние или Евклидово расстояние отправит робота в (3,4), и обратный ход не разрешен, каково возможное решение (эвристический механизм) этой проблемы?

РЕДАКТИРОВАТЬ: Чтобы прояснить проблему, я отметил некоторые расстояния Манхэттена на доске:

Было бы очевидно, что при использовании расстояния Манхэттена следующий шаг робота будет в (3,4), поскольку он имеет эвристическое значение 2 - HC выберет это и застрянет навсегда. Цель состоит в том, чтобы попытаться и никогда не идти по этому пути, находя правильный эвристический алгоритм.

Answer 1

Я думал о препятствиях как о горячих, и это тепло поднимается. Я делаю чистую стоимость ячейки как сумму метрического расстояния Манхэттена до F плюс штраф за тепло. Таким образом, существует сила притяжения, притягивающая робота к F, а также сила отталкивания, которая отталкивает его от препятствий.

Существует два вида штрафов за жару:

1) Очень плохо трогать препятствие. Посмотрите на 2 или 3 ячейки соседних ячеек в ряду непосредственно под данной ячейкой. Добавьте 15 для каждой ячейки препятствий, которая находится непосредственно под данной ячейкой, и 10 для каждой диагональной соседки, которая находится непосредственно под

2) Для ячеек, которые не находятся в прямом контакте с инструкциями - тепло более рассеянное Я рассчитываю это как 6-кратное среднее число блоков препятствий ниже ячейки как в ее столбце, так и в соседних столбцах.

Ниже показан результат объединения всего этого, а также путь от S до F:

Важнейшим моментом является то, как при усреднении робот поворачивается влево, а не вправо, когда он попадает в верхний ряд. Необогреваемые колонны влево делают направление круче. Интересно отметить, как эта эвристика выводит все ячейки (с возможным исключением двух в верхнем правом углу) в F.