自動計画

索引トップ用語の索引ランキングカテゴリー

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/16 01:19 UTC 版)

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

同時並行に複数のアクションを実行できるプランニング問題はスケジューリング問題、ないし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]

出典

^ Bylander, Tom. "The computational complexity of propositional STRIPS planning." Artificial Intelligence 69.1-2 (1994): 165-204.
^ Bylander, Tom. "The computational complexity of propositional STRIPS planning." Artificial Intelligence 69.1 (1994): 165-204.
^ 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.
^ Imai, Tatsuya, and Alex Fukunaga. "A Practical, Integer-Linear Programming Model for the Delete-Relaxation in Cost-Optimal Planning." ECAI. 2014.
^ Bylander et al.
^ Helmert, Malte, and Carmel Domshlak. "Landmarks, critical paths and abstractions: what's the difference anyway?." ICAPS. 2009.
^ Davies, Toby O., et al. "Sequencing Operator Counts." ICAPS. 2015.
^ Alcázar, Vidal, et al. "Revisiting regression in planning." Twenty-Third International Joint Conference on Artificial Intelligence. 2013.
^ Holte, Robert C., et al. "Bidirectional Search That Is Guaranteed to Meet in the Middle." AAAI. 2016.
^ Alcázar, Vidal, Patricia J. Riddle, and Mike Barley. "A Unifying View on Individual Bounds and Heuristic Inaccuracies in Bidirectional Search." AAAI. 2020.
^ 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).
^ 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.
^ Helmert, Malte, and Gabriele Röger. "How Good is Almost Perfect?." AAAI. Vol. 8. 2008.
^ 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.
^ Lipovetzky, Nir, Christian J. Muise, and Hector Geffner. "Traps, Invariants, and Dead-Ends." ICAPS. 2016.
^ Torralba, Alvaro, et al. "On State-Dominance Criteria in Fork-Decoupled Search." IJCAI. 2016.
^ Hall, David Leo Wright, et al. "Faster Optimal Planning with Partial-Order Pruning." ICAPS. 2013.
^ 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.
^ N.J. Nilsson, Principles of Artificial Intelligence, Tioga Publishing, Palo Alto, CA, 1980.
^ Hansen, Eric A., and Shlomo Zilberstein. "LAO∗: A heuristic search algorithm that finds solutions with loops." Artificial Intelligence 129.1-2 (2001): 35-62.
^ Yoon, Sung Wook, et al. "Probabilistic Planning via Determinization in Hindsight." AAAI. 2008.
^ Yoon, Sung Wook, Alan Fern, and Robert Givan. "FF-Replan: A Baseline for Probabilistic Planning." ICAPS. Vol. 7. 2007.
^ 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.
^ 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.
^ Fox, Maria, and Derek Long. "Modelling mixed discrete-continuous domains for planning." Journal of Artificial Intelligence Research 27 (2006): 235-297.
^ Piacentini, Chiara, et al. "Linear and Integer Programming-Based Heuristics for Cost-Optimal Numeric Planning." AAAI. 2018.
^ Karaman, Sertac, and Emilio Frazzoli. "Sampling-based algorithms for optimal motion planning." The international journal of robotics research 30.7 (2011): 846-894.
^ 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.
^ Burfoot, Daniel, Joelle Pineau, and Gregory Dudek. "RRT-Plan: A Randomized Algorithm for STRIPS Planning." ICAPS. 2006.
^ Karpas, Erez, et al. "Temporal landmarks: What must happen, and when." (2015).
^ Erol, Kutluhan, James Hendler, and Dana S. Nau. "HTN planning: Complexity and expressivity." AAAI. Vol. 94. 1994.
^ Höller, Daniel, et al. "HDDL: An Extension to PDDL for Expressing Hierarchical Planning Problems." AAAI. 2020.
^ Höller, Daniel, et al. "Hierarchical Planning in the IPC." arXiv preprint arXiv:1909.04405 (2019).
^ Alford, Ron, et al. "Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems." ICAPS. 2016.
^ Shivashankar, Vikas, Ron Alford, and David W. Aha. "Incorporating domain-independent planning heuristics in hierarchical planning." Thirty-First AAAI Conference on Artificial Intelligence. 2017.
^ Cserna, Bence, et al. "Avoiding Dead Ends in Real-Time Heuristic Search." AAAI. 2018.
^ Brafman, Ronen I., and Carmel Domshlak. "From One to Many: Planning for Loosely Coupled Multi-Agent Systems." ICAPS. Vol. 8. 2008.
^ SPSS
^ Spike