계획 도메인 정의 언어

Planning Domain Definition Language

계획 도메인 정의 언어(PDDL)는 인공지능(AI) 계획 언어를 표준화하려는 시도입니다.1998년 Drew McDermott와 그의 동료들에 의해 처음 개발되었으며(STRIPS와 ADL에서 영감을 받아), 주로 1998/2000 국제 계획 대회(IPC)를 가능하게 하기 위해 개발되었으며, 이후 각 대회와 함께 발전하였습니다.PDDL에 의해 제공되는 표준화는 도메인 고유의 시스템에 [1]비해 표현력을 희생하더라도 연구의 재사용성과 비교가 용이하다는 장점이 있습니다.

PDDL의 사실상의 정식 버전

PDDL 1.2

이것은 1998년과 2000년에 [2]각각 제1차 IPC와 제2차 IPC의 공식 언어였습니다.계획 문제의 모델을 (1) 도메인 설명과 (2) 관련 문제 설명의 두 가지 주요 부분으로 구분하였다.이러한 모델의 분할을 통해 (1) 문제 영역의 모든 특정 문제에 존재하는 요소(이 요소들은 도메인 설명에 포함됨)와 (2) 특정 계획 문제를 결정하는 요소(이 요소들은 문제 설명에 포함됨)를 직관적으로 분리할 수 있다.따라서 여러 문제 설명은 동일한 도메인 설명에 연결될 수 있습니다(예를 들어 OOP(Object Oriented Programming) 또는 OWL(Web Ontology Language)에 클래스의 여러 인스턴스가 존재할 수 있습니다).따라서 도메인과 연결 문제 설명은 계획 문제의 PDDL 모델을 형성하고, 이는 결국 적절한 계획 알고리즘을 통해 주어진 계획 문제를 해결하는 것을 목표로 하는 플래너(일반적으로 도메인 독립형 AI 플래너) 소프트웨어의 입력입니다.플래너의 출력은 PDDL에 의해 지정되어 있지 않지만, 일반적으로는 완전 또는 부분적으로 순서가 매겨진 플랜(일련의 액션)이며, 그 중 일부는 병렬로 실행되기도 합니다.이제 PDDL 1.2 도메인의 내용과 일반적인 문제 설명을 살펴보겠습니다.
(1) 도메인 기술은 도메인 이름의 정의, 요건의 정의(PDDL 모델이 실제로 사용하고 있는 모델 요소를 플래너에 선언하기 위한 것), 객체형 계층의 정의(OOP의 클래스 계층과 같음), 상수 객체의 정의(도메인 정의의 모든 문제에 존재하는 것),술어(논리적인 사실에 대한 설명) 및 가능한 액션의 정의(실행 중에 접지/조사되어야 하는 파라미터가 있는 schema)입니다.액션에는 파라미터(개체로 인스턴스화될 수 있는 변수), 전제조건 및 효과가 있습니다.작용의 효과는 또한 조건부일 수 있다(시기 효과).
(2) 문제의 설명은 문제명의 정의, 관련 도메인명의 정의, 가능한 모든 오브젝트의 정의(논리적인 세계), 초기 조건(계획 환경의 초기 상태, 참/거짓 사실의 결합) 및 목표 상태의 정의(논리적인 표현 이상의)로 구성되었다.r 계획 환경의 목표 상태에서 참/거짓이어야 하는 사실).따라서 최종적으로 PDDL1.2는 결정론적 단일 에이전트 이산형 완전 접근 가능 계획 환경의 "물리학"을 포착했다.

PDDL 2.1

이것은 2002년 [3]제3차 IPC의 공식 언어였다.수치적 플루엔트(예: 연료 수준, 시간, 에너지, 거리, 무게 등 비이진 자원 모델링), 계획 메트릭(목표 중심뿐만 아니라 효용 중심 계획, 즉 최적화, 메트릭 최소화/최대화), 지속적/연속적 조치(변수 가능)를 도입했다.비표준 길이, 조건 및 효과).결국 PDDL2.1은 언어의 원래 버전보다 더 많은 실제 문제를 표현하고 해결할 수 있게 되었습니다.

PDDL 2.2

이는 2004년 [4]제4차 IPC의 결정론적 트랙의 공식 언어였다.도출된 술어(예: A가 B에서 도달 가능하고 B가 C에서 도달 가능한 경우)와 시간적 초기 리터럴(계획-실행으로부터 독립적으로 발생하는 외부 사건을 모델링하기 위해)을 도입했다.결국 PDDL2.2는 몇 가지 중요한 요소로 언어를 확장했지만 PDDL1.2 이후의 PDDL2.1과 비교하면 급진적인 진화는 아니었다.

PDDL 3.0

이것은 [5][6][7]2006년 제5차 IPC의 결정론적 트랙의 공식 언어였다.그것은 상태-여행 제약 조건(모달-로직 표현 형식의 하드 제약, 주어진 계획 문제의 해결책인 계획의 실행 중에 생성된 상태-여행에 대해 참이어야 함)과 선호도(하드 제약 조건과 유사한 논리적 표현 형식의 소프트 제약 조건)를 도입했지만, 만족했다.이온은 예를 들어 만족된 선호의 수를 최대화하거나 단지 계획의 품질을 측정하여 선호 기반 계획을 가능하게 하기 위해 계획 수립에 통합될 수 있지만 필요하지 않았다.결국 PDDL3.0은 언어의 표현력을 업데이트하여 계획의 최근 중요한 발전에 대응할 수 있게 되었습니다.

PDDL 3.1

이는 2008년과 2011년 각각 [8][9][10]제6차 IPC와 제7차 IPC의 결정론적 트랙의 공식 언어였다.오브젝트 플루언트(즉, 함수의 범위는 숫자(정수 또는 실수)일 뿐만 아니라 모든 오브젝트 유형일 수도 있음)를 도입했다.따라서 PDDL3.1은 구문적으로는 작아 보이지만 의미적으로는 상당히 의미 있는 표현력의 변화로 언어를 현대적 기대에 더 많이 적응시켰다.

현황

언어의 최신 버전은 PDDL3.1입니다.PDDL 3.1의 BNF(Backus-Naur Form) 구문 정의는 IPC-2011 홈페이지 또는 IPC-2014 홈페이지의 리소스에 있습니다.

PDDL의 후계자/변수/확장자

PDDL+

2002~2006년 경부터의 PDDL2.1의 이 확장에 의해 자율 프로세스와 [1][11]이벤트를 사용한 연속적인 변경의 보다 유연한 모델이 제공됩니다.이 확장이 제공하는 열쇠는 에이전트의 동작과 에이전트 환경에 의해 시작된 변경 간의 상호 작용을 모델링하는 기능입니다.공정이 시간 경과에 따라 실행되며 숫자 값에 지속적인 영향을 미칩니다.에이전트의 직접 작업 또는 환경에서 트리거된 이벤트에 의해 시작 및 종료됩니다.이 3부분 구조를 시작-공정-중지 모델이라고 합니다.논리상태와 수치상태는 구별됩니다.논리상태 간의 이행은 순간적인 것으로 간주되며 주어진 논리상태의 점유는 시간이 지남에 따라 지속될 수 있습니다.따라서 PDDL+에서는 연속 업데이트 식이 프로세스 효과에서만 발생하도록 제한됩니다.순간적인 행동과 사건은 이산적인 변화의 표현으로 제한된다.이것은 앞에서 언급한 연속적인 변화 기간의 3부 모델링을 도입한다. (1) 작용 또는 사건은 프로세스에 의해 표현된 수치 변수에 대한 연속적인 변화 기간을 시작한다. (2) 프로세스는 수치 변수의 연속적인 변화를 실현한다. (3) 작용 또는 사건은 최종적으로 프로세스와 기간의 실행을 중단한다.숫자 변수에 대한 영향을 나타냅니다.코멘트: 액티브한 프로세스를 정지하기 전에 계획의 목표를 달성할 수 있습니다.

NDDL

NDDL(New Domain Definition Language)은 [12][13]2002년경부터 PDDL에 대한 NASA의 응답입니다.그 표현은 여러 측면에서 PDDL과 다르다. 1) 명제/1차 논리가 아닌 변수/값 표현(타임라인/활동)을 사용하고 2) 상태나 동작의 개념이 없으며, 이러한 활동 사이의 간격(활동)과 제약 조건만 있다.이 점에서 NDDL의 모델은 PDDL 모델이라기보다는 계획상의 문제를 SAT 인코딩하기 위한 스키마에 가깝습니다.전술한 차이 때문에 (예를 들어 중요한 우주 임무 중) 계획의 계획과 실행은 NDDL을 사용할 때 더 견고할 수 있지만, PDDL 이외의 표준 계획-문제 표현에 대한 대응은 PDDL의 경우보다 훨씬 덜 직관적일 수 있다.

맵

MAPL(Multi-Agent Planning Language, "메이플"로 발음)은 [14]2003년경부터 PDDL2.1의 확장판입니다.그것은 원어를 상당히 심각하게 수정한 것이다.비제안 상태 변수(n-ary: true, false, unknown 또는 기타 모든 것)가 도입됩니다.모달 연산자와 함께 주어진 시간 모델을 소개합니다(전, 후 등).그럼에도 불구하고 PDDL 3.0에서는 더 철저한 시간 모델이 제공되었으며, 이는 원래의 PDDL 구문과도 호환됩니다(그리고 이것은 단지 옵션 추가일 뿐입니다).또한 MAPL은 에이전트 간의 음성 행위 기반 통신을 통해 실현되는 런타임 및 명시적 계획 동기화에서 기간이 결정되는 액션을 도입합니다.동시 계획을 실행하는 에이전트가 멀티 에이전트 환경에서 기능하기 위해 반드시 통신할 필요는 없기 때문에 이 가정은 인위적일 수 있습니다.마지막으로 MAPL은 액션의 동시성을 처리하기 위해 이벤트(내생 및 외생)를 도입합니다.따라서 이벤트는 명시적으로 계획의 일부가 되고 제어 기능에 의해 에이전트에 할당되며, 이 역시 계획의 일부입니다.

옵트

OPT(다형 타입을 사용한 온톨로지)는 Drew McDermott가 2003-2005년 경에 PDDL2.1을 대폭 확장한 것입니다(PDDL+[15]와 일부 유사함).이는 온톨로지 작성을 위한 범용 표기법을 작성하기 위한 시도였으며, 이는 계획 애플리케이션이 추론해야 하는 도메인을 계획하기 위한 공식화된 개념 프레임워크로 정의되었습니다.그 구문은 PDDL에 기초하고 있었지만, 훨씬 더 정교한 타입 시스템을 가지고 있어 사용자가 명시적인 θ-표현식 등의 고차 구조를 사용할 수 있어 효율적인 타입 추론을 가능하게 했다(즉, 도메인 오브젝트만이 타입(레벨0 타입)을 가지고 있을 뿐만 아니라 이들 오브젝트 위에 정의된 함수/플루언트도 arbi 형식의 타입을 가지고 있었다).일반적일 수 있는 3차 매핑(레벨 1 타입), 따라서 변수(일반 매핑의 도메인 및 범위)를 변수로 정의할 수 있으며, 이는 매핑이 임의적일 수 있다는 것을 말할 수 없는 훨씬 더 높은 수준 유형(레벨 2 타입)을 가질 수 있다. 즉, 함수의 도메인 또는 범위(예: 술어, 수치적 유창)가 될 수 있다.y 레벨 0/1/2 타입.예를 들어 함수는 임의의 함수에서 임의의 함수로 매핑할 수 있습니다.OPT는 기본적으로 (거의) PDDL2.1과의 상위 호환성을 의도하고 있습니다.프로세스와 지속적 작용에 대한 표기법은 주로 PDDL+와 PDDL2.1에서 차용되었지만, OPT는 다른 많은 중요한 확장을 제공했다(예: 데이터 구조, 비불리안 플루언트, 작용에 대한 반환값, 작용 간 링크, 계층적 작용 확장, 도메인 정의 계층, 호환성에 대한 이름 공간 사용).ty와 시멘틱 웹).

PPDDL

PPDDL(확률론적 PDDL) 1.0은 2004년과 2006년에 각각 [16]4번째와 5번째 IPC의 확률론적 트랙의 공식 언어였다.그것은 확률론적 효과(행동의 가능한 효과에 대한 이산적, 일반적인 확률 분포), 보상 유발 요소(행동의 효과에서 계획의 총 보상을 증가시키거나 감소시키기 위한), 목표 보상(최소한 하나의 목표 상태를 통합한 상태-배상 보상을 위한) 및 목표 달성을 포함한 PDDL2.1을 확장했다.lunts(상태정보에 적어도1개의 목표상태가 포함되어 있는 경우)결국 이러한 변경으로 PPDDL1.0은 마르코프 의사결정 프로세스(MDP) 계획을 실현할 수 있게 되었다. 여기서 상태 전환은 불확실할 수 있지만, 설계자/에이전트는 환경을 완전히 관찰할 수 있다.

응용 프로그램

APPL(Abstract Plan Preparation Language)은 2006년부터 NDDL의 새로운 변종으로, PDDL이나 NDDL [17]등 대부분의 기존 계획 언어보다 추상적입니다.이 언어의 목표는 미래 유인 우주선의 전력 관리 또는 자동 랑데부(lendezvous)와 같은 안전 중요 애플리케이션을 위한 계획 문제의 공식 분석 및 사양을 단순화하는 것이었다.APPL은 NDDL과 동일한 개념을 사용하여 액션을 확장하고 다른 개념을 사용했지만 표현력은 여전히 PDDL보다 훨씬 낮습니다(강건하고 공식적으로 검증 가능한 상태를 유지하기를 희망함).

RDDL

RDDL(Relational Dynamic Influence Diagram Language)은 2011년 [18]제7차 IPC의 불확실성 추적 공식 언어였다.개념적으로는 PPDDL1.0과 PDDL3.0을 기반으로 하지만 실제로는 구문론적으로나 의미론적으로 전혀 다른 언어입니다.부분 관측 가능성의 도입은 PPDDL1.0에 비해 RDDL에서 가장 중요한 변화 중 하나입니다.이것은 모든 것(상태-유동성, 관측치, 작용 등)을 변수로 표현함으로써 마르코프 의사결정 프로세스(MDP)와 부분적으로 관측 가능한 마르코프 의사결정 프로세스(POMDP)를 효율적으로 기술할 수 있게 한다.이렇게 하면 RDDL은 PDDL에서 크게 출발합니다.접지 RDDL은 PPDDL1.0과 마찬가지로 Dynamic Bayesian Network(DBN; 동적 베이지안 네트워크)에 대응하지만 RDDL은 PPDDL 1.0보다 표현력이 높습니다.

MA-PDDL

MA-PDDL(Multi Agent PDDL)은 2012년에 도입된PDDL 3.1의 미니멀리즘 모듈러 확장입니다.:multi-agent여러 에이전트에 의한 및 여러 [19]에이전트에 대한 계획을 수행할 수 있습니다.이 추가 기능은 PDDL3.1의 모든 기능과 호환되며 MAPL의 대부분의 문제에 대응하고 있습니다.다른 에이전트의 다른 액션(즉, 다른 기능)을 구별할 수 있는 가능성을 추가합니다.마찬가지로 에이전트마다 목표나 측정기준이 다를 수 있습니다.현재 동작의 전제조건은 동시 동작(예를 들어 다른 에이전트의 동작)을 직접 참조할 수 있으므로 상호 작용 효과가 있는 동작은 일반적으로 유연한 방법으로 나타낼 수 있습니다(예를 들어 최소 2개의 에이전트가 필요한 경우).lift무거운 테이블을 공중으로 들어 올리지 않으면 테이블이 지면에 남습니다(이는 건설적인 시너지의 예시이지만 파괴적인 시너지는 MA-PDDL에서도 쉽게 나타날 수 있습니다).또한 통사당 종류로서 작용, 목표 및 측정기준의 유전과 다형성을 위한 간단한 메커니즘이 MA-PDDL에 도입되었다.:typing선언됩니다).PDDL3.1은 환경이 결정적이고 완전히 관찰 가능한 것으로 가정하기 때문에 MA-PDDL에 대해서도 같은 상태가 유지됩니다.즉, 모든 에이전트는 모든 시간에 유창한 모든 상태의 값에 액세스하여 각 에이전트의 이전에 실행된 모든 액션을 관찰할 수 있습니다.또한 에이전트의 동시 액션에 의해 환경의 다음 상태가 명확하게 결정됩니다.nt. 이것은 나중에 부분 관측 가능성과 확률론적 영향을 추가함으로써 개선되었다(이것도 두 가지 새로운 모듈러 요건의 형태로,:partial-observability그리고.:probabilistic-effects후자는 각각 PPDDL1.0에서 영감을 받아 다음과 같은 언어의 모든 이전 기능과 호환됩니다.:multi-agent를 참조해 주세요.[20]

예

두 그리퍼 [21]암이 있는 로봇의 자동 계획을 위한 STRIPS 인스턴스의 도메인 정의입니다. 

(정의하다(영역 그리퍼의 매개에 의한)   (: 증명서 (방 ?r) (공 ?b) (그리퍼 ?g) (강도의 ?r)                (에 ?b ?r) (공짜 ?g) (운반하다 ?o ?g))   (: 액션 움직이다    : 파라미터 (?부터 ?에게)    : 전제 조건 (그리고.(방 ?부터)                       (방 ?에게)                       (강도의 ?부터))    : 효과 (그리고.(강도의 ?에게)                 (것은 아니다.(강도의 ?부터))))   (: 액션 고르다    : 파라미터 (?obj ?룸 ?카운터)    : 전제 조건 (그리고.(공 ?obj)                       (방 ?룸)                       (그리퍼 ?카운터)                       (에 ?obj ?룸)                       (강도의 ?룸)                       (공짜 ?카운터))    : 효과 (그리고.(운반하다 ?obj ?카운터)                 (것은 아니다.(에 ?obj ?룸))                 (것은 아니다.(공짜 ?카운터))))   (: 액션 떨어지다    : 파라미터 (?obj ?룸 ?카운터)    : 전제 조건 (그리고.(공 ?obj)                       (방 ?룸)                       (그리퍼 ?카운터)                       (운반하다 ?obj ?카운터)                       (강도의 ?룸))    : 효과 (그리고.(에 ?obj ?룸)                 (공짜 ?카운터)                 (것은 아니다.(운반하다 ?obj ?카운터)))))

그리고 이것이 바로 2개의 방과 2개의 공이 있는 구체적인 환경에서 이전의 도메인 정의를 인스턴스화하는 문제 정의입니다. 

(정의하다(문제 스트립-스파이퍼2)     (: 도메인 그리퍼의 매개에 의한)     (: 개요 룸아 룸바 볼1 공2 왼쪽 맞다)     (: init(초기) (방 룸아)            (방 룸바)            (공 볼1)            (공 공2)            (그리퍼 왼쪽)            (그리퍼 맞다)            (강도의 룸아)            (공짜 왼쪽)            (공짜 맞다)            (에 볼1 룸아)            (에 공2 룸아))     (: 개요 (에 볼1 룸바)))

레퍼런스

  1. ^ a b Fox, M.; Long, D. (2002). "PDDL+: Modeling continuous time dependent effects". Proceedings of the 3rd International NASA Workshop on Planning and Scheduling for Space. CiteSeerX 10.1.1.15.5965.
  2. ^ McDermott, Drew; Ghallab, Malik; Howe, Adele; Knoblock, Craig; Ram, Ashwin; Veloso, Manuela; Weld, Daniel; Wilkins, David (1998). "PDDL---The Planning Domain Definition Language" (PDF). Technical Report CVC TR98003/DCS TR1165. New Haven, CT: Yale Center for Computational Vision and Control. CiteSeerX 10.1.1.51.9941.
  3. ^ Fox, M.; Long, D. (2003). "PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains" (PDF). Journal of Artificial Intelligence Research. 20: 61–124. doi:10.1613/jair.1129. S2CID 1397894.
  4. ^ Edelkamp, S.; Hoffmann, J. (2003). "PDDL2.2: The Language for the Classical Part of the 4th International planning Competition" (PDF). Technical Report No. 195. Institut für Informatik.
  5. ^ Gerevini, A.; Long, D. (2006). "Preferences and Soft Constraints in PDDL3" (PDF). Proceedings of the ICAPS-2006 Workshop on Preferences and Soft Constraints in Planning. pp. 46–54.
  6. ^ Gerevini, A.; Long, D. (2005). "Plan Constraints and Preferences in PDDL3" (PDF). Technical Report R. T. 2005-08-47. Dipartimento di Elettronica per l'Automazione, Università degli Studi di Brescia.
  7. ^ Gerevini, A.; Long, D. (2005). "BNF Description of PDDL3.0" (PDF). Unpublished Manuscript Linked from the IPC-5 Website.
  8. ^ Helmert, M. (2008). "Changes in PDDL 3.1". Unpublished Summary from the IPC-2008 Website.
  9. ^ Kovacs, D. L. (2011). "BNF Definition of PDDL3.1: completely corrected, without comments" (PDF). Unpublished Manuscript from the IPC-2011 Website.
  10. ^ Kovacs, D. L. (2011). "BNF Definition of PDDL3.1: partially corrected, with comments/explanations" (PDF). Unpublished Manuscript from the IPC-2011 Website.
  11. ^ Fox, M.; Long, D. (2006). "Modelling Mixed Discrete-Continuous Domains for Planning" (PDF). Journal of Artificial Intelligence Research. 27: 235–297. arXiv:1110.2200. CiteSeerX 10.1.1.75.6792. doi:10.1613/jair.2044. S2CID 5730335.
  12. ^ Frank, J.; Jonsson, A. (2002). "Constraint-based attribute and interval planning" (PDF). Technical Report. Moffett Field, CA: NASA Ames Research Center.
  13. ^ Bernardini, S.; Smith, D. E. (2007). "Developing Domain-Independent Search Control for EUROPA2" (PDF). Proceedings of the Workshop on Heuristics for Domain-independent Planning: Progress, Ideas, Limitations, Challenges. 17th International Conference on Automated Planning and Scheduling (ICAPS-2007). Rhode Island, USA.
  14. ^ Brenner, M. (2003). "A Multiagent Planning Language" (PDF). Proceedings of the Workshop on PDDL. 13th International Conference on Automated Planning and Scheduling (ICAPS-2003). Trento, Italy.
  15. ^ McDermott, D. (2005). "OPT Manual Version 1.7.3 (Reflects Opt Version 1.6.11) * DRAFT **" (PDF). Unpublished Manuscript from Drew McDermott's Website.
  16. ^ Younes, H. L. S.; Littman, M. L. (2004). "PPDDL 1.0: an extension to PDDL for expressing planning domains with probabilistic effects" (PDF). Technical Report CMU-CS-04-167. Pittsburgh: Carnegie Mellon University.
  17. ^ Butler, R.; Muñoz, C. (2006). "An Abstract Plan Preparation Language" (PDF). NASA Technical Report NASA/TM-2006-214518.
  18. ^ Sanner, S. (2010). "Relational Dynamic Influence Diagram Language (RDDL): Language Description" (PDF). Unpublished Manuscript from the IPC-2011 Website.
  19. ^ Kovacs, D. L. (2012). "A Multi-Agent Extension of PDDL3.1" (PDF). Proceedings of the 3rd Workshop on the International Planning Competition (IPC). 22nd International Conference on Automated Planning and Scheduling (ICAPS-2012). Atibaia, São Paulo, Brazil. pp. 19–27.
  20. ^ Kovacs, D. L.; Dobrowiecki, T. P. (2013). Converting MA-PDDL to extensive-form games (PDF). Acta Polytechnica Hungarica. Vol. 10, no. 8. pp. 27–47. doi:10.12700/APH.10.08.2013.8.2.
  21. ^ Veloso, Manuela. "PDDL by Example" (PDF). Carnegie Mellon University. Retrieved 2015-11-28.