A star

 

Q-Learning 알고리즘으로 구현하였던 길찾기를 A star 알고리즘으로 구현해 보았다.

그리드 구성은 이전과 동일하다.

#
# A* 
#

import numpy as np
import matplotlib.pyplot as plt
import heapq

# 그리드 월드 환경 설정
# 0: 빈공간, 1: 벽, 2: 목적지, (0,0): 시작위치
grid = np.array([[0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
                 [0, 0, 0, 1, 0, 0, 1, 0, 0, 0],
                 [0, 0, 0, 0, 1, 0, 0, 1, 0, 0],
                 [0, 1, 1, 0, 1, 0, 0, 0, 1, 0],
                 [0, 0, 0, 0, 0, 0, 0, 0, 1, 2]])

# 그리드 월드 환경 출력 함수
def plot_grid_world(start, goal, path=[]):
    plt.imshow(grid, cmap="gray", interpolation="none", origin="upper")
    plt.xticks([])
    plt.yticks([])
    
    if path:
        path = np.array(path)
        plt.plot(path[:, 1], path[:, 0], marker='o', markersize=4, linestyle='-', color='green')
        
        for i, pos in enumerate(path):
            plt.text(pos[1], pos[0], str(i + 1), ha="center", va="center", color="orange", fontsize=14)
    
    plt.text(start[1], start[0], "A", ha="center", va="center", color="red", fontsize=16)
    plt.text(goal[1], goal[0], "B", ha="center", va="center", color="green", fontsize=16)

# 휴리스틱 계산 함수
# A* 알고리즘을 이용하여 최적 경로 찾기
def heuristic(state, goal):
    return abs(state[0] - goal[0]) + abs(state[1] - goal[1])

# A* 알고리즘
def astar(grid, start, goal):
    frontier = [(0, start)]
    came_from = {}
    visited = set()
    
    # 'frontier'를 최소 힙(min heap)으로 변환
    #heapq.heapify(frontier)
    
    while frontier:
        current_cost, current_state = heapq.heappop(frontier)
        
        if current_state == goal:
            # 시작 지점부터 목표 지점까지의 경로를 재구성
            path = []
            while current_state in came_from:
                path.append(current_state)
                current_state = came_from[current_state]
            path.append(start)
            return path[::-1] # 리스트 역순으로 변환 
        
        # 현재 상태가 방문한 곳이라면 스킵.
        if current_state in visited:
            continue
        
        # 현재 상태 방문 리스트에 추가 
        visited.add(current_state)
        
        for next_state in get_neighbors(grid, current_state):
            if next_state not in visited:
                priority = current_cost + 1 + heuristic(next_state, goal)   # 우선순위 계산 
                heapq.heappush(frontier, (priority, next_state)) # 최소 우선순위를 가진 상태가 먼저 나오도록 정렬 
                came_from[next_state] = current_state # 현재 이동상태 기록 
    
    return None

# 현재 위치에서 이동 가능한 이웃 반환
def get_neighbors(grid, state):
    neighbors = []
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] 
    for dx, dy in directions:
        new_position = (state[0] + dx, state[1] + dy)
        if 0 <= new_position[0] < grid.shape[0] and 0 <= new_position[1] < grid.shape[1] and grid[new_position] != 1:
            neighbors.append(new_position)
    return neighbors

# 시작 위치 및 타겟 위치 설정
start_position = (0, 0)
target_position = tuple(np.argwhere(grid == 2)[0]) # grid값이 2인 곳이 목적지

# A* 알고리즘 실행
optimal_path = astar(grid, start_position, target_position)

# 결과 출력
print("최적 경로:", optimal_path)


# 최적 경로 및 순서 출력
plt.ion() # nteractive mode
plt.figure(3)
plt.clf()   # clear
plt.title(f"Optimal Path - Distance : {len(optimal_path)}")
plot_grid_world(start_position, target_position, optimal_path)
plt.show(block=True)

 

결과는 아래 그림과 같다.

 

 

2023.12.07 - [iOS] - XOR 연산을 이용한 문자열 비교

2023.11.03 - [AI,ML] - Gomoku(Five in a Row, Omok) (5/5) - 3x3 체크 추가

2023.10.29 - [AI,ML] - Gomoku(Five in a Row, Omok) (5/5) - 머신러닝으로 게임 구현

2023.10.29 - [AI,ML] - Gomoku(Five in a Row, Omok) (4/5) - 훈련 데이터 생성 및 학습

2023.10.28 - [AI,ML] - Gomoku(Five in a Row, Omok) (3/5) - 속도 최적화 2차 (RANDOM모드 추가)

2023.10.27 - [AI,ML] - Gomoku(Five in a Row, Omok) (2/5) - 속도 최적화 1차 (minimax 속도 개선)

2023.10.27 - [AI,ML] - Gomoku(Five in a Row, Omok) (1/5) - 기본 구현 (minimax, alpha-beta pruning)

2023.08.28 - [AI,ML] - Q-learning