home lecture link bbs blame

◈인공 지능 (A. I.)◈


1.9 길 찾기

인공 지능의 길 찾기 알고리듬에 STL을 활용해서 구현 하면 좀 더 쉽게 알고리듬을 프로그램으로 만들 수 있습니다. 길 찾기 문제는 인공지능에서 주어진 초기 상태에서 목표 상태를 도달하기까지의 경로 탐색의 한 종류입니다. 길 찾기는 인공 지능의 그래프의 탐색(Search)으로 표현할 수 있습니다. 인공지능에서 탐색은 크게 맹목적 탐색(Blind Search)과 경험적 탐색(Heuristic Search) 두 종류가 있습니다.

 

맹목적 탐색은 목표 노드의 위치에 상관 없이 시작 노드부터 순서대로 탐색하는 방법입니다.  DFS(Depth First Search: 깊이 우선 탐색), BFS(Breadth First Search: 너비 우선 탐색)은 맹목적 탐색의 한 종류이며 목표 노드까지의 도달 방법 중에서 비용이 적게 드는 최적의 경로를 보장하는 탐색 방법은 균일 비용 탐색(Uniform Search) Dijkstra(데이크스트라) 탐색 방법이 있습니다.

Dijkstra 알고리듬은 최적의 경로를 찾아주지만 문제는 너무 많은 노드들을 탐색한다는데 있습니다. 경험적 탐색은 목표 노드의 위치를 이용해서 탐색할 노드들을 줄여 프로그램의 효율을 높이는 방법입니다. 경험적 탐색의 대표적인 예가 A*-알고리듬입니다. A*-알고리듬을 배우는 방법은 여러 가지가 있지만 Dijkstra 알고리듬을 이해하는 것이 가장 빠른 지름길입니다. 여러분은 Dijkstra 알고리듬을 구현할 수 있으면 A*-알고리듬 또한 쉽게 구현할 수 있습니다.

 

 

1.9.1 Dijkstra 알고리듬

Dijkstra 알고리듬은 다음과 같이 알려져 있습니다.

 

// Define

// G: 탐색 비용, Q: 탐색할 노드 리스트, s: 시작 노드, t: 목표 노드

// C(i, j): 간선(Edge) {i, j}의 경로 비용(Cost)

 

for All Vertex v              // 모든 노드의 경로 비용은 로 설정

        G(v) ← ∞

 

G(s) ← 0                      // 시작 노드의 비용은 0

Q←V                          // 모든 정점을 탐색할 리스트에 추가

 

while( Q ≠ ø)                      // 탐색할 노드가 없을 때까지 반복

{

        v←min{G(v)}           // Q에서 경로비용이 가장 작은 정점 v 선택

        if v == t then         // v가 목표 노드이면 중지

               break;

 

        Q←Q-{v}               // 탐색 리스트 Q 에서 v 제거

 

        // 이미 계산 된 G(x)와 새로 계산 되는 "G(v) + C(v, x)" 중에서

        // 가장 작은 값을 새로운 G(x)로 변경

        for_each v 에 인접한 모든 정점 x

               G(x)← min{G(x), G(v) + C(v, x)}

}

 

프로그램으로 Dijkstra 알고리듬을 구현하기 위해서 앞으로 탐색할 노드들의 집합을 Open List라 하고 이미 탐색을 완료한 노드들의 집합을 Close List 라 정의 합시다.

Dijkstra 알고리듬 대로 프로그램을 만들면 모든 노드를 전부 탐색하게 되므로 모든 노드를 탐색할 노드 Open List에 넣지 않고 시작 노드부터 조건에 따라 Open List에 추가해서 구현합니다. 이렇게 하면 전체 리스트를 검사하지 않게 되어 프로그램의 효율이 높아 집니다.

다음은 Dijkstra을 프로그램으로 구현할 때의 순서입니다.

 

0. 탐색할 모든 노드의 경로 비용 G로 설정한다.

1. Open List에 출발노드를 넣는다. 출발노드의 G 0으로 정한다.

2. Open List에 노드가 남아 있는 동안 다음을 반복한다.

2.1 Open List에서 G가 가장 작은 노드를 m 이라 하고 이 노드를 꺼내어 Close List에 넣는다.

2.2 m이 목표 노드이면 탐색은 성공으로 끝낸다.

   2.3 m을 확장하여 후계 노드(n)들에 대해서 다음을 반복한다.

      2.3.1 각각의 후계 노드들에 대한 경로 비용 G_new(n) = G(m) + C(m, n)을 계산 한다.

      2.3.2 n Open List에 있다면

           2.3.2.1 이전 G 값이 새로운 G_new 보다 크면 이전 값을 새로 계산한 G_new로 바꾸고

부모 노드 또한 m으로 교체한다.

           2.3.2.2 이전의 G 값이 새로 계산한 G_new 보다 작다면 이 노드는 무시한다.

2.3.3 n Close List에 있다면 n은 무시한다.

2.3.4 n Open List Close List에 없다면 부모 노드 m과 경로 비용 G_new를 첨가하고

Open List에 넣는다.

 

3. 탐색은 실패로 끝낸다.

 

Dijkstra를 작성하기 전에 다음과 같은 그래프 구조에서 v0를 출발 노드로 하고 목적 노드 v5에 도달하는 최적 경로를 구해 봅시다.

 

 

먼저 모든 노드의 경로비용과 부모 노드를 정합니다.

 

 

다음으로 출발 노드 v0의 경로 비용을 0으로 설정하고 부모 노드는 자신 v0로 설정합니다. 그리고 나서 인접 노드 v1 v2의 경로 비용을 계산합니다. v1 v2의 경로 비용은 이전에 이므로 새로운 값으로 바뀌게 되고 부모 노드는 v0가 됩니다.

 

 

 

Open List에서 v1 v2를 추가하고 while 문의 처음으로 와서 Open List에서 경로가 최소인 노드를 선택하게 되면 v2가 선택이 됩니다. v2에서 인접한 하위 노드 v1, v3, v4의 경로 비용을 계산하고 이전 값과 비교해서 이전 값보다 작으면 경로 비용을 작은 값으로 바꾸고 부모 노드를 v2로 합니다. 또한 v3, v4 Open List에 추가합니다.

 

 

Open List에 남아 있는 v1, v3, v4 중에서 경로 비용이 가장 작은 v1을 선택하고 이전의 내용을 반복하면 v3, v4, v5 기준으로 while문이 다음 그림처럼 진행이 됩니다.

 

  

 

 

최적 경로는 목적 노드 v5부터 부모노드를 찾아오면 되는데 그림의 최적 경로는 부모 노드가 v5 à v4 à v3 à v1 à v2 à v0이 되므로 v0, v2, v1, v3, v4, v5를 거치는 경로가 됩니다.

 

게임에서 Dijkstra 방법은 격자가 일정한 실외 지형에서 길 찾기 용도로 자주 사용됩니다. 격자가 일정하면 인접한 노드(Cell)까지의 경로 비용은 다음과 같이 설정 할 수 있습니다.

 

<격자의 크기가 일정한 노드 m의 인접한 노드에 대한 경로 비용>

 

여기서 경로의 비용이 141로 설정한 것은 √21.41 를 정수화 하기 위해서 100을 곱한 값입니다. 이로 인해 바로 옆에 있는 노드의 경로 비용은 100으로 설정되었습니다.

 

만약 2차원 격자의 자료가 다음과 같이 움직일 수 있는 영역은 0으로 갈 수 없는 벽은 1로 주어질 때 Dijkstra를 적용해 봅시다.

 

#define TILE_LEN       11

 

INT bMap[TILE_LEN][TILE_LEN]  =

{

  // 0  1  2  3  4  5  6  7  8  9  10

  {  0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, }, // 0

  {  0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, }, // 1

  {  0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, }, // 2

  {  0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, }, // 3

  {  0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, }, // 4

  {  0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, }, // 5

  {  0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, }, // 6

  {  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }, // 7

  {  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }, // 8

  {  0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, }, // 9

  {  0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, }, // 10

};

 

여러분은 Start Node에서 Terminal Node까지의 경로를 찾기 위해서 탐색에 대한 정보를 저장하기 위한 구조체를 작성해야 합니다.

 

struct UscNode

{

        INT     nCurX;         // 셀 인덱스 X

        INT     nCurY;         // 셀 인덱스 Y

        INT     nCst;          // 셀까지 경로 비용

        INT     eLst;          // 탐색 후 노드 위치: 탐색 안함. Open List. Close List.

        INT     nPrnX;         // 부모 셀 인덱스 X

        INT     nPrnY;         // 부모 셀 인덱스 Y

        INT     bWall;         // 노드가 벽인가?

};

 

여러분은 dv13_01UniformCost01.zip_consoleTest01 폴더의 main.cpp파일을 보면 이 구조체를 이용해서 Dijkstra 방법으로 시작 노드에서 목표 노드를 검색하는 예를 볼 수 있습니다. 실행을 하면 경로 비용과 부모 노드의 인덱스가 result.txt 파일에 저장됩니다. _consoleTest02 폴더는 좀 더 넓은 격자에 대한 예제입니다.

dv13_01UniformCost01 폴더의 PathFind.dsp은 경로를 화면에 D3DX Sprite를 이용해서 출력합니다.  Main.cpp 파일의 PathFinding() 함수는 경로를 찾는 함수이며 프로젝트를 실행하면 10000정도 PathFinding() 함수를 호출해서 경로를 계산하는 시간을 측정합니다.

 

dv13_01UniformCost02.zip 예제는 부모 노드 정보를 인덱스 대신 포인터를 이용한 예제입니다.

실행하면 다음과 같은 화면을 볼 수 있습니다.

 

<Dijkstra 알고리듬을 이용한 길 찾기: dv13_01UniformCost02.zip>

 

 

1.9.2 A* 알고리듬

Dijkstra 알고리듬에서는 출발노드로부터 현재 노드까지의 가중치를 합한 값을 평가함수로 정했습니다. A* 알고리듬은 이 부분을 개선해서 현재 노드(n)까지의 비용 G(n)과 앞으로 목표 노드까지 비용(Heurist 추정 값) H(n)을 합한 값을 노드를 탐색하는 평가함수로 정합니다.

 

F(n) = G(n) + H(n)

 

A* 알고리듬은 H값에 따라 달라지는데 만약 H가 완벽하다면 탐색은 최적 경로에 대한 노드를 한 번에 찾아 낼 수 있을 것입니다. H가 완벽하지 않더라도 H G에 대해서 [0, 1]이면 탐색 횟수는 줄어들고 거의 최적화 경로를 찾아냅니다. H=0이면 Dijkstra 방법과 동일합니다.

 

따라서 Dijkstra 방법을 사용하는 것보다 A*를 사용하는 것이 여러모로 이점이 있습니다. 다음은 Dijkstra 를 수정한 A* 알고리듬입니다.

 

0. 탐색할 모든 노드의 경로 비용 G로 설정한다.

1. 출발 노드의 G(0), H, F를 계산한 후에 Open List에 를 넣는다.

2. Open에 노드가 남아 있는 동안 다음을 반복한다.

2.1 Open에서 F가 가장 작은 노드를 m 이라 하고 이 노드를 꺼내어 Close에 넣는다.

2.2 m이 목표 노드이면 탐색은 성공으로 끝낸다.

2.3 m을 확장하여 후계 노드(n)들에 대해서 다음을 반복한다.

2.3.1 각각의 후계 노드들에 대한 평가 값 F_new(n) = G_new(n) + H_new(n)을 계산 한다.

 

2.3.2 n Open 또는 Close 에 있다면

            2.3.2.1 이전의 F_old 값이 새로 계산한 F_new 보다 작다면 이 노드는 무시한다.

            2.3.2.2 이전의 F_old 값이 새로 계산한 F_new 보다 크다면 이전의 F_old와 새로

 계산한 F_new를 교체한 후, 부모 노드 또한 m으로 교체한다.

      2.3.2 n Open Close에 없다면 부모 노드 m과 경로 비용 F_new를 첨가하고

 Open List에 넣는다.

 

3. 탐색은 실패로 끝낸다.

 

A* 알고리듬은 H(n)를 설정 방법에 따라 최적 경로와 효율이 달라집니다. 게임에서 격자(Cell)의 크기가 일정한 공간이라면 H 값을 다음과 같이 맨하튼(Manhattan) 방식으로 계산하면 산술 계산이 되어 처리 속도 가 빨라집니다.

 

H(n) = | Node n.x - Terminal Node x | + | Node n.y - Terminal Node y |

 

좀 더 정확한 H(n)을 제공하고자 한다면 거리의 제곱을 이용한 방법도 좋습니다.

 

H(n) = ( Node n.x - Terminal Node x )2 + ( Node n.y - Terminal Node y )2

 

dv13_02A_star.zip A* 알고리듬의 예로 H 값은 대각선의 길이는 맨하튼(Manhattan) 방식을 계산을 하고 나머지 직선 거리는 격자 사이의 거리로 계산을 한 예제 입니다. 폴더 _consoleTest은 이전의 Dijkstra 예처럼 경로 계산의 결과를 파일로 출력하는 예제이며 Main.cpp 파일의 PathFinding() 함수는 A* 길 찾기를 구현한 함수입니다.

 

<A* 알고리듬을 이용한 길 찾기: dv13_02A_star.zip>

 

같은 조건에 대해서 A* 알고리듬이 Dijkstra 보다 3배 정도 빠름을 볼 수 있는데 이것은 그 만큼의 노드 탐색 횟수가 줄었음을 의미합니다.

 

dv13_02A_star.zip 예제에서 시간을 측정하기 위해서 10000 정도 PathFinding() 함수를 호출하는 것을 1회로 정하고 LEFT, RIGHT, UP, DOWN 키를 누르면 목표 노드의 위치가 수정되고 A* 경로를 찾는 것을 볼 수 있습니다.



Copyright (c) 2004 3dapi.com All rights reserved.

Creative Commons License