전방 탐색 플래닝 알고리즘 (Forward Search Planning Algorithms)

1. 개요

전방 탐색(forward search) 플래닝은 초기 상태 s_0에서 시작하여 적용 가능한 행동을 순차적으로 확장하며 목표 상태에 도달하는 경로를 탐색하는 알고리즘이다. 현대 최고 성능 계획기(FF, Fast Downward, LAMA)의 기반 알고리즘이다.

2. 기본 알고리즘

2.1 일반 전방 탐색

function ForwardSearch(P = ⟨S, A, γ, s₀, G⟩):
    Open = {s₀}
    Closed = {}
    while Open ≠ ∅:
        s = selectAndRemove(Open)
        if G ⊆ s:
            return reconstructPlan(s)
        Closed = Closed ∪ {s}
        for each a ∈ applicableActions(s):
            s' = γ(s, a)
            if s' ∉ Closed:
                Open = Open ∪ {s'}
    return FAILURE

2.2 탐색 전략에 ��른 변형

3. 휴리스틱 전방 탐색

3.1 A* 알고리즘

f(s) = g(s) + h(s)

h(s)가 허용 가능(admissible)하면 A*는 최적 계획을 보장한다. 그러나 메모리 소모가 큰 것이 한계이다.

탐욕 최선 우선 탐색 (GBFS)

f(s) = h(s)

목표까지의 추정 비용만으로 탐색을 유도한다. 최적성은 보장되지 않으나, 빠른 해 발견에 효과적이다. FF 계획기의 기본 전략이다.

3.2 가중 A* (WA*)

f(s) = g(s) + w \cdot h(s), \quad w > 1

w에 의해 최적성과 속도의 균형을 조절한다. w = 1이면 A*, w \rightarrow \infty이면 GBFS에 근접한다.

FF 계획기의 전방 탐색

FF(Fast Forward) 계획기는 다음 전략을 사용한다.

1. GBFS: 기본 탐색 전략으로 h_{\text{FF}} 휴리스틱을 사용
2. 도움 행동(helpful actions): 휴리스틱 값을 감소시키는 행동만을 확장 후보로 선택
3. 지역 탐색 탈출: GBFS가 정체되면 BFS로 전환하여 탈출

이 전략 조합에 의해 FF는 빠른 속도와 높은 해 품질을 달성한다.

상태 저��과 중복 감지

해시 기반 중복 감지

탐색 중 이미 방문한 상태의 재방문을 방지하기 위해, 상태의 해시값을 저장한다.

비트 벡터 인코딩

명제적 상태를 비트 벡터로 인코딩하여, 상태 비교와 해싱의 효율을 높인다.

참고 문헌

• Hoffmann, J. (2001). “FF: The Fast-Forward Planning System.” AI Magazine, 22(3), 57-62.
• Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach. 4th ed. Pearson.
• Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.