계획 및 스케줄링 자동화

Automated planning and scheduling
시리즈의 일부
인공지능
Anatomy-1751201 1280.png
주요 목표
접근
철학
역사
테크놀로지
용어집

자동 계획 및 스케줄링(Automated Planning and Scheduling)은 때로는 단순한 AI [1]계획으로 표현되기도 하며 전략 또는 액션 시퀀스의 실현과 관련된 인공지능의 한 분야이며, 일반적으로 지능형 에이전트, 자율 로봇 및 무인 차량에 의해 실행된다.기존의 제어 및 분류 문제와 달리 솔루션은 복잡하며 다차원 공간에서 발견 및 최적화되어야 합니다.계획도 의사결정 이론과 관련이 있다.

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

개요

상세 정보:상태 공간 검색

세계의 가능한 초기 상태에 대한 설명, 원하는 목표의 설명 및 일련의 가능한 행동에 대한 설명이 주어진다면, 계획 문제는 (초기 상태 중 하나에 적용될 때) 보장된 계획을 합성하여 원하는 목표를 포함하는 상태(예를 들어 상태를 목표 상태라고 한다)를 생성하는 것이다.

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

  • 행동은 결정론적인가 비결정론적인가?비결정적 조치의 경우 관련 확률을 이용할 수 있는가?
  • 상태 변수가 이산형입니까, 연속형입니까?이산형일 경우 가능한 값의 수는 한정되어 있습니까?
  • 현재 상태를 명확하게 관찰할 수 있습니까?전체 관측 가능성과 부분 관측 가능성이 있을 수 있습니다.
  • 초기 상태는 유한 또는 임의 중 몇 가지입니까?
  • 액션에 지속시간이 있나요?
  • 여러 작업을 동시에 수행할 수 있습니까? 아니면 한 번에 한 작업만 수행할 수 있습니까?
  • 계획의 목표는 지정된 목표 상태에 도달하는 것입니까, 아니면 보상 기능을 최대화하는 것입니까?
  • 에이전트가 1개뿐입니까, 아니면 여러 에이전트가 있습니까?요원들은 협조적인가요 아니면 이기적인가요?모든 에이전트가 개별적으로 계획을 구축합니까?아니면 모든 에이전트에 대해 일원적으로 계획을 구축합니까?

가장 간단한 계획 문제(클래식 계획 문제)는 다음과 같이 결정됩니다.

  • 고유하게 알려진 초기 상태,
  • 지속시간 없는 액션,
  • 결정론적 행동,
  • 한 번에 하나씩만 먹을 수 있어요.
  • 그리고 한 명의 에이전트.

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

또한 어떤 조치가 필요할지 항상 미리 알고 있기 때문에 계획은 조치의 시퀀스로 정의할 수 있습니다.

에이전트가 제어할 수 없는 비결정적 액션 또는 기타 이벤트를 수행할 경우 가능한 실행이 트리를 형성하고 트리의 모든 노드에 대해 적절한 액션을 결정해야 합니다.

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

  • 지속시간 없는 액션,
  • 확률이 있는 비결정적 행동,
  • 완전한 관측 가능성,
  • 보상 기능의 최대화
  • 그리고 한 명의 에이전트.

완전한 관측가능성이 부분 관측가능성으로 대체되는 경우, 계획은 부분적으로 관측 가능한 마르코프 의사결정 과정(POMDP)에 해당합니다.

에이전트가 여러 개인 경우 다중 에이전트 계획이 있으며 이는 게임 이론과 밀접하게 관련되어 있습니다.

도메인에 의존하지 않는 계획

AI 계획에서 계획자는 일반적으로 입력 도메인이 지정되지 않은 것과 대조적으로 초기 상태와 목표에 의해 해결되어야 할 특정 문제뿐만 아니라 도메인 모델(도메인을 모델링하는 일련의 가능한 액션)을 입력한다.이러한 플래너를 「도메인 인디펜던트」라고 하는 것은, 다양한 도메인으로부터 플래닝 문제를 해결할 수 있는 것을 강조하기 위해서입니다.도메인의 일반적인 예로는 블록 스택, 로지스틱스, 워크플로우 관리 및 로봇 작업 계획이 있습니다.따라서 단일 도메인 독립 플래너를 사용하여 이러한 다양한 도메인의 계획 문제를 해결할 수 있습니다.한편, 루트 플래너는 도메인 고유의 플래너의 전형적인 형태입니다.

계획 도메인 모델링 언어


계획 도메인 및 특정 계획 문제(예: STRIPS 및 PDDL for Classical Planning)를 나타내기 위해 가장 일반적으로 사용되는 언어는 상태 변수를 기반으로 합니다.세계의 각 가능한 상태는 상태 변수에 대한 값 할당이며, 액션은 해당 액션이 실행될 때 상태 변수의 값이 어떻게 변화하는지 결정합니다.상태 변수 집합은 집합에서 기하급수적인 크기를 갖는 상태 공간을 유도하기 때문에, 다른 많은 계산 문제와 마찬가지로 계획도 차원성과 조합적 폭발의 저주를 겪습니다.

계획상의 문제를 기술하는 대체언어는 일련의 태스크가 주어지는 계층형 태스크 네트워크의 언어이며, 각 태스크는 원시적인 액션에 의해 실현되거나 다른 태스크의 집합으로 분해될 수 있다.보다 현실적인 응용 프로그램에서는 상태 변수가 태스크네트워크의 설명을 단순화할 수 있지만, 여기에는 반드시 상태 변수가 포함되는 것은 아닙니다.

계획 알고리즘

고전적 계획

다음 항목도 참조하십시오.서스먼 이상

다른 문제에 대한 감소

  • 명제 만족도 문제(satplan)로 감소합니다.
  • 모형 확인으로 축소 - 두 가지 모두 기본적으로 상태 공간을 횡단하는 문제이며, 고전적 계획 문제는 모형 확인 문제의 하위 클래스에 해당합니다.

시간 계획

시간적 계획은 고전적 계획과 유사한 방법으로 해결할 수 있다.주요 차이점은 여러 활동이 동시에 수행되는 시간 동안 일시적으로 중복될 수 있기 때문에 상태의 정의는 현재 절대 시간에 대한 정보와 각 활성 작업의 실행 진행 정도에 대한 정보를 포함해야 한다는 것이다.또, 합리적 또는 리얼타임에 의한 계획에서는, 종래의 계획이나 정수시간에 의한 계획과는 달리, 상태 공간은 무한해도 좋다.시간 계획은 불확실성이 수반될 때 스케줄링 문제와 밀접하게 관련되며, 시간 자동화의 측면에서도 이해될 수 있다.불확실성이 있는 단순 시간 네트워크 (STNU)는 제어 가능한 행동, 불확실한 이벤트 및 시간적 제약과 관련된 스케줄링 문제입니다.이러한 문제에 대한 동적 제어성은 모든 제약이 충족되도록 불확실한 이벤트가 관찰될 때 반응적으로 제어 가능한 행동을 활성화하기 위한 시간 계획 전략을 필요로 하는 스케줄링의 한 유형이다.[2]

확률론적 계획

주요 기사:마르코프 결정 과정과 부분적으로 관측 가능한 마르코프 결정 과정

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

선호도 기반 계획

주요 기사: 선호도 기반 계획

선호 기반 계획에서 목표는 계획 작성뿐만 아니라 사용자 지정 선호도 충족시키는 것입니다.더 일반적인 보상 기반 계획과의 차이, 예를 들어 MDP에 해당하는 선호도는 반드시 정확한 수치 값을 가질 필요는 없다.

조건부 계획

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

조건부 계획의 초기 예는 1970년대 [5]중반에 도입된 "Warplan-C"이다.if-then-statement를 포함하는 일반 순서와 복잡한 계획의 차이점은 무엇입니까?그것은 계획 실행 시 불확실성과 관련이 있다.계획은 계획자가 알지 못하는 센서 신호에 반응할 수 있습니다.플래너는 두 가지 선택지를 미리 생성합니다.예를 들어 오브젝트가 검출되면 액션 A가 실행되고 오브젝트가 누락되면 액션 B가 실행됩니다.[6]조건부 계획의 주요 장점은 부분적인 [7]계획을 처리할 수 있다는 것입니다.에이전트는 처음부터 끝까지 모든 것을 계획할 필요는 없지만 문제를 청크로 나눌 수 있습니다.이렇게 하면 상태 공간을 줄이고 훨씬 더 복잡한 문제를 해결할 수 있습니다.

우발 계획

센서를 통해 환경을 관찰할 수 있을 때 '컨셉트 플래닝'을 말하는데, 이는 결함이 있을 수 있습니다.따라서 기획 담당자는 불완전한 정보 하에서 행동하는 상황입니다.우발 계획 문제의 경우, 계획은 더 이상 일련의 행동이 아니라 의사결정 나무이다. 왜냐하면 계획의 각 단계는 고전 [8]계획의 경우와 같이 완벽하게 관측 가능한 단일 상태가 아니라 일련의 상태로 표현되기 때문이다.선택한 작업은 시스템 상태에 따라 달라집니다.예를 들어, 비가 오면 에이전트는 우산을 가져가기로 선택하고, 비가 오지 않으면 우산을 가져가지 않을 수도 있습니다.

마이클 L.리트만은 1998년에 분기 액션으로 계획 문제가 [9][10]EXPTIME-complete가 된다는 것을 보여 주었다.연속 계획의 특정 사례는 "완전 관찰 가능하고 비결정적"인 FOND 문제로 나타난다.목표가 LTLf(유한 트레이스상의 선형 시간 논리)로 지정되어 있는 경우, 문제는 항상[11] EXPTIME-complete이고, 목표가 LDLf로 지정되어 있는 경우 2EXPTIME-complete입니다.

적합 계획

적합성 계획이란 에이전트가 시스템 상태를 불확실하고 관찰할 수 없는 경우를 말합니다.그러면 에이전트는 실제 세계에 대한 믿음은 가지지만, 예를 들어 감지 행동으로는 이를 확인할 수 없습니다.이러한 문제는 고전적 [12][13]계획과 유사한 기술로 해결되지만, 현재 상태에 대한 불확실성 때문에 상태 공간이 문제의 크기에서 기하급수적인 위치에 있다.적합성 계획 문제에 대한 해결책은 일련의 조치입니다.Haslum과 Jonson은 초기 상황이 불확실할 때 적합성 계획의 문제가 EXPACE-완전이고 2EXPTIME-완전이며 [14]행동 [10]결과에 비결정론이 있음을 입증했다.

계획 시스템의 도입

「 」를 참조해 주세요.

리스트

레퍼런스

  1. ^ Ghallab, Malik; Nau, Dana S.; Traverso, Paolo (2004), Automated Planning: Theory and Practice, Morgan Kaufmann, ISBN 1-55860-856-7
  2. ^ Vidal, Thierry (January 1999). "Handling contingency in temporal constraint networks: from consistency to controllabilities". Journal of Experimental & Theoretical Artificial Intelligence. 11 (1): 23--45. doi:10.1080/095281399146607.
  3. ^ Neufeld, Xenija and Mostaghim, Sanaz and Sancho-Pradel, Dario and Brand, Sandy (2017). "Building a Planner: A Survey of Planning Systems Used in Commercial Video Games". IEEE Transactions on Games. IEEE.{{cite journal}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  4. ^ Sanelli, Valerio and Cashmore, Michael and Magazzeni, Daniele and Iocchi, Luca (2017). Short-term human robot interaction through conditional planning and execution. Proc. of International Conference on Automated Planning and Scheduling (ICAPS).{{cite conference}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  5. ^ Peot, Mark A and Smith, David E (1992). Conditional nonlinear planning (PDF). Artificial Intelligence Planning Systems. Elsevier. pp. 189–197.{{cite conference}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  6. ^ Karlsson, Lars (2001). Conditional progressive planning under uncertainty. IJCAI. pp. 431–438.
  7. ^ Liu, Daphne Hao (2008). A survey of planning in intelligent agents: from externally motivated to internally motivated systems (Technical report). Technical Report TR-2008-936, Department of Computer Science, University of Rochester.
  8. ^ Alexandre Albore; Hector Palacios; Hector Geffner (2009). A Translation-Based Approach to Contingent Planning. International Joint Conference of Artificial Intelligence (IJCAI). Pasadena, CA: AAAI.
  9. ^ Littman, Michael L. (1997). Probabilistic Propositional Planning: Representations and Complexity. Fourteenth National Conference on Artificial Intelligence. MIT Press. pp. 748–754. Retrieved 2019-02-10.
  10. ^ a b Jussi Rintanen (2004). Complexity of Planning with Partial Observability (PDF). Int. Conf. Automated Planning and Scheduling. AAAI.
  11. ^ De Giacomo, Giuseppe; Rubin, Sasha (2018). Automata-Theoretic Foundations of FOND Planning for LTLf and LDLf Goals. IJCAI. Retrieved 2018-07-17.
  12. ^ Palacios, Hector; Geffner, Hector (2009). "Compiling uncertainty away in conformant planning problems with bounded width". Journal of Artificial Intelligence Research. 35: 623–675. doi:10.1613/jair.2708.
  13. ^ Albore, Alexandre; Ramírez, Miquel; Geffner, Hector (2011). Effective heuristics and belief tracking for planning with incomplete information. Twenty-First International Conference on Automated Planning and Scheduling (ICAPS).
  14. ^ Haslum, Patrik; Jonsson, Peter (2000). "Some Results on the Complexity of Planning with Incomplete Information". Recent Advances in AI Planning. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 1809: 308–318. doi:10.1007/10720246_24. ISBN 9783540446576.

추가 정보

외부 링크