時間的プランニングとスケジューリング

時間的プランニングとスケジューリングは、時間を要し、並行して実行され、限られたリソースを消費するアクションを扱うようにプランニングを拡張し、何を行うかだけでなく、いつ行うかを指定する計画を作成します。

Definition

時間的プランニングは、アクションが持続時間を持ち、時間的およびリソースの制約に従って重複する可能性のある計画を作成します。スケジューリングは、順序付け、期限、容量などのすべての制約が満たされるように、一連の活動に開始時刻（およびリソース）を割り当てます。

Scope

このトピックでは、明示的な時間とリソースを伴うプランニングとスケジューリングについて扱います。具体的には、持続的アクション、並行性および時間的制約、時間的制約ネットワーク（単純時間問題など）の表現と解決、アレンの時間間隔代数、ならびにリソース制約のある活動のスケジューリングとプランニングの統合が含まれます。時間とリソースの実現可能性が、アクション選択と並行してどのように推論されるかについて考察します。純粋なリソースフリーの古典的プランニングは、関連トピックで扱われます。

Core questions

• 持続的アクションとその開始条件および終了条件はどのように表現されますか？
• イベント間の時間的制約はどのようにモデル化され、一貫性がチェックされますか？
• 限られたリソースは並行する活動間でどのように割り当てられますか？
• プランニング（どのアクションを行うかを決定すること）とスケジューリング（いつ行うかを決定すること）はどのように組み合わされるか、または分離されますか？

Key concepts

• 持続的アクション
• 並行性と重複
• 時間的制約
• 単純時間問題
• アレンの時間間隔代数
• リソース制約
• スケジューリング
• 期限とメイクスパン

Key theories

時間制約ネットワーク

時点間の定量的時間制約はネットワークとして表現でき、その一貫性と最も厳密な境界は単純時間問題に対して効率的に計算され、多くのプランナーやスケジューラーの時間推論の基盤を提供します。

定性的時間のための時間間隔代数

アレンの時間間隔代数は、時間間隔間の可能な定性的関係（前、中、重複など）を捉え、正確な時間が不明な場合の時間的知識に関する推論をサポートします。

プランニングとスケジューリングの統合

現実的な問題では、アクションを選択し、それらに時間とリソースを割り当てることを同時に行う必要があります。自動プランニングの理論は、持続的アクション、並行性、およびリソース制約を、アクション選択と制約ベースのスケジューリングを結びつける拡張として扱います。

Clinical relevance

時間的プランニングとスケジューリングは、宇宙船や探査機の運用、製造およびプロジェクトのスケジューリング、輸送および乗務員のスケジューリング、ならびに時間指定され、並行し、リソースが限定された活動を調整する必要があるあらゆる状況において不可欠です。このようなシステムは、実際の宇宙ミッションのために計画された運用を持っています。

History

定性的時間推論はアレンの時間間隔代数（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

プランニングとスケジューリングの違いは何ですか？

プランニングは目標を達成するためにどのアクションを取るかを決定し、スケジューリングはそれらのアクションがいつ発生し、どのリソースを使用するかを、順序付けと容量の制約を考慮して決定します。多くの現実の問題では両方が必要であり、時間的プランニングはアクション選択をタイミングとリソースの推論と統合します。

単純時間問題とは何ですか？

単純時間問題は、各制約が2つの時点間の差をある時間間隔で制限する時間制約ネットワークです。その一貫性と最も厳密な暗黙の境界は効率的に計算できるため、プランナーやスケジューラーにおける時間推論の実用的な核となります。