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

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

введите описание изображения здесь

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

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

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

введите описание изображения здесь

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


artificial-intelligence heuristics hill-climbing
person GengisKhan    schedule 02.09.2015    source источник
comment
Не совсем понятно, о чем вы спрашиваете. Что следует использовать для подъема на холм, чтобы «оптимизировать» позицию или путь? В последнем случае вы можете начать с пути, идущего прямо от начала до цели, и взбираться по нему, чтобы проходить через все меньше и меньше препятствий, пока не найдете путь, который не проходит через вообще никаких препятствий.   -  person tobias_k    schedule 03.09.2015
comment
Спасибо за ответ! Робот, назовем объект, начинающийся с буквы S, будет использовать алгоритм HC для перемещения. Он не будет использоваться для оптимизации - единственная цель - заставить его перейти в блок F с помощью эвристического механизма. Нам нужно найти тот механизм, который не застревает в коробке под S.   -  person GengisKhan    schedule 03.09.2015
comment
Я думаю, что проблема все еще недооценена. Под восхождением я понимаю локальный поиск, который подразумевает, что в эвристической функции может учитываться только локальная информация (например, о соседних государствах). В этом случае, используя позицию как состояние (а не путь в целом), я не думаю, что это возможно. Но если на вашу эвристическую функцию нет других ограничений, вы можете просто сказать: перейдите к квадрату аджакнета, который имеет наименьшее расстояние до F, используя алгоритм поиска A * (т.е. используя полный поиск A * в качестве эвристики для жадного поиска) .   -  person tobias_k    schedule 03.09.2015

Ответы (1)


arrow_upward
4
arrow_downward

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

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

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

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

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

введите описание изображения здесь

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

person John Coleman    schedule 03.09.2015
comment
Замечательное, отличное решение! - person GengisKhan; 03.09.2015
comment
Это работает для этой конкретной карты, но имеет много предположений. Например, зачем считать только препятствия южнее? Это сломается, если поле F находится к северу от S, а между ними есть препятствие. Кроме того, он не работает, если есть узкое узкое место, через которое робот должен пройти, чтобы добраться до цели. Но текст в задании специально требует эвристики для решения этой проблемы, а не такого рода, так что палец вверх! Просто хотел указать. - person tobias_k; 03.09.2015
comment
@tobias_k Хорошее замечание. Я думаю, что без поиска с возвратом трудно или невозможно найти общую эвристику, которая будет работать со всеми подобными проблемами. Например, вам может потребоваться пройти лабиринт препятствий, чтобы добраться до целевой ячейки. - person John Coleman; 03.09.2015
comment
Еще одна небольшая поправка: манхэттенское расстояние для тупика должно быть 2, а не 4, но это ничего не меняет в результате. - person tobias_k; 03.09.2015
comment
@tobias_k Спасибо - нужно исправить. - person John Coleman; 03.09.2015