自動計画問題の概要と実装/参考図書

2023.06.05
人工知能技術 機械学習技術 自然言語処理技術 人工知能アルゴリズム ICT技術 デジタルトランスフォーメーション 人工生命 推論技術 知識工学 オートマトンと自動計画  本ブログのナビ
自動計画問題の概要

自動計画問題とは、ある目標を達成するために必要な一連の行動を計画する問題となる。具体的には、ある状態から出発し、目標状態に至るための行動の順序を決定するアルゴリズムで、自動計画問題は、人工知能やロボット工学などの分野で広く用いられる。

自動計画問題は、次のような要素を持つ。

  • 状態空間: 自動計画問題は、状態空間上で定義される。状態空間とは、システムが取りうる全ての状態の集合のこととなる。状態空間は、有限状態空間や無限状態空間である場合がある。
  • 行動空間: 自動計画問題では、ある状態から別の状態に遷移するために取る行動の集合を行動空間と呼ぶ。行動空間には、有限行動空間や無限行動空間がある。
  • 制約条件: 自動計画問題には、行動に制約条件がある場合がある。制約条件の例として例えば、ある行動は他の行動に先行する必要がある、ある状態では特定の行動を実行することができない、などがある。
  • 目的関数: 自動計画問題においては、目標状態に到達するための最小のコストや最短時間などの目的関数を最小化することが求められる。

自動計画問題には、状態空間探索法や逆問題解法、深層強化学習など様々な手法があり、実際に、自動計画問題を解決するには、問題に応じた最適な手法を選択することが重要となる。以下にそれらの手法について述べる。

自動計画問題での各種手法

自動計画問題を解決する手法として、以下のようなものがある。

  • 状態空間探索法: 状態空間探索法は、状態空間が有限である場合に有効な手法で、状態空間上を探索することで、目標状態に至る計画を見つけるものとなる。具体的なアルゴリズムとしては、幅優先探索、深さ優先探索、Aアルゴリズム、IDAアルゴリズムなどがある。以下に状態空間探索系のアルゴリズムについて述べる。
  • 逆問題解法: 逆問題解法は、目標状態が与えられている場合に有効な手法で、目標状態から逆に遡って、初期状態に至る計画を見つける手法となる。これは以下のような手順で行われる。
    1. 目標状態を初期状態として設定する。
    2. 初期状態に至るためのアクションを計画に従って逆に適用し、現在の状態を更新する。
    3. 現在の状態が初期状態と一致する場合は、計画が見つかったとして終了する。そうでない場合は、ステップ2に戻る。
    4. 計画が見つからなかった場合は、問題が解決不能であることを示す。

この手法は、計画の長さに比例して計算量が増大するため、大規模な問題には適していない。また、計画の逆方向に進むためには、計画に関する情報を保持する必要があるため、メモリの使用量も問題となる場合もある。

  • ランダム化探索法: ランダム化探索法は、ランダムな行動を繰り返して目標状態に至る計画を見つける手法となる。具体的には、”メタヒューリスティクスの数理　読書メモ“で述べてられているようなヒュリスティック系のアルゴリズムである”ランダムウォークの概要とアルゴリズム及び実装例“でも述べているランダムウォーク、焼きなまし法、遺伝的アルゴリズムなどとなる。ランダム化探索法は、局所解に陥る可能性に注意する必要がある。
  • 最適化問題としての解法: 自動計画問題を最適化問題として定式化し、最適化手法を用いて解く手法がある。具体的には、線形計画法、整数計画法、非線形計画法などになる。これらの詳細は”機械学習における数学について“の最適化の数学の項に述べている。また、最適化問題として定式化することで、多目的最適化問題にも対応することもできる。
  • 深層強化学習: 深層強化学習は、深層学習と強化学習を組み合わせた手法であり、行動決定のためのニューラルネットワークを学習することで、最適な計画を見つける手法となる。深層強化学習の自動計画への適用は、状態空間や行動空間が大きい場合に有効な手法として、近年注目されている。深層強化学習の詳細に関しては”様々な強化学習技術の理論とアルゴリズムとpythonによる実装“にて述べているので参照のこと。
自動計画問題に用いられるライブラリやプラットフォームについて

自動計画問題に取り組むために使用できるさまざまなライブラリやプラットフォームが存在する。以下にそれらのうちのいくつかについて述べる。

  • PDDL (Planning Domain Definition Language): PDDLは、自動計画問題を表現するための一般的な言語となる。PDDLをサポートするライブラリやツールは、問題のモデリング、計画生成、計画の解析などのタスクを実行するのに役立つ。
  • Fast Downward: Fast Downwardは、効率的なプランニングアルゴリズムを実装したオープンソースのプランニングフレームワークとなる。PDDLに対応しており、さまざまなドメインでの計画生成をサポートしている。
  • STRIPS: STRIPS(Stanford Research Institute Problem Solver)は、自動計画問題を解くための古典的なフレームワークとなる。STRIPSは、アクションの前提条件と効果を定義し、計画を生成するためのアルゴリズムを提供している。
  • ROS (Robot Operating System): ROSは、ロボットアプリケーション開発のための柔軟で強力なプラットフォームであり、ROSは、自動計画に関連するライブラリやツールを提供し、ロボットの移動計画、タスクのスケジューリングなどの問題を解決するために使用されている。
  • PDDL4J: PDDL4Jは、Javaで書かれたPDDL(Planning Domain Definition Language)の解析および操作をサポートするライブラリとなる。PDDL4Jは、PDDLファイルの読み込み、問題の定義、計画の生成など、さまざまなPDDL関連のタスクを実行するために使用できる。

次に自動計画法の適用事例について述べる。

自動計画法の適用事例

自動計画問題は、多くの分野で活用されている。以下に、代表的な適用事例について述べる。

  • スケジューリング: 自動計画問題が最もよくつか寄れているものにスケジューリング問題への適用がある。これは例えば、製造工程のスケジューリングや、オフィス内での会議のスケジューリングなどになる。
  • ロボット制御: 自動計画問題は、ロボットの動作計画やタスクプランニングに応用されている。これは例えば、工場内での自律移動ロボットの動作計画や、物流センターでの搬送ロボットのタスクプランニングなどになる。
  • ゲームAI: 自動計画問題は、”デジタルゲームAIの基本技術(時間認織) 過去記憶、未来(プランニング)“でも述べられているように、ゲームAIの分野でも活用されている。これは例えば、チェスや将棋などのボードゲームで、次の最適手を考える問題が自動計画問題であったり、また、リアルタイムストラテジーゲームでの、ユニットの移動や攻撃などの行動計画などになる。
  • 認知ロボティクス: 自動計画問題は、認知ロボティクスの分野でも活用されている。これは例えば、視覚情報を基にして机の上の物体をつかむためのアームの動作計画や、人間との共同作業を実現するための行動計画などになる。
  • 自動運転: 自動計画問題は、自動運転技術にも応用されている。これは例えば、車両の軌道計画や速度制御などになる。
pythonによる実装

自動計画法のPythonを用いた実装にはいくつかのライブラリがある。ここでは、PDDLという形式で記述された問題を解くためのライブラリであるpyperplanを使用した自動計画法のPython実装について述べる。まずは、pyperplanライブラリをインストールする。

>pip install pyperplan

次に、PDDLファイルを作成する。

PDDL（Planning Domain Definition Language）は、人工知能の分野で自動計画を行うために使用される形式言語の一つであり、計画のドメインと問題を記述するための標準的な記述言語で、多くの自動計画システムがPDDLをサポートしているものとなる。

PDDLでは、計画問題の状態、初期状態、アクション、ゴール状態などを定義することができ、ドメイン記述には、アクションや状態変数、制約条件などを定義するための言語要素がある。問題記述には、具体的な状態や目標状態、使用可能なオブジェクトなどが含まれる。

(define (problem sample)
  (:domain sample-domain)
  (:objects a b c)
  (:init (on a b) (on b c) (clear a) (clear c))
  (:goal (and (on a c) (on c b))))

上記のPDDLファイルは、サンプルのドメインという名前のドメインにおいて、a、b、cという3つのオブジェクトがあり、aがbの上に、bがcの上に、aとcがどちらも自由な状態から始まり、aがcの上に、cがbの上になるようにすることを目標としている。次に、Pythonコードを作成する。

from pyperplan import Plan
from pyperplan.planning import AbstractTask, Task
from pyperplan.search import AStar
from pyperplan.propositional_planner import PropositionalPlanner
from pyperplan.heuristics import BlindHeuristic

# PDDLファイルを読み込む
domain_file = 'sample-domain.pddl'
problem_file = 'sample-problem.pddl'

# 問題を表すオブジェクトを作成する
task = Task(domain_file, problem_file)

# 問題を解くための検索アルゴリズムを作成する
search_algorithm = AStar()

# 問題を解くためのプランナーを作成する
planner = PropositionalPlanner(task, search_algorithm, BlindHeuristic())

# 問題を解く
plan = planner.plan()

# プランを表示する
for action in plan:
    print(action.name)

上記のPythonコードは、pyperplanライブラリを使用して、先ほど作成したPDDLファイルで表された問題を解き、プランを表示するものとなる。この他にも、pythonではFFやFast-Downwardといった自動計画法のためのライブラリがある。

Clojureでの実装

自動計画法は、Clojureのような関数型言語でも実装できる。Clojureには、PDDL形式の問題を解くためのライブラリであるclj-planningがある。以下で、clj-planningを使用した自動計画法のClojure実装例を示す。まずは、clj-planningライブラリをプロジェクトに追加する。

;; Leiningenを使っている場合
[clj-planning "0.4.0"]

次に、前述のpyhtonのケースと同様にPDDLファイルを作成する。

(define (problem sample)
  (:domain sample-domain)
  (:objects a b c)
  (:init (on a b) (on b c) (clear a) (clear c))
  (:goal (and (on a c) (on c b))))

上記のPDDLファイルは、サンプルのドメインという名前のドメインにおいて、a、b、cという3つのオブジェクトがあり、aがbの上に、bがcの上に、aとcがどちらも自由な状態から始まり、aがcの上に、cがbの上になるようにすることを目標としている。次に、Clojureコードを作成する。

(ns my-project.core
  (:require [clj-planning.core :as planning]))

;; PDDLファイルを読み込む
(def domain-file "sample-domain.pddl")
(def problem-file "sample-problem.pddl")

;; 問題を解く
(let [task (planning/task-from-files domain-file problem-file)
      plan (planning/plan task)]
  ;; プランを表示する
  (doseq [action plan]
    (println (:name action))))

上記のClojureコードは、clj-planningライブラリを使用して、先ほど作成したPDDLファイルで表された問題を解き、プランを表示するものとなる。Clojureでは他にも、STRIPSやFast Downwardといった自動計画法のためのライブラリがある。

これらの基本的な概念は古くはLISPで開発されており、それらの詳細については”実用Common Lisp　読書メモ“も参照のこと。

参考図書

自動計画法の参考図書として”Automated Planning theory and practice“がある。

これは、自動プランニングの理論と実践に関する包括的で最新のリソースを提供することで、この対話を反映させているもので。古典的なプランニングにとどまらず、時間的プランニング、リソーススケジューリング、不確実性の下でのプランニング、そしてタスク分解、命題充足性、制約充足、モデルチェックなどのプラン生成の最新テクニックも含んでいる参考図書となる。

以下に内容を示す。

Automated Palnning  theory and practices
	Chapter 1 Introduction and Overview
		1.1 First Intuitions on Planning
		1.2 Forms of Planning
		1.3 Domain-independent Planning
		1.4 Conceptual Model for Planning
		1.5 Restricted Model
		1.6 Extended Models
		1.7 A Running Example:Dock-Worker Robots
	Part 1 Classical Planning
		Chapter 2 Representations for Classical Planning
			2.1 Introduction
			2.2 Set-Theoretic Representations
				2.2.1 Planning Domain, Problems, and Solutions
				2.2.2 State Reachability
				2.2.3 Starting a Planning Problem
				2.2.4 Properties of the Set-Theoretic Representation
			2.3 Classical Representation
				2.3.1 States
				2.3.2 Operators and Actions
				2.3.3 Plans, Problems, and Solutions
				2.3.4 Semantics of Classical Representations
			2.4 Extending the Classical Representation
				2.4.1 Simple Syntactical Extensions
				2.4.2 Conditional Planning Operations
				2.4.3 Quantified Expressions
				2.4.4 Disjunctive Preconditions
				2.4.5 Axiomatic Inference
				2.4.6 Function Symbols
				2.4.7 Attached Procedures
				2.4.8 Extended Goal
			2.5 State-Variable Representation
				2.5.1 State Variables
				2.5.2 Operators and Actions
				2.5.3 Domains and Problems
				2.5.4 Properties
			2.6 Comparisons
			2.7 Discussion and Historical Remarks
			2.8 Exercise
		Chapter 3 Complexy of Classical Planning
			3.1 Introduction
			3.2 Preliminaries
			3.3 Decidability and Undecidability Results
			3.4 Complexity Results
				3.4.1 Binary Counters
				3.4.2 Unrestricted Classical Planning
				3.4.3 Other Results
			3.5 Limitations
			3.6 Discussion and Historical Remarks
			3.7 Exercises
		Chapter 4 State-Space Planning
			4.1 Introduction
			4.2 Forward Search
				4.2.1 Formal Properties
				4.2.2 Deterministic implementations
			4.3 Backward Search
			4.4 The STRIPS Algorithm
			4.5 Domain-Specific Sates-Space Planning
				4.5.1 The Container-Stacking Domain
				4.5.2 Planning Algorithm
			4.6 Discussion and Historical Remarks
			4.7 Exercises
		Chapter 5 Plan-Space Planning
			5.1 Introduction
			5.2 The Search Space of Partial Plans
			5.3 Solution Plans
			5.4 Algorithms for plan-Space Planning
				5.4.1 The PSP Procedure
				5.4.2 The PoP Procedure
			5.5 Extensions
			5.6 Plan-Space versus State-Space Planning
			5.7 Discussions and Historical Planning
			5.8 Exercises
	Part 2 Neoclassical Planning
		Chapter 6 Planning-Graph Technique
		Chapter 7 Probabilistic Satisfiability Technique
		Chapter 8 Constraint Satisfaction Techniques
	Part 3 Heuristics and Control Startegies
		Chapter 9 Heuristic in Planning
		Chapter 10 Control Rules in Planning
		Chapter 11 Hierarchical Task Network Planning
		Chapter 12 Control Strategies in Deductive Planning
	Part 4 Planning with Time and Resources
		Chapter 13 Time for Planning
		Chapter 14 Temporal Planning
		Chapter 15 Planning and Resources Scheduling
	Part 5 Planning under Uncertainty
		Chapter 16 Planning Based on Markov Decu¥vision Processing
		Chapter 17 Planning Based on Model Checking
		Chapter 18 Uncertainty with Neoclassical Techniques
	Part 6 Case Studies and Applications
		Chapter 19 Space Applications
		Chapter 20 Planning in Robotics
		Chapter 21 Planning for Manufacturability Analysis
		Chapter22 Emergency Evacuation Planning
		Chapter 23 Planning ih the Game of Bridge
	Part 7 Conclusion
		Chapter 24 Other Approach to Planning
	Part 8 Appendices
		Appendix A
		Appendix B
		Appendix C

コメント

  1. オートマトンと状態遷移/ペトリネットと自動計画 | Deus Ex Machina より:
    2023年9月14日 4:39 AM

    […] 自動計画問題の概要と参考図書 […]

    返信
タイトルとURLをコピーしました