임의각 경로 계획

임의각 경로 계획 알고리즘은 공간 내 두 지점 사이의 경로를 검색하고 경로의 회전이 임의의 각도를 가질 수 있도록 하는 경로 탐색 알고리즘의 하위 집합이다. 그 결과는 목표를 향해 직진하고 상대적으로 턴이 적은 길이다.^[1] A*와 같은 다른 경로 탐색 알고리즘은 들쭉날쭉한 간접 경로를 생성하는 그리드에 대한 경로를 제한한다.

배경

실제 세계와 많은 게임 지도에는 가장 효율적으로 직접 횡단되는 열린 영역이 있다. 기존 알고리즘은 다음과 같은 문제를 해결하기에 적합하지 않다.

• 8개의 분리된 격자 그래프를 가진 A*는 매우 빠르지만 45도 증분으로 경로를 볼 뿐이다. 빠른 스무팅 후 단계를 사용하여 들쭉날쭉한 출력을 직진(즉, 단축)할 수 있지만, 가능한 모든 경로를 보지 않기 때문에 결과가 최적의 결과를 보장할 수 없다. (더 구체적으로, 차단된 셀의 어느 쪽을 통과하는지 변경할 수 없다.) 점프 포인트 검색과 같은 그리드 A*의 최적화가 모두 적용되는 것이 장점이다.
• 모든 격자점이 표시된 가시성 그래프는 A*로 검색하여 최적의 솔루션을 찾을 수 있다. 그러나 $V{\displaystyle }$ ${\displaystyle V}$ 정점이$$ 있는 그래프의 에지 수가 $O{\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle O(V^{2})$이므로 성능은 문제가 있다$.$

An-angle path planning 알고리즘은 기본 가시성 그래프 접근법보다 시간을 적게 들이면서 최적 또는 거의 최적 솔루션을 생산하는 것을 목표로 한다. 빠른 Any-angle 알고리즘은 그리드 기반 컴퓨팅 솔루션과 거의 동일한 시간이 걸린다.

정의들

토우트 경로

경로의 모든 제목이 어떤 장애물 주위에 단단히 "걸려" 있는 경로. 균일한 그리드의 경우, taut 경로만 최적일 수 있다.

단일 소스

하나의 꼭지점에서 시작하여 그래프에서 모든 부분에 대한 최단 경로를 찾으려는 경로 찾기 문제.

알고리즘

이 절에는 비교표(최적성, 균일하지 않은 그리드에 대한 지원, 단일 소스 [전체 지도], 그리고 일부 속도 메트릭에 대한 정보가 누락되어 있다. 이 정보를 포함하도록 섹션을 확장하십시오. 자세한 내용은 대화 페이지에 있을 수 있다. (2020년 7월)

A* 기반

지금까지 휴리스틱스 검색 알고리즘 ^[2]A*에 기반한 5가지 주요 An-angle 경로 계획 알고리즘이 개발되었으며, 이 모든 알고리즘은 그리드 가장자리를 따라 정보를 전파한다.

• 필드 D*(^[3][4]FD*)^[5] 및 3D 필드 D*^[6][7] - 각 꼭지점 확장 시 보간법을 사용하고 규칙적이고 통일되지 않은 비용 그리드를 통해 최적에 가까운 경로를 찾는 D* 기반 동적 경로 찾기 알고리즘. 따라서 필드 D*는 가중 영역 문제와^[8] 3D 필드 D*에 해당하는 3차원 문제를 해결하려고 시도한다.
  • 다중 분해능 필드 D*^[9] – 다중 분해능 그리드를 위한 필드 D* 확장.
• 만약 가시 거리, p에서 경로는 rent(s)은 Theta*[5][10]-A*지만 한 꼭지점 s{s\displaystyle}의 각 확장에 대비한, p사이의 송수 신선이 직결된 수표는 rent(s){\displaystyle parent(s)}과 s{s\displaystyle}의 후계자, s′{s\displaystyle'} 된다. 이에 동일한 루프를 사용합니다. {\disp항상$$ p ${\displaystyle a}$ r ${\displaystyle \mathrm{en}}$ ${\displaystyle t}$( ${\displaystyle s}$) ${\displaystyle s'}$에서 s ${\displaystyle$ $s$$}$까지의 경로만큼 짧기 때문에 $laystyle parent(s)$에서 s${\$까지의 경로를 사용한다$.$ 이 알고리즘은 균일한 비용 그리드에서만 작동한다.^[5] Theta*의 O(1)에 가시 거리 내 계산을 수행하는의 비용 감소에 angle-propagation을 사용합니다 APTheta*[5][10] 있는 최적화, 그리고 Theta*의 각 노드에 대한 시정 계산을 지연시킴으로썰 때e.에서 가시 거리 내 계산의 수를 줄이려는 게으른 평가를 사용하여 게으른 Theta*[11]은 또 다른 최적화에 xplored 확장이 되면 증분 Phi*^[12]는 알려지지 않은 2D 환경을 위해 설계된 Teta*의 증분적이고 효율적인 변형이다.^[13]
  • 엄격한 테타*와 반복적인 엄격한 테타*는 ANYA가 도입한 Taut 경로로 검색 공간을 제한함으로써 테타*를 개선한다. Theta*와 마찬가지로, 이것은 거의 최적 경로를 반환하는 알고리즘이다.
• 블록 A* - 그리드의 작은 섹션에서 가능한 모든 경로를 포함하는 로컬 거리 데이터베이스 생성 이 데이터베이스는 조각별로 모든 각도 경로를 신속하게 찾기 위해 이 데이터베이스를 참조한다.
• ANEA^[16] - 검색 공간을 Taut 경로(일부 장애물을 중심으로 모든 헤딩이 "wrap" 변경되는 경로)로 제한하여 최적의 임의 각도 경로를 찾는다. 단일 지점이 아닌 노드로서 지점 간격을 살펴본다. 알려진 가장 빠른 온라인 최적 기술.
• CWave^[17][18] - 기하학적 원시 요소(원형 호와 선 분리)를 사용하여 그리드의 전파 전방을 나타낸다. 실제 지도에 있는 단일 소스 경로 계획의 경우, 그래프 검색 기반 방법보다 더 빠른 것으로 입증된다. 최적 및 정수 산술 구현이 있다.

위의 제품군과 구별되는 A* 기반 알고리즘도 있다.

• 가시성 그래프 접근법의 성능은 팽팽한 경로를 형성할 수 있는 가장자리만 고려하는 희박한 접근법에 의해 크게 개선될 수 있다. ENLSVG라는 다단계 버전이 ANEA보다 빠른 것으로 알려져 있지만, 사전 처리와 함께만 사용할 수 있다.^[19]
• 아래에서 논의한 RRT 솔루션과 유사하게, 실제 차량을 조종할 때 조향 제약도 반드시 고려해야 하는 경우가 많다. 하이브리드 A*는 차량 상태를 나타내는 두 개의 추가 치수를 고려하는 A*의 연장선으로, 경로가 실제로 가능하다. 스탠포드 레이싱이 주니어를 위한 내비게이션 시스템의 일부로 DARPA Urban Challenge에 참가하기 위해 만들었다.^[20] 좀 더 자세한 토론은 Peterit, et al.에 의해 쓰여진다.^[21]

RRT 기반

또한, 시스템의 구성 공간이 고려해야 할 많은 자유도를 포함할 때(동작 계획 참조), 그리고/또는 모멘텀을 고려할 필요가 있다(검색 공간의 치수 수를 효과적으로 배가할 수 있음). 모멘텀을 포함한 이 더 큰 공간을 알 수 있다.n 위상 공간으로서), 빠르게 탐색되는 무작위 트리(RRT)^[22]의 변형들이 개발되어 있으며, (거의 확실히) 점점 더 짧고 짧은 경로를 발견함으로써 최적의 경로로 수렴된다.

• 빠르게 탐색되는 RRG(Random Graph) 및 RRT*^[23][24]
• 지식 RRT*^[25]는 A*가 Dijkstra 알고리즘에서 향상되는 방식과 유사한 휴리스틱스를 도입하여 RRT*의 수렴 속도를 향상시킨다.

적용들

임의각 경로 계획은 보다 최적의 경로가 바람직한 로봇 내비게이션과 실시간 전략 게임에 유용하다. 예를 들어 하이브리드 A*는 DARPA 챌린지에 대한 항목으로 사용되었다.^[20] 일부 사례의 조향 인식 특성은 자율주행차로도 해석된다.

참고 항목

• 모션 기획

참조

외부 링크

• 게으른 세타*: 모든 각도 경로 계획 속도 향상
• A. 나시와 S. 코에니그. 모든 각도 경로 계획. 인공지능 매거진, 34, (4), 85-107, 2013.
• Any Angle Pathfinding, Sunhao Oh의 오픈 소스 데모 코드