필드에서 객체를 찾는 가장 빠른 알고리즘

Question

필드에서 객체를 찾는 속도면에서 가장 좋은 알고리즘은 무엇입니까?

필드는 측면 길이가 30.48 cm 인 18 x 18 정사각형으로 구성됩니다. 로봇은 정사각형 (0, 0)에 배치되고 그 작업은 방해물을 피하면서 광원에 도달하는 것입니다. 광원을 찾기 위해 로봇은 360도 회전하여 가장 밝은 판독 값을 가진 각도를 찾은 다음 소스를 향해 이동합니다. 100 cm에서 광원을 안정적으로 감지 할 수 있습니다.

현재 구현중인 방식은 각 타일에 대한 정보를 2x2 배열에 저장하는 것입니다. 타일의 가능한 값은 미개척 (기본값), 차단 (장애물 있음), 비어 있음 (아무 것도 없음)입니다. 나는 아이들이 위치 (i + 3, j) 또는 (i, j + 3)에있는 DFS 알고리즘을 사용하려고 생각하고있다. 그러나 각 어린이에서 가장 높은 빛의 판독 값을 갖는 각도를 찾기 위해 회전을 할 것이라는 사실을 고려할 때, DFS보다 광원을 더 빨리 찾을 수있는 알고리즘이있을 수 있다고 생각합니다. 또한 로봇이 바닥에있는 그리드 선을 사용하여 x 및 y 위치를 수정하기 때문에 x 및 y 방향으로 만 이동합니다.

이 작업을 수행하는 데 빠르고 신뢰할 수있는 알고리즘을 제안 할 수 있다면 감사하겠습니다.

Answer 1

이것은 매우 광범위한 질문이며 저는 전문가가 아니므로 제 대답은 현장 경험이 아닌 "첫 번째 원칙"에 근거합니다.

는 (나는 로봇 시력과 운동의 일반적으로 탁 트인 라인을 가지고 있으리라 믿고있어, 즉 그렇지 않은 미로에 흩어져 장애물이 열려있는 영역입니다.)

이 문제는 당신이 얻을 수있는 정보를 해석한다 다시 360도 스캔에서.

• 로봇이 다음 광원에 대한 경로를 가로 지르는 광원을 보는 경우

  는 사소한, 또는 "간단한"미로 도보 작업 중 하나입니다.

• 소스가 보이지 않는 경우가 있습니다. 소스가 가시성의 원 안에 있지 않을 수도 있습니다. 그러나 그것은 빛이 장애물 뒤에 있다는 것을 의미 할 수도 있습니다. 그리고 불행히도, 당신 같은 간단한 센서는이 두 가지 경우를 구분할 수 없습니다. 당신의 센서 시스템은 당신이 장애물을 볼 수있는 경우

, 당신은 "그림자"지역 (장애물 뒤에 지역)의 위치를 ​​플롯 및 검색 남아있는 곳을 추적하기 위해 그것을 사용할 수 있습니다. 따라서 귀하의 전략은 소수의 위치를 ​​방문하여 각각을 스캔 한 다음 그림자가있는 소수의 영역을 조직적으로 "정리"하는 것입니다.

그러나 그림자 영역이 어디인지 쉽게 알 수 없으므로 (궁극적으로) 사방을 검색하는 알고리즘이 필요합니다. DFS는 어디에서나 검색 할 수있는 일반적인 전략이지만 실제로는 구석과 구불 구불 한 곳을 (실제로는) 살펴 봅니다. 더 나은 전략은 광 범위 한 검색이 광원을 찾지 못하면 광 범위 한 첫 번째 검색에만 있으며 구석과 구불 구불 한 지점을 방문하는 것입니다. 빠르고 신뢰할 수있는 알고리즘이 작업을 수행하기 위해 제안 할 수 있다면

---

나는 그것을 감사하겠습니다.

당신은 스스로를 개발할 필요가 있다고 생각합니다.(이 문제/과제/경쟁의 지점이 아닌가요?)

Answer 2

이 모양은 좋지 않을 수도 있지만, 문제는 미로 다음과 비슷한 것으로 보입니다. 나는 이것이 일종의 도전이나 경쟁 상황이라고 생각합니다. 시작부터 목표까지 항상 경로가 있지만, 잠시 동안은 그렇지 않다고 가정합니다. 장애물로 완전히 둘러싸인 표지를 탐색하는 로봇의 성공적인 결과 중 하나는 신호를 둘러싼 장애물의 폐쇄 경로에 대한 설명이 포함 된 보고서입니다. 그런 닫힌 경로가 없다면 어딘가에서 구멍을 찾을 수 있습니다. 이것이 미로처럼 보이는 이유입니다.

내가 선택한 기본 알고리즘은 나선형 - 내부 방향 변환으로 시작하여 충분히 좁은 경로를 지나치는 것이므로 신호가 있으면 신호를 볼 수 있습니다. 장애물이 없으면 (퇴행성 사건), 이것은 최소한의 시간 내에 목표물을 찾습니다. (힌트 : 매 턴마다 센서가 단계별로 찾을 수있는 셀의 수를 줄입니다.)

반대로 나선형 순회를 수행하십시오. 그렇다면 당신은 벽에 오른손을 유지하고 생성 된 경로를 따라 미로를 푸는 규칙과 관련이 있습니다. 이 경우 미로의 시작은 경계에 있지만 끝은 아닐 수도 있다는 합병증이 있습니다. 이러한 상황에서 오른손 접촉 경로가 실패 할 수 있습니다. 이 상황을 감지하려면 벽에 인접하여 휩쓸린 지역의 "충치"를 찾아야합니다.