그래프의 부분 지식을 가진 길 찾기 알고리즘

Question

"미로"(시작점, 목표, 빈 칸 및 교차 할 수없는 공백 또는 "벽"이있는 직사각형 그리드)를 통해 로봇을 탐색하는 알고리즘을 프로그래밍해야합니다. 이동 당 일정한 비용으로 모든 추기경 (N, NW, W, SW, S, SE, E, NE)으로 이동할 수 있습니다.

문제는 로봇이지도의 레이아웃을 "알지 못한다"는 것입니다. 8 개의 주변 공간 만보고 저장할 수 있습니다 (방문하는 모든 공간의 주변 타일을 암기합니다). 유일한 다른 입력은 모든 이동에 목표가있는 기본 방향입니다.

이 문제를 해결하기 위해 구현할 수있는 연구 알고리즘이 있습니까? Dijkstra 또는 A *와 같은 전형적인 것들은 비용없이 그래프에서 이전 노드를 다시 방문 할 수 없기 때문에 사소한 작업에 적응하지 못합니다 (더 나은 경로로 이동하는 단계를 거슬러 올라가면 이동 비용이들 것입니다. 다시), 그리고 A *에 대한 합리적인 경험법을 만드는 방법을 생각할 수 없습니다.

은 아마 합리적인 뭔가 가지고 올 수 있지만, 난 그냥이 이미 해결 문제가 있다면 알고 싶어, 나는 바퀴를 재발견 할 필요가 없습니다 : P 어떤 조언을위한

감사합니다!

Answer 1

문제는 해결되지 않지만 많은 계획 문제와 마찬가지로 이미 많은 양의 연구가 가능합니다.

이 영역의 대부분의 작업은 R. E. Korf의 "실시간 휴리스틱 검색"논문의 원본을 기반으로합니다. 그 논문은 페이 월 (paywalled) 인 것으로 보이지만,이 논문의 preliminary results은 Real-Time A * 알고리즘에 대한 토론과 함께 계속 사용할 수 있습니다.

숨겨진 상태 (그래프의 부분적 지식이있는 경로 찾기)에 대한 최신 계획은 Sven Koenig입니다. 여기에는 Learning Real-Time A * 알고리즘에 대한 중요한 작업이 포함됩니다.

Koenig의 작품에는 시뮬레이션에서 발생할 가능성이있는 이론적 인 실험에 대한 다양한 알고리즘 데모가 포함되어 있습니다. 특히 Koenig와 Simmons의 "Easy and Hard Testbeds for Real-Time Search Algorithms"을 참조하십시오.