고전적 계획 수립 및 STRIPS
고전적 계획 수립은 결정론적이고, 완전하게 관찰 가능하며, 정적인 환경에서 목표에 도달하기 위한 일련의 행동을 찾는 문제를 다루며, 전제 조건과 효과에 의한 STRIPS 방식의 행동 표현을 사용합니다.
Definition
고전적 계획 수립은 완전히 알려진 초기 상태를 목표를 만족하는 상태로 변환하는 일련의 결정론적 행동을 찾습니다. 여기서 각 행동은 적용되기 위해 충족되어야 하는 조건과 그 행동이 일으키는 변화로 설명됩니다.
Scope
이 주제는 고전적 계획 수립 모델과 그 가정(결정론적 행동, 완전한 관찰 가능성, 단일 에이전트, 원자적 시간), 상태 및 행동에 대한 STRIPS 및 ADL/PDDL 표현, 전향(진행) 및 후향(회귀) 상태 공간 탐색 및 부분 순서 계획 수립의 기본 해결 방법, 그리고 명제적 계획 수립의 계산 복잡성을 다룹니다. 휴리스틱 안내 및 계획 그래프는 관련 주제에서 다루며, 비결정론적 또는 확률론적 변형은 범위 외입니다.
Core questions
- 고전적 계획 수립 모델을 정의하는 가정은 무엇이며, 언제 적절한가요?
- STRIPS 표현은 상태를 명제로, 행동을 전제 조건과 추가/삭제 효과로 어떻게 분해하나요?
- 진행 탐색과 회귀 탐색은 계획 수립 전략으로서 어떻게 다른가요?
- 일반적으로 고전적 계획 수립은 계산적으로 얼마나 어려운가요?
Key concepts
- 결정론적, 완전 관찰 가능 모델
- STRIPS 전제 조건 및 효과
- 추가 및 삭제 목록
- PDDL 및 ADL
- 진행(전향) 탐색
- 회귀(후향) 탐색
- 부분 순서 계획 수립
- 계획 존재 복잡성
Key theories
- STRIPS 표현
- STRIPS는 세상을 참인 명제들의 집합으로, 각 행동을 전제 조건 목록과 추가 및 삭제 목록으로 설명합니다. 따라서 행동을 적용하는 것은 단순히 명제를 추가하고 제거하는 것이며, 이 분해된 모델은 거의 모든 고전적 계획 수립기의 기초입니다.
- 진행 및 회귀 탐색
- 고전적 계획은 초기 상태에서 적용 가능한 행동을 적용하여 전향적으로 탐색하거나(진행), 목표에서 회귀된 하위 목표를 계산하여 후향적으로 탐색함으로써 찾을 수 있으며(회귀), 부분 순서 계획 수립은 총체적인 행동 순서에 대한 약속을 완화합니다.
- 계획 수립의 복잡성
- 명제적 STRIPS 계획의 존재 여부를 결정하는 것은 일반적으로 PSPACE-완전하며, 이는 계획 수립이 어려운 이유를 형식적으로 설명하고 이를 실용적으로 만들기 위한 휴리스틱 및 구조적 방법을 동기 부여합니다.
Clinical relevance
고전적 계획 수립 표현은 로봇 작업 계획, 자동 조립 및 물류, 그리고 결정론적 행동이 목표에 도달하기 위해 순서화되어야 하는 모든 응용 분야에서 공통적인 인터페이스입니다. PDDL 기반 고전적 계획 수립기는 이 분야와 국제 계획 수립 대회의 핵심 도구입니다.
History
STRIPS는 1971년경 SRI에서 Shakey 로봇을 제어하기 위해 개발되었으며, 고전적 계획 수립을 정의하는 전제 조건/효과 행동 모델을 도입했습니다. 부분 순서 계획 수립은 1970년대-80년대에 성숙했으며, Bylander는 1994년에 명제적 계획 수립의 PSPACE-완전성을 확립했고, PDDL 표준은 나중에 이 분야의 벤치마크를 통합했습니다.
Key figures
- Richard E. Fikes
- Nils J. Nilsson
- Tom Bylander
- Earl D. Sacerdoti
Related topics
Seminal works
- fikes1971
- bylander1994
Frequently asked questions
- 고전적 계획 수립의 가정은 무엇인가요?
- 고전적 계획 수립은 단일 에이전트가 결정론적이고, 완전하게 관찰 가능하며, 정적인 환경에서 행동하며, 행동은 단위 시간을 소요하고 초기 상태는 완전히 알려져 있다고 가정합니다. 이러한 가정 중 하나라도 완화하면, 예를 들어 불확실성이나 동시성을 허용하면, 고전적 모델을 넘어서는 더 풍부한 계획 수립 문제로 이어집니다.
- STRIPS의 추가 목록과 삭제 목록은 무엇을 의미하나요?
- STRIPS 행동이 적용될 때, 추가 목록에 있는 명제는 참이 되고 삭제 목록에 있는 명제는 거짓이 됩니다. 다른 모든 명제는 변경되지 않습니다. 이 간단한 업데이트 규칙은 STRIPS가 행동이 세상을 어떻게 변화시키는지에 대한 간결하고 계산적으로 편리한 표현이 되도록 합니다.