自動計画
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/16 01:19 UTC 版)
自動計画（じどうけいかく、英: Automated planning and scheduling）は、人工知能のテーマの1つであり、戦略や行動順序の具体化をすること。典型的な例として、知的エージェント、自律型ロボット、無人航空機などでの利用がある。古典的制御システムや統計分類問題とは異なり、自動計画の解は複雑で未知であり、多次元空間における発見と最適化が必要となる。
- ^ 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
自動計画
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/11/04 08:12 UTC 版)
自動計画システムは、以上のような記述を入力として、初期状態から目標状態へと導く計画（すなわち一連の行動実行順序）を導出する。 形式的には状態は命題の集合であり、ある時点の状態はそのときに真である命題の集合で表される。状態間の遷移は遷移関数にモデル化でき、行動の実行によって発生する、ある状態から別の状態への写像とみなせる。状態は行動に対応するため、STRIPS のインスタンス ⟨ P , O , I , G ⟩ {\displaystyle \langle P,O,I,G\rangle } に関する遷移関数は次のように表される: succ : 2 P × O → 2 P , {\displaystyle \operatorname {succ} :2^{P}\times O\rightarrow 2^{P},} ここで、 2 P {\displaystyle 2^{P}} は P {\displaystyle P} の全部分集合の集合であり、システムがとりうる全状態の集合である。 あるアクション a ∈ O {\displaystyle a\in O} が状態 s {\displaystyle s} に適用できる条件は、 s ⊇ p r e ( a ) {\displaystyle s\supseteq pre(a)} である。これが満たされている場合、アクションを適用できて、その結果状態 s {\displaystyle s} は以下のような状態 s ′ {\displaystyle s'} に遷移する: succ ( s , a ) {\displaystyle \operatorname {succ} (s,a)} = ( s ∖ e − ) ∪ e + {\displaystyle (s\setminus e^{-})\cup e^{+}} ここで、 e − , e + {\displaystyle e^{-},e^{+}} の適用の順番は重要であり、これは同じ命題が e − {\displaystyle e^{-}} 、 e + {\displaystyle e^{+}} の両方に含まれた場合には追加効果が優先するという動作を決定する。 関数 succ {\displaystyle \operatorname {succ} } は以下のように再帰的に行動の列に展開できる: succ ( s , [ ] ) = C {\displaystyle \operatorname {succ} (s,[])=C} succ ( s , [ a 1 , a 2 , … , a n ] ) = succ ( succ ( s , a 1 ) , [ a 2 , … , a n ] ) {\displaystyle \operatorname {succ} (s,[a_{1},a_{2},\ldots ,a_{n}])=\operatorname {succ} (\operatorname {succ} (s,a_{1}),[a_{2},\ldots ,a_{n}])} STRIPS のインスタンスの計画は、初期状態から目標状態へと遷移させる一連の行動の並びである。形式的には、 s = succ ( I , [ a 1 , a 2 , … , a n ] ) {\displaystyle s=\operatorname {succ} (I,[a_{1},a_{2},\ldots ,a_{n}])} が G ⊆ s {\displaystyle G\subseteq s} を満たす場合、プラン π = [ a 1 , a 2 , … , a n ] {\displaystyle \pi =[a_{1},a_{2},\ldots ,a_{n}]} がこのインスタンスの解となる。
※この「自動計画」の解説は、「STRIPS」の解説の一部です。
「自動計画」を含む「STRIPS」の記事については、「STRIPS」の概要を参照ください。
- 自動計画のページへのリンク
