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

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

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

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

EDIT: Для того, чтобы сделать эту проблему более ясной, я пометил некоторые из расстояний Манхэттена на борту:

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

источник

2015-09-02 GengisKhan

Непонятно, что вы просите. Должны ли вы использовать «восхождение на холм», чтобы «оптимизировать» положение или путь? В последнем случае вы можете начать с пути, идущего прямо от начала до цели, и «подняться на вершину», чтобы пройти через все меньше и меньше препятствий, пока не найдете путь, который не пропускает никаких препятствий. –

Спасибо за ваш ответ! «Робот», назовем объект, начинающийся с S, будет использовать алгоритм HC для перемещения. Он не будет использоваться для оптимизации - единственная цель - заставить его перейти в поле F с помощью эвристического механизма. Нам нужно найти тот механизм, который не собирается зацикливаться на коробке под символом S. – GengisKhan

Я думаю, что проблема все еще недоказана. Я понимаю восхождение по холму как локальный поиск, что подразумевает, что в эвристической функции можно учитывать только локальную информацию (например, соседние «состояния»). В этом случае, используя позицию как состояние (а не путь в целом), я не думаю, что это возможно.Но если нет никаких других ограничений на вашу эвристическую функцию, вы можете просто сказать: «Перейдите к квадрату adjacnet, который имеет самое низкое расстояние до F, используя алгоритм поиска A *» (т. Е. Используя полный поиск A * как эвристический для жадных поиск). –

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

Есть два типа тепловых штрафов:

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

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

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

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

источник

2015-09-03 03:39:58

Удивительное, отличное решение! – GengisKhan

Это работает для этой конкретной карты, но в ней много предположений. Например, зачем считать только препятствия на юге? Это сломается, если поле F находится к северу от S, и между ними есть препятствие. Кроме того, он терпит неудачу, если есть узкое узкое место, которое должен пройти робот, чтобы добраться до цели. Но текст в задании специально требует эвристики для решения «этой проблемы», а не «такой проблемы», так что палец вверх! Просто хотел указать. –

@tobias_k Хорошая точка. Я думаю, что без обратного пути невозможно найти общую эвристику, которая будет работать над всеми такими проблемами. Например, вам может понадобиться перемещаться по лабиринту препятствий, чтобы добраться до целевой ячейки. –

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

ответ

Смежные вопросы