시간 계획 및 스케줄링

시간 계획 및 스케줄링은 시간이 소요되고, 동시에 실행될 수 있으며, 제한된 자원을 소비하는 행동들을 처리하기 위해 계획을 확장하여, 무엇을 할지뿐만 아니라 언제 할지도 명시하는 계획을 생성합니다.

Definition

시간 계획은 행동들이 지속 시간을 가지며 시간적, 자원적 제약 하에 중첩될 수 있는 계획을 생성합니다. 스케줄링은 순서, 마감일, 용량과 같은 모든 제약이 충족되도록 일련의 활동에 시작 시간(및 자원)을 할당합니다.

Scope

이 주제는 명시적인 시간과 자원을 고려한 계획 및 스케줄링을 다룹니다: 지속적인 행동, 동시성 및 시간 제약, 시간 제약 네트워크(예: 단순 시간 문제) 및 Allen의 간격 대수의 표현 및 해결, 그리고 자원 제약 활동의 스케줄링과 계획의 통합. 이는 행동 선택과 함께 시간 및 자원 타당성을 어떻게 추론하는지 다룹니다. 순수한 자원 없는 고전적 계획은 관련 주제에서 다룹니다.

Core questions

• 지속 행동과 그 시작 및 종료 조건은 어떻게 표현되는가?
• 이벤트 간의 시간 제약은 어떻게 모델링되고 일관성이 확인되는가?
• 제한된 자원은 동시 활동들 사이에 어떻게 할당되는가?
• 계획(어떤 행동을 할지 결정)과 스케줄링(언제 할지 결정)은 어떻게 결합되거나 분리되는가?

Key concepts

• 지속 행동
• 동시성 및 중첩
• 시간 제약
• 단순 시간 문제
• Allen의 간격 대수
• 자원 제약
• 스케줄링
• 마감일 및 완료 시간

Key theories

시간 제약 네트워크

시간 지점 간의 정량적 시간 제약은 네트워크로 표현될 수 있으며, 단순 시간 문제의 경우 일관성 및 가장 엄격한 경계가 효율적으로 계산되어 많은 계획기 및 스케줄러의 시간 추론 백본을 제공합니다.

정성적 시간을 위한 간격 대수

Allen의 간격 대수는 시간 간격(이전, 도중, 중첩 등) 간의 가능한 정성적 관계를 포착하며, 정확한 시간을 알 수 없을 때 시간 지식에 대한 추론을 지원합니다.

계획과 스케줄링의 통합

현실적인 문제는 행동을 선택하고 동시에 시간과 자원을 할당해야 합니다. 자동화된 계획 이론은 지속 행동, 동시성 및 자원 제약을 행동 선택과 제약 기반 스케줄링을 결합하는 확장으로 다룹니다.

Clinical relevance

시간 계획 및 스케줄링은 우주선 및 로버 운영, 제조 및 프로젝트 스케줄링, 운송 및 승무원 스케줄링, 그리고 시간 제약적이고 동시적이며 자원 제약적인 활동들이 조정되어야 하는 모든 환경에서 필수적입니다. 이러한 시스템은 실제 우주 임무를 위한 계획된 운영에 사용되었습니다.

History

정성적 시간 추론은 Allen의 간격 대수(1983)에 의해 공식화되었고, 정량적 시간 제약 네트워크는 Dechter, Meiri, Pearl(1991)에 의해 공식화되었습니다. 이러한 기초는 2000년대 초 PDDL에 추가된 지속 행동 모델과 함께 자율 우주선 제어와 같은 응용 분야에 사용되는 시간 계획기를 가능하게 했습니다.

Key figures

• James F. Allen
• Rina Dechter
• Judea Pearl
• Itay Meiri
• Nicola Muscettola

Seminal works

• dechter1991
• allen1983

Frequently asked questions

계획과 스케줄링의 차이점은 무엇인가요?

계획은 목표 달성을 위해 어떤 행동을 취할지 결정하는 반면, 스케줄링은 순서 및 용량 제약을 고려하여 해당 행동이 언제 발생하고 어떤 자원을 사용할지 결정합니다. 많은 실제 문제는 둘 다 필요하며, 시간 계획은 행동 선택을 타이밍 및 자원 추론과 통합합니다.

단순 시간 문제란 무엇인가요?

단순 시간 문제는 각 제약이 두 시간 지점 간의 차이를 간격으로 제한하는 시간 제약 네트워크입니다. 그 일관성과 가장 엄격하게 암시된 경계는 효율적으로 계산될 수 있으며, 이는 계획기 및 스케줄러에서 시간 추론의 실용적인 핵심이 됩니다.