자동화된 계획 및 스케줄링

자동화된 계획 및 스케줄링(automated planning and scheduling) 또는 간단히 AI 계획(AI planning)이라고도 불리며,^[1]은 일반적으로 지능형 에이전트, 자율 로봇 및 무인 항공기가 실행할 전략 또는 행동 시퀀스의 실현과 관련된 인공지능의 한 분야이다. 고전적인 제어 시스템 및 통계적 분류 문제와 달리, 해결책은 복잡하며 다차원 공간에서 발견되고 최적화되어야 한다. 계획은 또한 결정 이론과도 관련이 있다.

사용 가능한 모델이 있는 알려진 환경에서는 계획을 오프라인으로 수행할 수 있다. 실행 전에 해결책을 찾고 평가할 수 있다. 동적으로 알려지지 않은 환경에서는 전략을 온라인으로 수정해야 하는 경우가 많다. 모델과 정책을 조정해야 한다. 해결책은 일반적으로 인공지능에서 흔히 볼 수 있는 반복적인 시행착오 과정에 의존한다. 여기에는 동적 계획법, 강화 학습 및 조합 최적화가 포함된다. 계획 및 스케줄링을 설명하는 데 사용되는 언어를 종종 행위 언어라고 부른다.

개요

 상태 공간 탐색 문서에 이 부분의 추가 정보가 있습니다.

가능한 초기 세계 상태에 대한 설명, 원하는 목표에 대한 설명, 가능한 행동 집합에 대한 설명이 주어졌을 때, 계획 문제는 (어떤 초기 상태에 적용하더라도) 원하는 목표를 포함하는 상태(이러한 상태를 목표 상태라고 한다)를 생성하는 계획을 합성하는 것이다.

계획의 난이도는 사용되는 단순화 가정에 따라 달라진다. 여러 차원에서 문제의 특성에 따라 여러 종류의 계획 문제를 식별할 수 있다.

• 행동이 결정론적인가 비결정론적인가? 비결정론적 행동의 경우 관련 확률을 사용할 수 있는가?
• 상태 변수는 이산적인가 연속적인가? 이산적이라면 가능한 값이 유한한가?
• 현재 상태를 명확하게 관찰할 수 있는가? 완전한 관찰 가능성과 부분적인 관찰 가능성이 있을 수 있다.
• 초기 상태는 몇 개인가, 유한한가 또는 임의로 많은가?
• 행동에 지속 시간이 있는가?
• 여러 행동을 동시에 수행할 수 있는가, 아니면 한 번에 하나의 행동만 가능한가?
• 계획의 목표가 지정된 목표 상태에 도달하는 것인가, 아니면 보상 함수를 최대화하는 것인가?
• 에이전트가 한 명인가 아니면 여러 명인가? 에이전트는 협력적인가 이기적인가? 모든 에이전트가 각자 자신의 계획을 구성하는가, 아니면 모든 에이전트에 대해 중앙에서 계획을 구성하는가?

가장 간단한 계획 문제인 고전적 계획 문제는 다음으로 결정된다.

• 고유하게 알려진 초기 상태,
• 지속 시간이 없는 행동,
• 결정론적 행동,
• 한 번에 하나의 행동만 수행할 수 있으며,
• 단일 에이전트.

초기 상태가 명확하게 알려져 있고 모든 행동이 결정론적이기 때문에, 어떤 행동 시퀀스 이후의 세계 상태도 정확하게 예측할 수 있으며, 관찰 가능성 문제는 고전적 계획에서는 무관하다.

또한, 계획은 행동 시퀀스로 정의될 수 있다. 왜냐하면 어떤 행동이 필요할지는 항상 미리 알려져 있기 때문이다.

비결정론적 행동이나 에이전트의 통제를 벗어난 다른 사건이 있는 경우, 가능한 실행은 트리를 형성하며, 계획은 트리의 각 노드에 대해 적절한 행동을 결정해야 한다.

이산 시간 마르코프 결정 과정(MDP)은 다음과 같은 계획 문제이다.

• 지속 시간이 없는 행동,
• 확률이 있는 비결정론적 행동,
• 완전한 관찰 가능성,
• 보상 함수 최대화,
• 단일 에이전트.

완전한 관찰 가능성이 부분적인 관찰 가능성으로 대체될 때, 계획은 부분 관측 마르코프 결정 과정(POMDP)에 해당한다.

에이전트가 둘 이상인 경우, 우리는 게임 이론과 밀접하게 관련된 다중 에이전트 계획을 다룬다.

도메인 독립 계획

AI 계획에서 플래너는 일반적으로 입력 도메인이 지정되지 않은 플래너와 달리, 도메인 모델(도메인을 모델링하는 가능한 행동 집합에 대한 설명)과 초기 상태 및 목표로 지정된 특정 문제 자체를 입력으로 받는다. 이러한 플래너는 광범위한 도메인의 계획 문제를 해결할 수 있다는 사실을 강조하기 위해 "도메인 독립"이라고 불린다. 도메인의 일반적인 예로는 블록 쌓기, 물류, 워크플로 관리 및 로봇 작업 계획이 있다. 따라서 단일 도메인 독립 플래너는 이러한 다양한 도메인의 계획 문제를 해결하는 데 사용될 수 있다. 반면에 경로 플래너는 도메인 특정 플래너의 전형적인 예이다.

계획 도메인 모델링 언어

고전적 계획을 위한 STRIPS 및 PDDL과 같이 계획 도메인 및 특정 계획 문제를 표현하는 데 가장 일반적으로 사용되는 언어는 상태 변수를 기반으로 한다. 세계의 각 가능한 상태는 상태 변수에 값을 할당한 것이며, 행동은 해당 행동이 취해질 때 상태 변수의 값이 어떻게 변하는지 결정한다. 상태 변수 집합은 집합의 크기에 따라 지수적으로 증가하는 상태 공간을 유도하기 때문에, 계획은 다른 많은 계산 문제와 마찬가지로 차원의 저주 및 조합 폭발의 영향을 받는다.

계획 문제를 설명하는 대체 언어는 계층적 작업 네트워크이다. 여기서는 작업 집합이 주어지며, 각 작업은 원시 행동으로 실현되거나 다른 작업 집합으로 분해될 수 있다. 이는 반드시 상태 변수를 포함하지는 않지만, 보다 현실적인 응용 프로그램에서는 상태 변수가 작업 네트워크 설명을 단순화한다.

계획 알고리즘

고전적 계획

• 전방 추론 상태 공간 탐색, 휴리스틱으로 강화될 수 있음
• 후방 추론 탐색, 상태 제약 사용으로 강화될 수 있음 (STRIPS, 그래프플랜 참조)
• 부분 순서 계획

 서스만 이상 문서를 참고하십시오.

행동 모델 학습

도메인 모델을 만드는 것은 어렵고 많은 시간이 걸리며 쉽게 실수를 유발할 수 있다. 이를 돕기 위해 주어진 관찰로부터 전체 또는 부분 도메인 모델을 자동으로 학습하는 여러 방법이 개발되었다. ^{[2] [3] [4]}

• 더 읽어보기: 행동 모델 학습

다른 문제로의 환원

• 명제 만족 문제(SATPLan)로의 환원.
• 모델 검증으로의 환원 - 둘 다 본질적으로 상태 공간을 탐색하는 문제이며, 고전적 계획 문제는 모델 검증 문제의 하위 클래스에 해당한다.

시간 계획

시간 계획은 고전적 계획과 유사한 방법으로 해결할 수 있다. 주요 차이점은 여러 개의 시간적으로 겹치는, 지속 시간이 있는 행동이 동시에 수행될 가능성 때문에 상태의 정의가 현재 절대 시간 및 각 활성 행동의 실행이 얼마나 진행되었는지에 대한 정보를 포함해야 한다는 것이다. 또한, 합리적 또는 실시간을 이용한 계획에서는 고전적 계획이나 정수 시간을 이용한 계획과 달리 상태 공간이 무한할 수 있다. 시간 계획은 불확실성이 포함될 때 스케줄링 (컴퓨팅) 문제와 밀접하게 관련되어 있으며, 시간 오토마타의 관점에서 이해될 수도 있다. 불확실성이 있는 단순 시간 네트워크(STNU)는 제어 가능한 행동, 불확실한 사건 및 시간 제약이 포함된 스케줄링 문제이다. 이러한 문제에 대한 동적 제어 가능성은 모든 제약이 충족되도록 불확실한 사건이 관찰될 때 제어 가능한 행동을 반응적으로 활성화하는 시간 계획 전략을 요구하는 스케줄링 유형이다.^[5]

확률적 계획

 이 부분의 본문은 마르코프 결정 과정 및 부분 관측 마르코프 결정 과정입니다.

확률적 계획은 상태 공간이 충분히 작을 때 가치 반복 및 정책 반복과 같은 반복적인 방법으로 해결할 수 있다. 부분 관찰 가능성이 있는 경우, 확률적 계획은 유사하게 반복적인 방법으로 해결되지만, 상태 대신 믿음의 공간에 대해 정의된 가치 함수의 표현을 사용한다.

선호 기반 계획

 이 부분의 본문은 선호 기반 계획입니다.

선호 기반 계획의 목표는 계획을 생성하는 것뿐만 아니라 사용자가 지정한 선호를 만족시키는 것이다. MDP에 해당하는 보상 기반 계획과의 차이점은 선호가 반드시 정확한 수치 값을 갖지는 않는다는 것이다.

조건부 계획

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

조건부 플래너의 초기 예는 1970년대 중반에 소개된 "Warplan-C"이다.^[8] 일반적인 시퀀스와 if-then문이 포함된 복잡한 계획의 차이점은 무엇일까? 이는 계획의 실행 시간의 불확실성과 관련이 있다. 아이디어는 계획이 플래너에게 알려지지 않은 센서 신호에 반응할 수 있다는 것이다. 플래너는 미리 두 가지 선택을 생성한다. 예를 들어, 개체가 감지되면 행동 A가 실행되고, 개체가 없으면 행동 B가 실행된다.^[9] 조건부 계획의 주요 장점은 부분 계획을 처리할 수 있다는 것이다.^[10] 에이전트는 모든 것을 처음부터 끝까지 계획할 필요가 없으며, 문제를 청크로 나눌 수 있다. 이는 상태 공간을 줄이고 훨씬 더 복잡한 문제를 해결하는 데 도움이 된다.

우발 계획

환경이 센서를 통해 관찰 가능하지만 센서가 오작동할 수 있는 경우를 "우발 계획"이라고 한다. 따라서 이는 계획 에이전트가 불완전한 정보 하에서 행동하는 상황이다. 우발 계획 문제의 경우, 계획은 더 이상 일련의 행동이 아니라 결정 트리이다. 왜냐하면 계획의 각 단계는 고전적 계획의 경우처럼 단일의 완벽하게 관찰 가능한 상태가 아닌 일련의 상태로 표현되기 때문이다.^[11] 선택된 행동은 시스템의 상태에 따라 달라진다. 예를 들어, 비가 오면 에이전트는 우산을 가져가기로 선택하고, 비가 오지 않으면 우산을 가져가지 않기로 선택할 수 있다.

마이클 L. 리트만(Michael L. Littman)은 1998년에 분기 행동을 사용하면 계획 문제가 EXPTIME-완전해진다는 것을 보여주었다.^[12][13] 우발 계획의 특정 사례는 FOND 문제(완전 관찰 가능 및 비결정론적)로 표현된다. 목표가 LTLf(유한 추적에 대한 선형 시간 논리)로 지정되면 문제는 항상 EXPTIME-완전하며,^[14] LDLf로 목표가 지정되면 2EXPTIME-완전이다.

순응 계획

순응 계획은 에이전트가 시스템 상태에 대해 불확실하고 어떠한 관찰도 할 수 없을 때 발생한다. 에이전트는 실제 세계에 대한 믿음을 가지고 있지만, 예를 들어 센싱 행동으로 이를 확인할 수 없다. 이러한 문제는 고전적 계획의 기술과 유사한 기술로 해결되지만,^[15][16] 현재 상태에 대한 불확실성 때문에 상태 공간이 문제 크기에 대해 지수적으로 증가한다. 순응 계획 문제에 대한 해결책은 일련의 행동이다. 해슬럼(Haslum)과 존슨(Jonsson)은 순응 계획 문제가 EXPSPACE-완전하며,^[17] 초기 상황이 불확실하고 행동 결과에 비결정성이 있을 경우 2EXPTIME-완전하다는 것을 입증했다.^[13]

계획 시스템의 배포

• 허블 우주망원경은 SPSS라는 단기 시스템과 Spike라는 장기 계획 시스템을 사용한다.

같이 보기

• 행위 기술 언어
• 행동 모델 학습
• 행위자 모델
• 인공지능의 응용
• 제약 충족 문제
• International Conference on Automated Planning and Scheduling
• 반응형 계획
• 스케줄링 (컴퓨팅)
• 전략 (게임 이론)

목록

• 제약 프로그래밍 언어 목록
• 신흥 기술 목록
• SMT 솔버 목록
• 인공지능의 개요