自動計画

人工知能
概念
目的
研究手法
機械学習
応用（英語版）
課題と哲学（英語版）
歴史とできごと
歴史
できごと
フィクション
法規制
組織
著作
一覧
用語集
関連項目
神経科学
カテゴリカテゴリ

自動計画（じどうけいかく、英: Automated planning and scheduling）は、人工知能のテーマの1つであり、戦略や行動順序の具体化をすること。典型的な例として、知的エージェント、自律型ロボット、無人航空機などでの利用がある。古典的制御システムや統計分類問題とは異なり、自動計画の解は複雑で未知であり、多次元空間における発見と最適化が必要となる。

概要

Automated Planning 4
Automated Planning 1
Automated Planning 2

機械であるか人間であるかに関わらず、周囲の状況が既知で、その構造がよく理解されている場合、計画や戦略というものは行動する前にあらかじめ組み立てておく(計算しておく)ことができる。一方未知の環境では、周囲の状況が明らかになるにつれて、戦略の修正を迫られる場合も多い。前者はオフラインプランニング、静的プランニングなどと呼ばれ、後者は動的プランニング、オンラインプランニングなどと呼ばれる。計画の修正のことを特にリプランニングとも呼ぶ。いずれのプランニングでも、人工知能によく見られる試行錯誤の反復過程が必要となることが多い。自動計画には、動的計画法、強化学習、組合せ最適化が含まれる。

プランナ(自動計画器)は一般に、外界の初期状態、目標とされるゴール、とりうるアクションの集合という3つの入力を必要とする。これらは STRIPS をはじめとする形式言語で記述される。STRIPSはプログラミング言語のような見た目をしているため、ある程度人間にも読め、かつ機械可読である。プランナ(自動計画器)は初期状態からゴール状態へと状態を変化させる一連のアクションの計画を生成する。例えば、右図は Blocksworld (つみ木の世界) と呼ばれる、教科書でよく使われるSTRIPS問題の例を示している。初期状態は積み木が地面に置いてある状態、ゴールは積み木がA,B,Cの順で積まれている状態である。この問題のプランは、ロボットアームが積み木を運ぶ動作に相当する。今日では、STRIPS入力形式に拡張を加えたen:PDDLが主に使われている。

プランニングの難しさは、前提の単純化（不確実性、観測可能性、並列性、時間、連続変数）をどの程度行うかに依存する。そのため、単純化のレベルによりその様々な変種が存在し、またそれに適したアルゴリズムが提案されている。単純化したモデルは現実世界をモデル化するのに必ずしも実用的であるとは限らないが、実用的な場合も存在するし、またその存在意義には、単純なモデルで発見された知見は基礎的であり、より複雑なモデルにも適用できるはずだという期待が込められている。 ただし注意したいのは、最も基礎的な古典的プランニングでさえその計算複雑性クラスがPSPACE完全であり、すでにあきれるほど難しいという事実である。 拡張を加えることは、問題が上位の複雑性クラス(例えばEXPTIME)などに繰り上がることを意味している。

古典的プランニング

古典的プランニング (Classical Planning) は、それらの前提を全て単純化した基礎的なモデルである(不確実性なし、完全情報、アクションの並列実行なし)。人工知能黎明期から存在し、よく研究されている。計算複雑性クラスはPSPACE完全に属する[1]。 STRIPSプランニングはクラスPSPACE完全に属し[2]、一般に「計算量理論に基づき難しい」と考えられているNP完全問題以上に難しいと考えられている。ただし、であってもかはまだ証明されていない。

プランニング問題を解く手法の研究は主に２つのカテゴリに大別できる。 １つ目のカテゴリは、誤解を招く名称であるが、プランニング分野における Model-based Planning である。このグループの手法は、PDDLによって表現された問題を充足可能性問題（Satplan）や整数計画問題 [3][4]に変換して解く。この種類の研究では、主に２つの問題が主眼となる。１つ目は、対象となるソルバへの変換が多項式時間で行えるか、そして２つ目は対象となるソルバが枝刈りを行いやすいようにいかに追加の冗長な制約 (SATにおける項、整数計画における不等式制約) を与えるかである。

２つ目の、より主流の探索手法は、状態空間探索である。 状態空間探索の研究にも２つのカテゴリがある。 まず１つ目のカテゴリはヒューリスティック関数の開発である。 ヒューリスティック関数は、状態空間探索における探索ノードに対する評価関数であり、探索ノードを順位づけし、分枝限定法における下界関数として振る舞い枝刈りに寄与する。 ２つ目のカテゴリは探索手法の開発である。 それぞれの探索手法は、ヒューリスティクス関数を持ちいてどのように状態空間を探索するかを決定し、これはメモリの使用量、実行時間、解の質(quality)や性質(characteristics)に影響する。 探索手法と評価関数は独立であり、おおよそ任意の探索手法と任意の枝刈り手法を組み合わせることができる。

古典的プランニングにおけるヒューリスティック関数

プランニング問題の計算複雑性は、問題に様々な仮定を入れることで下げることができることが知られている。 この事実を利用して、与えられた問題に制約を加えた簡単な問題 (緩和問題)を解くことで、元の問題を解く際の枝刈りに用いる手法が多数提案されている。 プランニングのおけるヒューリスティック関数とは、緩和によって簡単になった問題を解くことによって得られる緩和コストのことである。 近年の研究は、特定のドメインに依存しないドメイン非依存ヒューリスティックの研究に集中している。

一方で、ドメイン依存ヒューリスティックの研究も、特定の重要な応用分野においては行われている。 ドメイン依存ヒューリスティックの例としては、迷路における経路探索において、ゴールまでのユークリッド距離やマンハッタン距離をA*探索などのアルゴリズムにおいて使うことに相当する。 この場合、ユークリッド距離は「壁の存在しない迷路」という緩和問題の解コストと捉えることができる。

注意したいのが、ここにおける「ヒューリスティック」と、焼きなまし法や遺伝的アルゴリズムなどの文脈における「ヒューリスティック手法」という言葉における「ヒューリスティック」とでは 意味合いが異なるという点である。後者では解の収束性や実用的に得られる解の最適性などの理論的保証に問題があり、「実応用ではおおよそ動くヒューリスティック(勘)」という意味合いがあるのに対して、 プランニングにおけるヒューリスティックはあくまで「アルゴリズムにとって人間の勘に相当するもの」という意味合いであり、 また実際に分枝限定法の下界関数として振る舞うため解の最適性が証明されている。

以下には、特に古典的プランニングの代表的なドメイン非依存ヒューリスティックについて述べる。

  • 削除効果緩和: 現在最も主要な緩和手法である。削除効果を持たないプランニング問題を最小ステップで解く最適解を得る問題は、NP完全である[5]。この事実は、Landmark-Cut [6], Operator Counting [7] など近年の枝刈り手法の基礎となっている。これらの手法では、緩和によってNP完全になった問題をさらに緩和してPに落とすことにより、計算量と緩和の質をバランスさせている。
  • ランドマーク: ある問題において、すべてのプランにおいて必ず現れるアクション/命題のことをランドマークと呼ぶ。このグループのヒューリスティックは、削除効果緩和を施した上で、さらに探索空間をランドマークに絞って探索することで多項式時間に落とす。
  • コスト分割 (Cost partitioning): ある問題Pのすべてのアクションにおいて、アクションのコストcをc=c_1+c_2 と分割し、分割されたコストをコストにもつ２つの問題P1,P2に複製することを考える。このとき、P1の最小解コストとP2の最小解コストの和はPの最小解コストの下界となる。このことを利用して、適切にコスト分割を施せば、それぞれの小さな問題を解くことでより高速に下界を得ることができる。
  • Abstraction : PDB, Merge-and-Shrink, Bisumlation Merge-and-Shrink

古典的プランニングにおける探索手法

現在最も多数派の探索手法は前方探索(Forward search)である。 このカテゴリの基礎的なものとしては、A*(ダイクストラ法+ヒューリスティック関数)、反復深化A*(反復深化深さ優先探索+ヒューリスティック関数)、貪欲最良優先探索(Greedy Best First Search)などがある。

後方探索は、ゴールから逆にたどってどのようにすれば初期状態にたどり着けるかを探索する[8]。 後方探索には前方探索にない固有の技術的困難があり、近年では研究が停滞している。

ここ近年活発に研究され始めたものが双方向探索である。双方向探索は70年台に研究されていたが、探索の効率性を担保する理論的発展が得られず研究が衰退していた。 2016年のMMアルゴリズム[9]の発見によって前方探索と後方探索のフロンティアが探索深さの中心点で出会う保証がなされ、 近年再び活発に研究が行われている[10]。

またもや誤解を招く名称であるが、プランニング分野における Symbolic Planning (PDDLプランニングの分野全体が記号的AIに含まれるにもかかわらず) とは、二分決定図 / Binary Decision Diagram によって、多数の探索ノードを圧縮表現として保持、かつ圧縮されたまま操作する探索手法である。これは前方/後方探索のどちらにも対応しており、国際コンペティション IPC 2014 にてSymBA*プランナーが優勝している[11]。

近年の新たな方向性としては、Top-K プランニング[12]および多様性プランニング(Diverse Planning)がある。 これは、実応用では複数の「次善の策」を用意しておくことが求められること、および(人間による間違ったモデリングにより)プランナの返却した最適解が現実の問題の最適解になっていないことを考慮して、 複数の、質的に異なるプランを返却する。

ヒューリスティック関数とも探索手法とも直行した探索改善手法

2008年の "How Good is Almost Perfect?." (AAAI08 Best Paper) [13] という論文によって、 ヒューリスティック関数をどれだけ改善しても、完璧なヒューリスティック(緩和を行わない=計算するのにもとの問題を解くのと同じだけの計算量がかかるので非実用的)を得ない限り究極的には指数爆発が避けられないケースがあることが示された。 以来、上記２つとは独立した探索手法の改善、ないし枝刈り手法が求められている。

このうち代表的な手法に、対称性検知(symmetry breaking)、行き止まり検知(dead-end detection)、Dominance Pruning、Partial Order Pruningなどがある。 対称性検知は、探索グラフのうちisomorphicな部分グラフを検知して、その一つを残してすべて枝刈りする[14]。 行き止まり検知は、現在のノードからはゴールにたどり着けないことを、実際にゴールを探索し尽くすことなく検知する[15]。 Dominance Pruningは、「あるノードが別のノードよりも悪い」ことを、ヒューリスティクス関数/下界関数による分枝限定法とは別の仕組みで検知する[16]。 Partial Order Pruningは、順序を入れ替えただけのアクションの列のうち、一つを残して枝刈りする[17]。

不完全情報に基づくプランニング

不完全情報を取り入れたプランニングは、「センサなしでも確実に実行できるプランを生成する」Conformant Planning,「センサによる観測アクションを含めた実行プランを生成する」Contingent Planning に分類される。

不確実性のある環境でのプランニング

アクションの実行結果に不確実性を取り入れたプランニングは 非決定的プランニング(Nondeterministic Planning) と呼ばれる。 非決定的プランニングのもとでは、一つのアクションの結果として複数の実行結果がありえ、どの状態に遷移するかがわからない。 古典プランニングの解がアクションの列であるプランを返すのに対し、非決定的プランニングの解はアクションのDAGであるポリシーである。 これは、非決定性の影響でアクションの実行結果が枝分かれするからである。 非決定的プランニングの探索グラフは、アクションの非決定性を表現できるAND-OR木である。

非決定的プランニングのうち、それぞれの結果について遷移確率があたえられる場合を 確率的プランニング(Probabilistic Planning) と呼ぶ。 確率的プランニングはマルコフ決定過程 (MDP) として定式化される。また、不完全情報での確率的プランニングは部分観測マルコフ決定過程 (POMDP) によってモデル化される。

非決定/確率的プランニング問題を表現するモデル言語として、PDDLの拡張言語、Probabilistic PDDL (PPDDL) が2004年に提唱され[18]、コンペティションおよび実応用で用いられている。

非決定プランニングでの探索手法

非決定的プランニングに対する古典的な探索アルゴリズムの代表的なものに、Value IterationおよびAO*アルゴリズム[19]がある。 Value Iterationはヒューリスティクスを用いない知識なし探索であるため、ダイクストラ法の非決定的プランニングへの拡張と捉えることができる。 この理解のもとでは、AO*はValue Iterationにヒューリスティクスを足した知識有り探索版であり、またA*を非決定的プランニングに拡張したものとも捉えられる。 ダイクストラやA*と同様、AO*は、許容的ヒューリスティック関数(厳密な下界関数)を用いれば最適ポリシーを発見できる。 これらのアルゴリズムは確率的プランニングにも同様に適用できる。

非決定的プランニングのうち、解ポリシーにループを含む必要がある場合(すなわち、ポリシーが非DAGとなる場合)AO*は適切な解を生成しない。この点を改善したのがLAO*である[20]。

非決定的環境に対する確率的探索アルゴリズムの代表的なものとして、モンテカルロ木探索(MCTS)がある。 確率的アルゴリズムであること(アルゴリズムが乱択に基づくこと)と、環境の振る舞い(アクション)が確率的であることは別の概念であることに注意したい。 確率的アルゴリズムであるMCTSは、時間を無限大にとる極限では最適解に収束するが、実時間ではこれは保証されない。

非決定プランニングでのヒューリスティック関数

非決定的プランニング問題への強力なヒューリスティクス関数として、決定化(Determination)がある[21]。 これは、現在ノードからゴールまでのコストの下界を、問題が決定的であると仮定して解くことにより得る手法である。 この手法は驚くほどシンプルであるが、国際コンペティション IPC 2004 確率的プランニング部門で優勝し、その後活発に研究された[22]。 決定化にも複数の種類が有り、「成功」と「失敗」と言ったように片方がもう一方をdominateする場合には「成功」だけを採択して決定化する手法[23]や、 すべての非決定的実行結果を別のノードとして扱うことによる決定化、 あるいは(確率的プランニングで最適性が求められない場合)もっとも確からしい結果のみを用いる決定化などが存在する。

近年、ポリシーを実数値関数としてニューラルネットワークにより近似し、これを強化学習によって訓練する手法が活発に研究されている。 これらの手法によって得られたポリシー関数・Q関数は、プランニングにおけるヒューリスティック関数を同様、実行時に探索を誘導する役目を持っている。 しかし、これらの学習された関数とプランニングにおけるヒューリスティック関数には大きな違いがある。

  1. 学習された関数は特定の問題ドメインに特化した関数である。例えば、特定のゲームのために訓練されたポリシー関数は、別のゲームにおいては使うことが出来ない。
  2. メタ強化学習を仮定するとしても、あくまでも訓練ゲームと似たドメインにおいて内挿を行うことが暗黙の前提となっている。
  3. プランニングにおけるヒューリスティック関数は訓練を必要としない。新たに与えられた問題を、問題を解く時間の中で分析し、自動で探索の誘導を行う。言い換えれば、初めて見た問題を観察し、その場で学習を行うと言うこともできる。
  4. プランニングにおけるヒューリスティック関数は問題の解コストの下界関数である。有限時間で学習が停止されたポリシー関数にそのような性質はない。これは、時間を無限にとった極限で正しいポリシー関数に収束することとは別の性質である。

連続変数を許すプランニング

実数/連続変数を許すプランニングは Numeric Planning と呼ばれ、卑近な例ではピタゴラスイッチのような(重さ、角度などを考慮に入れた)問題を解けることを目指す。 実数に対する操作をSTRIPS/PDDL言語に導入する拡張は、PDDL2.1として2003年に導入された[24]。 また、実数に微分方程式によって連続的に変化させる拡張は、PDDL+として2006年に提案された[25]。 主なアプローチとしては、SMTソルバを用いて制約充足問題として解く手法と、 不等式制約によって定義された区間への帰属を離散変数とし、古典プランニングアルゴリズムを適用する手法などがある。 特に近年では、ランドマークの概念を連続変数に適用したNumeric Landmarkが研究されている[26]。

連続空間を対象にするプランニングは Motion Planning とも呼ばれ、ロボットアームの動作や、建物内を移動するロボットの経路探索に応用される。 Motion PlanningとNumeric Plannningは、ともにプランニングであることから用いられる要素技術には共通点も多いが、 Motion Planning は主に衝突検知、可動域の制限など、ロボットという主要アプリケーションのための幾何学的な制約に特化しており、異なるアルゴリズムが用いられる。 代表的なものに、RRT [27]、 PRM [28] などがある。

一方、RRTアルゴリズムなどの連続空間経路探索の知見を古典プランニングに逆輸入しようとする試みも見られる[29]。

並列性を許すプランニング

同時並行に複数のアクションを実行できるプランニング問題は スケジューリング問題、ないしTemporal Planning問題とも呼ばれる。オペレーションリサーチではスケジューリング問題がよく研究されているが、それらがある特定の決められた問題ドメイン (例:特定の種類の組み立て問題や特定の種類の配送問題など) を解くことを目標としているのに比べて、AIおよび自動プランニング・スケジューリングでの目標は、与えられるまで未知の問題ドメインを解くことが出来る汎用問題解決機を実現することである。

連続変数の場合と同様、 ランドマークの概念をこの問題に拡張したTemporal Landmarkが研究されている[30]。

階層的なアクション定義を許すプランニング

計画問題を記述する他の言語としては階層型タスクネットワーク (HTN) があり、タスクを階層的に細分化することで一連の基本的アクションの計画を生成する。 HTNプランニングから階層を除いたものはSTRIPSプランニングに帰着する。 HTNプランニングにも複数のバリエーションが有り、その計算複雑性はPSPACE完全、EXPTIME、DEXPTIME、決定不能などに分かれる[31]。 HTNはSTRIPSよりも高い表現性を持ち、STRIPSよりもさらに通常のプログラミング言語に似ている。 実際、HTNはCommon Lispプログラミング言語のまるで一部であるかのように見え、実際にSmart Information Flow Technologies (SIFT)で用いられているオープンソースHTNソルバSHOP3はCommon Lispによって書かれている。 SIFTの主な顧客に代表されるように、HTNは多くの実用アプリケーション、特に宇宙分野や軍事用途に用いられている。

永らく実応用に用いられてきたため、理論的な定式化は共通しているにもかかわらず異なる入力フォーマットをとるソルバが複数存在していた。 この状況を改善するため、2019年、複数のソルバ作成者グループの共同研究により HDDL (Hierarchical Domain Description Language) が作成され[32]、 正式な国際コンペティションが開催された[33]。 この入力フォーマットはPDDLの拡張言語になっているため、既存のパーサに対する追加の労力は最小限に抑えられる。

HTNプランニングでのヒューリスティック関数

HTNプランニングをSTRIPSプランニング問題に直接変換することは可能だが、その際には問題サイズが指数的に大きくなってしまい、非実用的である。 ただし、HTNプランニングのうち末尾再帰的(Tail-Recursive)な問題は、多項式時間でSTRIPSに変換することができる[34]。 実応用に使われるHTNプランニング問題の多くは、全体が末尾再帰的ではないにしろ、一部に末尾再帰的な要素が含まれているため、 この問題を末尾再帰的に緩和した問題はもとの問題のよい下界を返すことが期待される。 これに基づいて、HTNプランニングのヒューリスティクス関数として、HTNプランニングをSTRIPSに緩和して解く手法がある(Hierarchy Relaxation)[35]。 緩和の結果得られたSTRIPS問題は、既存のSTRIPSソルバによって解かれる(これはさらに削除効果緩和やランドマークによる多項式時間緩和問題を解くことで探索する)。

オンラインプランニング

自律飛行ドローンなど、状態や時間発展の不確実性、外乱などの様々な理由により、プランの作成と実行を交互に繰り返しながら適切に自律行動をすることが求められる実用分野がある。 このような実用アプリケーションでは、時間という資源を適切に使うことが求められる。 たとえば、時間をプランニングに費やしすぎれば反応時間が遅れてドローンは墜落してしまうし、 一方短期的なプランばかりを生成してすぐさま実行に移していると、いつのまにか渓谷など安全には脱出不可能な状況に陥ってしまう可能性がある。 オンラインプランニングのアルゴリズムで代表的なものはSMA*などがあるが、 近年の研究では、環境のモデルから Safe state を自動的に検出し、これを用いて脱出不可能な状況を避ける手法が提案されている。 [36]

マルチエージェントプランニング

無線ネットワークでつながった多数のロボットを用いた倉庫管理など、複数の分散エージェントを用いたプランニング問題を考える。 この問題をSTRIPSプランニングとして定式化すると、STRIPSが完全情報問題を前提としているため、問題の計算量がエージェントの数に従って指数爆発する。 この問題を解決するために提案されたのが、 MA-STRIPS [37] 言語を用いるマルチエージェントプランニング問題である。 マルチエージェントプランニング問題は、すべてのアクションがエージェント引数を持ち、エージェント間での情報交換が制限される。 このクラスの問題の計算複雑性や、問題を解く様々なアルゴリズムが提案されている。 実応用上の要求から特に経路探索問題が重点的に研究されており、この場合には MAPF (Multi-Agent Path Finding) と呼ばれる。

現実世界での応用例

ハッブル宇宙望遠鏡では、短期計画システム「SPSS」[38]と長期計画システム「Spike」[39]が使われている。

出典

  1. ^ Bylander, Tom. "The computational complexity of propositional STRIPS planning." Artificial Intelligence 69.1-2 (1994): 165-204.
  2. ^ Bylander, Tom. "The computational complexity of propositional STRIPS planning." Artificial Intelligence 69.1 (1994): 165-204.
  3. ^ Van Den Briel, Menkes HL, and Subbarao Kambhampati. "Optiplan: Unifying IP-based and graph-based planning." Journal of Artificial Intelligence Research 24 (2005): 919-931.
  4. ^ Imai, Tatsuya, and Alex Fukunaga. "A Practical, Integer-Linear Programming Model for the Delete-Relaxation in Cost-Optimal Planning." ECAI. 2014.
  5. ^ Bylander et al.
  6. ^ Helmert, Malte, and Carmel Domshlak. "Landmarks, critical paths and abstractions: what's the difference anyway?." ICAPS. 2009.
  7. ^ Davies, Toby O., et al. "Sequencing Operator Counts." ICAPS. 2015.
  8. ^ Alcázar, Vidal, et al. "Revisiting regression in planning." Twenty-Third International Joint Conference on Artificial Intelligence. 2013.
  9. ^ Holte, Robert C., et al. "Bidirectional Search That Is Guaranteed to Meet in the Middle." AAAI. 2016.
  10. ^ Alcázar, Vidal, Patricia J. Riddle, and Mike Barley. "A Unifying View on Individual Bounds and Heuristic Inaccuracies in Bidirectional Search." AAAI. 2020.
  11. ^ Torralba, A., Alcázar, V., Borrajo, D., Kissmann, P., & Edelkamp, S. (2014). SymBA*: A symbolic bidirectional A* planner. In International Planning Competition (pp. 105-108).
  12. ^ Riabov, Anton, Shirin Sohrabi, and Octavian Udrea. "New algorithms for the top-k planning problem." Proceedings of the Scheduling and Planning Applications woRKshop (SPARK) at the 24th International Conference on Automated Planning and Scheduling (ICAPS). 2014.
  13. ^ Helmert, Malte, and Gabriele Röger. "How Good is Almost Perfect?." AAAI. Vol. 8. 2008.
  14. ^ Domshlak, Carmel, Michael Katz, and Alexander Shleyfman. "Enhanced symmetry breaking in cost-optimal planning as forward search." Twenty-Second International Conference on Automated Planning and Scheduling. 2012.
  15. ^ Lipovetzky, Nir, Christian J. Muise, and Hector Geffner. "Traps, Invariants, and Dead-Ends." ICAPS. 2016.
  16. ^ Torralba, Alvaro, et al. "On State-Dominance Criteria in Fork-Decoupled Search." IJCAI. 2016.
  17. ^ Hall, David Leo Wright, et al. "Faster Optimal Planning with Partial-Order Pruning." ICAPS. 2013.
  18. ^ Younes, Håkan LS, and Michael L. Littman. "PPDDL1. 0: An extension to PDDL for expressing planning domains with probabilistic effects." Techn. Rep. CMU-CS-04-162 2 (2004): 99.
  19. ^ N.J. Nilsson, Principles of Artificial Intelligence, Tioga Publishing, Palo Alto, CA, 1980.
  20. ^ Hansen, Eric A., and Shlomo Zilberstein. "LAO∗: A heuristic search algorithm that finds solutions with loops." Artificial Intelligence 129.1-2 (2001): 35-62.
  21. ^ Yoon, Sung Wook, et al. "Probabilistic Planning via Determinization in Hindsight." AAAI. 2008.
  22. ^ Yoon, Sung Wook, Alan Fern, and Robert Givan. "FF-Replan: A Baseline for Probabilistic Planning." ICAPS. Vol. 7. 2007.
  23. ^ Botea, Adi, Evdokia Nikolova, and Michele Berlingerio. "Multi-modal journey planning in the presence of uncertainty." Twenty-third international conference on automated planning and scheduling. 2013.
  24. ^ Fox, Maria, and Derek Long. "PDDL2. 1: An extension to PDDL for expressing temporal planning domains." Journal of artificial intelligence research 20 (2003): 61-124.
  25. ^ Fox, Maria, and Derek Long. "Modelling mixed discrete-continuous domains for planning." Journal of Artificial Intelligence Research 27 (2006): 235-297.
  26. ^ Piacentini, Chiara, et al. "Linear and Integer Programming-Based Heuristics for Cost-Optimal Numeric Planning." AAAI. 2018.
  27. ^ Karaman, Sertac, and Emilio Frazzoli. "Sampling-based algorithms for optimal motion planning." The international journal of robotics research 30.7 (2011): 846-894.
  28. ^ Kavraki, Lydia E., et al. "Probabilistic roadmaps for path planning in high-dimensional configuration spaces." IEEE transactions on Robotics and Automation 12.4 (1996): 566-580.
  29. ^ Burfoot, Daniel, Joelle Pineau, and Gregory Dudek. "RRT-Plan: A Randomized Algorithm for STRIPS Planning." ICAPS. 2006.
  30. ^ Karpas, Erez, et al. "Temporal landmarks: What must happen, and when." (2015).
  31. ^ Erol, Kutluhan, James Hendler, and Dana S. Nau. "HTN planning: Complexity and expressivity." AAAI. Vol. 94. 1994.
  32. ^ Höller, Daniel, et al. "HDDL: An Extension to PDDL for Expressing Hierarchical Planning Problems." AAAI. 2020.
  33. ^ Höller, Daniel, et al. "Hierarchical Planning in the IPC." arXiv preprint arXiv:1909.04405 (2019).
  34. ^ Alford, Ron, et al. "Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems." ICAPS. 2016.
  35. ^ Shivashankar, Vikas, Ron Alford, and David W. Aha. "Incorporating domain-independent planning heuristics in hierarchical planning." Thirty-First AAAI Conference on Artificial Intelligence. 2017.
  36. ^ Cserna, Bence, et al. "Avoiding Dead Ends in Real-Time Heuristic Search." AAAI. 2018.
  37. ^ Brafman, Ronen I., and Carmel Domshlak. "From One to Many: Planning for Loosely Coupled Multi-Agent Systems." ICAPS. Vol. 8. 2008.
  38. ^ SPSS
  39. ^ Spike

関連項目

外部リンク