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

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

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

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

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

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

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

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

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

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

自動計画問題に用いられるライブラリやプラットフォームについて

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

  • 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　読書メモ“も参照のこと。

参考図書

基礎と体系的解説

  1. Automated Planning: Theory and Practice
    Malik Ghallab, Dana Nau, Paolo Traverso
    Morgan Kaufmann, 2004

    • 自動計画の古典的かつ体系的な教科書。STRIPS, HTN, PDDLなどの形式表現やアルゴリズムを詳細に解説。

  2. Planning Algorithms
    Steven M. LaValle
    Cambridge University Press, 2006（無料オンライン版あり）

    • ロボット工学や経路計画まで含む幅広い計画アルゴリズムを網羅。動的環境や確率的計画にも対応。

  3. Automated Planning and Acting
    Malik Ghallab, Dana Nau, Paolo Traverso
    Cambridge University Press, 2016

    • 上記の改訂・発展版。古典的プランニングに加え、リアクティブプランニングや実行監視を解説。

発展・専門分野

  1. Principles of Artificial Intelligence Planning
    Michael Ghallab, Craig Knoblock（編）

    • 古典AI計画から発展的テーマまで、特定分野の深掘りに有用。

  2. Articles on Automated Planning and Scheduling, Including: Planner (Programming Language), Deterministic Policy, Planning Domain Definition Language, Strips, Graphplan, Multi-Agent Planning, Satplan, Hierarchical Task Network 

  3. Temporal Planning
    Daniele Magazzeni, Enrico Scala

    • 時間制約やリソース制約を含む計画手法を扱う専門書。

関連・応用

  1. Artificial Intelligence: A Modern Approach (3rd Edition)
    Stuart Russell, Peter Norvig

    • AI全般の教科書だが、自動計画の基礎（古典的計画、部分順序計画、確率的計画）もカバー。

  2. Automated Planning and Scheduling

コメント

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

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

    返信
モバイルバージョンを終了
タイトルとURLをコピーしました