연속지도 (예 : 다각형)에 대한 경로 찾기 알고리즘
다각형 장애물이있는 평면에서 두 지점 사이의 짧은 경로에 대해 서로 다른 알고리즘을 조사하려고합니다. 내가 찾은 대부분의 알고리즘은 개별 맵 (그리드 맵, 가시성 그래프, 보로 노이 로드맵 등)을 사용합니다. Ben-Ari의 "Elements of Robotics"또는 Nikolaus Correll의 "Introduction to Autonomous Robots"와 같은 일부 책은 연속 맵 (예 : 원시 다각형 데이터)을 언급하지만 해당 알고리즘에 대해서는 설명하지 않습니다. 그들은 몇 가지 간단한 장애물에 대한 메모리 또는 효율성 이점을 주장하는데, 이는 저에게 매우 흥미로울 수 있습니다.
기하학적 계산 (예 : 교차점 감지)과 일부 알고리즘 패러다임 (예 : 최소 비용 분기 및 경계)을 사용하는 현명한 접근 방식이 있어야한다고 생각하지만 휠을 잘못 재발 명하고 싶지는 않습니다.
연속 맵이나 유용한 키워드를 사용하여 검색 할 수있는 단거리 (가장) 경로 알고리즘에 대한 리소스가 있습니까?
제안 된대로 내가 사용한 용어 중 일부를 지정하려고합니다.
연속지도 ( 그림 참조)는 기하학적 모양의 (연속적인) 실수 값의 저장을 나타냅니다. 장애물 / 삼각형 I.는 A = (3,2), B = (7,5), C = (7,2)로 저장됩니다.
이산 맵 ( 그림 참조)은 청크로 세분화 (예 : 그리드 맵에서와 같이 이산화)를 나타냅니다. 장애물 / 삼각형 I.은 이제 셀 인덱스로 저장됩니다 : (3,2), (4,2), (5,2), (6,2), (5,3), (6,3), ( 6,4) 불연속지도에서 경로 찾기는 종종 Dijkstra 또는 A *와 같은 그래프 기반 알고리즘으로 수행됩니다.
기하학적 계산 은 연속 맵에 대한 경로 찾기 알고리즘에서 기대할 수있는 계산 기하학 연산에 사용하는 모호한 용어 일뿐입니다. (예 : 변환, 수직 거리, 교차점 감지)
답변
당신이 부르는 "연속 맵"의 경우 모든 정점에 Dijkstra를 사용하십시오. 유일한 차이점은 노드 간의 거리를 계산할 때 클리핑을 확인해야한다는 것입니다.
내 문제에 대해 더 자주 사용되는 또 다른 용어는 Euclidean Shortest Path (s) 인 것 같습니다 . Continuous maps 와 Discrete maps에 대한 알고리즘의 차이점은 나에게 약간 모호한 것 같습니다.
그러나 연속 맵에 대한 알고리즘에서 가장 가까운 것은 연속 Dijkstra 문제에 대한 Mitchell의 알고리즘 (또는 연속 Dijkstra 방법)입니다. 이 알고리즘은 시작점에서 고르게 퍼지는 웨이블릿을 사용합니다. 웨이블릿의 "회절"에 의해 직접 도달 할 수없는 영역에 도달합니다. 이렇게하면 연속 구성 공간의 모든 지점에 대한 유클리드 최단 경로를 식별하는 데 사용할 수있는 최단 경로 맵이 생성됩니다.
자세한 내용은 다음을 참조하십시오.
- F. Li 및 R. Klette의 "Euclidean Shortest Paths Exact or Approximate Algorithms"
- 멋지지만 약간 버그가있는 이반 첸의 애니메이션
- Anton Kovsharov의 신청
생성 된 최단 경로 맵은 연속적인 구성 공간의 또 다른 이산화 일 뿐이라고 주장 할 수 있습니다. 그러나 최단 경로 맵은 알고리즘을 전체 구성 공간에 적용하면 얻을 수있는 결과 일 뿐이라고 생각합니다. 두 지점 사이의 최단 경로 만 원하는 경우 알고리즘은 목표 지점에 도달 한 후 중지 할 수 있습니다. 나는 이러한 알고리즘의 분류에 대해 확신이 없지만 이것이 내 질문에 답할 것입니다.