397.24 순방향 탐색(Forward Search) 기반 계획

1. 개요

순방향 탐색(forward search) 기반 계획은 초기 상태에서 출발하여 행동을 적용함으로써 후속 상태(successor state)를 생성하고, 목표 조건을 만족하는 상태에 도달할 때까지 탐색을 진행하는 계획 기법이다. 이 접근 방식은 **진행 방향 계획(progression planning)**이라고도 하며, 초기 상태가 완전히 정의된 상태(fully specified state)인 고전적 계획 문제에서 가장 자연스러운 탐색 전략이다. 순방향 탐색은 현대 고성능 계획기(예: Fast Downward, LAMA, FF)의 핵심 알고리즘 기반으로 자리 잡았으며, 로봇 임무 계획에서 광범위하게 활용된다.

2. 순방향 탐색의 수학적 기초

2.1 고전적 계획의 상태 공간 모델

고전적 계획 문제는 상태 공간 모델(state-space model)로 형식화할 수 있다. 고전적 계획 문제 $\mathcal{P}$ 는 다음의 4-튜플로 정의된다.

$\mathcal{P} = \langle \mathcal{F}, \mathcal{A}, s_0, G \rangle$

여기서 각 구성 요소는 다음과 같다.

$\mathcal{F}$ : 명제 변수(propositional variables)의 유한 집합으로, 가능한 상태 속성을 정의한다.
$\mathcal{A}$ : 행동(actions)의 유한 집합으로, 각 행동 $a \in \mathcal{A}$ 는 전제 조건 $\text{pre}(a) \subseteq \mathcal{F}$ , 긍정 효과 $\text{add}(a) \subseteq \mathcal{F}$ , 부정 효과 $\text{del}(a) \subseteq \mathcal{F}$ 로 정의된다.
$s_0 \subseteq \mathcal{F}$ : 초기 상태로, 명제 변수의 부분 집합이다.
$G \subseteq \mathcal{F}$ : 목표 조건으로, 달성하여야 할 명제의 집합이다.

상태 $s$ 에서 행동 $a$ 가 **적용 가능(applicable)**하기 위한 조건은 다음과 같다.

$\text{pre}(a) \subseteq s$

행동 $a$ 를 상태 $s$ 에 적용한 결과인 후속 상태 $s'$ 는 다음과 같이 정의된다.

$s' = \gamma(s, a) = (s \setminus \text{del}(a)) \cup \text{add}(a)$

계획(plan) $\pi = \langle a_1, a_2, \ldots, a_n \rangle$ 은 행동의 순서열이며, 이를 초기 상태에 순차적으로 적용하여 최종 상태 $s_n$ 이 $G \subseteq s_n$ 을 만족하면 유효한 계획(valid plan)이라 한다.

2.2 상태 공간 그래프

순방향 탐색은 상태 공간을 **암묵적 그래프(implicit graph)**로 간주한다. 이 그래프에서 각 노드는 세계 상태(world state)를 나타내고, 간선은 행동의 적용에 의한 상태 전이를 나타낸다. 그래프의 형식적 정의는 다음과 같다.

$\mathcal{G} = (V, E), \quad V = 2^{\mathcal{F}}, \quad E = \{(s, s') \mid \exists a \in \mathcal{A}: \text{pre}(a) \subseteq s \wedge s' = \gamma(s, a)\}$

상태 공간 그래프의 크기는 명제 변수의 수 $|\mathcal{F}|$ 에 대해 지수적( $2^{|\mathcal{F}|}$ )으로 증가하므로, 탐색의 효율성을 결정하는 핵심 요소는 탐색 전략의 선택과 휴리스틱 함수의 품질이다.

3. 순방향 탐색 알고리즘

3.1 기본 순방향 탐색 절차

순방향 탐색의 기본 절차는 다음과 같다.

$\begin{aligned} &\textbf{Algorithm: Forward-Search}(\mathcal{P}) \\ &\quad \text{Open} \leftarrow \{s_0\} \\ &\quad \text{Closed} \leftarrow \emptyset \\ &\quad \textbf{while } \text{Open} \neq \emptyset \textbf{ do} \\ &\quad\quad s \leftarrow \text{Select}(\text{Open}) \\ &\quad\quad \textbf{if } G \subseteq s \textbf{ then return } \text{ExtractPlan}(s) \\ &\quad\quad \text{Closed} \leftarrow \text{Closed} \cup \{s\} \\ &\quad\quad \textbf{for each } a \in \mathcal{A} \text{ with } \text{pre}(a) \subseteq s \textbf{ do} \\ &\quad\quad\quad s' \leftarrow \gamma(s, a) \\ &\quad\quad\quad \textbf{if } s' \notin \text{Closed} \cup \text{Open} \textbf{ then} \\ &\quad\quad\quad\quad \text{Open} \leftarrow \text{Open} \cup \{s'\} \\ &\quad \textbf{return } \text{FAIL} \end{aligned}$

여기서 Select 함수는 개방 목록(open list)에서 다음에 확장할 상태를 선택하는 함수로, 이 함수의 정의에 따라 탐색 전략이 결정된다.

3.2 비정보 탐색(Uninformed Search)

비정보 탐색 전략은 휴리스틱 정보 없이 상태 공간을 체계적으로 탐색한다.

너비 우선 탐색(Breadth-First Search, BFS): 개방 목록을 큐(queue)로 구현하여, 초기 상태로부터 동일한 깊이에 있는 모든 상태를 먼저 확장한 후 다음 깊이로 진행한다. BFS는 모든 행동의 비용이 동일한 경우 최적 해를 보장하지만, 메모리 소모가 크다. 시간 복잡도와 공간 복잡도는 모두 $O(b^d)$ 이다. 여기서 $b$ 는 분기 인수(branching factor)이고, $d$ 는 해의 깊이이다.

깊이 우선 탐색(Depth-First Search, DFS): 개방 목록을 스택(stack)으로 구현하여, 하나의 경로를 최대 깊이까지 탐색한 후 역추적(backtracking)한다. DFS는 메모리 효율이 높지만( $O(bm)$ , $m$ 은 최대 깊이), 최적성을 보장하지 않으며 무한 경로에 빠질 위험이 있다.

반복 심화 탐색(Iterative Deepening Search, IDS): 깊이 제한(depth limit)을 점진적으로 증가시키면서 깊이 제한 탐색을 반복한다. BFS의 완전성·최적성과 DFS의 공간 효율성을 동시에 달성한다. 시간 복잡도는 $O(b^d)$ 이며, 공간 복잡도는 $O(bd)$ 이다.

전략	완전성	최적성	시간 복잡도	공간 복잡도
너비 우선 탐색	예	예 (균등 비용)	$O(b^d)$	$O(b^d)$
깊이 우선 탐색	아니오	아니오	$O(b^m)$	$O(bm)$
반복 심화 탐색	예	예 (균등 비용)	$O(b^d)$	$O(bd)$
균등 비용 탐색	예	예	$O(b^{1+\lfloor C^*/\epsilon \rfloor})$	$O(b^{1+\lfloor C^*/\epsilon \rfloor})$

여기서 $C^*$ 는 최적 해의 비용이고, $\epsilon$ 은 최소 행동 비용이다.

3.3 정보 탐색(Informed Search)과 휴리스틱

정보 탐색 전략은 휴리스틱 함수(heuristic function) $h : S \rightarrow \mathbb{R}_{\geq 0}$ 를 활용하여 탐색을 안내한다. 휴리스틱 함수는 현재 상태에서 목표까지의 예상 비용을 추정하며, 이 추정치의 품질이 탐색 효율을 결정한다.

탐욕적 최적 우선 탐색(Greedy Best-First Search, GBFS): 휴리스틱 값 $h(s)$ 가 가장 작은 상태를 우선적으로 확장한다. 평가 함수는 $f(s) = h(s)$ 이다. GBFS는 빠른 해 발견에 유리하지만 최적성을 보장하지 않는다.

A 탐색*: 평가 함수 $f(s) = g(s) + h(s)$ 를 사용한다. 여기서 $g(s)$ 는 초기 상태에서 현재 상태까지의 실제 비용이고, $h(s)$ 는 현재 상태에서 목표까지의 추정 비용이다. 휴리스틱 $h$ 가 허용적(admissible), 즉 실제 비용을 초과 추정하지 않는 경우 A*는 최적 해를 보장한다.

$h(s) \leq h^*(s), \quad \forall s \in S$

여기서 $h^*(s)$ 는 상태 $s$ 에서 목표까지의 실제 최적 비용이다.

가중 A 탐색(Weighted A, WA*)**: 평가 함수 $f(s) = g(s) + w \cdot h(s)$ 를 사용하며, 가중치 $w > 1$ 은 탐색의 탐욕성을 조절한다. $w$ 가 클수록 GBFS에 가까워져 탐색이 빨라지지만 해의 품질이 저하된다. WA*는 $w$ -최적(w-optimal) 해를 보장한다.

$\text{cost}(\pi_{WA^*}) \leq w \cdot \text{cost}(\pi^*)$

4. 순방향 탐색 계획의 휴리스틱 함수

4.1 삭제 완화 휴리스틱(Delete Relaxation Heuristics)

삭제 완화(delete relaxation)는 순방향 탐색 계획에서 가장 성공적인 휴리스틱 설계 기법이다. 삭제 완화는 모든 행동의 부정 효과(delete effects)를 무시하여 완화된 문제(relaxed problem)를 구성하며, 이 완화된 문제의 최적 해 비용 $h^+(s)$ 를 원래 문제의 휴리스틱으로 사용한다.

완화된 상태 전이 함수는 다음과 같이 정의된다.

$\gamma^+(s, a) = s \cup \text{add}(a)$

삭제 완화된 문제에서는 한번 참이 된 명제가 다시 거짓이 되지 않으므로, 상태가 단조 증가(monotonically increasing)한다. $h^+(s)$ 의 정확한 계산은 NP-hard이지만(Bylander, 1994), 이를 다항 시간에 근사하는 여러 휴리스틱이 개발되었다.

4.1.1 가산 휴리스틱( $h^{\text{add}}$ )

가산 휴리스틱(additive heuristic)은 각 목표 명제를 독립적으로 달성하는 비용의 합으로 목표 달성 비용을 추정한다. 각 명제 $p \in \mathcal{F}$ 에 대한 추정 비용 $h^{\text{add}}(s, p)$ 는 다음과 같이 재귀적으로 계산된다.

$h^{\text{add}}(s, p) = \begin{cases} 0 & \text{if } p \in s \\ \min_{a \in \mathcal{A}: p \in \text{add}(a)} \left( \text{cost}(a) + \sum_{q \in \text{pre}(a)} h^{\text{add}}(s, q) \right) & \text{otherwise} \end{cases}$

목표 조건 $G$ 에 대한 가산 휴리스틱 값은 다음과 같다.

$h^{\text{add}}(s) = \sum_{p \in G} h^{\text{add}}(s, p)$

$h^{\text{add}}$ 는 목표 명제 간의 긍정적 상호 작용(positive interaction)을 고려하지 않으므로 관대하지 않으며(inadmissible), 실제 비용을 과대 추정할 수 있다. 그러나 정보량이 풍부하여 만족형 계획에서 효과적이다.

4.1.2 최대 휴리스틱( $h^{\text{max}}$ )

최대 휴리스틱(maximum heuristic)은 목표 명제 중 가장 비용이 높은 명제의 비용을 추정치로 사용한다.

$h^{\text{max}}(s, p) = \begin{cases} 0 & \text{if } p \in s \\ \min_{a \in \mathcal{A}: p \in \text{add}(a)} \left( \text{cost}(a) + \max_{q \in \text{pre}(a)} h^{\text{max}}(s, q) \right) & \text{otherwise} \end{cases}$

$h^{\text{max}}(s) = \max_{p \in G} h^{\text{max}}(s, p)$

$h^{\text{max}}$ 는 허용적(admissible)이므로 A* 탐색에서 최적 해를 보장하지만, 정보량이 적어 많은 수의 노드를 확장하여야 하는 경향이 있다.

4.1.3 FF 휴리스틱( $h^{\text{FF}}$ )

FF 휴리스틱(Hoffmann, 2001)은 삭제 완화된 문제를 완화된 계획 그래프(relaxed planning graph)를 이용하여 효율적으로 풀고, 완화된 계획의 행동 수를 휴리스틱 값으로 사용한다. FF 휴리스틱은 $h^{\text{add}}$ 보다 정확한 추정을 제공하면서도 다항 시간에 계산 가능하다.

FF 휴리스틱의 계산 절차는 다음과 같다.

현재 상태 $s$ 에서 완화된 계획 그래프를 구성한다.
목표 명제가 모두 나타나는 계층에서 역추적(backtracking)을 수행하여 완화된 계획을 추출한다.
추출된 완화된 계획의 행동 수(또는 비용 합)를 $h^{\text{FF}}(s)$ 로 사용한다.

4.1.4 LM-Cut 휴리스틱( $h^{\text{LM-cut}}$ )

LM-Cut 휴리스틱(Helmert & Domshlak, 2009)은 삭제 완화 문제에서 **비용 분할(cost partitioning)**을 통해 허용적이면서도 정보량이 높은 휴리스틱을 구성한다. LM-Cut은 삭제 완화 그래프에서 최소 절단(minimum cut)에 해당하는 **적절 디스절트 행동 랜드마크(disjunctive action landmarks)**를 반복적으로 식별하고, 각 랜드마크의 최소 비용을 합산한다.

$h^{\text{LM-cut}}(s) = \sum_{i=1}^{k} \min_{a \in L_i} \text{cost}_i(a)$

여기서 $L_i$ 는 $i$ 번째 반복에서 식별된 행동 랜드마크 집합이고, $\text{cost}_i(a)$ 는 해당 반복에서의 행동 비용이다. $h^{\text{LM-cut}}$ 은 허용적이므로 최적 계획 탐색에 적합하다.

4.2 추상화 기반 휴리스틱(Abstraction-Based Heuristics)

추상화 기반 휴리스틱은 원래 문제의 상태 공간을 축소된 추상 공간으로 매핑하고, 추상 공간에서의 최적 거리를 휴리스틱으로 사용한다.

패턴 데이터베이스(Pattern Database, PDB): 상태 변수의 부분 집합(패턴)으로 정의된 사영(projection)에 의한 추상화를 사용한다. 사영된 문제에서 모든 상태 쌍 간의 최적 거리를 사전 계산하여 룩업 테이블에 저장한다.

$h^{\text{PDB}}(s) = d^*(\alpha(s), \alpha(s_G))$

여기서 $\alpha$ 는 사영 함수이고, $d^*$ 는 추상 공간에서의 최적 거리이다.

병합 및 축소(Merge-and-Shrink): 주어진 계획 문제의 상태 전이 시스템을 점진적으로 합성하면서, 크기가 과도해지면 상태를 병합(축소)하여 관리 가능한 크기의 추상화를 구성한다. 축소 과정에서 허용성을 보존하는 전략(예: 양분법적 축소)을 사용하면 허용적 휴리스틱을 얻을 수 있다.

4.3 랜드마크 기반 휴리스틱(Landmark-Based Heuristics)

**랜드마크(landmark)**는 임의의 유효한 계획에서 반드시 어느 시점에 참이 되어야 하는 명제 또는 반드시 어느 시점에 실행되어야 하는 행동이다. 랜드마크 기반 휴리스틱은 아직 달성되지 않은 랜드마크의 수 또는 비용을 휴리스틱 값으로 사용한다.

LAMA 계획기(Richter & Westphal, 2010)는 랜드마크 기반 비용 인식 휴리스틱을 사용하며, 다음과 같이 정의된다.

$h^{\text{lama}}(s) = \sum_{L \in \mathcal{L}_{\text{not-achieved}}} \min_{a \in \text{achievers}(L)} \text{cost}(a)$

여기서 $\mathcal{L}_{\text{not-achieved}}$ 는 현재까지 달성되지 않은 랜드마크의 집합이다.

5. 순방향 탐색의 실질적 구현

5.1 SAS+ 표현으로의 변환

현대 순방향 탐색 계획기는 PDDL의 명제적 표현을 SAS+ 표현(Bäckström & Nebel, 1995)으로 변환하여 내부적으로 사용한다. SAS+ 표현은 이진 명제 대신 **유한 도메인 변수(finite-domain variables)**를 사용하여 상태를 기술한다.

$\text{SAS+ 문제: } \langle \mathcal{V}, \mathcal{A}, s_0, G \rangle$

여기서 $\mathcal{V} = \{v_1, v_2, \ldots, v_n\}$ 은 유한 도메인 변수의 집합이고, 각 변수 $v_i$ 의 도메인은 $D_i$ 이다. 상태 $s$ 는 각 변수에 대한 값의 할당 $s = \{v_1 \mapsto d_1, v_2 \mapsto d_2, \ldots, v_n \mapsto d_n\}$ 이다.

SAS+ 표현의 장점은 다음과 같다.

상호 배타성(Mutex) 관계의 자동 인코딩: 하나의 변수는 동시에 하나의 값만 가질 수 있으므로, 상호 배타적 명제 그룹이 자연스럽게 표현된다.
상태 표현의 압축: 다수의 이진 명제를 단일 다치 변수로 압축할 수 있다.
효율적인 후속 상태 생성: 변수 기반 표현은 행동의 적용과 상태 비교를 효율적으로 수행할 수 있게 한다.

5.2 후속 상태 생성의 최적화

순방향 탐색에서 가장 빈번하게 수행되는 연산은 주어진 상태에서 적용 가능한 행동의 열거와 후속 상태의 생성이다. 이 연산의 최적화는 탐색 성능에 직접적 영향을 미친다.

적용 가능 행동 열거: 모든 행동에 대해 전제 조건의 충족 여부를 검사하는 순진한(naive) 방식은 $O(|\mathcal{A}| \cdot |\text{pre}_{\max}|)$ 의 시간이 소요된다. 이를 개선하기 위해 역 인덱스(inverted index) 구조를 사용하여, 각 명제에 대해 해당 명제를 전제 조건으로 갖는 행동의 목록을 미리 구성한다.

class ForwardSearchPlanner:
    """순방향 탐색 기반 계획기의 구현"""
    
    def __init__(self, domain):
        self.domain = domain
        self._build_action_index()
    
    def _build_action_index(self):
        """행동의 역 인덱스를 구성한다."""
        self.precond_index = {}
        for action in self.domain.actions:
            for precond in action.preconditions:
                if precond not in self.precond_index:
                    self.precond_index[precond] = []
                self.precond_index[precond].append(action)
    
    def get_applicable_actions(self, state):
        """주어진 상태에서 적용 가능한 행동을 반환한다."""
        applicable = []
        for action in self.domain.actions:
            if all(p in state for p in action.preconditions):
                applicable.append(action)
        return applicable
    
    def apply_action(self, state, action):
        """행동을 상태에 적용하여 후속 상태를 생성한다."""
        new_state = (state - action.delete_effects) | \
                    action.add_effects
        return frozenset(new_state)
    
    def solve(self, problem, strategy='gbfs',
              heuristic=None):
        """
        순방향 탐색을 수행하여 계획을 생성한다.
        
        Args:
            problem: 계획 문제 인스턴스
            strategy: 탐색 전략 ('bfs', 'gbfs', 'astar')
            heuristic: 휴리스틱 함수
        
        Returns:
            plan: 행동 시퀀스 또는 None
        """
        initial_state = frozenset(problem.init)
        goal = problem.goal
        
        if strategy == 'bfs':
            return self._bfs(initial_state, goal)
        elif strategy == 'gbfs':
            return self._gbfs(initial_state, goal,
                             heuristic)
        elif strategy == 'astar':
            return self._astar(initial_state, goal,
                              heuristic)
    
    def _astar(self, init, goal, h):
        """A* 탐색을 수행한다."""
        import heapq
        
        open_list = []
        g_values = {init: 0}
        parent = {init: (None, None)}
        closed = set()
        
        h_val = h(init, goal)
        heapq.heappush(open_list,
                       (0 + h_val, id(init), init))
        
        while open_list:
            f, _, state = heapq.heappop(open_list)
            
            if state in closed:
                continue
            
            if goal.issubset(state):
                return self._extract_plan(parent, state)
            
            closed.add(state)
            g = g_values[state]
            
            for action in self.get_applicable_actions(
                state
            ):
                successor = self.apply_action(
                    state, action
                )
                new_g = g + action.cost
                
                if (successor not in g_values or 
                    new_g < g_values[successor]):
                    g_values[successor] = new_g
                    parent[successor] = (state, action)
                    h_val = h(successor, goal)
                    heapq.heappush(
                        open_list,
                        (new_g + h_val,
                         id(successor), successor)
                    )
        
        return None  # 해 없음
    
    def _extract_plan(self, parent, state):
        """역추적으로 계획을 추출한다."""
        plan = []
        while parent[state][0] is not None:
            prev_state, action = parent[state]
            plan.append(action)
            state = prev_state
        plan.reverse()
        return plan

5.3 상태 등가 검사와 해시 테이블

순방향 탐색에서 폐쇄 목록(closed list)을 유지하여 중복 상태를 방지하는 것은 탐색 효율의 핵심이다. 상태 등가 검사와 해시 연산의 효율적 구현이 필요하다.

상태를 정렬된 튜플(sorted tuple) 또는 **비트 벡터(bit vector)**로 표현하면, 해시 테이블을 통한 $O(1)$ 평균 시간의 중복 검사가 가능하다. 비트 벡터 표현은 명제의 수가 기계어(machine word) 크기 이하일 때 특히 효율적이다.

$s = \sum_{i: p_i \in s} 2^i$

이 표현에서 상태의 해시는 정수 자체이며, 상태 비교는 정수 비교로 수행된다.

6. 로봇 임무 계획에서의 순방향 탐색 적용

6.1 적용 시 고려사항

로봇 임무 계획 문제에 순방향 탐색을 적용할 때 다음의 사항을 고려하여야 한다.

상태 공간의 크기 관리: 로봇 임무 도메인에서 객체의 수(로봇, 위치, 물체 등)가 증가하면 기저화된 행동(ground actions)의 수가 급격히 증가한다. $n$ 개의 객체와 $k$ 개의 매개변수를 갖는 행동 스키마에 대해 기저 행동의 수는 $O(n^k)$ 이다.

수치적 상태 변수: 배터리 잔량, 적재 중량 등의 연속적 변수를 포함하는 문제에서는 상태 공간이 무한해진다. 이를 관리하기 위해 수치 변수를 이산화(discretization)하거나, 수치 계획을 지원하는 계획기(예: Metric-FF, OPTIC)를 사용한다.

실시간 제약: 로봇 시스템은 계획을 실시간에 가까운 시간 내에 생성하여야 하는 경우가 빈번하다. 따라서 최적 해 대신 만족형 해를 빠르게 생성하는 전략(GBFS, WA*)이 선호된다.

6.2 대표적 순방향 탐색 계획기

Fast Downward (Helmert, 2006): PDDL을 SAS+ 표현으로 변환하고, 다양한 휴리스틱과 탐색 전략을 조합하여 사용할 수 있는 모듈형 계획기이다. 순방향 탐색 기반의 대표적 고성능 계획기로, 국제 계획 대회(International Planning Competition, IPC)에서 우수한 성적을 거두었다.

FF (Hoffmann, 2001): 탐욕적 최적 우선 탐색(GBFS)과 FF 휴리스틱을 결합한 계획기로, 빠른 해 생성에 특화되어 있다. 강화된 언덕 오르기(enforced hill climbing) 전략을 기본 탐색 모드로 사용한다.

LAMA (Richter & Westphal, 2010): 랜드마크 기반 비용 인식 휴리스틱과 FF 휴리스틱을 결합한 만족형 계획기이다. 점진적(anytime) 계획을 지원하여, 시간이 허용되는 만큼 계획의 품질을 점진적으로 개선한다.

6.3 순방향 탐색의 장점과 한계

순방향 탐색 기반 계획의 장점은 다음과 같다.

자연스러운 탐색 방향: 초기 상태로부터 진행하므로 실행 가능한 계획을 직접 생성한다.
완전한 상태 정보: 각 탐색 노드에서 완전히 정의된 상태를 유지하므로, 강력한 휴리스틱 계산이 가능하다.
풍부한 휴리스틱 기법: 삭제 완화, 추상화, 랜드마크 등 다양한 고성능 휴리스틱이 개발되어 있다.
확장성: 대규모 계획 문제에 대한 우수한 확장성을 보인다.

한계는 다음과 같다.

분기 인수의 폭발: 적용 가능한 행동의 수가 많으면 각 상태에서의 분기 인수가 과도하게 커진다.
상태 공간의 지수적 크기: 명제 변수의 수에 대해 상태 공간의 크기가 지수적으로 증가한다.
비관련 행동의 탐색: 목표와 무관한 행동까지 탐색하여 비효율이 발생할 수 있다.
수치적 상태의 처리 한계: 연속적 수치 변수가 포함된 문제에서는 상태 공간의 이산화가 필요하다.

7. 참고 문헌

Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.
Hoffmann, J. (2001). “FF: The Fast-Forward Planning System.” AI Magazine, 22(3), 57–62.
Richter, S., & Westphal, M. (2010). “The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks.” Journal of Artificial Intelligence Research, 39, 127–177.
Helmert, M., & Domshlak, C. (2009). “Landmarks, Critical Paths and Abstractions: What’s the Difference Anyway?” Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009), 162–169.
Bäckström, C., & Nebel, B. (1995). “Complexity Results for SAS+ Planning.” Computational Intelligence, 11(4), 625–655.
Bylander, T. (1994). “The Computational Complexity of Propositional STRIPS Planning.” Artificial Intelligence, 69(1–2), 165–204.
Bonet, B., & Geffner, H. (2001). “Planning as Heuristic Search.” Artificial Intelligence, 129(1–2), 5–33.
Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
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.

v0.2.0