경로 검색

Pathfinding
그 외의 용도는, 패스파인더(명료화)를 참조해 주세요.
그래프와 트리
검색 알고리즘
최단 경로
리스트
관련 토픽
2D 환경에서 A와 B 사이의 동등한 경로

경로 찾기 또는 패싱은 컴퓨터 응용 프로그램에 의해 두 지점 사이의 최단 경로를 표시하는 것입니다.그것은 미로를 해결하는 데 있어 보다 실용적인 변형이다.이 연구 분야는 가중 그래프에서 최단 경로를 찾기 위한 다이크스트라의 알고리즘에 크게 기초하고 있다.

경로 검색은 그래프 이론 내의 최단 경로 문제와 밀접하게 관련되어 있습니다.그래프 이론에서는 대규모 네트워크 내의 2개의 포인트 간에 어떤 기준(최단, 최저, 고속 등)을 가장 잘 충족하는 경로를 식별하는 방법을 조사합니다.

알고리즘

패스파인딩 방법은 하나의 정점에서 시작하여 목적지 노드에 도달할 때까지 인접 노드를 탐색함으로써 그래프를 검색하며, 일반적으로 가장 저렴한 경로를 찾는 것을 목적으로 한다.폭 우선 검색과 같은 그래프 검색 방법은 충분한 시간이 주어지면 경로를 찾지만 그래프를 "탐색"하는 다른 방법은 목적지에 더 빨리 도달하는 경향이 있습니다.예를 들어 방을 가로질러 걸어가는 사람이 있을 것이다; 가능한 모든 경로를 미리 검토하기 보다는, 그 사람은 일반적으로 목적지의 방향으로 걷고 장애물을 피하기 위해 경로에서 벗어날 뿐이고 가능한 한 사소한 일탈을 할 것이다.

경로 검색의 두 가지 주요 문제는 (1) 그래프 내의 두 노드 간의 경로를 찾는 것과 (2) 최단 경로 문제를 찾는 것입니다.폭 우선 및 깊이 우선 검색과 같은 기본 알고리즘은 모든 가능성을 소진하여 첫 번째 문제를 해결합니다. 지정된 노드에서 시작하여 대상 노드에 도달할 때까지 모든 가능한 경로에 걸쳐 반복됩니다.이러한 알고리즘은 O( V+ O + ) 선형 시간으로 됩니다.여기서 V는 정점의 수이고 E는 정점 사이의 에지 수입니다.

더 복잡한 문제는 최적의 경로를 찾는 것이다.이 경우 포괄적인 접근방식은 Bellman-Ford 알고리즘으로 알려져 있으며, 이 알고리즘은 OE O E time 2차 시간을 산출합니다.그러나 최적의 경로를 찾기 위해 가능한 모든 경로를 검사할 필요는 없습니다.A* 및 Dijkstra 알고리즘과 같은 알고리즘은 휴리스틱스 또는 동적 프로그래밍을 통해 경로를 전략적으로 제거합니다.이러한 알고리즘은 불가능한 경로를 배제함으로써 O( log () \ O ( \( ) )[1]} 까지의 복잡성을 줄일 수 있습니다.

위의 알고리즘은 전처리 없이 그래프 상에서 동작하는 최적의 일반 알고리즘 중 하나입니다.그러나 실제 이동 경로 시스템에서는 더 나은 [2]성능을 얻기 위해 그래프를 사전 처리할 수 있는 알고리즘에 의해 더 나은 시간 복잡성을 달성할 수 있습니다.이러한 알고리즘 중 하나가 수축 계층입니다.

다이크스트라 알고리즘

그래프 기반 경로 검색 알고리즘의 일반적인 예는 Dijkstra 알고리즘입니다.이 알고리즘은 시작 노드와 후보 노드의 "오픈 세트"에서 시작합니다.각 스텝에서는, 개시로부터 가장 거리가 낮은 오픈 세트내의 노드를 조사한다.노드가 "closed"로 표시되며 노드에 인접한 모든 노드가 아직 검사되지 않은 경우 열린 세트에 추가됩니다.이 프로세스는 대상에 대한 경로가 발견될 때까지 반복됩니다.가장 낮은 거리의 노드가 먼저 검사되기 때문에, 행선지가 최초로 검출되었을 때에, 행선지에의 패스가 최단 [3]패스가 됩니다.

음의 에지 웨이트가 있으면 Dijkstra 알고리즘이 실패합니다.노드 A, B 및 C가 모서리가 AB = 3, AC = 4, BC = -2인 연결된 무방향 그래프를 형성하는 가상 상황에서는 A에서 C로 가는 최적 경로 비용이 1, A에서 B로 가는 최적 경로 비용이 2이다.A에서 시작하는 Dijkstra의 알고리즘은 가장 가까운 B를 먼저 조사합니다.그것은 그것에 3의 비용을 할당하고, 그것을 마감으로 표시하게 됩니다.그것은 그 비용을 재평가하지 않는다는 것을 의미합니다.따라서 Dijkstra는 음의 모서리 가중치를 평가할 수 없습니다.그러나 많은 실용적인 목적을 위해 음의 에지 웨이트가 존재하지 않기 때문에 Dijkstra의 알고리즘은 경로 검색 목적에 대체로 적합합니다.

A* 알고리즘

A*는 게임에서 일반적으로 사용되는 Dijkstra 알고리즘의 변형입니다.A*는 열려 있는 각 노드에 해당 노드에 대한 엣지의 무게에 해당 노드와 피니시 사이의 대략적인 거리를 더한 가중치를 할당합니다.이 대략적인 거리는 휴리스틱에 의해 발견되며, 해당 노드와 끝 사이의 가능한 최소 거리를 나타냅니다.이를 통해 초기 경로가 발견되면 더 긴 경로를 제거할 수 있습니다.시작과 결승 사이에 길이 x의 경로가 있고 노드와 피니시 사이의 최소 거리가 x보다 클 경우 해당 노드를 검사할 [4]필요가 없습니다.

A*는 이 휴리스틱을 사용하여 Dijkstra 알고리즘에 대한 동작을 개선합니다.휴리스틱이 0으로 평가되면 A*는 Dijkstra의 알고리즘과 동일합니다.경험적 견적이 증가하고 실제 거리에 가까워질수록 A*는 최적의 경로를 계속 찾지만 노드 수를 줄임으로써 더 빠르게 실행됩니다.휴리스틱의 값이 정확한 실제 거리일 경우 A*는 가장 적은 노드를 조사합니다.(그러나, 같은 비교 결과는 종종 간단한 계산을 사용하여 도달할 수 있기 때문에, 항상 실제 거리를 계산하는 휴리스틱 함수를 작성하는 것은 일반적으로 비현실적이다. 예를 들어, 2차원 공간에서 유클리드 거리에 대한 맨해튼 거리를 사용한다.)경험적 접근법의 가치가 증가함에 따라 A*는 검사하는 노드의 수는 줄어들지만 더 이상 최적의 경로를 보장하지는 않습니다.많은 애플리케이션(비디오 게임 등)에서 알고리즘의 신속한 실행을 위해 이 방법은 허용 가능하며 바람직하기까지 합니다.

샘플 알고리즘

이것은 타일 기반 맵에 대한 매우 간단하고 이해하기 쉬운 경로 검색 알고리즘입니다.먼저 지도, 시작 좌표 및 목적지 좌표가 있습니다.지도는 이렇게 생겼고X벽이 되고,S첫 번째가 아니라O마지막이 되는 것_열린 공간인 경우 상단 및 오른쪽 모서리에 있는 숫자가 열 및 행 번호입니다.

1 2 3 4 5 6 7 X X X X X X X X X X X X 1 X X _ X _ X _ X _ X _ 2 X S X _ X _ X _ X _ 3 X _ X _ X _ 4 _ X _

먼저 큐로 사용할 좌표 목록을 만듭니다.큐는 하나의 좌표(종료 좌표)로 초기화됩니다.각 좌표에는 카운터 변수도 부착됩니다(이러한 목적은 곧 명확해질 것입니다).따라서 큐는 ((3,8,0)부터 시작됩니다.

그런 다음 알고리즘 진행 중에 끝에 추가된 새 요소를 포함하여 큐 내의 모든 요소를 살펴보고 각 요소에 대해 다음 작업을 수행합니다.

  1. 현재 요소의 카운터 변수 + 1의 카운터 변수를 사용하여 인접한 4개의 셀 목록을 작성합니다(이 예에서는 4개의 셀이 ((2,8,1), (3,7,1), (4,8,1), (3,9,1)).
  2. 각 목록의 모든 셀에서 다음 두 가지 조건을 확인합니다.
    1. 셀이 벽인 경우 목록에서 제거합니다.
    2. 기본 목록에 동일한 좌표를 가진 요소가 있는 경우 셀 목록에서 제거합니다.
  3. 목록의 나머지 모든 셀을 기본 목록 끝에 추가합니다.
  4. 목록의 다음 항목으로 이동합니다.

따라서 1회전 후 요소의 리스트는 다음과 같습니다. ((3,8,0), (2,8,1), (4,8,1)

  • 2회전 후: (3,8,0), (2,8,1), (4,8,1), (1,8,2), (4,7,2)
  • 3회전 후: (...(1,7,3), (4,6,3), (5,7,3)
  • 4회전 후: (...(1,6,4), (3,6,4), (6,7,4)
  • 5회전 후: (...(1,5,5), (3,5,5), (6,6,5), (6,8,5)
  • 6회전 후: (...(1,4,6), (2,5,6), (3,4,6), (6,5,6), (7,8,6)
  • 7회전 후: (...(1,3,7) – 문제를 해결한 알고리즘의 이 스테이지를 종료합니다.여러 유닛이 같은 타깃을 쫓고 있는 경우(많은 게임과 마찬가지로 알고리즘의 종료는 이것을 용이하게 하기 위한 것입니다), 맵 전체가 시작되거나 모든 유닛이 도달하거나 설정된 카운터 제한에 도달할 때까지 계속할 수 있습니다.

다음으로 카운터를 맵에 매핑합니다.

1 2 3 4 5 6 7 X X X X X X X X X X X X 1 X X X _ X _ X _ X _ 2 X S X _ X _ X _ 3 X 6 X 6 X _ X 5 X 5 X 6

다음으로 S(7)부터 시작하여 번호가 가장 낮은 가까운 셀로 이동합니다(체크되지 않은 셀은 이동할 수 없습니다).추적되는 경로는 (1,3,7) -> (1,4,6) -> (1,5,5) -> (1,6,4) -> (1,7,3) -> (1,8,2) -> (2,8,1) -> (3,8,0) 입니다.두 숫자가 모두 낮은 경우(예: S가 (2,5)에 있는 경우) 랜덤 방향을 선택합니다. 길이는 동일합니다.이것으로 알고리즘이 완료되었습니다.

비디오 게임에서는

1982년 크리스 크로포드는 컴퓨터 탱크가 U자형 호수 안에 있는 육지에 갇힌 탱크틱스의 경로 찾기 문제를 해결하기 위해 "많은 시간을 소비했다"고 기술했다."많은 노력을 헛되이 한 후, 저는 더 나은 해결책을 발견했습니다: 지도에서 U자형 호수를 삭제하는 것입니다,"라고 그는 말했다.[5]

계층 경로 검색

계층 경로 검색에 4중 트리를 사용할 수 있습니다.

이 아이디어는 CPU 시간이 짧은 대형 지도에서 계획이 필요했던 비디오 게임 업계에 의해 처음 설명되었습니다.추상화 및 휴리스틱스 사용의 개념은 더 오래되었고 [7]논리 게임의 상태 공간을 효율적으로 검색하기 위해 사용된 [6]추상화 기반 스트립스(ASTRIPS)라는 이름으로 처음 언급되었다.유사한 기술로는 네비게이션 메쉬(navmesh)가 있습니다.이것은 게임의 기하학적 계획과 복수의 수송 차량을 이용한 출장 세일즈맨의 문제에 이용되는 멀티모달 운송 계획에 사용됩니다.

맵은 클러스터로 분할됩니다.상위 계층에서는 클러스터 간의 경로가 계획됩니다.계획이 발견된 후 하위 [8]레벨의 클러스터 내에서 두 번째 경로가 계획됩니다.즉, 계획은 원래 공간에서 안내된 로컬 검색인 두 단계로 이루어집니다.장점은 노드 수가 적고 알고리즘이 매우 잘 수행된다는 것입니다.단점은 계층형 경로 플래너는 [9]구현하기 어렵다는 것입니다.

예

지도의 크기는 3000x2000 픽셀입니다.픽셀 베이스로 패스를 계획하는 것은 매우 오랜 시간이 걸립니다.효율적인 알고리즘도 많은 그래프를 계산해야 합니다.그 이유는 그러한 지도는 전체적으로 600만 화소를 포함하고 기하학적 공간을 탐사할 가능성이 매우 크기 때문이다.계층형 패스 플래너의 첫 번째 단계는 맵을 작은 서브맵으로 분할하는 것입니다.각 클러스터의 크기는 300 x 200 픽셀입니다.전체 군집 수는 10x10=100입니다.새로 작성된 그래프에서는 노드의 수가 적기 때문에 100개의 클러스터 사이를 이동할 수 있지만 상세 맵 내에서는 이동할 수 없습니다.개요 그래프에서 유효한 경로가 발견된 경우 다음 단계는 각 클러스터 내에서 경로를 계획하는 것입니다.서브맵은 300x200 픽셀로 일반 A* 패스플래너로 쉽게 처리할 수 있습니다.

경로 검색에 사용되는 알고리즘

  • 다이크스트라 알고리즘
  • A* 검색 알고리즘, Dijkstra 알고리즘의 특수한 경우
  • D* 시간 경과에 따라 제약이 달라지거나 에이전트가 경로를 처음 계획할 때 완전히 파악되지 않는 문제에 대한 증분 경험적 검색 알고리즘 패밀리
  • 임의 각도 경로 계획 알고리즘. 검색 그래프의 가장자리를 따라 이동하도록 제한되지 않는 경로를 계획하기 위한 알고리즘으로, 모든 각도에서 취할 수 있으므로 더 짧고 직선적인 경로를 찾을 수 있습니다.

다중 에이전트 경로 검색

주요 기사:다중 에이전트 경로 검색

다중 에이전트 경로 검색은 여러 에이전트가 현재 위치에서 타깃 위치까지의 경로를 서로 충돌하지 않고 찾는 동시에 모든 에이전트의 경로 길이 합계와 같은 비용 함수를 최적화하는 것입니다.그것은 경로 찾기의 일반화이다.많은 다중 에이전트 경로 검색 알고리즘은 A*에서 일반화되거나 정수 선형 [10]프로그래밍과 같이 잘 연구된 다른 문제로 축소된 것을 기반으로 합니다.그러나 그러한 알고리즘은 일반적으로 불완전하다. 즉, 다항식 시간 내에 솔루션을 생성하는 것이 증명되지 않는다.다른 카테고리의 알고리즘에서는 기존의 네비게이션 패턴(트래픽 플로우 등) 또는 문제 [11]공간의 토폴로지를 사용함으로써 퍼포먼스를 위한 최적성이 저하됩니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ "7.2.1 Single Source Shortest Paths Problem: Dijkstra's Algorithm". Archived from the original on 2016-03-04. Retrieved 2012-05-18.
  2. ^ Delling, D.; Sanders, P.; Schultes, D.; Wagner, D. (2009). "Engineering route planning algorithms". Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation. Lecture Notes in Computer Science. Vol. 5515. Springer. pp. 117–139. CiteSeerX 10.1.1.164.8916. doi:10.1007/978-3-642-02094-0_7. ISBN 978-3-642-02093-3.
  3. ^ "5.7.1 Dijkstra Algorithm".
  4. ^ "Introduction to A* Pathfinding".
  5. ^ Crawford, Chris (December 1982). "Design Techniques and Ideas for Computer Games". BYTE. p. 96. Retrieved 19 October 2013.
  6. ^ Sacerdoti, Earl D (1974). "Planning in a hierarchy of abstraction spaces" (PDF). Artificial Intelligence. 5 (2): 115–135. doi:10.1016/0004-3702(74)90026-5.
  7. ^ Holte, Robert C and Perez, MB and Zimmer, RM and MacDonald, AJ (1995). Hierarchical a*. Symposium on Abstraction, Reformulation, and Approximation.{{cite conference}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  8. ^ Pelechano, Nuria and Fuentes, Carlos (2016). "Hierarchical path-finding for Navigation Meshes (HNA⁎)" (PDF). Computers & Graphics. 59: 68–78. doi:10.1016/j.cag.2016.05.023. hdl:2117/98738.{{cite journal}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  9. ^ Botea, Adi and Muller, Martin and Schaeffer, Jonathan (2004). "Near optimal hierarchical path-finding". Journal of Game Development. 1: 7–28. CiteSeerX 10.1.1.479.4675.{{cite journal}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  10. ^ 항마, 스벤 코엔, 노라 아야니안, 리론 코헨, 볼프강 회니그, T. K. 사티시 쿠마르, 탄젤 우라스, 홍수, 크레이그 토비, 구니 샤론.개요: 실제 시나리오에 대한 멀티 에이전트 경로 검색의 일반화.2016년 제25회 국제인공지능공동회의(IJCAI) 멀티에이전트 경로찾기 워크숍.
  11. ^ Khorshid, Mokhtar (2011). "A Polynomial-Time Algorithm for Non-Optimal Multi-Agent Pathfinding". SOCS.

외부 링크