정보가없는 미로의 출구를 찾는 최적의 알고리즘

Question

로봇이 미로에서 벗어날 수있는 방법을 결정해야합니다. 문제는 미로의 레이아웃을 알 수 없으며 이탈 위치도 알 수 없다는 것입니다. 로봇은 또한 미로에서 알려지지 않은 위치에서 시작합니다. 3 가지 솔루션을 찾았지만 어느 것이 사용해야하는지 알기가 힘듭니다. 결국 솔루션은 순전히 무작위 적으로 보이기 때문입니다. 나는이 3 가지 해결책을 가지고있다 :
1) 벽에 손을 대고 필요한 경우 모든 미로를 통과하는 기본적인 "인간"전략 (?). 또한 로봇 루프가있는 상황을 피하기 위해 변수 "회전 카운터"를 유지합니다. 로봇을 만들기
2) 깊이 우선 탐색
3) 그가 출구를 찾기 위해 영원히 걸릴 수 있습니다 (그러나 다른 한편으로는 그가 너무 빠른 될 수 있기 때문에 랜덤 하나가 더 나쁜 것 같다 무작위로

방향을 선택합니다. ..). 하지만 다른 두 사람에 대해서는 잘 모르겠습니다.
또한 어떤 종류의 경험적 방법이 있습니까? 다시 한 번 정보가 없어서 불가능하다고 생각하게되었지만, 아마도 뭔가를 잃어 버렸을 것입니다.

마지막 사항 : 로봇이 이탈을 발견하면 그는 A *를 사용하여 시작 위치로 돌아 가야합니다. 이것은 첫 번째 부분에서 출구를 찾는 곳에서 그가 2 부에 사용할 미로의지도를 그릴 것임을 의미합니다. 아마 이것은 첫 번째 부분에 대한 최상의 알고리즘을 선택하는 데 도움이 될 수 있지만, 왜 나는 사람이 더 나을지 모르겠다.

누군가 나를 도와 줄 수 있습니까? 고마워 (또한, 나의 영어를 위해 유감스럽게 생각한다).

Answer 1

이와 같은 문제는 실시간 검색으로 분류됩니다. 가장 잘 알려진 예로 Learning Real-Time A *가 있습니다. 여기에서 이전에 본 내용에 대한 정보를 결합 할 수 있습니다 (역 추적하거나 보다 쉬운 방법으로 국가에 접근 할 수 있음), 그리고 취할 수있는 행동. reinforcement learning과 같은 영역의 경우와 같이 일정 수준의 무작위성은 탐색과 개발의 균형을 유지하는 데 도움이됩니다.

그래프가 방향이없고 시간이 일정하지 않고 초기 및 종료 노드가 동일한 구성 요소에 있다고 가정하면 각 꼭지점에서 임의로 방향을 선택하면 random walk on a graph과 같습니다. 그래프가 처음에 알려진 것인지 아닌지에 관계없이 이것은 매우 잘 이해되는 수학 분야로 absorbing Markov chain과 같으며이 경우 이탈 상태에 도달하는 시간은 Discrete phase-type distribution입니다. 그러나 종종 느리게 나타납니다. 병적 인 경우에는 무작위 도보가 DFS보다 우수한 미로를 설계 할 수 있습니다.

Answer 2

@beaker는 당신이 제안한 처음 두 가지는 동일한 결과를 이끌어 내야한다는 점에서 옳습니다. 그러나 찾은 루프를 추적하여 검색을 약간 향상시킬 수 있습니다. 로봇이 이미 방문한 곳에서 로봇을 찾으면 로봇이 막 다른 골목으로 되돌아 가야한다. 찾은 지름길이 있다면 지금까지 갈 필요가 없다. 또한 나가는 길에 매핑 된 세그먼트를 사용하고 Dijkstra의 알고리즘 또는 A *를 적용하여 가장 효율적인 방법을 찾으십시오. 미지의 길로 돌아 오는 것이 더 빠를 수 있지만 빠른 결과를 얻는 가장 안전한 방법입니다.

분명히 불필요한 백 추적을 막기 위해 루프 검사를 구현하면 구현하기가 더 복잡해집니다. Dijkstra의 알고리즘을 사용하여 처음으로 돌아 오면 복잡한 것은 아닙니다.

이제는 출구를 발견 한 야심이 있다면 무작위로 생성 된 미로에서 많은 도움이되지는 않지만이 정보를 사용하여 로봇에게 방향 감각을 줄 수 있습니다.