플래닝 도메인의 표현력과 복잡도 관계 (Relationship Between Domain Expressiveness and Complexity)

1. 개요

플래닝 언어의 표현력이 증가하면 더 다양한 문제를 모델링할 수 있으나, 동시에 계산 복잡도도 증가한다. 이 트레이드오프는 실용적 계획기 설계에서 표현 수준의 선택을 결정한다.

2. 표현력-복잡도 스펙트럼

표현력이 증가해도 최악 복잡도가 변하지 않는 경우(STRIPS→ADL)와, 표현력 증가가 복잡도를 본질적으로 상승시키는 경우(수치 추가)가 있다.

3. 실용적 선택 기준

필요한 표현력만큼만 사용하고, 불필요한 표현력 확장을 피하는 것이 효율적 계획 생성의 원칙이다.

4. 참고 문헌

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