자동 계획 및 스케줄링 (때로 AI 계획이라고도 함)은 일반적으로 지능형 에이전트, 자율 로봇 및 무인 차량에 의한 실행을위한 전략 또는 동작 시퀀스의 실현과 관련된 인공 지능의 한 부문입니다. 고전적인 제어 및 분류 문제와 달리 솔루션은 복잡하며 다차원 공간에서 발견되고 최적화되어야합니다. 계획은 의사 결정 이론과도 관련이 있습니다.

사용 가능한 모델이있는 알려진 환경에서 계획을 오프라인으로 수행 할 수 있습니다. 솔루션은 실행 전에 찾아서 평가할 수 있습니다. 동적으로 알려지지 않은 환경에서 전략은 종종 온라인으로 수정되어야합니다. 모델과 정책을 수정해야합니다. 일반적으로 솔루션은 인공 지능에서 흔히 볼 수있는 반복 시행 및 오류 프로세스에 의존합니다. 여기에는 동적 프로그래밍, 강화 학습 및 조합 최적화가 포함됩니다. 계획 및 일정을 설명하는 데 사용되는 언어는 대개 액션 언어라고합니다.

개요
가능한 초기 상태에 대한 설명, 원하는 목표에 대한 설명 및 가능한 조치 집합에 대한 설명이 주어지면 계획 문제는 (초기 상태에 적용될 때) 보장되는 계획을 종합하여, 원하는 목표를 포함하는 상태를 생성합니다 (이러한 상태를 목표 상태라고합니다).

계획의 어려움은 채택 된 단순화 가정에 달려있다. 문제가 여러 가지 차원에서 갖는 특성에 따라 계획 문제의 여러 클래스가 식별 될 수 있습니다.

행동이 결정적인가 비 결정적인가? 비 결정적 행동의 경우 관련 확률이 사용 가능한가?
상태 변수는 불연속 적이거나 연속적입니까? 그것들이 불연속이라면, 가능한 값의 유한 수만 있는가?
현재의 상태가 모호하지 않게 관찰 될 수 있는가? 완전한 관찰 성과 부분 관찰 가능성이있을 수 있습니다.
유한하거나 임의로 많은 초기 상태가 몇 개 있습니까?
행동에는 기간이 있습니까?
여러 작업을 동시에 수행 할 수 있습니까? 아니면 한 번에 하나의 작업 만 가능합니까?
지정된 목표 상태에 도달하거나 보상 기능을 최대화하기위한 계획의 목표입니까?
에이전트가 하나입니까? 아니면 여러 명의 에이전트가 있습니까? 대리인이 협동 적이거나 이기적입니까? 모든 상담원이 자체 계획을 별도로 구성합니까? 아니면 모든 상담원이 중앙에서 계획을 세우고 있습니까?

클래식 계획 문제로 알려진 가장 간단한 계획 문제는 다음에 의해 결정됩니다.

유일하고 고유 한 초기 상태,
무한 동작,
결정 론적 행동,
한 번에 하나씩 만 찍을 수있는
및 단일 에이전트.

초기 상태는 모호하지 않으며 모든 동작은 결정론 적이기 때문에 어떤 동작 시퀀스 이후의 세계 상태가 정확하게 예측 될 수 있으며 관찰 가능성의 문제는 고전적 계획과 관련이 없습니다.

더 나아가, 어떤 행동이 필요한지 미리 알기 때문에 계획은 일련의 행동으로 정의 될 수 있습니다.

비 결정적 활동 또는 에이전트 제어를 벗어나는 다른 이벤트의 경우 가능한 실행은 트리를 형성하고 계획은 트리의 모든 노드에 대해 적절한 조치를 결정해야합니다.

이산 시간 마르코프 결정 프로세스 (MDP)는 다음과 같은 문제를 계획하고 있습니다.

무한 동작,
확률로 비 결정적 행동,
완전한 관찰 성,
보상 기능의 최대화,
및 단일 에이전트.

전체 관측 가능성이 부분 관측 가능성으로 대체되면 계획은 부분적으로 관찰 가능한 마르코프 결정 프로세스 (POMDP)에 해당합니다.

둘 이상의 에이전트가있는 경우 게임 이론과 밀접하게 관련된 다중 에이전트 계획이 있습니다.

도메인 독립적 계획
AI 계획에서 계획자는 일반적으로 도메인 모델 (도메인을 모델링 할 수있는 일련의 가능한 동작에 대한 설명)과 초기 상태 및 목표에 의해 지정된 특정 문제를 입력합니다. 입력 도메인이 지정되었습니다. 이러한 계획자는 광범위한 영역의 계획 문제를 해결할 수 있다는 사실을 강조하기 위해 “도메인 독립적”이라고합니다. 도메인의 일반적인 예로는 블록 스태킹, 물류, 워크 플로우 관리 및 로봇 작업 계획이 있습니다. 따라서 단일 도메인 독립 플래너가 모든 다양한 도메인에서 계획 문제를 해결하는 데 사용될 수 있습니다. 다른 한편, 경로 플래너는 도메인 특정 플래너의 전형입니다.

도메인 모델링 언어 계획
STRIPS 및 고전 계획을위한 PDDL과 같은 계획 도메인 및 특정 계획 문제를 나타내는 데 가장 일반적으로 사용되는 언어는 상태 변수를 기반으로합니다. 각 가능한 상태는 상태 변수에 값을 할당하는 것이며, 조치는 해당 조치가 수행 될 때 상태 변수 값이 변경되는 f}을 판별합니다. 상태 변수들의 집합은 집합에서 지수 함수적인 크기를 갖는 상태 공간을 유도하기 때문에 계획은 다른 많은 계산 문제들과 마찬가지로 차원 성 및 조합 폭발의 저주를 겪는다.

계획 문제를 설명하는 또 다른 언어는 계층 적 작업 네트워크로, 일련의 작업이 주어지며 각 작업은 기본 동작으로 구현되거나 다른 작업 집합으로 분해 될 수 있습니다. 보다 실제적인 응용 프로그램 상태 변수가 작업 네트워크의 설명을 단순화하더라도 상태 변수가 반드시 포함되는 것은 아닙니다.

계획 알고리즘
고전적인 계획
앞으로 연결되는 상태 공간 검색 (휴리스틱과 함께 향상 될 수 있음)
(STRIPS, graphplan을 참조하십시오)
부분 주문 계획

클래식 계획
전통적인 계획은 두 가지 가정에 기초합니다 :

행동의 결정론. 예를 들어 “테이블에 큐브 놓기”작업은 결정적입니다. 실행함으로써 한 상태에서 다른 상태로 이동합니다. 반대로, “주사위 굴리기”는 가능한 값이 있기 때문에 비 결정적입니다. “주사위 굴리기”행동은 전통적인 계획의 범위에 포함되지 않습니다.
완벽한 관찰. 에이전트 (로봇, 프로그램 등)는 세계의 상태를 완전히 알고 있습니다.

n 고전적인 계획, 그것은 일련의 행동 (예를 들어, “냄비 잡기”, “물 넣기”, “파스타 채우기”, “불을 붙이기”, “도달”, ” 불”). A * 알고리즘은 고전적인 계획 알고리즘의 전형적인 예이며, 간략하게 소개 과정에 자주 사용됩니다. 다음은 클래식 플래너에서 사용되는 알고리즘 기법입니다.

상태 공간에서의 순방향 검색 : HSP (heuristic search planning) 알고리즘, FF (fast-forward 알고리즘),
상태 공간에서 다시 검색,
계획, Graphplan의 공간에서 전에 검색
계획 문제의 완화 : 초기 문제를 푸는 데 도움이되는 계획이 있는지를 쉽게 알 수있는 편안한 문제 계산
명제 논리의 공식의 만족 가능성 문제로의 변환.

Bylander는 1994 년에 기존 계획이 PSPACE 완료라고 시연했습니다.

다른 문제 감소
명제적 만족 가능성 문제 (satplan) 로의 축소.
모델 검사로 축소 – 둘 다 본질적으로 상태 공간을 가로 지르는 문제이며, 고전적인 계획 문제는 모델 검사 문제의 하위 클래스에 해당합니다.

시간 계획
시간 계획은 고전 계획과 유사한 방법으로 해결할 수 있습니다. 가장 큰 차이점은 여러 시간적으로 겹치는 동작이 동시에 진행될 가능성이 있기 때문에 상태 정의에는 현재 절대 시간에 대한 정보와 각 활성 동작의 실행이 진행된 시간이 포함되어야한다는 것입니다. 또한, 합리적 또는 실시간으로 계획 할 때, 정수 시간을 갖는 고전적 계획 또는 계획과는 달리 상태 공간은 무한 할 수 있습니다. 시간 계획은 스케줄링 문제와 밀접한 관련이 있습니다. 시간 계획은 또한 시간 자동 기능으로 이해할 수 있습니다.

확률 론적 계획
확률 적 계획은 상태 공간이 충분히 작 으면 값 반복 및 정책 반복과 같은 반복적 인 방법으로 해결할 수 있습니다. 부분적인 관측 가능성과 함께 확률 적 계획은 반복적 인 방법으로 유사하게 해결되지만 상태 대신 신념의 공간에 대해 정의 된 가치 함수의 표현을 사용합니다.

환경 설정 기반 계획
우선 순위 기반 계획에서 목표는 계획을 수립하는 것뿐만 아니라 사용자가 지정한 기본 설정을 충족시키는 것입니다. 예를 들어 MDP에 해당하는보다 일반적인 보상 기반 계획과의 차이점은 반드시 정확한 수치 값을 가질 필요는 없습니다.

조건부 계획
결정 론적 계획은 계층 적 계획자인 STRIPS 계획 시스템으로 도입되었습니다. 작업 이름은 시퀀스로 정렬되며 이는 로봇을위한 계획입니다. 계층 적 계획은 자동 생성 된 동작 트리와 비교할 수 있습니다. 단점은 정상적인 행동 트리가 컴퓨터 프로그램처럼 표현력이 약하다는 것입니다. 즉, 동작 그래프의 표기법에는 동작 명령이 포함되지만 루프 또는 if-then-statement는 포함되지 않습니다. 조건부 계획은 병목 현상을 극복하고 파스칼과 같은 다른 프로그래밍 언어에서 알려진 제어 흐름과 유사한 정교한 표기법을 도입합니다. 이것은 프로그램 합성과 매우 유사합니다. 즉, 플래너가 인터프리터에 의해 실행될 수있는 소스 코드를 생성한다는 의미입니다.

조건부 계획자의 초기 사례는 1970 년대 중반에 소개 된 “Warplan-C”입니다. 지금까지 질문은 일반적인 순서와 if-then- 진술이 포함 된 복잡한 계획 사이의 차이점에 대해서는 답변하지 않았습니다. 그것은 계획의 실행 시간에 불확실성과 관련이 있습니다. 계획은 계획자가 알 수없는 센서 신호에 반응 할 수 있다는 아이디어입니다. 플래너는 두 가지 선택을 미리 생성합니다. 예를 들어, 객체가 발견되면 동작 A가 실행되고, 객체가 없으면 동작 B가 실행됩니다. 조건부 계획의 주요 장점은 부분 계획을 처리 할 수 ​​있다는 점입니다. 상담원이 처음부터 끝까지 모든 것을 계획해야하는 것은 아니지만 문제를 청크로 나눌 수 있습니다. 이것은 상태 공간을 줄이는 데 도움이되며 훨씬 더 복잡한 문제를 해결합니다.

계획 시스템의 배치
허블 우주 망원경은 SPSS라는 단기 시스템과 Spike라고하는 장기 계획 시스템을 사용합니다.

기타 유형의 계획
실제로는 고전 계획의 가정을 거의 확인하지 않습니다. 이것이 많은 확장이 등장한 이유입니다.

준수 계획
우리는 시스템이 불확실한 상태에있는 준수 계획 (적합 일정)에 대해 이야기하지만 관찰은 불가능합니다. 에이전트는 실제 세계에 대한 믿음을가집니다. 이러한 문제는 전통적인 계획과 유사한 기술로 해결되지만 현재 상태에 대한 불확실성으로 인해 상태 공간이 문제의 크기에서 기하 급수적 인 경우 해결됩니다. 규칙을 준수하는 문제에 대한 해결책은 일련의 작업입니다.

비상 계획
센서를 통해 환경을 관찰 할 수있는 비상 계획 (조건부 계획). 오류 일 수 있습니다. 우발적 인 계획 문제의 경우 계획은 더 이상 일련의 행동이 아니라 의사 결정 트리입니다. 왜냐하면 계획의 각 단계는 고전 계획의 경우처럼 완벽하게 관찰 가능한 상태가 아닌 상태 집합으로 표시되기 때문입니다.

Rintanen은 2004 년에 분기가 추가되면 (조건부 계획) 계획 문제가 EXPTIME으로 완료되었음을 입증했습니다. 연속 계획의 특별한 경우는 FOND – “완전히 관찰 가능하고 비 결정적인”문제로 표현됩니다. 목표가 LTLf (유한 시간 추적의 선형 시간 논리)로 지정되면 LDLf의 목적 지정을 위해 항상 EXPTIME-complete 16 및 2EXPTIME-complete가됩니다.

또한 전통적인 계획 (즉, 준수 계획)에 불확실성이 추가되면 EXPSPACE-complete가됩니다. 분기와 불확실성을 모두 추가하면 (준수 및 우발적으로 계획) 2EXPTIME으로 완료됩니다.

확률 론적 계획
Kushmerick et al. 확률 론적 계획 도입. 그들의 연구에서, 행동의 효과는 확률 론자들과 함께 기술된다. 그는 “로봇이 블록을 취하는”액션의 예를 다음과 같이 설명합니다 : 로봇의 그리퍼가 건조한 경우 로봇은 확률 0.95로 블록을 유지합니다. 클램프가 젖 으면 로봇은 0.5의 확률로 블록을 고정시킵니다.

이것은 Markov Decision Process (MDP) 또는 (일반적으로) 부분 관찰 Markov Decision Process (POMDP)에 대한 정책 생성 (또는 전략)의 문제로 이어진다.

비선형 계획
기본 계획은 주어진 순서대로 하위 목표를 해결합니다. 문제는 때로는 이미 구축 된 것을 파괴하기도합니다. 이 현상을 Sussman 변종이라고합니다.

맨발이 오른발과 왼발, 오른손 양말과 왼발 양말을 신은 것과 같은 상태에 있어야한다고 가정하십시오. 그가 발언의 순서대로 목표를 달성하고자한다면 그는 실패 할 것입니다.

이러한 유형의 문제를 해결하기 위해 필요한 경우에만 작업 사이의 순서가 고정되는 부분적으로 순서가 지정된 계획으로 이동할 수 있습니다 (최신 약속 또는 최소한의 약정 계획).

앞의 예에서 양말을 왼쪽으로 놓은 후에 왼쪽 신발을 넣어야합니다. 권리와 동일합니다. 반면에, 왼쪽에 대한 계획의 실행은 오른쪽에 대한 실행과 무관합니다. 따라서 전체 계획은 부분적으로 주문됩니다.

이 카테고리의 문제를 처리 할 수있는 계획자는 부분 순서 (POP, NOAH 등)라고합니다.

계층 적 계획
일반적으로 계획을 세울 때 액션에 대한 계층 적 정보, 즉 복잡한 액션이 어떻게 분해되는지에 대한 설명을 가질 수 있습니다. 예를 들어, “커피 한 잔”과 같은 복잡한 동작은 “커피 만들기”와 “커피 가져 오기”의 두 가지 복잡한 동작 순서로 나눌 수 있습니다. 따라서 ABSTRIPS와 같은 계획가가 행동의 설명에 추가하여 행동의 계층 적 설명을 입력으로 사용합니다. 예를 들어 높은 수준에서 계획을 세우고 필요하다면 세부 사항으로 넘어갈 수 있습니다 (예를 들어 ABSTRIPS처럼). 목표는 계층 적 작업 네트워크 (HTN)를 사용하여 설명됩니다.

시간 계획
시간 계획을 사용하면 작업 시간, 조건 시작, 종료 및 종료 시간, 작업 시작 및 종료 시점의 효과를 표현할 수 있습니다. PDDL 2.1에는 시간 계획이 포함됩니다. TLP-GP1 방법은 그래프를 작성한 다음 SMT 해석기를 사용하여 시간 제한을 해결합니다. 일관성이없는 경우 하나의 백 트랙킹 린 타넨 (Rintanen)은 병행 시간 계획 (동일한 병렬 작업의 여러 인스턴스가 가능함)이 EXPSPACE-complete임을 입증했습니다. 반면에 이러한 조건을 완화하면 기존 계획으로 줄일 수 있으므로 이러한 제한 사항을 적용한 임시 계획이 PSPACE 완료됩니다.

일반 계획
일반 계획은 여러 가지 시작 환경에서 작동하는 계획을 작성하는 것으로 구성됩니다.

다중 에이전트 계획
다중 에이전트 스케줄링은 여러 에이전트 (예 : 다중 로봇)의 작업 완료를 검사합니다. 계획의 생성과 실행은 종종 분산 / 분산화됩니다. 계획의 중요한 측면은 에이전트 간의 협력입니다. MA-STRIPS라고 불리는 다중 에이전트 프레임 워크에 대한 STRIPS의 일반화에 의존하는 중앙 집중식 스케줄링 알고리즘도 있습니다. 그 알고리즘은 에이전트 사이의 조정을 관리하기 위해 배포 된 솔버 CSP를 사용하여 분산 렌더링되었습니다. 저자 Nissim, Brafman 및 Domshlak은 에이전트가 상호 작용이 거의 없을 때 알고리즘이 중앙 집중식 스케줄링보다 우수하다는 것을 실험적으로 검증했습니다.

다중 에이전트 계획의 주요 어려움은 모든 조치의 조합 폭발입니다. 에이전트 수는 기하 급수적입니다. 2011 년 Jonsson과 Rovatsos는이 문제를 해결할 수있는 솔루션을 제공하여 기존의 단일 에이전트 계획을 줄였습니다. 또한 계획 알고리즘을 확장하기 위해 새로 사용되는 병렬 처리 기술이 있습니다.

인식 론적 계획
인식 론적 계획 문제는 주와 행동에 대한 설명에서 요원의 지식을 고려하는 것이다. 일반적으로 목표는 인식 론적 모달 논리의 공식입니다. 예를 들어 “에이전트는 블록 C가 블록 A에 있음을 알고 에이전트는 논리 동적 식 인식 론적 활동의 모델로 나타납니다. 계획 문제는 모든 일반에서 결정 불가능하다.

목표 :

위 (A, B) ∧ 위 (B, C)
초기 상태 :

[위 (A, 테이블) ∧ 위 (B, 테이블) ∧ 위 (C, A) Λ 잠금 (A) Λ 잠금 (B) Λ 잠금 (C) Dis osure osure (B) Dis Dis ((C)]
가능한 조치:

이동 (b, x, y)
(b ≠ y) Λ (x ≠ y) Λ (b, x) Λ (b, x)
추가 : 위 (b, y) Λ 발견 (x)
취소 : 위 (b, x) Λ 발견 (y)
Move_tool (b, x)
사전 조건 : 위 (b, x) Λ 벌집되지 않음 (b) Λ 벌채되지 않음 (y) Λ 블록 (b) Λ (b ≠ x)
추가 : 위 (b, 테이블) Λ 발견 (x)
취소 : 위 (b, x)

예

비공식적 인 계획의 예.

목표
냉장고에 과일과 야채가 가득하다.

초기 상태
[빈 냉장고, 집에서, 슬리퍼에서]

사용 가능한 동작 (정렬되지 않은 목록)
집에 나가,
신발,
차 열쇠를 가져 가라.
차로 가게에가,
도보로 상점에 도착,
집으로 돌아 가라.
냉장고에있는 장소 구입,
가게에 들어가,
열매를 맺다,
야채,
지불 할.

가능한 해결책 (정렬 된 목록)
[1- 신발 착용, 2- 자동차 열쇠 가져 오기, 3- 집에서 나가기, 4- 차로 가게 가져 오기, 5- 매장에 가져 오기, 6- 과일 잡기, 7- 야채 가져 오기, 8- 지불, 9- 집으로 돌아가고, 냉장고에 10 개를 구입하십시오.]

또 다른 가능한 해결책 (정렬 된 목록) :
[1- 입는 신발, 2- 외출, 3- 도보로 매장에 도착, 4- 매장에 들어가기, 5- 야채 가져 오기, 6- 과일 잡기, 7- 지불, 8- 집으로 이동, 9- 장소 구매 냉장고 안에]

결론
예제에서 우리는 다음과 같은 것을 볼 수 있습니다 :

솔루션은 여러 가지 일 수 있습니다.
필연적으로, 다른 사람들 (내가 전에 열쇠를 가져 가지 않았다면 나는 차로 가게에 갈 수 없다) 이후에 수행되어야하는 현존하는 행동들이있을 수있다.
뒤집을 수있는 행동이있을 수있다. (과일과 채소를 먹는다.)
최종 계획에 여러 행동이나 상호 작용이 가능한 일련의 행동 (도보 또는 자동차로 상점에 도착)의 경우 모든 행동이 포함되어있을 필요는 없습니다.