397.26 A* 알고리즘 기반 고수준 임무 시퀀싱 최적화
1. 개요
A* 알고리즘 기반 고수준 임무 시퀀싱 최적화는 로봇이 수행하여야 할 다수의 작업(task)을 최적의 순서로 배열하는 문제에 A* 탐색 알고리즘을 적용하는 기법이다. 임무 시퀀싱(mission sequencing)은 주어진 작업 집합에 대해 총 비용(이동 거리, 시간, 에너지 소모 등)을 최소화하는 실행 순서를 결정하는 조합 최적화 문제이며, 본질적으로 외판원 문제(Traveling Salesman Problem, TSP)와 밀접한 관계를 갖는다. A* 알고리즘은 허용적 휴리스틱을 활용하여 최적 해를 보장하면서 탐색 효율을 극대화하는 최적 우선 탐색(best-first search) 전략으로, 로봇 임무 시퀀싱의 정확하고 효율적인 해법을 제공한다.
2. 임무 시퀀싱 문제의 형식화
2.1 문제 정의
로봇 임무 시퀀싱 문제는 n개의 작업 \mathcal{T} = \{t_1, t_2, \ldots, t_n\}이 주어진 경우, 이 작업들을 수행하는 최적 순서를 결정하는 문제이다. 각 작업은 특정 위치에서 수행되며, 작업 간 전이 비용(transition cost)이 정의된다.
형식적으로, 임무 시퀀싱 문제는 다음과 같이 정의된다.
\mathcal{M} = \langle \mathcal{T}, c, t_{\text{start}}, \mathcal{C} \rangle
여기서 각 구성 요소는 다음과 같다.
- \mathcal{T} = \{t_1, t_2, \ldots, t_n\}: 수행하여야 할 작업의 유한 집합
- c : \mathcal{T} \times \mathcal{T} \rightarrow \mathbb{R}_{\geq 0}: 작업 간 전이 비용 함수. c(t_i, t_j)는 작업 t_i를 완료한 후 작업 t_j를 시작하기 위한 비용(이동 거리, 시간 등)
- t_{\text{start}}: 로봇의 현재 위치 또는 출발 작업
- \mathcal{C}: 선후 관계 제약(precedence constraints), 자원 제약, 시간 제약 등의 부가 조건 집합
2.2 상태 공간 모델
임무 시퀀싱 문제를 A* 알고리즘으로 풀기 위해 상태 공간 모델을 구성한다. 상태는 현재까지 수행한 작업의 집합과 마지막으로 수행한 작업으로 정의된다.
s = (V, t_{\text{last}})
여기서 V \subseteq \mathcal{T}는 이미 수행한(방문한) 작업의 집합이고, t_{\text{last}} \in V는 가장 최근에 수행한 작업이다.
- 초기 상태: s_0 = (\{t_{\text{start}}\}, t_{\text{start}})
- 목표 상태: V = \mathcal{T}(모든 작업이 수행됨)
- 후속 상태 생성: 현재 상태 (V, t_{\text{last}})에서 아직 수행하지 않은 작업 t_j \in \mathcal{T} \setminus V 중 제약 조건을 만족하는 것을 선택하여 전이한다.
\gamma((V, t_{\text{last}}), t_j) = (V \cup \{t_j\}, t_j), \quad t_j \notin V, \quad \text{constraints}(t_j, V) = \text{true}
전이 비용은 c(t_{\text{last}}, t_j)이다.
2.3 상태 공간의 크기
상태 공간의 크기는 가능한 (V, t_{\text{last}}) 조합의 수에 의해 결정된다. n개의 작업에 대해 가능한 상태의 수는 다음과 같다.
|\mathcal{S}| = \sum_{k=1}^{n} \binom{n}{k} \cdot k = n \cdot 2^{n-1}
이 값은 작업 수에 대해 지수적으로 증가하지만, 전체 순열의 수 n!보다는 크게 작다. A* 알고리즘은 이 상태 공간에서 최적 경로를 탐색한다.
3. A* 알고리즘의 임무 시퀀싱 적용
3.1 A* 알고리즘의 기본 구조
A* 알고리즘(Hart et al., 1968)은 평가 함수 f(s) = g(s) + h(s)를 사용하여 최적 우선 탐색을 수행한다.
- g(s): 초기 상태에서 현재 상태 s까지의 실제 누적 비용
- h(s): 현재 상태 s에서 목표 상태까지의 추정 비용(휴리스틱)
- f(s): 현재 상태를 경유하는 해의 추정 총 비용
A* 알고리즘은 휴리스틱 h가 **허용적(admissible)**인 경우, 즉 목표까지의 실제 비용을 초과 추정하지 않는 경우 최적 해를 보장한다.
h(s) \leq h^*(s), \quad \forall s \in \mathcal{S}
또한 h가 일관적(consistent), 즉 삼각 부등식을 만족하는 경우, 각 상태를 최대 한 번만 확장하므로 효율적이다.
h(s) \leq c(s, s') + h(s'), \quad \forall (s, s') \in E
3.2 임무 시퀀싱을 위한 A* 탐색 절차
임무 시퀀싱 문제에 대한 A* 탐색의 구체적 절차는 다음과 같다.
\begin{aligned} &\textbf{Algorithm: A*-Mission-Sequencing}(\mathcal{M}) \\ &\quad s_0 \leftarrow (\{t_{\text{start}}\}, t_{\text{start}}) \\ &\quad g(s_0) \leftarrow 0 \\ &\quad f(s_0) \leftarrow h(s_0) \\ &\quad \text{Open} \leftarrow \{s_0\} \\ &\quad \text{Closed} \leftarrow \emptyset \\ &\quad \textbf{while } \text{Open} \neq \emptyset \textbf{ do} \\ &\quad\quad s = (V, t_{\text{last}}) \leftarrow \arg\min_{s \in \text{Open}} f(s) \\ &\quad\quad \textbf{if } V = \mathcal{T} \textbf{ then return } \text{ExtractSequence}(s) \\ &\quad\quad \text{Open} \leftarrow \text{Open} \setminus \{s\} \\ &\quad\quad \text{Closed} \leftarrow \text{Closed} \cup \{s\} \\ &\quad\quad \textbf{for each } t_j \in \mathcal{T} \setminus V \text{ with constraints satisfied do} \\ &\quad\quad\quad s' \leftarrow (V \cup \{t_j\}, t_j) \\ &\quad\quad\quad g' \leftarrow g(s) + c(t_{\text{last}}, t_j) \\ &\quad\quad\quad \textbf{if } s' \notin \text{Closed} \text{ and } (s' \notin \text{Open} \text{ or } g' < g(s')) \textbf{ then} \\ &\quad\quad\quad\quad g(s') \leftarrow g' \\ &\quad\quad\quad\quad f(s') \leftarrow g' + h(s') \\ &\quad\quad\quad\quad \text{parent}(s') \leftarrow (s, t_j) \\ &\quad\quad\quad\quad \text{Open} \leftarrow \text{Open} \cup \{s'\} \\ &\quad \textbf{return } \text{FAIL} \end{aligned}
4. 임무 시퀀싱을 위한 휴리스틱 함수
4.1 최소 신장 트리(MST) 기반 휴리스틱
최소 신장 트리(Minimum Spanning Tree, MST) 기반 휴리스틱은 TSP에 대한 고전적 허용적 휴리스틱이다. 현재 상태 s = (V, t_{\text{last}})에서 미방문 작업 집합 U = \mathcal{T} \setminus V에 대해, t_{\text{last}}를 포함한 U \cup \{t_{\text{last}}\}의 최소 신장 트리 비용을 휴리스틱으로 사용한다.
h^{\text{MST}}(s) = \text{MST-cost}(U \cup \{t_{\text{last}}\})
MST 비용은 TSP 최적 비용의 하한이다. 이는 TSP의 최적 투어에서 하나의 간선을 제거하면 신장 트리가 되고, MST는 모든 신장 트리 중 최소 비용이기 때문이다.
h^{\text{MST}}(s) \leq h^*(s)
MST는 Prim 알고리즘 또는 Kruskal 알고리즘으로 O(|U|^2) 시간에 계산할 수 있다.
4.2 최근접 이웃 완화(Nearest Neighbor Relaxation) 휴리스틱
최근접 이웃 완화 휴리스틱은 미방문 작업 간의 최소 비용 간선의 합으로 잔여 비용을 추정한다. 미방문 작업의 각 노드에서 가장 가까운 이웃까지의 거리를 합산한다.
h^{\text{NN}}(s) = \frac{1}{2} \sum_{t \in U \cup \{t_{\text{last}}\}} \min_{t' \in (U \cup \{t_{\text{last}}\}) \setminus \{t\}} c(t, t')
이 휴리스틱은 1-트리(1-tree) 하한의 단순화된 형태로, 허용적이며 계산 비용이 O(|U|^2)이다.
4.3 할당 문제(Assignment Problem) 기반 휴리스틱
더욱 강력한 허용적 휴리스틱으로, 미방문 작업의 잔여 시퀀싱 비용을 **할당 문제(assignment problem)**의 최적 해로 하한한다. 각 작업 노드에서 정확히 하나의 출발 간선과 하나의 도착 간선을 선택하는 최소 비용 할당을 구한다. 할당 문제는 헝가리 알고리즘(Hungarian algorithm)으로 O(|U|^3) 시간에 풀 수 있다.
h^{\text{AP}}(s) = \text{AP-cost}(U \cup \{t_{\text{last}}\})
할당 문제 하한은 MST 하한보다 일반적으로 더 조밀(tight)하지만, 계산 비용이 더 높다.
4.4 자원 제약 반영 휴리스틱
로봇 임무 시퀀싱에서 배터리 잔량 등의 자원 제약을 반영하기 위해, 휴리스틱에 자원 소모의 하한을 추가할 수 있다.
h^{\text{resource}}(s) = \max\left( h^{\text{MST}}(s), \ \sum_{t \in U} e_{\min}(t) - B_{\text{remaining}} \right)
여기서 e_{\min}(t)는 작업 t를 수행하기 위한 최소 에너지 소모이고, B_{\text{remaining}}은 잔여 배터리 용량이다. 잔여 작업의 최소 에너지 합이 잔여 배터리를 초과하면, 해당 상태에서의 해는 실행 불가능(infeasible)하므로 h = \infty로 설정하여 가지치기한다.
5. A* 기반 임무 시퀀싱의 구현
5.1 상태 표현의 최적화
임무 시퀀싱에서 상태 (V, t_{\text{last}})의 효율적 표현은 탐색 성능에 직접적 영향을 미친다. 방문한 작업 집합 V를 **비트마스크(bitmask)**로 표현하면, 상태의 해시 및 비교 연산이 O(1)로 수행된다.
\text{bitmask}(V) = \sum_{i: t_i \in V} 2^i
상태는 튜플 (\text{bitmask}(V), \text{index}(t_{\text{last}}))로 표현되며, 해시 테이블의 키로 사용된다.
5.2 구현 예시
다음은 A* 기반 임무 시퀀싱 최적화기의 구현 예시이다.
import heapq
from typing import List, Tuple, Optional, Dict
from dataclasses import dataclass
@dataclass
class MissionTask:
"""임무 작업을 나타내는 클래스"""
id: int
name: str
location: Tuple[float, float]
execution_time: float = 0.0
energy_cost: float = 0.0
class MSTHeuristic:
"""최소 신장 트리 기반 허용적 휴리스틱"""
def __init__(self, cost_matrix):
self.cost_matrix = cost_matrix
def compute(self, visited_mask: int,
last_task: int,
num_tasks: int) -> float:
"""MST 비용을 계산하여 휴리스틱 값을 반환한다."""
unvisited = []
for i in range(num_tasks):
if not (visited_mask & (1 << i)):
unvisited.append(i)
if not unvisited:
return 0.0
# 현재 위치를 포함한 노드 집합
nodes = [last_task] + unvisited
# Prim 알고리즘으로 MST 비용 계산
n = len(nodes)
if n <= 1:
return 0.0
in_mst = [False] * n
min_edge = [float('inf')] * n
min_edge[0] = 0.0
total_cost = 0.0
for _ in range(n):
# 최소 비용 노드 선택
u = -1
for v in range(n):
if (not in_mst[v] and
(u == -1 or
min_edge[v] < min_edge[u])):
u = v
in_mst[u] = True
total_cost += min_edge[u]
# 인접 노드의 최소 간선 갱신
for v in range(n):
if not in_mst[v]:
cost = self.cost_matrix[
nodes[u]][nodes[v]]
if cost < min_edge[v]:
min_edge[v] = cost
return total_cost
class AStarMissionSequencer:
"""A* 알고리즘 기반 임무 시퀀싱 최적화기"""
def __init__(self, tasks: List[MissionTask],
cost_matrix: List[List[float]]):
"""
Args:
tasks: 수행할 작업 목록
cost_matrix: 작업 간 전이 비용 행렬
"""
self.tasks = tasks
self.cost_matrix = cost_matrix
self.n = len(tasks)
self.heuristic = MSTHeuristic(cost_matrix)
def solve(self, start_task: int = 0,
precedence: Dict[int, List[int]] = None
) -> Optional[Tuple[List[int], float]]:
"""
최적 임무 시퀀스를 탐색한다.
Args:
start_task: 시작 작업 인덱스
precedence: 선후 관계 제약
{task: [선행 작업 목록]}
Returns:
(최적 시퀀스, 총 비용) 또는 None
"""
if precedence is None:
precedence = {}
all_visited = (1 << self.n) - 1
# 상태: (비트마스크, 마지막 작업)
init_mask = 1 << start_task
init_state = (init_mask, start_task)
g_values = {init_state: 0.0}
parent = {init_state: None}
h0 = self.heuristic.compute(
init_mask, start_task, self.n
)
# (f값, 타이브레이크 카운터, 상태)
open_list = [(h0, 0, init_state)]
counter = 1
closed = set()
while open_list:
f, _, state = heapq.heappop(open_list)
mask, last = state
if state in closed:
continue
# 목표 검사: 모든 작업 방문 완료
if mask == all_visited:
return (
self._extract_sequence(
parent, state
),
g_values[state]
)
closed.add(state)
g = g_values[state]
# 미방문 작업으로의 전이
for j in range(self.n):
if mask & (1 << j):
continue # 이미 방문
# 선후 관계 제약 검사
if not self._check_precedence(
j, mask, precedence
):
continue
new_mask = mask | (1 << j)
new_state = (new_mask, j)
new_g = g + self.cost_matrix[last][j]
if (new_state not in g_values or
new_g < g_values[new_state]):
g_values[new_state] = new_g
parent[new_state] = (state, j)
h = self.heuristic.compute(
new_mask, j, self.n
)
heapq.heappush(
open_list,
(new_g + h, counter, new_state)
)
counter += 1
return None
def _check_precedence(self, task_id: int,
visited_mask: int,
precedence: Dict
) -> bool:
"""선후 관계 제약을 검사한다."""
if task_id not in precedence:
return True
for pred in precedence[task_id]:
if not (visited_mask & (1 << pred)):
return False
return True
def _extract_sequence(self, parent, state):
"""역추적으로 최적 시퀀스를 추출한다."""
sequence = []
while parent[state] is not None:
prev_state, task_id = parent[state]
sequence.append(task_id)
state = prev_state
sequence.append(state[1]) # 시작 작업
sequence.reverse()
return sequence
6. A* 기반 임무 시퀀싱의 확장
6.1 시간 윈도(Time Window) 제약
각 작업에 수행 가능한 시간 구간(time window) [e_i, l_i]가 주어진 경우, 상태에 현재 시각 정보를 추가하여야 한다.
s = (V, t_{\text{last}}, \tau)
여기서 \tau는 현재 시각이다. 전이 시 작업 t_j를 수행하기 위해 도착 시각 \tau' = \tau + c(t_{\text{last}}, t_j)가 시간 윈도 내에 있어야 한다.
\tau' \leq l_j, \quad \text{실제 시작 시각}: \tau_{\text{start}} = \max(\tau', e_j)
시간 윈도 제약이 있는 경우 상태 공간의 크기가 크게 증가하므로, 시간 변수의 이산화 또는 상태 지배(state dominance) 관계를 활용한 가지치기가 필요하다.
6.2 다중 로봇 임무 시퀀싱
다중 로봇 시스템에서 m대의 로봇이 n개의 작업을 분담하여 수행하는 경우, 임무 시퀀싱 문제는 **다중 외판원 문제(multiple Traveling Salesman Problem, mTSP)**로 확장된다. 상태는 각 로봇의 현재 위치와 전체 방문 집합으로 구성된다.
s = (V, t_{\text{last}}^{(1)}, t_{\text{last}}^{(2)}, \ldots, t_{\text{last}}^{(m)})
다중 로봇 시퀀싱의 상태 공간은 단일 로봇 문제보다 크게 증가하므로, 분해(decomposition) 기반 접근이나 경매(auction) 기반 할당과의 결합이 실용적일 수 있다.
6.3 불확실성 하의 임무 시퀀싱
전이 비용이 확률 변수인 경우, 확률적 임무 시퀀싱 문제가 된다. 이 경우 기대 비용을 최소화하거나, 일정 확률 수준 이상의 임무 완수를 보장하는 시퀀스를 탐색하여야 한다. A*의 확률적 확장 또는 기대 비용을 사용하는 변형 알고리즘을 적용할 수 있다.
7. 계산 효율 향상 전략
7.1 대칭성 배제(Symmetry Breaking)
임무 시퀀싱 문제에서 동일한 작업 집합을 방문하는 순서가 다른 경우에도 동일한 잔여 비용을 가질 수 있다. 이러한 대칭 상태를 식별하고 중복 탐색을 방지하는 기법이 대칭성 배제이다. 예를 들어, 동일한 비용의 작업 그룹을 사전 순서로 정렬하여 탐색 순서를 고정하면 대칭 상태의 수를 줄일 수 있다.
7.2 점진적 A* (Anytime A*)
실시간 시스템에서 최적 해를 보장하는 A* 탐색이 시간 제약 내에 완료되지 않을 수 있다. 이 경우 가중 A(Weighted A)** 또는 ARA(Anytime Repairing A)**(Likhachev et al., 2004)를 사용하여, 초기에 빠르게 준최적 해를 생성하고 시간이 허용되는 만큼 해의 품질을 점진적으로 개선한다.
f_w(s) = g(s) + w \cdot h(s), \quad w > 1
가중치 w를 점진적으로 감소시키며 탐색을 반복하면, 최종적으로 최적 해에 수렴한다. 각 반복에서의 해는 w-최적(w-optimal)이 보장된다.
7.3 메모이제이션과 동적 프로그래밍
비트마스크 기반 상태 표현에서 동일한 (V, t_{\text{last}}) 상태에 대한 최소 비용 g(s)를 테이블에 저장함으로써, 중복 계산을 방지한다. 이 접근은 Held-Karp 알고리즘(Held & Karp, 1962)의 동적 프로그래밍 기법과 동일한 상태 공간을 공유하며, TSP에 대한 O(n^2 \cdot 2^n) 시간 복잡도를 달성한다.
A* 탐색은 휴리스틱의 품질에 따라 실제 탐색하는 상태의 수를 크게 줄일 수 있으므로, 동적 프로그래밍보다 실용적으로 빠른 경우가 많다.
8. 로봇 임무 시퀀싱의 응용 사례
8.1 물류 로봇의 멀티 픽업 시퀀싱
물류 로봇이 다수의 물체를 순차적으로 수집(pick-up)하여 배달 지점에 전달하는 임무에서, 수집 순서의 최적화는 총 이동 거리와 시간을 크게 절감한다. 비용 행렬은 물체의 위치 간 최단 경로 거리로 구성하며, 적재 용량 제약을 부가 조건으로 반영한다.
8.2 드론 정찰 임무 시퀀싱
복수의 정찰 지점을 순회하는 드론 임무에서, 방문 순서는 총 비행 시간과 에너지 소모에 직접적 영향을 미친다. 배터리 잔량 제약과 각 정찰 지점의 우선순위를 반영한 A* 기반 시퀀싱은 효율적이고 최적인 정찰 계획을 제공한다.
8.3 검사 로봇의 다지점 점검 시퀀싱
산업 시설의 다수 점검 지점을 순회하는 검사 로봇의 점검 순서 최적화에 A* 기반 시퀀싱이 적용된다. 시간 윈도 제약(특정 설비는 특정 시간대에만 점검 가능), 접근 제약(일부 구역은 선행 점검 완료 후에만 접근 가능) 등을 반영한 최적 순서를 생성한다.
9. 참고 문헌
- 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.
- Held, M., & Karp, R. M. (1962). “A Dynamic Programming Approach to Sequencing Problems.” Journal of the Society for Industrial and Applied Mathematics, 10(1), 196–210.
- Likhachev, M., Gordon, G. J., & Thrun, S. (2004). “ARA*: Anytime A* with Provable Bounds on Sub-Optimality.” Advances in Neural Information Processing Systems (NeurIPS 2003), 767–774.
- Christofides, N. (1976). “Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem.” Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University.
- Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press.
- Russell, S. J., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.
- Pearl, J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley.
v0.2.0