Оптимальный алгоритм, чтобы найти выход из лабиринта без информации

Question

Я должен определить способ для робота выйти из лабиринта. Дело в том, что макет лабиринта неизвестен, и положение выхода тоже неизвестно. Робот также начинается в неизвестном месте в лабиринте. Я нашел 3 решения, но мне трудно узнать, что я должен использовать, потому что в конце концов кажется, что решения будут в любом случае случайными. У меня есть эти 3 решения:
1) Основная «человеческая» стратегия (?), Где вы кладете руку на стену и проходите через все лабирины, если необходимо. Я также сохраняю переменную «счетчик поворота», чтобы избежать ситуации, когда петля робота.
2) Глубина первого поиск
3) Создание робота выбрать направление случайным образом

Случайный один кажется хуже, потому что он может взять навсегда, чтобы найти выход (но с другой стороны, он может быть самым быстрым тоже. ..). Однако я не уверен в двух других.
Кроме того, есть ли способ иметь какую-то эвристику? Опять же отсутствие информации заставляет меня думать, что это невозможно, но, может быть, я что-то упустил.

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

Не мог бы кто-нибудь помочь мне, пожалуйста? Спасибо (тоже, извините за мой английский).

Answer 1

Проблемы, подобные этому, относятся к поиску в режиме реального времени, возможно, самым известным примером является Learning Real-Time A *, в котором вы объединяете информацию о том, что вы видели раньше (если вам пришлось отступить или узнать более дешевый способ достичь состояния) и действия, которые вы можете предпринять. Как и в таких областях, как reinforcement learning, некоторый уровень случайности помогает сбалансировать исследования и эксплуатацию.

Предполагая, что ваш график неориентирован, инвариант времени и начальный и конечный узлы существуют в одном и том же компоненте, а выбор направления в случайном порядке в каждой вершине эквивалентен random walk on a graph. Независимо от того, известен ли граф изначально или нет, это очень хорошо изученная область математики, эквивалентная absorbing Markov chain, время достижения состояния выхода в таких случаях имеет Discrete phase-type distribution - часто довольно медленно, но также стоит отметить что в патологических случаях можно создать лабиринт, где случайное блуждание превосходит DFS.

Answer 2

@beaker прямо в том, что первые два, которые вы предложили, должны привести к такому же результату. Тем не менее, вы можете немного улучшить поиск, отслеживая любые петли, которые вы найдете. Если робот окажется в месте, которое он уже посетил, и ему нужно вернуться, когда он приходит в тупик, может быть нет необходимости возвращаться до сих пор, если есть ярлык, который он нашел. Также используйте сегменты, которые были отображены на выходе, и примените алгоритм Дейкстры или A * на нем, чтобы найти наиболее эффективный путь назад. Возможно, будет более быстрый путь назад по неизведанному пути, но это будет самый безопасный способ получить быстрый результат.

Очевидно, что выполнение проверок циклов для предотвращения ненужного отслеживания назад сделает задачу сложнее. Хотя для возвращения к старту с использованием алгоритма Дейкстры не должно быть столь сложным.

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