계획 그래프 및 휴리스틱

계획 그래프와 도메인 독립적 휴리스틱은 도달 가능성을 간결하게 분석하고 상태에서 목표까지의 거리를 자동으로 추정함으로써 고전적 계획을 빠르게 만든 기술입니다.

Definition

계획 그래프는 도달 가능성을 근사화하기 위해 명제 및 행동 수준을 뮤텍스 제약 조건과 교차시키는 계층적 구조입니다. 계획 휴리스틱은 종종 이러한 구조나 삭제 완화 문제로부터 계산되는 함수로, 상태에서 목표에 도달하는 비용을 추정합니다.

Scope

이 주제는 Graphplan에 의해 도입된 계획 그래프 데이터 구조를 다룹니다. 여기에는 명제 및 행동 수준과 어떤 사실 및 행동이 동시에 발생할 수 없는지를 포착하는 상호 배제(mutex) 관계가 포함됩니다. 또한, 현대 휴리스틱 탐색 플래너를 구동하는 완화된 문제(특히 삭제 효과를 무시하는)에서 파생된 도메인 독립적 휴리스틱 계열도 다룹니다. 도달 가능성 정보가 어떻게 계산되고 탐색을 안내하는 데 사용되는지 설명합니다. 기본 고전적 계획 모델은 관련 주제에서 다룹니다.

Core questions

• 계획 그래프는 도달 가능한 명제와 행동을 수준별로 어떻게 표현합니까?
• 뮤텍스 관계는 무엇이며, 사실과 행동 간의 비호환성을 어떻게 포착합니까?
• 삭제 완화는 허용 가능한 또는 유익한 계획 휴리스틱을 도출하는 데 어떻게 사용됩니까?
• 이러한 휴리스틱은 계획을 효율적인 휴리스틱 탐색으로 어떻게 전환합니까?

Key concepts

• 계획 그래프
• 명제 및 행동 수준
• 상호 배제 (뮤텍스)
• Graphplan
• 삭제 완화
• h-max 및 h-add 휴리스틱
• FF 휴리스틱 및 완화된 계획
• 휴리스틱 전방 탐색

Key theories

계획 그래프 및 Graphplan

Graphplan은 각 수준에서 어떤 명제와 행동이 도달 가능하며 어떤 쌍이 상호 배타적인지를 간결하게 인코딩하는 계획 그래프를 구축한 다음, 이 구조를 통해 역방향으로 탐색하여 계획을 추출함으로써 계획 속도를 획기적으로 향상시킵니다.

삭제 완화 휴리스틱

행동의 삭제 효과를 무시하면 훨씬 쉽게 해결할 수 있는 완화된 계획 문제가 생성됩니다. 이 완화된 문제를 해결하는 비용은 전방 탐색을 안내하는 유익하고 종종 허용 가능한 휴리스틱(예: h-max, h-add 및 FF 휴리스틱)을 제공합니다.

휴리스틱 탐색 계획

최첨단 고전적 플래너는 자동으로 파생된 휴리스틱을 최선 우선 또는 탐욕적 탐색 및 선호 연산자와 같은 개선 사항과 결합하여 다양한 도메인에서 강력한 범용 성능을 달성합니다.

Clinical relevance

계획 그래프와 삭제 완화 휴리스틱은 로봇 공학, 물류 및 자율 제어에 사용되는 경쟁 우승 플래너의 핵심 기술이며, 도메인 독립적 플래너가 수작업으로 만든 탐색 지침 없이도 큰 문제를 신속하게 해결할 수 있도록 합니다.

History

Blum과 Furst의 Graphplan (1995, 저널 버전 1997)은 계획 그래프를 도입하고 계획 속도를 혁신했습니다. 1990년대 후반과 2000년대에는 삭제 완화 휴리스틱이 부상했으며, FF 플래너 (Hoffmann과 Nebel, 2001)와 이후 Fast Downward (Helmert, 2006)가 휴리스틱 전방 탐색을 지배적인 접근 방식으로 확립했습니다.

Key figures

• Avrim L. Blum
• Merrick L. Furst
• Jörg Hoffmann
• Bernhard Nebel
• Malte Helmert

Seminal works

• blum1997
• hoffmann2001

Frequently asked questions

계획 그래프에서 뮤텍스란 무엇입니까?

뮤텍스(상호 배제) 관계는 두 명제 또는 두 행동이 동일한 수준에서 동시에 유지되거나 적용될 수 없음을 나타냅니다. 예를 들어, 한 행동이 다른 행동의 전제 조건을 삭제하기 때문입니다. 뮤텍스는 계획 그래프를 실제 도달 가능성에 대한 더 엄격한 근사치로 만듭니다.

삭제 효과를 무시하는 것이 왜 유용한 휴리스틱을 제공합니까?

삭제 효과가 없으면 하나의 목표를 달성하는 것이 다른 목표를 되돌리지 않으므로 완화된 문제는 훨씬 쉽게 해결할 수 있으며 원래 문제보다 결코 어렵지 않습니다. 따라서 완화된 계획의 비용은 실제 비용의 하한 또는 정보에 입각한 추정치이므로 탐색을 안내하는 효과적인 휴리스틱이 됩니다.