397.28 GraphPlan 알고리즘의 원리와 적용
1. 개요
GraphPlan(Blum & Furst, 1997)은 고전적 AI 계획 분야에서 획기적 성능 향상을 달성한 계획 알고리즘으로, **계획 그래프(planning graph)**라는 특수한 데이터 구조를 구성하고, 이 그래프에서 역추적 탐색을 통해 유효한 계획을 추출하는 방식으로 동작한다. GraphPlan은 계획 그래프의 확장(expansion) 단계와 해 추출(solution extraction) 단계를 반복하며, 계획의 최소 시간 단계(makespan)를 보장하는 계획을 생성한다. 본 절에서는 GraphPlan 알고리즘의 이론적 원리, 계획 그래프의 구조, 상호 배타 관계(mutex relations)의 역할, 해 추출 과정, 그리고 로봇 임무 계획에서의 적용을 기술한다.
2. 계획 그래프의 구조
2.1 계획 그래프의 정의
계획 그래프(planning graph)는 명제 계층(proposition levels)과 행동 계층(action levels)이 교대하는 계층적(layered) 방향 그래프이다. 형식적으로 계획 그래프 \mathcal{PG}는 다음과 같이 정의된다.
\mathcal{PG} = (P_0, A_0, P_1, A_1, \ldots, P_k, A_k, P_{k+1})
여기서 각 구성 요소는 다음과 같다.
- P_i: i번째 명제 계층으로, 시간 단계 i에서 잠재적으로 참일 수 있는 명제의 집합
- A_i: i번째 행동 계층으로, 시간 단계 i에서 잠재적으로 실행 가능한 행동의 집합
각 계층은 다음의 요소로 구성된다.
명제 노드(Proposition Node): 특정 시간 단계에서 참일 수 있는 상태 속성을 나타낸다. 명제 노드는 선행 행동 계층의 행동 노드로부터 **효과 간선(effect edge)**으로 연결된다.
행동 노드(Action Node): 특정 시간 단계에서 실행 가능한 행동을 나타낸다. 행동 노드는 선행 명제 계층의 명제 노드로부터 **전제 조건 간선(precondition edge)**으로 연결되고, 후속 명제 계층의 명제 노드로 효과 간선으로 연결된다.
유지 행동(No-op / Persistence Action): 명제의 값이 변하지 않는 것을 나타내는 특수한 행동이다. 각 명제에 대해, 해당 명제를 전제 조건으로 하고 동일한 명제를 효과로 갖는 유지 행동이 자동으로 추가된다.
2.2 계획 그래프의 구성(Expansion)
계획 그래프의 구성은 초기 상태에서 시작하여 시간 단계를 하나씩 증가시키며 진행된다.
초기 명제 계층 P_0: 초기 상태 s_0의 모든 명제를 포함한다.
P_0 = s_0
행동 계층 A_i 구성: 명제 계층 P_i에서 전제 조건이 모두 충족되는 행동을 식별하고, 해당 행동의 상호 배타 관계를 계산한다.
A_i = \{ a \in \mathcal{A} \mid \text{pre}(a) \subseteq P_i \wedge \text{no mutex preconditions} \}
여기서 “no mutex preconditions“는 전제 조건의 모든 명제 쌍이 P_i에서 상호 배타가 아닌 조건이다.
명제 계층 P_{i+1} 구성: 행동 계층 A_i의 모든 행동의 효과를 합집합으로 구성한다. 유지 행동에 의해 P_i의 명제도 P_{i+1}에 전이된다.
P_{i+1} = P_i \cup \bigcup_{a \in A_i} \text{add}(a)
계획 그래프의 핵심적 속성은 **단조 증가(monotonic growth)**이다. 명제 계층의 크기는 비감소하며(|P_i| \leq |P_{i+1}|), 상호 배타 관계의 수는 비증가한다. 이 단조성은 알고리즘의 종료를 보장한다.
3. 상호 배타 관계(Mutex Relations)
3.1 행동 간 상호 배타
두 행동 a_1, a_2 \in A_i가 **상호 배타(mutex)**인 조건은 다음의 세 가지 중 하나 이상을 만족하는 경우이다.
1. 불일치 효과(Inconsistent Effects): 한 행동의 긍정 효과가 다른 행동의 부정 효과와 충돌한다.
\text{add}(a_1) \cap \text{del}(a_2) \neq \emptyset \quad \vee \quad \text{add}(a_2) \cap \text{del}(a_1) \neq \emptyset
2. 간섭(Interference): 한 행동의 효과가 다른 행동의 전제 조건을 삭제한다.
\text{del}(a_1) \cap \text{pre}(a_2) \neq \emptyset \quad \vee \quad \text{del}(a_2) \cap \text{pre}(a_1) \neq \emptyset
3. 경합 전제 조건(Competing Needs): 두 행동의 전제 조건 중 상호 배타인 명제 쌍이 존재한다.
\exists p \in \text{pre}(a_1), q \in \text{pre}(a_2) : \text{mutex}_{P_i}(p, q)
3.2 명제 간 상호 배타
두 명제 p, q \in P_i가 상호 배타인 조건은, p와 q를 동시에 달성하는 비상호 배타적 행동 쌍이 존재하지 않는 경우이다.
\text{mutex}_{P_{i+1}}(p, q) \iff \forall a_1 \in \text{achievers}(p), a_2 \in \text{achievers}(q) : \text{mutex}_{A_i}(a_1, a_2)
여기서 \text{achievers}(p)는 명제 p를 효과로 갖는 행동 계층 A_i의 행동 집합이다.
상호 배타 관계는 계획 그래프의 **도달 불가능 분석(unreachability analysis)**을 수행하는 핵심 도구이다. 두 명제가 동일 시간 단계에서 상호 배타라면, 이 두 명제가 동시에 참인 상태는 해당 시간 단계까지의 어떤 유효한 계획에서도 도달 불가능하다.
3.3 상호 배타의 의의
상호 배타 관계는 휴리스틱 계산과 탐색 공간 축소의 두 가지 측면에서 중요한 역할을 수행한다.
- 해의 하한 추정: 목표 조건의 모든 명제가 동일 명제 계층에 나타나고 쌍별(pairwise) 상호 배타가 아닌 최초의 계층 인덱스는 계획 길이의 하한을 제공한다.
- 탐색 공간 가지치기: 상호 배타인 행동은 동일 시간 단계에서 동시에 선택될 수 없으므로, 해 추출 시 탐색 공간이 축소된다.
4. GraphPlan 알고리즘
4.1 알고리즘 절차
GraphPlan 알고리즘은 다음의 두 단계를 반복한다.
\begin{aligned} &\textbf{Algorithm: GraphPlan}(\mathcal{P}) \\ &\quad \text{Initialize } \mathcal{PG} \text{ with } P_0 = s_0 \\ &\quad k \leftarrow 0 \\ &\quad \textbf{loop} \\ &\quad\quad \text{Expand } \mathcal{PG} \text{ by one level: compute } A_k, P_{k+1} \\ &\quad\quad \text{Compute mutex relations for } A_k \text{ and } P_{k+1} \\ &\quad\quad \textbf{if } G \subseteq P_{k+1} \text{ and } \nexists \text{ mutex pair in } G \text{ at } P_{k+1} \textbf{ then} \\ &\quad\quad\quad \Pi \leftarrow \text{ExtractSolution}(\mathcal{PG}, G, k+1) \\ &\quad\quad\quad \textbf{if } \Pi \neq \text{FAIL} \textbf{ then return } \Pi \\ &\quad\quad \textbf{if } \text{graph leveled off} \textbf{ then return } \text{FAIL} \\ &\quad\quad k \leftarrow k + 1 \\ &\quad \textbf{end loop} \end{aligned}
그래프 안정화(Level-Off) 조건: 연속된 두 명제 계층이 동일하고(P_i = P_{i+1}), 상호 배타 관계도 동일한 경우, 계획 그래프가 안정화되었다고 판단한다. 안정화 후에도 해가 추출되지 않으면 계획 문제는 해가 없다.
4.2 해 추출(Solution Extraction)
해 추출 단계에서는 계획 그래프의 마지막 계층에서 목표 명제를 달성하는 행동 집합을 역추적 방식으로 구성한다. 이 과정은 다음과 같이 진행된다.
- 마지막 명제 계층 P_{k+1}에서 목표 조건 G의 모든 명제를 식별한다.
- 각 목표 명제를 달성할 수 있는 행동을 행동 계층 A_k에서 선택한다.
- 선택된 행동들이 상호 배타가 아닌지 확인한다.
- 선택된 행동들의 전제 조건을 이전 명제 계층 P_k에서의 새로운 하위 목표로 설정한다.
- 명제 계층 P_0에 도달할 때까지 위 과정을 재귀적으로 반복한다.
해 추출은 **제약 충족 문제(Constraint Satisfaction Problem, CSP)**와 유사한 구조를 가지며, 역추적 탐색(backtracking search)으로 구현된다.
class GraphPlanSolver:
"""GraphPlan 알고리즘의 구현"""
def __init__(self, domain, problem):
self.domain = domain
self.problem = problem
self.prop_layers = []
self.action_layers = []
self.mutex_props = []
self.mutex_actions = []
self.no_good_table = {}
def solve(self):
"""GraphPlan 알고리즘을 실행한다."""
# 초기 명제 계층
self.prop_layers.append(
set(self.problem.init)
)
self.mutex_props.append(set())
level = 0
while True:
# 그래프 확장
self._expand_graph(level)
# 목표 도달 가능성 검사
goal = set(self.problem.goal)
current_props = self.prop_layers[level + 1]
current_mutex = self.mutex_props[level + 1]
if goal.issubset(current_props):
# 목표 명제 간 상호 배타 검사
goal_mutex = False
goal_list = list(goal)
for i in range(len(goal_list)):
for j in range(i + 1,
len(goal_list)):
pair = frozenset(
{goal_list[i],
goal_list[j]}
)
if pair in current_mutex:
goal_mutex = True
break
if goal_mutex:
break
if not goal_mutex:
plan = self._extract_solution(
goal, level + 1
)
if plan is not None:
return plan
# 안정화 검사
if self._leveled_off(level):
return None
level += 1
def _expand_graph(self, level):
"""계획 그래프를 한 단계 확장한다."""
current_props = self.prop_layers[level]
# 적용 가능한 행동 식별
actions = set()
for action in self.domain.ground_actions:
if action.preconditions.issubset(
current_props
):
# 전제 조건 간 상호 배타 검사
pre_list = list(action.preconditions)
has_mutex = False
for i in range(len(pre_list)):
for j in range(i + 1,
len(pre_list)):
pair = frozenset(
{pre_list[i], pre_list[j]}
)
if pair in self.mutex_props[
level
]:
has_mutex = True
break
if has_mutex:
break
if not has_mutex:
actions.add(action)
# 유지 행동 추가
for prop in current_props:
actions.add(NoOp(prop))
self.action_layers.append(actions)
# 행동 간 상호 배타 계산
action_mutex = set()
action_list = list(actions)
for i in range(len(action_list)):
for j in range(i + 1, len(action_list)):
if self._actions_mutex(
action_list[i], action_list[j],
level
):
pair = frozenset(
{action_list[i], action_list[j]}
)
action_mutex.add(pair)
self.mutex_actions.append(action_mutex)
# 다음 명제 계층 구성
next_props = set(current_props)
for action in actions:
next_props |= action.add_effects
self.prop_layers.append(next_props)
# 명제 간 상호 배타 계산
prop_mutex = set()
prop_list = list(next_props)
for i in range(len(prop_list)):
for j in range(i + 1, len(prop_list)):
if self._props_mutex(
prop_list[i], prop_list[j], level
):
pair = frozenset(
{prop_list[i], prop_list[j]}
)
prop_mutex.add(pair)
self.mutex_props.append(prop_mutex)
def _actions_mutex(self, a1, a2, level):
"""두 행동이 상호 배타인지 검사한다."""
# 불일치 효과
if (a1.add_effects & a2.del_effects or
a2.add_effects & a1.del_effects):
return True
# 간섭
if (a1.del_effects & a2.preconditions or
a2.del_effects & a1.preconditions):
return True
# 경합 전제 조건
for p in a1.preconditions:
for q in a2.preconditions:
pair = frozenset({p, q})
if pair in self.mutex_props[level]:
return True
return False
def _props_mutex(self, p, q, level):
"""두 명제가 상호 배타인지 검사한다."""
achievers_p = [
a for a in self.action_layers[level]
if p in a.add_effects
]
achievers_q = [
a for a in self.action_layers[level]
if q in a.add_effects
]
for ap in achievers_p:
for aq in achievers_q:
pair = frozenset({ap, aq})
if (pair not in
self.mutex_actions[level]):
return False
return True
def _extract_solution(self, goals, level):
"""역추적 탐색으로 해를 추출한다."""
if level == 0:
# 초기 상태에서 모든 목표가 충족
if goals.issubset(self.prop_layers[0]):
return []
return None
# 메모이제이션 검사
key = (frozenset(goals), level)
if key in self.no_good_table:
return None
# 목표를 달성하는 행동 집합 탐색
plan_step = self._select_actions(
goals, level - 1
)
if plan_step is None:
self.no_good_table[key] = True
return None
# 선택된 행동의 전제 조건을 새 목표로 설정
new_goals = set()
for action in plan_step:
new_goals |= action.preconditions
# 재귀적으로 이전 계층에서 해 추출
sub_plan = self._extract_solution(
new_goals, level - 1
)
if sub_plan is None:
self.no_good_table[key] = True
return None
# 유지 행동 제거
real_actions = [
a for a in plan_step
if not isinstance(a, NoOp)
]
return sub_plan + [real_actions]
def _select_actions(self, goals, action_level):
"""목표를 달성하는 비상호 배타적 행동 집합을 선택"""
# CSP 기반 역추적 탐색 (간략화)
return self._backtrack_select(
list(goals), [], action_level, 0
)
def _backtrack_select(self, goal_list, selected,
action_level, idx):
"""역추적으로 행동 조합을 탐색한다."""
if idx >= len(goal_list):
return list(selected)
goal = goal_list[idx]
# 이미 선택된 행동이 이 목표를 달성하는 경우
for act in selected:
if goal in act.add_effects:
return self._backtrack_select(
goal_list, selected,
action_level, idx + 1
)
# 목표를 달성하는 행동 후보 열거
achievers = [
a for a in
self.action_layers[action_level]
if goal in a.add_effects
]
for act in achievers:
# 기존 선택과의 상호 배타 검사
conflict = False
for sel in selected:
pair = frozenset({act, sel})
if pair in self.mutex_actions[
action_level
]:
conflict = True
break
if not conflict:
result = self._backtrack_select(
goal_list, selected + [act],
action_level, idx + 1
)
if result is not None:
return result
return None
def _leveled_off(self, level):
"""그래프 안정화 여부를 검사한다."""
if level < 1:
return False
return (
self.prop_layers[level + 1] ==
self.prop_layers[level] and
self.mutex_props[level + 1] ==
self.mutex_props[level]
)
5. GraphPlan의 이론적 성질
5.1 완전성(Completeness)
GraphPlan은 **완전(complete)**하다. 즉, 해가 존재하면 반드시 해를 찾고, 해가 존재하지 않으면 반드시 실패를 보고한다. 완전성은 계획 그래프의 단조 증가 속성과 안정화 조건에 의해 보장된다.
5.2 건전성(Soundness)
GraphPlan이 반환하는 계획은 항상 **유효(valid)**하다. 해 추출 단계에서 모든 행동의 전제 조건 충족과 상호 배타 제약을 검증하므로, 추출된 계획의 행동을 실행하면 목표 조건이 달성된다.
5.3 최적성(Optimality)
GraphPlan은 최소 시간 단계(minimum makespan) 계획을 생성한다. 그래프를 한 계층씩 확장하며 해를 탐색하므로, 가장 적은 병렬 시간 단계로 실행 가능한 계획이 먼저 발견된다. 그러나 행동 비용을 고려한 최적성은 보장하지 않는다.
5.4 시간 복잡도
계획 그래프의 각 계층 구성에는 O(|\mathcal{A}|^2 \cdot |\mathcal{F}|^2)의 시간이 소요되며(행동 쌍과 명제 쌍의 상호 배타 계산), 해 추출은 최악의 경우 지수적 시간이 소요된다. 그러나 상호 배타 관계에 의한 효과적 가지치기와 메모이제이션(memoization)에 의해 실제 계산 시간은 대부분의 벤치마크 문제에서 양호하다.
6. 계획 그래프의 휴리스틱 활용
계획 그래프는 GraphPlan 알고리즘 자체뿐만 아니라, 다른 탐색 기반 계획기의 휴리스틱 함수 계산에도 널리 활용된다.
계획 그래프 계층 휴리스틱(h^{\text{level}}): 목표 조건의 모든 명제가 쌍별 비상호 배타로 처음 나타나는 계층의 인덱스를 휴리스틱으로 사용한다.
h^{\text{level}}(s) = \min \{i \mid G \subseteq P_i \wedge \nexists \text{mutex pair in } G \text{ at } P_i \}
최대 계층 휴리스틱(h^{\text{max-level}}): 각 목표 명제가 처음 나타나는 계층 인덱스의 최대값을 휴리스틱으로 사용한다.
h^{\text{max-level}}(s) = \max_{p \in G} \min \{i \mid p \in P_i\}
합산 계층 휴리스틱(h^{\text{sum-level}}): 각 목표 명제가 처음 나타나는 계층 인덱스의 합을 휴리스틱으로 사용한다.
h^{\text{sum-level}}(s) = \sum_{p \in G} \min \{i \mid p \in P_i\}
이러한 휴리스틱은 계획 그래프의 구성 비용(O(k \cdot |\mathcal{A}| \cdot |\mathcal{F}|), k는 계층 수)에 계산되며, 삭제 완화 휴리스틱과 유사한 정보량을 제공한다.
7. 로봇 임무 계획에서의 GraphPlan 적용
7.1 적용 시 고려사항
로봇 임무 계획에 GraphPlan을 적용할 때 다음의 사항을 고려하여야 한다.
병렬 행동의 식별: GraphPlan이 생성하는 계획은 각 시간 단계에서 동시에 실행 가능한 행동을 식별한다. 이는 다중 로봇 시스템이나 복수의 매니퓰레이터를 갖는 로봇에서 병렬 실행 가능한 행동을 자동으로 계획하는 데 유용하다.
기저화(Grounding) 비용: GraphPlan은 모든 행동을 기저화(ground)하여 사용하므로, 객체의 수가 많은 도메인에서는 기저 행동의 수가 급격히 증가한다. 이를 관리하기 위해 타입 기반 필터링과 관련성 분석(relevance analysis)을 통한 사전 가지치기가 필요하다.
수치 변수의 처리: 표준 GraphPlan은 명제적(propositional) 표현만 지원하므로, 배터리 잔량 등의 수치 변수를 직접 처리할 수 없다. 수치 변수의 이산화(discretization) 또는 수치 확장 GraphPlan 변형의 적용이 필요하다.
7.2 GraphPlan 기반 로봇 계획의 예시
다음은 물류 로봇의 물체 운반 임무에 대한 GraphPlan 적용 예시이다.
도메인: 로봇이 여러 방을 이동하면서 물체를 운반하는 임무
초기 상태 s_0:
{at(robot1, room-A), object-at(box1, room-A),
object-at(box2, room-B), gripper-free(robot1),
connected(room-A, room-B), connected(room-B, room-A),
connected(room-B, room-C), connected(room-C, room-B)}
목표 조건 G:
{object-at(box1, room-C), object-at(box2, room-C)}
GraphPlan은 이 문제에 대해 계획 그래프를 구성하고, 상호 배타 관계를 분석하여 최소 시간 단계의 계획을 추출한다.
7.3 역사적 의의와 현대적 위치
GraphPlan은 1997년 발표 이후 AI 계획 연구에 지대한 영향을 미쳤다. 계획 그래프의 개념은 이후 삭제 완화 휴리스틱(FF 휴리스틱), 도달 가능성 분석, 랜드마크 추출 등의 기법에 직접적 영향을 주었으며, 현대 고성능 계획기의 이론적 기반이 되었다.
그러나 현대의 고성능 계획기(Fast Downward, LAMA 등)는 GraphPlan의 해 추출 방식 대신 상태 공간 탐색에 계획 그래프 기반 휴리스틱을 결합하는 방식을 채택하여, GraphPlan보다 우수한 확장성을 달성하였다. 따라서 현대 로봇 임무 계획에서 GraphPlan은 주로 교육적 목적과 소규모 문제의 최적 병렬 계획 생성에 활용된다.
8. 참고 문헌
- Blum, A. L., & Furst, M. L. (1997). “Fast Planning Through Planning Graph Analysis.” Artificial Intelligence, 90(1–2), 281–300.
- Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
- Hoffmann, J., & Nebel, B. (2001). “The FF Planning System: Fast Plan Generation Through Heuristic Search.” Journal of Artificial Intelligence Research, 14, 253–302.
- Russell, S. J., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.
- Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.
- Kambhampati, S. (2000). “Planning Graph Heuristics for Belief Space Search.” Journal of Artificial Intelligence Research, 12, 373–416.
v0.2.0