작업 설명 언어

인공지능에서 액션 설명 언어(ADL)는 특히 로봇에 대한 자동화된 계획 및 스케줄링 시스템이다.그것은 스트립의 발전으로 간주된다.에드윈 페드놀트(Edwin^[1] Pednault, 1996년부터 데이터 추상화 연구 그룹의 IBM Research Steff 멤버로 재직하고 있는 데이터 추상화 및 모델링 분야의 전문가)는 1987년에 이 언어를 제안했다.그것은 행동언어의 한 예다.

오리진스

페드놀트는 STIP의 표현력이 연산자의 효과를 조건부로 허용함으로써 개선되기 쉽다고 보았다.이것은 기본적으로 페드놀트가 제안한 ADL의 명제적 파편인 ADL-A의 주요 개념으로 ADL-B는 -A의 연장선상에 있다.^[2]-B연장에서, 새로운 종류의 명제인 "정적법"의 도입에 의해 간접적인 효과로 행동을 설명할 수 있다.ADL의 세 번째 변형은 ADL-C로, -B와 유사하며, 그 명제는 정적 및 동적 법률로 분류될 수 있지만, 좀 더 특수성이 있다.^[3]

계획 언어의 감각은 환경의 특정 조건을 나타내며, 이를 바탕으로 일련의 행동들이 자동으로 생성되어 원하는 목표를 달성한다.목표는 일정 부분 명시된 조건이다.조치가 실행되기 전에 그 전제조건이 충족되어야 한다; 실행 후에 그 조치는 환경을 변화시키는 영향을 산출한다.환경은 충족되거나 충족되지 않는 특정 술어를 통해 설명된다.

스트립과는 반대로, 개방 세계의 원리는 ADL과 함께 적용된다: 조건에서 발생하지 않는 모든 것은 알 수 없다(거짓으로 간주되는 대신).또한, STIP에서는 양의 리터럴과 접속사만 허용되지만 ADL에서는 음의 리터럴과 분리도 허용된다.

ADL 구문

ADL 스키마는 작업 이름, 선택적 매개 변수 목록 및 Precond, Add, Delete 및 Update라는 4개의 선택적 절 그룹으로 구성된다.

Precond 그룹은 행동 실행의 전제조건을 정의하는 공식의 목록이다.세트가 비어 있는 경우 그룹에는 "TRUE" 값이 삽입되고 전제조건은 항상 보류 조건으로 평가된다.

Add 및 Delete 조건은 각각 Add 및 Delete 그룹에 의해 지정된다.각 그룹은 그림 1의 왼쪽 열에 표시된 형식의 절 세트로 구성된다.

1. R은 관계 기호를 나타낸다.
2. τ₁, ..., τ은_n 용어를 나타낸다.
3. ψ은 공식을 나타낸다.
4. sequence₁ z, ..., z는_k ..., ..., τ_1n 용어에 나타나는 가변 기호지만, 동작 스키마의 매개변수 목록에는 나타나지 않는다.
5. x₁, ..., x는_n 변수 z₁, ..., z와_n 다르고 τ₁, ..., τ_n, ψ, ψ 또는 동작 스키마의 매개 변수 목록에 나타나지 않는 변수 기호다.

업데이트 그룹은 기능 기호의 값을 변경하기 위한 업데이트 조건을 지정하는 데 사용된다.업데이트 그룹은 그림 2의 왼쪽 열에 표시된 양식 절 세트로 구성된다.

ADL의 의미론

ADL의 공식 의미론은 4가지 제약조건으로 정의된다.첫 번째 제약조건은 동작이 세계에 존재하는 개체 집합을 변경하지 않을 수 있다는 것이다. 즉, 모든 동작 α와 모든 전류 상태/다음 상태 쌍(s, t) ∈ a에 대해 t의 영역이 s의 영역과 같아야 하는 경우여야 한다는 것을 의미한다.

두 번째 제약조건은 ADL에서의 조치가 결정론적이어야 한다는 것이다.(s, t₁) 및 (s, t₂)가 현재 상태/다음 상태 조치 ∃인 경우, t₁ = t인₂ 경우여야 한다.

ADL에 통합된 세 번째 제약조건은 위에서 소개한 함수가 1차 공식으로 표현 가능해야 한다는 것이다.모든 n-ari 관계 기호 R에 대해 f(s)가^a_R 주어지는 자유 변수₂ x, ..., x를_n 포함하는 공식^a_R ((x₁,...,x_n)이 있어야 한다.

${\displaystyle t(R)=f_{R}^{a}(s)=(d_{1},\ldots ,d_{n})\in \operatorname {Dom} (s)^{n}\mid s[d_{1}/x_{1},\ldots ,d_{n}/x_{n}\models \Phi _{R}^{a}(x_{1},\ldots ,x_{n})]}$

따라서 F(n₁, ..., x_n) = φ^a_R(x₁, ..., x) = φ(x, ..., x_n,y)이 사전에 참이었던 경우에만 y가 참이 된다.이 표현성 요건은 첫 번째 제약조건(f의 영역은 s의 영역과 같아야 한다)에 의존한다는 점에 유의한다.

ADL에 통합된 네 번째 및 최종 제약조건은 조치가 실행 가능한 상태의 집합도 공식으로 표현 가능해야 한다는 것이다.ADL로 나타낼 수 있는 모든 작용 α에 대해, (s, t) α(즉, 작용 α가 상태 s에서 실행 가능한 어떤 상태 t가 있는 경우에만 s = π인_a 속성을 가진 공식 π이^a 존재해야 한다.

계획의 복잡성

계산 효율성의 측면에서 ADL은 STIP와 상황 미적분학 사이에 위치할 수 있다.^[4]모든 ADL 문제는 STIP 인스턴스로 변환될 수 있지만, 기존 컴파일 기술은 최악의 경우 지수적이다.^[5]우리가 다항식으로 계획의 길이를 보존할 의향이 있다면 이 최악의 경우는 개선될 수 없으며 따라서 ADL은 스트립보다 엄격히 더 짧다.^[6]

ADL 계획은 여전히 PSPACE-완전한 문제다.대부분의 알고리즘 다항식 공간은 전제조건과 효과가 복합적 공식이라 하더라도 말이다.^[7]

고전적 계획에 대한 대부분의 최고 성과 접근법은 내부적으로 STIP와 같은 표현을 사용한다.실제로 대부분의 기획자(FF, LPG, Fast-Downward, SGPLAN5 및 LAMA)는 ADL 인스턴스를 본질적으로 STIP 인스턴스(조건부 또는 정량화된 효과 또는 목표 없음)로 변환한다.

스트립과 ADL의 비교

1. STIP 언어는 주에서만 양의 리터럴을 허용하는 반면 ADL은 양의 리터럴과 음의 리터럴을 모두 지원할 수 있다.예를 들어, STIP의 유효한 문장은 Rich rich Beautiful일 수 있다.ADL에서도 ¬가빈 ∧글리와 같은 문장이 표현될 수 있었다.
2. STIP에서 언급되지 않은 리터럴은 거짓이다.이것을 폐쇄세계 가정이라고 한다.ADL에서는 언급되지 않은 문헌을 알 수 없다.이것은 오픈 월드 가정이라고 알려져 있다.
3. 스트립에서는 목표에서 지상 리터럴만을 찾을 수 있다.예를 들어, Rich ∧ Beautiful.ADL에서는 목표에서 계량화된 변수를 찾을 수 있다.예를 들어, xx At (P1, x) at At (P2, x)는 블록의 예에서 P1과 P2를 같은 위치에 두는 것을 목표로 한다.
4. STIP에서 목표는 접속사(예: (Rich beautiful Beautiful)이다.ADL에서 목표는 접속사 및 분리를 포함할 수 있다(Rich ∧ (Beautiful ∨ Smart)).
5. STIP에서 효과는 접속사지만 ADL 조건부 효과는 허용된다: P:E가 P가 만족될 때만 E가 효과라는 것을 의미할 때
6. SLIP 언어는 평등을 지원하지 않는다.ADL에서는 동등 조건자(x = y)가 내장되어 있다.
7. STIP는 타입에 대한 지원이 없지만 ADL에서는 지원된다(예: 변수 p : Person).

STIP 언어의 표현성은 언어로 설명할 수 있는 공식 집합의 변형 유형에 의해 제한된다.STIP 연산자를 사용한 공식 집합의 변환은 변환할 세트에서 일부 공식을 제거하고 새로운 공식을 추가함으로써 이루어진다.주어진 STIP 연산자의 경우 추가 및 삭제될 공식은 변환할 모든 공식 집합에 대해 고정된다.따라서 STIP 연산자는 효과가 수행되는 상황에 따라 달라지는 조치를 적절하게 모형화할 수 없다.일정 시간 동안 발사될 로켓을 생각해 보아라.궤적은 연소 기간뿐만 아니라 로켓의 속도, 질량 및 방향 때문에 달라질 수 있다.추가 및 삭제해야 하는 공식은 변환할 공식의 집합에 따라 달라지기 때문에 STIP 연산자를 통해 모델링할 수 없다.^[8]

STIP 언어를 사용할 때 효율적인 추론이 가능하지만, 일반적으로는 STIP의 표현성이 많은 실제 애플리케이션에서 작업을 모델링하는 데 적합하지 않다는 것이 인정된다.이 불충분한 점은 ADL 언어의 발전에 동기를 부여했다.^[9][10]ADL 표현력과 복잡성은 STIP 언어와 상황 미적분학 사이에 있다.그것의 표현력은 위에서 설명한 로켓의 예를 나타내기에 충분하지만, 동시에 효율적인 추론 알고리즘이 개발될 수 있을 만큼 충분히 제한적이다.

블록 월드의 더 복잡한 버전에서 예를 들면 다음과 같다.블럭 A가 블럭 B와 C의 두 배 크기일 수 있기 때문에, 작용 xMoveNoto(B,A)는 On(A,C)이 이미 사실일 경우 클리어(A)를 부정하거나 블록 크기에 따라 조건부 효과를 내는 효과만 있을 수 있다.이러한 종류의 조건부 효과는 조건부 효과 없이 STIP 표기법으로 표현하기 어려울 것이다.

예

특정 물품을 공항에서 다른 공항으로 비행기로 운송해야 하고 항공기를 적재하고 하역해야 하는 항공 화물 운송의 문제를 고려한다.

필요한 조치는 적재, 하역 및 비행일 것이다; 설명자 위로 표현될 수 있다.In(c, p)그리고At(x, A)화물 c가 비행기 p에 있는지 여부 및 물체 x가 공항 A에 있는지 여부.

이 조치는 다음과 같이 정의될 수 있다.

액션( 적재(c: 화물, p: 비행기, A: 공항) 전제 조건:에서(c, A) ^ at(p, A) 효과: ¬At(c, A) ^ in(c, p) )  액션( 언로드(c: 화물, p: 비행기, A: 공항) 전제 조건:인(c, p) ^ at(p, A)  효과:에서(c, A) ^ ^인(c, p) )  액션( 날다(p: 비행기, 출발지:공항, 도착지: 공항) 전제 조건:에서(p, from) 효과: ¬At(p, from) ^ at(p, to) ) 

참고 항목

• 액션어
• 액션선택
• 계층적 작업 네트워크
• PDDL(도메인 정의 언어) 계획

참조