12.9 A* 알고리즘과 휴리스틱 탐색

1. A* 알고리즘의 개요

A* 알고리즘(A-star algorithm)은 휴리스틱 정보를 활용하여 효율적으로 최단 경로를 찾는 그래프 탐색 알고리즘이다. 1968년 페터 하트(Peter Hart), 닐스 닐슨(Nils Nilsson), 베르트람 라파엘(Bertram Raphael)이 스탠포드 연구소에서 발표하였으며, 현재 인공지능, 게임 AI, 로봇 경로 계획 등에서 가장 널리 사용되는 알고리즘 중 하나이다. A*는 다익스트라 알고리즘과 그리디 최선 우선 탐색의 장점을 결합하여, 최적성을 보장하면서도 효율적인 탐색을 수행한다.

2. 휴리스틱 탐색의 동기

2.1 무정보 탐색의 한계

다익스트라 알고리즘은 시작 노드 주변을 동심원 형태로 탐색한다. 목표 노드의 위치 정보를 활용하지 않으므로 모든 방향으로 균등하게 탐색한다. 이는 큰 그래프에서 비효율적일 수 있다.

2.2 휴리스틱 정보의 활용

휴리스틱(heuristic)은 목표까지의 비용에 대한 추정값이다. 이 정보를 활용하면 목표 방향으로 우선적으로 탐색할 수 있어 탐색 공간이 줄어든다.

2.3 정보 탐색

휴리스틱을 사용한 탐색을 정보 탐색(informed search) 또는 휴리스틱 탐색(heuristic search)이라 한다. A*는 이러한 정보 탐색의 대표적 알고리즘이다.

3. A*의 핵심 아이디어

3.1 평가 함수

A* 알고리즘은 각 노드에 대해 다음의 평가 함수 $f(v)$ 를 정의한다.

$f(v) = g(v) + h(v)$

여기서

$g(v)$ : 시작 노드에서 $v$ 까지의 알려진 최단 거리
$h(v)$ : $v$ 에서 목표 노드까지의 추정 거리(휴리스틱)

$f(v)$ 는 $v$ 를 통한 시작-목표 경로의 추정 총 비용이다.

3.2 우선순위 큐

A*는 평가 함수 $f$ 를 키로 한 우선순위 큐를 사용한다. 가장 작은 $f$ 값을 가진 노드부터 처리한다. 이는 가장 유망한 노드부터 탐색하는 효과를 만든다.

4. 알고리즘의 구체적 설명

4.1 의사 코드

A_star(G, start, goal, h):
    open = priority queue (key = f)
    closed = empty set
    
    start.g = 0
    start.f = h(start)
    open.add(start)
    
    while open is not empty:
        current = open.extract_min()
        
        if current == goal:
            return reconstruct_path(current)
        
        closed.add(current)
        
        for each neighbor n of current:
            if n in closed:
                continue
            
            tentative_g = current.g + w(current, n)
            
            if n not in open:
                n.g = tentative_g
                n.f = n.g + h(n)
                n.parent = current
                open.add(n)
            elif tentative_g < n.g:
                n.g = tentative_g
                n.f = n.g + h(n)
                n.parent = current
                open.update(n)
    
    return failure  // 경로가 없음

4.2 단계별 동작

초기화: 시작 노드의 $g$ 를 0, $f$ 를 $h(\text{start})$ 로 설정한다. 시작 노드를 open 집합에 추가한다.
반복: open 집합이 빌 때까지 다음을 반복한다.

open 집합에서 $f$ 값이 가장 작은 노드를 추출한다.
그 노드가 목표이면 경로를 재구성하고 종료한다.
아니면 그 노드를 closed 집합에 추가하고, 이웃들을 처리한다.

이웃 처리: 각 이웃에 대해 이 노드를 통한 경로가 더 짧으면 갱신한다.

4.3 Open과 Closed 집합

Open 집합: 발견되었지만 아직 처리되지 않은 노드들. 우선순위 큐로 구현된다.
Closed 집합: 이미 처리된 노드들. 다시 처리되지 않는다.

5. 휴리스틱 함수의 성질

5.1 수용성

휴리스틱 함수 $h$ 가 다음을 만족하면 수용적(admissible)이라 한다.

$h(v) \leq h^*(v), \quad \forall v$

여기서 $h^*(v)$ 는 $v$ 에서 목표까지의 실제 최단 거리이다. 수용성은 휴리스틱이 실제 비용을 과대평가하지 않음을 의미한다.

5.2 일관성

휴리스틱 함수가 다음을 만족하면 일관적(consistent) 또는 단조적(monotonic)이라 한다.

$h(u) \leq w(u, v) + h(v), \quad \forall (u, v) \in E$

이는 삼각 부등식의 형태이며, 휴리스틱이 점진적으로 변함을 의미한다.

5.3 두 성질의 관계

일관성은 수용성을 함의한다. 즉, 일관적인 휴리스틱은 자동으로 수용적이다. 반대는 성립하지 않는다.

5.4 영 휴리스틱

$h(v) = 0$ 인 영 휴리스틱은 일관적이다. 이 경우 A*는 다익스트라 알고리즘과 같아진다.

5.5 완벽한 휴리스틱

$h(v) = h^*(v)$ 인 완벽한 휴리스틱은 직접 목표로의 경로를 찾는다. 다만 일반적으로 완벽한 휴리스틱은 알 수 없다.

6. A*의 최적성

6.1 정리

수용적 휴리스틱을 사용하는 A*는 최적 해(최단 경로)를 찾는다.

6.2 증명 개요

이 정리는 다음과 같이 증명된다. 목표 노드 $t$ 가 추출되는 시점에 그 $g(t)$ 가 최단 거리임을 보인다. 모순으로 $g(t) > \delta(s, t)$ 라고 가정하면, 최단 경로 위의 어떤 미처리 노드 $v$ 가 open에 있다. $h$ 가 수용적이므로 $f(v) = g(v) + h(v) \leq g(v) + h^*(v) = \delta(s, t) < g(t) = f(t)$ 이고, 이는 $t$ 가 추출되었다는 가정과 모순이다.

6.3 일관성과 효율성

일관적 휴리스틱을 사용하면 각 노드가 한 번만 처리된다. 일관적이지 않은 수용적 휴리스틱을 사용하면 노드가 여러 번 재처리될 수 있다.

7. 일반적 휴리스틱

7.1 격자 그래프의 휴리스틱

격자 그래프에서 자주 사용되는 휴리스틱은 다음과 같다.

7.1.1 맨해튼 거리

$h(v) = |v_x - t_x| + |v_y - t_y|$

이는 4방향(상, 하, 좌, 우)으로만 이동 가능한 격자에 적합하다. 수용적이고 일관적이다.

7.1.2 유클리드 거리

$h(v) = \sqrt{(v_x - t_x)^2 + (v_y - t_y)^2}$

이는 8방향으로 이동 가능한 격자에 적합하다. 수용적이고 일관적이다.

7.1.3 체비셰프 거리

$h(v) = \max(|v_x - t_x|, |v_y - t_y|)$

이는 8방향 격자에서 대각 이동 비용이 1인 경우에 적합하다.

7.1.4 옥타일 거리

$h(v) = (\sqrt{2} - 1)\min(|v_x - t_x|, |v_y - t_y|) + \max(|v_x - t_x|, |v_y - t_y|)$

이는 8방향 격자에서 직선 이동 비용이 1, 대각 이동 비용이 $\sqrt{2}$ 인 경우에 적합하다.

7.2 도로 네트워크의 휴리스틱

도로 네트워크에서는 노드의 좌표(위도, 경도)를 활용한 직선 거리가 일반적인 휴리스틱이다.

7.3 매니퓰레이터의 휴리스틱

매니퓰레이터의 운동 계획에서는 작업 공간의 거리가 휴리스틱으로 사용될 수 있다.

8. A*와 다익스트라의 비교

8.1 평가 함수

알고리즘	평가 함수
Dijkstra	$f(v) = g(v)$
Greedy Best-First	$f(v) = h(v)$
A*	$f(v) = g(v) + h(v)$

8.2 특성 비교

특성	Dijkstra	Greedy Best-First	A*
휴리스틱	사용 안 함	사용	사용
최적성	보장	보장 안 함	수용적 휴리스틱 시 보장
효율성	균등 탐색	매우 효율 (보통)	효율 + 최적

8.3 선택 기준

휴리스틱이 없거나 신뢰할 수 없으면 Dijkstra를 사용한다.
빠른 해답이 필요하고 최적성이 중요하지 않으면 Greedy Best-First를 사용한다.
일반적인 경우에는 A*를 사용한다.

9. A*의 변형

9.1 가중치 A*

가중치 A*(Weighted A*)는 휴리스틱에 가중치를 곱한다.

$f(v) = g(v) + w \cdot h(v), \quad w \geq 1$

가중치가 1보다 크면 휴리스틱의 영향이 커져 더 빠르게 해답을 찾지만, 최적성이 보장되지 않는다. 그러나 해답의 비용은 최적의 $w$ 배 이내이다.

9.2 IDA*

반복 깊이 A*(Iterative Deepening A*, IDA*)는 메모리 효율적인 A*이다. 점진적으로 $f$ 값의 임계값을 증가시키며 깊이 우선 탐색을 반복한다.

9.3 Bidirectional A*

양방향 A는 시작과 목표 노드에서 동시에 A를 시작한다. 두 검색이 만나는 점에서 종료한다.

9.4 Theta*

Theta* 알고리즘은 격자 그래프에서 비격자 경로(직선)를 찾는다. 일반 A*보다 자연스러운 경로를 생성한다.

9.5 Anytime A*

시간 제약이 있을 때 사용 가능한 A의 변형이다. 시간이 지날수록 더 좋은 해답을 산출한다. ARA(Anytime Repairing A*)가 대표적이다.

9.6 Lifelong Planning A*

동적 환경에서 변화에 대응할 수 있는 A의 변형이다. D(Dynamic A*) Lite가 대표적이며, 환경이 변할 때 효율적으로 재계획한다.

9.7 Jump Point Search

격자 그래프에서 A*를 가속하는 기법이다. 중복 노드를 건너뛰어 탐색 공간을 줄인다.

10. Python 구현

10.1 기본 A*

import heapq

def a_star(graph, start, goal, heuristic):
    open_set = [(heuristic(start, goal), 0, start, [start])]
    closed_set = set()
    g_scores = {start: 0}
    
    while open_set:
        f, g, current, path = heapq.heappop(open_set)
        
        if current == goal:
            return path
        
        if current in closed_set:
            continue
        closed_set.add(current)
        
        for neighbor, weight in graph[current].items():
            if neighbor in closed_set:
                continue
            
            tentative_g = g + weight
            
            if neighbor not in g_scores or tentative_g < g_scores[neighbor]:
                g_scores[neighbor] = tentative_g
                f_score = tentative_g + heuristic(neighbor, goal)
                heapq.heappush(open_set, (f_score, tentative_g, neighbor, path + [neighbor]))
    
    return None  # 경로가 없음

10.2 격자 A*

def grid_a_star(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    
    def heuristic(pos):
        return abs(pos[0] - goal[0]) + abs(pos[1] - goal[1])  # 맨해튼
    
    open_set = [(heuristic(start), 0, start)]
    came_from = {start: None}
    g_scores = {start: 0}
    
    while open_set:
        _, g, current = heapq.heappop(open_set)
        
        if current == goal:
            return reconstruct_path(came_from, goal)
        
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = current[0] + dr, current[1] + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
                neighbor = (nr, nc)
                tentative_g = g + 1
                
                if neighbor not in g_scores or tentative_g < g_scores[neighbor]:
                    g_scores[neighbor] = tentative_g
                    f_score = tentative_g + heuristic(neighbor)
                    heapq.heappush(open_set, (f_score, tentative_g, neighbor))
                    came_from[neighbor] = current
    
    return None

11. 시간 복잡도

11.1 최악의 경우

A*의 최악의 시간 복잡도는 휴리스틱의 품질에 의존한다. 휴리스틱이 영이면(다익스트라와 같음) $O((|V| + |E|)\log|V|)$ 이다.

11.2 일반적인 경우

좋은 휴리스틱을 사용하면 A*의 시간 복잡도는 다익스트라보다 훨씬 낮다. 최적의 경우 거의 직선 경로를 따라가는 정도이다.

11.3 메모리 복잡도

A*의 메모리 복잡도는 $O(|V|)$ 이지만, 실제로는 open 집합과 closed 집합의 크기에 의존한다. 큰 그래프에서는 메모리 사용이 문제가 될 수 있다.

12. 응용

12.1 게임 AI

게임에서 캐릭터가 목표 위치로 이동할 때 A가 표준이다. 격자 기반 게임에 효과적이며, 다양한 변형(JPS, Theta)이 사용된다.

12.2 로봇 경로 계획

모바일 로봇의 경로 계획에서 A*가 가장 일반적인 알고리즘이다. 격자 기반 환경에 효과적이다.

12.3 자율 주행

자율 주행 차량의 경로 계획에서 A와 그 변형이 사용된다. Hybrid A는 차량의 운동학적 제약을 고려한다.

12.4 인공지능

AI 계획 문제에서 A*는 표준 알고리즘이다. 상태 공간 탐색에 사용된다.

12.5 네트워크 라우팅

네트워크 라우팅에서 A*가 사용될 수 있지만, 다익스트라가 더 일반적이다.

13. 로봇공학에서의 응용

13.1 모바일 로봇의 경로 계획

모바일 로봇이 환경에서 목표 위치로 이동할 때 A*가 가장 일반적이다. 격자 기반 환경에서 효과적이며, 휴리스틱(맨해튼 거리, 유클리드 거리)이 직관적이다.

13.2 Hybrid A*

자율 주행 차량과 같이 운동학적 제약(비홀로노믹)이 있는 시스템에서는 Hybrid A*가 사용된다. 이는 연속적인 상태 공간에서 동작하며, 차량의 운동을 시뮬레이션하여 노드를 확장한다.

13.3 매니퓰레이터의 운동 계획

매니퓰레이터의 구성 공간에서 A*가 사용될 수 있다. 다만 고차원 공간에서는 샘플링 기반 방법(RRT)이 더 일반적이다.

13.4 무인 항공기

드론의 비행 경로 계획에서 3차원 격자 또는 그래프에서 A*가 사용된다.

13.5 다중 로봇 경로 계획

다중 로봇이 협력하여 경로를 계획할 때 CBS(Conflict-Based Search) 등의 알고리즘에서 A*가 하위 루틴으로 사용된다.

14. 응용 예시: 청소 로봇

청소 로봇이 시작 위치에서 목표 위치로 이동할 때 A*가 사용된다. 환경을 격자로 분할하고, 장애물을 제외한 셀들이 그래프의 노드가 된다. 휴리스틱은 맨해튼 거리이다.

15. 응용 예시: 게임 캐릭터의 이동

RPG 게임에서 NPC가 목표 위치로 이동할 때 A*가 사용된다. 좋은 휴리스틱이 있으면 매우 효율적으로 동작한다.

16. 응용 예시: 자율 주행 차량

자율 주행 차량의 경로 계획에서 Hybrid A*가 사용된다. 차량의 운동학(비홀로노믹)을 고려하여 자연스러운 경로를 생성한다.

17. 응용 예시: 무인 항공기의 비행 경로

드론이 장애물을 회피하면서 목표 위치로 비행할 때 3차원 A*가 사용된다. 휴리스틱은 3차원 유클리드 거리이다.

18. 응용 예시: 매니퓰레이션 작업 계획

매니퓰레이션 작업의 시퀀스를 계획할 때 A*가 상태 공간 탐색에 사용된다. 각 상태는 객체와 매니퓰레이터의 자세이다.

19. 휴리스틱 설계의 고려사항

19.1 수용성 보장

휴리스틱은 수용적이어야 최적성이 보장된다. 일반적으로 직선 거리가 좋은 시작점이다.

19.2 정확성

더 정확한 휴리스틱일수록 탐색이 효율적이다. 다만 휴리스틱 계산 비용도 고려해야 한다.

19.3 일관성

가능하면 일관적 휴리스틱을 사용한다. 노드의 재처리를 피할 수 있다.

19.4 도메인 지식

응용의 도메인 지식을 활용하면 더 좋은 휴리스틱을 설계할 수 있다.

20. A*의 한계

20.1 메모리 사용

A*는 모든 발견된 노드를 메모리에 저장한다. 큰 그래프에서는 메모리 사용이 문제가 될 수 있다.

20.2 휴리스틱의 품질

A*의 효율성은 휴리스틱의 품질에 크게 의존한다. 나쁜 휴리스틱은 거의 다익스트라와 같은 성능을 산출한다.

20.3 동적 환경

환경이 변할 때 A는 처음부터 다시 계산해야 한다. 이를 해결하기 위해 D Lite 등이 개발되었다.

21. A*의 최적화

21.1 효율적인 자료 구조

이진 힙, 피보나치 힙 등의 효율적인 우선순위 큐가 사용된다.

21.2 휴리스틱 캐싱

자주 사용되는 휴리스틱은 사전 계산하여 캐시할 수 있다.

21.3 메모리 압축

큰 그래프에서는 메모리를 압축하여 사용한다.

21.4 병렬 A*

병렬 A*는 여러 프로세서를 사용하여 탐색을 가속한다.

22. A*의 라이브러리 지원

22.1 NetworkX

import networkx as nx

G = nx.Graph()
G.add_weighted_edges_from([(1, 2, 1), (1, 3, 4), (2, 3, 2), (2, 4, 5), (3, 4, 1)])

def heuristic(u, v):
    return 0  # 자명한 휴리스틱

path = nx.astar_path(G, source=1, target=4, heuristic=heuristic)

22.2 다른 라이브러리

Boost Graph Library
Google OR-Tools
게임 엔진의 내장 A* (Unity, Unreal)

23. 학습의 가치

A* 알고리즘을 깊이 이해하는 것은 다음과 같은 이점을 제공한다.

가장 영향력 있는 인공지능 알고리즘 중 하나를 익힌다.
휴리스틱 탐색의 원리와 실용을 학습한다.
로봇 경로 계획의 표준 도구를 습득한다.
다양한 변형 알고리즘의 기초를 형성한다.
게임 AI와 자율 시스템의 핵심 알고리즘을 이해한다.

24. 학습 권장사항

24.1 직접 구현

A*를 처음부터 직접 구현해 보는 것이 가장 효과적이다. 격자 환경에서 시작하여 점차 복잡한 그래프로 확장한다.

24.2 시각화

A*의 단계별 시각화는 알고리즘의 동작을 이해하는 데 매우 유용하다. open과 closed 집합의 변화를 볼 수 있다.

24.3 휴리스틱 실험

다양한 휴리스틱을 시도해 보고 효율성을 비교한다. 휴리스틱의 품질이 성능에 미치는 영향을 직접 확인한다.

24.4 변형 학습

가중치 A*, IDA*, D* Lite 등의 변형을 학습한다. 각 변형의 응용 영역을 이해한다.

25. 본 절의 의의

본 절은 A* 알고리즘과 휴리스틱 탐색을 자세히 다루었다. A*는 인공지능과 로봇공학의 가장 중요한 알고리즘 중 하나이며, 효율적인 경로 계획의 표준이다. 휴리스틱의 활용은 알고리즘 설계의 핵심 기법이며, 다양한 문제에 응용된다.

26. 참고 문헌

Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). “A formal basis for the heuristic determination of minimum cost paths.” IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.
LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.
Korf, R. E. (1985). “Depth-first iterative-deepening: An optimal admissible tree search.” Artificial Intelligence, 27(1), 97–109.
Koenig, S., & Likhachev, M. (2002). “D* lite.” AAAI Conference on Artificial Intelligence, 476–483.
Harabor, D., & Grastien, A. (2011). “Online graph pruning for pathfinding on grid maps.” AAAI Conference on Artificial Intelligence, 1114–1119.

version: 1.0