SAS+를 확장한 고전 계획 표현인 팩터드 태스크(factored tasks)를 SAT 솔버로 인코딩하는 방법을 최초로 체계적으로 연구했다. 팩터드 전이 관계를 명제 논리로 변환하는 다양한 인코딩 전략을 제안하고, 다양한 수준의 병렬성 활용과 일반 태스크 변환이 SAT 기반 플래너 성능에 미치는 영향을 분석했다. 기존에는 휴리스틱 탐색 방법만 존재했던 팩터드 태스크 계획에 SAT 기반 접근의 가능성과 실효성을 탐구해 새로운 계획 패러다임을 열었다. AI 계획 연구자들에게 팩터드 태스크의 SAT 인코딩 설계를 위한 실용적 지침을 제공한다.
- •팩터드 태스크를 SAT 인코딩하는 최초의 체계적 연구로, 기존 휴리스틱 탐색만 가능했던 이 표현에 SAT 기반 계획을 도입했다.
- •팩터드 전이 관계를 명제 논리로 변환하는 다양한 인코딩 전략과 병렬성 활용 방법을 제안·비교했다.
- •태스크 변환이 SAT 기반 플래너 성능에 긍정적·부정적으로 작용하는 조건을 실험으로 분석해 실용 설계 지침을 제공한다.
Transforming and Encoding FTS for SAT Solving: What Helps, What Hurts (Extended Version)
- 1.SAS+를 확장한 Factored Task(FTS) 계획 표현을 SAT 인코딩으로 변환하는 여러 전략 제안 및 분석
- 2.전이 관계의 명제 논리 변환 방식과 병렬성 활용 수준에 따른 SAT 플래너 성능 차이 실험적 규명
- 3.태스크 변환이 SAT 기반 플래너 성능에 미치는 영향 분석, 휴리스틱 탐색 일변도를 SAT로 확장
왜 중요한가?
FTS는 조건부 효과·앤절릭 비결정성으로 압축 표현이 가능하지만 SAT 기반 접근이 없었는데, 이를 최초로 체계화해 자동 계획(Automated Planning) 연구의 솔버 선택 폭을 넓힌다.
본문 미리보기
arXiv:2605.30563v1 Announce Type: new Abstract: Factored tasks are a classical planning representation that extends SAS+ with limited forms of disjunctive preconditions, conditional effects, and angelic nondeterminism. This allows for a more compact representation of tasks than traditional formalisms such as STRIPS or SAS+, and supports a wide range of task transformations. However, existing planning approaches for factored tasks have been limited to heuristic search methods. In this work, we
전체 내용이 궁금하다면?
원문을 직접 읽어보세요