제약 만족 기반 플래닝 (Constraint Satisfaction-Based Planning)

1. 개요

제약 만족 기반 플래닝은 계획 문제를 제약 만족 문제(Constraint Satisfaction Problem, CSP)로 변환하여, CSP 솔버를 활용하여 계획을 탐색하는 기법이다. 각 시간 단계의 행동과 상태를 변수로, 전제 조건과 효과를 제약으로 인코딩한다.

2. CSP 인코딩

2.1 변수

• 각 시간 단계 t에서의 행동 변수 a_t \in A
• 각 시간 단계 t에서의 상태 변수 s_t^{(i)} \in D_i

2.2 제약

• 초기 상태 제약: s_0 = s_0^*
• 목표 제약: G \subseteq s_k
• 전이 제약: s_{t+1} = \gamma(s_t, a_t)
• 전제 조건 제약: \text{Pre}(a_t) \subseteq s_t

3. SAT 기반과의 비교

4. 장점

수치적 제약과 시간적 제약을 자연스럽게 표현할 수 있어, 시간적 계획과 자원 제약 계획에 적합하다.

5. 참고 문헌

• Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.