12章資料

Russell, S. & Norvig, P. Artiﬁcial Intelligence : A Modern Approach (2nd Ed.). (2003).
Pearson Education. (古川ら訳. 共立出版. 2008)
12
実世界におけるプランニングと行為
• 実世界におけるプランニングは 11 章で述べたものよりも複雑—記述言語の基礎と、
プランナが環境と相互作用する方法の基礎を拡張
• 12.1 節は時間と資源制約がある場合、12.2 節は事前に定義された副プランによるプ
ランニング、12.3 節から 12.6 節は不確かな環境を扱うエージェントアーキテクチャ、
12.7 節は他のエージェントの存在があるときのプランニング
12.1
時間、スケジュール、資源
• Strips 表現の問題: 行為に要する時間や、その行為が起こる時間を表現できない
• ジョブ・ショップ・スケジューリング (job shop scheduling) — タスクは一組のジョブ
の完了を要求、個々のジョブは一連の行為からなり、各行為は実施の長さ (duration)
をもち、なんらかの資源が必要なことがある。資源制約を考慮しながらすべてのジョ
ブを完了するために必要な総時間を短縮するスケジュールを決める、という問題
• ジョブ・ショップ・スケジューリングの例: 図 12.1 — 自動車組み立て問題 (数字は行
為の実行にかかる時間)
Init(Chasis(C1 ) ∧ Chassis(C2 ) ∧ Engine(E1 , C1 , 30)∧
Engine(E2 , C2 , 60) ∧ W heels(W1 , C1 , 30) ∧ W heels(W2 , C2 , 15))
Goal(Done(C1 ) ∧ Done(C2 ))
Action(AddEngine(e, c),
Precond: Engine(e, c, d) ∧ Chassis(c) ∧ ¬EngineIn(c),
Effect: EngineIn(c) ∧ Duration(d))
Action(AddW heels(w, c),
Precond: W heels(w, c, d) ∧ Chasis(c) ∧ EngineIn(c)
Effect: W heelsOn(c) ∧ Duration(d))
Action(Inspect(c),
Precond: EngineIn(c) ∧ W heelsOn(c) ∧ Chassis(c)
Effect: Done(c) ∧ Duration(10))
図 12.1 2 台の自動車を組み立てるジョブショップスケジューリング問題
• プランニング問題ではなくスケジューリング問題として捉える— 行為の順序だけで
はなく期間も考慮しながら、各行為の始まりと終了時間を決定する
• クリティカルパス法 (CPM: critical path method): 期間を伴う半順序行為が与えら
れれば、各行為の可能な開始時間と終了時間を決定。
半順序プランのパス (path): 線形に順序化された一連の行為、 Start で始まり Finish
で終わる
1
• クリティカルパス (critical path):パスの合計期間が一番長いもの—全体プランの期間
を決定するため「重要」—このパス上のどんな行為もその遅延が全体プランの遅延
を引き起こす
クリティカルパス上にない行為は、実行開始時間に幅 (window) がある— 最早開始
可能時間 (ES, earliest possible start time) と最遅開始可能時間 (LS, latest possible
start time) によって特定。LS − ES は「行為の余裕 (slack)」
全行為における ES 時間と LS 時間は、問題のためのスケジュールを構成
• ES と LS の定義を与え、これらを計算するための動的計画アルゴリズムの概略:
ES(Start) = 0
ES(B) = maxA≺B ES(A) + Duration(A)
LS(F inish) = ES(F inish)
LS(A) = minA≺B LS(B) − Duration(A)
例: ES(Start) = 0、Duration(Start) = 0 から ES(AddEngine1) = 0、ES(AddEngine2) =
0。ここで、Duration(AddEngine1) = 30, Duration(AddEngine2) = 60 だから (な
ぜなら Engine(E1 , C1 , 30) と Engine(E2 , C2 , 60) から)、ES(AddW heels1) = 30,
ES(AddW heels2) = 60 となる。このようにして ES(F inish) = 85 が求まる。逆に
LS(F inish) = ES(F inish) = 85 から、LS(Inspedct1) = LS(Inspect2) = 85−10 =
75 となる。
• クリティカルパスアルゴリズムの複雑さ: O(N b)—N は行為の数、b は行為への最大
分岐数／行為からの最大分岐数。
最小期間スケジュールを求める問題は、「半順序行為が与えられれば」容易に解決さ
れる
資源制約ありスケジューリング
• 実際のスケジューリングは資源 (resource) の制約により複雑化する
• 再利用可能資源 (reusable resource): 行為が終了するとふたたび利用可能になる資源
• 集約 (aggregation): 目的に関してオブジェクトを区別できないとき、個々のオブジェ
クトを量として扱う—集約は複雑さを減少させるのに必須
• 行為間の相互作用が導入されると、資源制約はスケジューリング問題をさらに複雑化
する—クリティカルパス法を用いた制約のないスケジューリングは簡単だが、最早可
能完了時間を考慮した資源制約スケジュールを見いだすことは NP 困難
• 最小余裕 (minimum slack) アルゴリズム—単純だが有名。欲張り (greedy) アルゴリ
ズムにより行為をスケジュール。各試行でまだスケジュールされていないスケジュー
ル可能な行為に対し、最小限の余裕で (できるだけ早く開始させるため) スケジュー
ルする。次にその影響を受ける各行為の ES と LS 時間を更新。これを繰り返す。
制約充足において最も制約された変数に関するヒューリスティクスと同じ理論に基
づく。
図 12.4 の例では 115 分ではなく 130 分という解を出す (?!)
2
Init(Chasis(C1 ) ∧ Chassis(C2 ) ∧ Engine(E1 , C1 , 30)∧
Engine(E2 , C2 , 60) ∧ W heels(W1 , C1 , 30) ∧ W heels(W2 , C2 , 15))∧
EngineHoists(1) ∧ W heelStations(1) ∧ Inspectors(2)
Goal(Done(C1 ) ∧ Done(C2 ))
Action(AddEngine(e, c),
Precond: Engine(e, c, d) ∧ Chassis(c) ∧ ¬EngineIn(c),
Effect: EngineIn(c) ∧ Duration(d)
Resource: EngineHoists(1))
Action(AddW heels(w, c),
Precond: W heels(w, c, d) ∧ Chasis(c) ∧ EngineIn(c)
Effect: W heelsOn(c) ∧ Duration(d)
Resource: W heelStations(1))
Action(Inspect(c),
Precond: EngineIn(c) ∧ W heelsOn(c) ∧ Chassis(c)
Effect: Done(c) ∧ Duration(10)
Resource: Inspectors(1))
図 12.3 2 台の自動車を組み立てる資源ありジョブショップスケジューリング問題
• 本節のアプローチ: 前半のプランを練る (問題解決に必要な行為の選択、全体の問題
を半順序化するプランニング) フェーズと、後半のスケジュールする (資源や締め切
りの制約を充足するために時間的な情報をプランに加えるスケジューリング) フェー
ズに分かれる— 実際の製造業などで使われる。
プランニングフェーズとスケジューリングフェーの「統合」— 11 章のアルゴリズム
の多くはこれが可能
12.2
階層的タスクネットワークプランニング
• 階層的分解 (hierarchical decomposition): 複雑な対象を、階層構造 (hierarchical structure) に分解して考える— 階層の各レベルにおいて計算タスクや行政機能が、次の下
位レベルで少ない行動数に削減され、必要な行動を用意するための計算コストが小さ
くなる
• 階層的タスクネットワーク (HTN: hierarchical task network) に基づくプランニング
手法—問題を記述する初期プランは何がなされるべきかを表す上位レベルの記述、プ
ランは行為分解 (action decomposition) によって洗練化。個々の行為分解は上位レベ
ルの行為を半順序構造をも使いレベルの行為の集合に変換。このプロセスは、プラ
ン上に原始的行為 (primitive action、基本行為) だけが残るまで続く— 原始的行為は
エージェントがそれ自体で実行可能な行為
例: 家を建てる (上位レベル)—許可獲得、建築業者の雇用、工事、支払いに分解
• 「純」HTN プランニング: プランは連続した行為分解によってのみ作られる—行為
記述を構築ではなく、具体化するプロセスとしてみなす
このプランニングが不自然なタスクもある (連言ゴールが要求されるような場合) —
行為分解を半順序プランニングにおけるプラン洗練として使用するハイブリッドアプ
ローチとしての見方
3
行為分解の表現
• 記述をプランライブラリ (plan library) に保存、構築されるプランの必要性に応じて
記述は抽出 (extract)、具体化 (instantiate) される
個々の方法の表現: Decompose(a, d) —行為 a が半順序プラン記述 d に分解される
• 例「家を建てる」(図 12.5) : BuildHouse 行為を 4 つの下位レベルの行為に分解、図
12.6 は問題を解くための行為記述
• 外的前提条件 (external precondition)—Start 行為が与える「他の行為によって導か
れないプラン上の行為の前提条件」
外的効果 (external eﬀect)— 他の行為によって否定されないプラン上の行為の全効
果、Finish 行為の前提条件
• 効果の区別: 主要効果 (primary eﬀect) と副次効果 (secondary eﬀect)
• 分解は行為の「正しい」実装であるべき
プラン d が行為 a の正しい実装: 行為 a の前提条件が与えられた状態で、プラン d が
a の効果を達成するための完全、かつ競合のない半順序プラン。
健全な半順序プランナの実行結果であれば、明らかにその分解は正しい
• プランライブラリは、与えられたどの行為に対する分解を複数保存可能—前提条件
や効果以外も付加可能 (例: 図 12.5 における ¬M oney という効果の付加)
• 別な情報隠蔽の形式が二つ: (1) 上位レベルの記述における、分解による内的効果
(internal eﬀect)—例: BuildHouse の分解における Peermit と Contract、(2) 上位レ
ベルの記述における、前提条件と効果の間の内的行為の時間間隔—例: GetPermit が
実行されるまで前提条件 Load が真であること
• 情報隠蔽の必要性—階層プランニングの複雑さを軽減する
• 情報隠蔽の代償—例えば、上位レベルの行為における内的条件と別な内的行為との
間の競合の発見
要するに、プランニングアルゴリズムでは、原始行為はポイント事象 (瞬間事象) と
して、上位レベルの行為はそこで何でも起きうる「時間を持つ」事象として扱われる
分解のためのプランナ修正
• HTN(階層的タスクネットワーク) プランニングを組み込むための POP(半順序プラ
ンナ) の修正方法—部分プランに分解法を適用するよう POP 後続関数の修正— 部分
プラン P に対し、P 中の非原始行為 a を選び、a と単一化可能な行為 a と単一化子 θ
をもつプランライブラリ中の Decompose(a, d) 方法に対して、a を d =Subst(θ, d)
で置き換える。
• 図 12.7 がその例。上位の BuildHouse 行為を分解対象に選ぶ。図 12.5 から分解 d が
選ばれ、BuildHouse がこれで置換される。(ここで GetLoan は Money という新たな
未解決条件の解決のために導入)
• 詳細な説明—可能な分解 d それぞれに対して以下を実施:
4
1. プラン P から行為 a を除去。次に、分解 d の各ステップ s に対し、s の役割を
満たす行為を選び、それをプラン P に加える。このとき加えられるのは、 s の
新たなインスタンスか、もしくは s に単一化する P の既存のステップ s —サブ
タスク共有 (subtask sharing)—のいずれか (図 12.7 の場合は共有できないので
新しい行為が作られる)
2. 元のプランの行為 a に対する順序制約を d のステップに加える。
例えばプラン P の順序制約として B ≺ a があるとする。これは a の分解 d の
ステップとどのような関係にあるか？— d 中のどのステップ s に対しても B ≺ s
とするのは厳しすぎる。その例: BuyLand は BuildHouse の前にないといけな
いが、だからといって BuildHouse の分解したステップ HireBuilder の前になく
てもよい。
最良の解決策は、それぞれの順序制約に「理由」を記録すること。そうすれば、
上位レベルの行為が展開された場合、新たな順序制約は可能な限り緩めること
が可能になる。この考え方は a ≺ C という形の制約を置き換える場合にもあて
はまる。
p
3. 最後のステップは、因果リンクをつなぐこと。元のプランで B −→ a が因果リ
ンクとすると、分解 d において Start ステップから与えられる前提条件 p をもつ
d のすべてのステップ (つまり、p が外的前提条件となるような d のすべてのス
テップ) に B から因果リンクをはることで置き換える。
Land
Land
例: 図 12.7 において、BuyLand −→ BuildHouse が、BuyLand −→ GetP ermit
リンクで置き換えられる。 —n!—
p
同様に、プラン中の a −→ C という形の因果リンクそれぞれを、 d のどのス
テップであれ分解 d の Finish ステップに p を提供しているもの (つまり、p を外
的効果とする d のステップ) から C に因果リンクをはって置き換える。
House
House
例: 図 12.7 において、BuildHouse −→ F inish リンクが、P ayBuilder −→
F Inish リンクで置き換えられる。
これにより、POP プランナにおいて分解を生成するための付加的条件が満足される。
• POP アルゴリズムに追加の修正が必要—上位レベルの行為がその最終的な実装に関
する情報を遮蔽しているから。特に、元の POP アルゴリズムはプランに解消不能な
競合—つまり、因果リンクと行為とが競合し、順序の並び替えができない場合— が
あれば失敗によりバックトラックする。
それに対し、上位レベルの行為は一見解消不能な競合でも、競合している行為を分解
しステップをインターリーブすれば、時に解消できる場合がある (その例は図 12.8)。
つまり、上位レベルでは完全で無矛盾なプランがない場合でも、分解によって完全で
無矛盾な基本行為レベルのプランが得られる場合がある。これにより、完全な HTN
プランナは標準的な POP プランナが利用可能な多くの枝刈り機会を「なし」ですま
せなければならない、ということを意味。言い換えれば、枝刈りするならば、解の見
落としがある可能性がある。
議論
• 悪いお知らせ: (使える洗練のための手法が分解だけの場合) HTN プランニングは、
たとえその状態空間が有限としても決定不能 (undecidable)。
5
問題は、行為分解が再帰的になり、任意に長くなる可能性があること—有限時間内に
探索を終了させることができない
そこで、次の 3 つの方法
1. 再帰を行わない。この場合、すべての HTN プランは有限の長さで数え上げ可能
2. 解の長さに制限をつける。こうしても失うものは少なく、探索を制御可能
3. POP と HTN プランニングを組み合わせたハイブリッドアプローチの採用。プ
ランの存在を決定するのには半順序プランニングで十分であるため、問題が明
らかに決定可能 (decidable)
• 3 番目の方法についての注意—行為分解を行為の追加よりも優先度を持たせるようハ
イブリッド探索を制御する。そのためのひとつの方法は、行為の追加に対し割引を与
えるコスト関数の導入
• HTN プランのもう一つの重要な特徴: サブタスク共有— サブタスク共有が許されな
ければ、分解の具体化は一通りに決まり、探索空間はかなり狭くなるが、問題が起こ
るケースもある (「ハネムーンを楽しみ、子供達を育てる」の例)。
• サブタスク共有の利点と問題点に関する話題—コンパイラの最適化
tan(x) − sin(x) のコンパイル: それぞれの式を計算するよりも、行為分解すると効率
的—しかしすべての共有可能なタスクの探索には時間がかかりすぎる
• HTN プランニングの効率がよいと信じる根拠: 理想的なケースによる説明
n 個の行為からなるプランを作成する場合、各状態で b 個の行為を許す非階層的前向
き状態空間プランナのコストは O(bn )、HTN プランナは d 種類の分解により、個々
の非原始的行為が下位レベルで k 個の行為に分解されるという分解構造を仮定する
と、その内部の分解ノード数は (n − 1)/(k − 1)(高さが logk n より) となることから、
d(n−1)/(k−1) 通りの分解木が可能。これにより k を小さく、k を大きく取れば、コス
トを小さくできることが分かる—b と d が同じくらいなら HTN プランナは k 分の 1
乗根のコストとなる。
• HTN プランニングの効率がよいと信じる別な根拠: 実際に動く。大規模な応用プラ
ンナのほとんどは HTN プランナ—専門家の知識を使って少ない計算コストで大規模
プランが作れる。
• HTN プランニングの鍵: 複雑で高次レベルの行為を実装するための既知の手法を納
めたプランライブラリを構築すること—学習と一般化
12.3
非決定領域におけるプランニングと行為
• 古典的でないプランニング: 不完全 (incomplete) な情報と不正確 (incorrect) な情報
を扱う
不完全性は、世界が部分観測、非決定的、もしくはその両方であることから生じる
不正確性は、世界モデルと実世界とが必ずしも一致しないことから生じる
6
• 完全な、正確な知識をもつ可能性は、どのくらい世界に不確定性が存在するかに依存
限定不確定性 (bounded indeterminacy): 行為は予測不能な効果を持ちうるが、どの
ような効果が可能か行為記述公理に書き出せる
非限定不確定性 (unbounded indeterminacy): 行為の前提条件や効果が未知か、もし
くは完全に数え上げることができない
• 限定不確定性の場合は、起こりうる状況すべてを考慮したプランを作成することで対
処可能
非限定不確定性の場合は、プランや知識ベースを改訂する準備がある場合にのみ対処
可能—10 章の制限条件記述問題 (qualiﬁcation problem) と関連
• 不確定性を扱うプランニング手法 (初め 2 つは限定不確定性、残り 2 つは非限定不確
定性に適す)
1. センサーなしプランニング (順応プランニング): 知覚なしに実行される標準的
で逐次的なプランを構築。プランはどのような環境でもゴールの達成を保証し
なければならない。エージェントが状態について部分情報しか無い場合でも世
界は何らかの状態であるとみなす「強制」(coercion) に基づく—強制が常に可
能とは限らないため、この手法が使えないことがある
2. 条件付きプランニング (偶発性プランニング): 起こりうるいろいろな状況に対
していろいろな選択肢を持つ条件的なプランを構築することで、限定不確定性
に対処。古典的プランニング同様、エージェントはプランをたて、それを実行
する。ただし、条件をチェックするセンサー情報をプランに含めることでどのプ
ランを実行すべきかを決定する。
3. 実行モニタリングと再プランニング: 上の二つのプランニングに加えて、実行
モニタリングを用いてプランが実際に実行可能かそれともプランの改訂が必要
かを判断する。何か障害があったときには、再プランニングが行われる。
4. 連続プランニング: 所定の時間を越えて動くよう設計されている。プラン作成
の途中であっても予期せぬ環境の変化があればそれに対処できる。ゴール体系
化 (goal formulation) によりゴールの破棄や追加生成が可能。
それぞれのプランニングを採用したエージェントの違い: 初期状態で「椅子、テーブ
ル、色が分からないペンキ缶がある」として、椅子とテーブルを同じ色に塗る (それ
ぞれ埋めること)
– 古典的プランニング: 初期状態が完全に明記されていないので、対処不能
– センサなしプランニング:
– 条件付きプランニング
– 再プランニング
– 連続プランニング
実世界では、これらを組み合わせて使用。
12.4
条件付きプランニング
完全観測環境と部分観測環境
7
完全観測環境における条件付きプランニング
• 完全観測性 (full observability): いつもエージェントが現在の状態をすべて知ってい
る。しかし環境が非決定的であれば、行為の結果については予測不能
• 条件付きプランによって、環境状態を実行時にチェックするというステップをプラン
に組み込むことで、非決定性に対処。この場合の問題: どのようにして条件付きプラ
ンを作成するか
• 例題: 掃除機の世界
非決定性を捉えるよう、Strips 言語を拡張: 効果に選言を導入— 複数の結果の可能
性を許す
Action(Left, Precond: AtR, Effect:AtL∨¬ AtR)
• 条件付き結果 (conditional eﬀect) : when 条件 : 効果
Action(Suck, Precond: , Effect: (when AtL: CleanL) ∧ (whenAtR: CleanR))
選言的かつ条件付き記述の例
Action(Suck, Precond: , Effect:AtL ∨ (AtL ∧ when CleanL: ¬CleanL))
• 条件付きステップ (conditional step): if 条件 then plan A else plan B
• 非決定的プランニング問題—自然を相手にしたゲーム: 行為の結果がどうなるかに関
係なく、うまくいく条件付きプランを作成しなければならない
条件付きプランニングのための「修正」を施したミニマックスアルゴリズムを用い
る—max と min ノードを or と and ノードとし、単なる一つの移動ではなく条件付
きプランを与える: or ノードのプランはどのようなことが起きても選択される行為、
and ノードのプランは個々の結果に対するサブプランを示す if–then–else ステップの
連続入れ子状態
部分観測環境における条件付きプランニング
本節では完全観測環境ではなく、部分観測環境を扱う
• 部分観測プランニング問題の初期状況のモデル化—エージェントは実際の状況の一部
だけを知っている— エージェントの信念状態を記述する方法である状態集合 (state
set) を用いる
• 掃除機世界において、エージェントは右の区画にいてその区画がきれいであることを
知っているが、別の区画についてはごみの状態は分からないとする。このとき、左の
区画はきれいか、汚いかのどちらか。この信念状態を図 12.12 の A で示す
• 「別な二重マーフィ─」掃除機世界: 掃除が終わってエージェントが部屋を離れたと
きにごみが時々残っていることがあるような世界
• 完全観測可能な世界ならば、「区画の移動は左から右、ごみがある限り掃除を行い、
両方の区画がきれいになるまでこれを続ける、最後に左の区画にいる」という解を
作れる—局所的にしかごみの存在を検知できないのなら、このプランは実行不能—
「両方の区画がきれい」かどうかが判定できないから
8
• and-or グラフの作り方: 信念状態 A から Lef t に移動した結果 (他の行為は無意味)
を示す—掃除機が移動した後、ごみを残す可能性があるので、可能な世界は 4 通り (B
と C に 2 つずつ)。得られるセンサー情報から二つの異なる信念世界が構築される。
• まとめ: 非決定的で部分観測可能な環境では信念状態の and-or グラフを作れる。そ
れゆえ、And-Or-Graph 探索という、完全観測可能な環境と同じアルゴリズムが使
える
別な見方：エージェントの「信念」状態は常に完全観測可能。
「標準的」な完全観測問題解決は、どの信念状態もただ一つの物理状態を含む特殊な
ケース、とみなせる
• 残る問題—信念状態の表現、センサーの働き、行為の記述
• 信念状態の三つの基本的な選択
1. 完全状態記述の集合として—例えば図 12.12 の初期信念状態は次のように記述
される: {(ArtR ∧ CleanR ∧ CleanL), (AtR ∧ CleanR ∧ ¬CleanL)}
簡単だがコストが高い—状態を表す n 個のブール命題があるとすれば、一個の
信念状態は O(2n ) 個の物理状態記述を含み、それぞれの物理状態記述はサイズ
O(n)。断片的にしかエージェントに知識がなければ、より多くの可能な状態を
含むので、指数関数的に増える1 。
2. 信念状態における可能な世界の集合だけを正確に表す論理文として—例えば初
期状態は AtR ∧ CleanR と表される
同じ信念状態を表す文は多数あるので、グラフ探索では状態検査が繰り返し必
要で、そのために一般的な定理証明が必要—何らかの標準形があるとよい (例え
ば命題論理の連言標準形)。
開世界仮説のもとでの標準的な状態表現に相当
3. エージェントの知識を表す「知識命題」として。例えば初期状態は、K(AtR) ∧
K(CleanR) と表される。
ここで、K は「知っている (Knows that)」を表し、K(P ) はエージェントが P
が真であることを知っていることを意味
閉世界仮説を用いると、このリストにない命題は偽と仮定される
2 番目と 3 番目の選択肢はほぼ等価であるが、3 番目の知識命題を採用— 我々は閉世
界仮説ものとでどのように Strips 流の記述をするかを知っており、またセンサーの
記述がやりやすい
• これらの選択肢において、命題記号は次の 3 通りのいずれか: 肯定 (positive)、否定
(negative)、未知 (unknown) —この方法だと 3n 個の可能な信念状態がありうる2 。
n
物理状態は 2n なので、信念状態は 22 通り3 。これは 3n よりも大きい。—そこで選
択肢 2 と 3 は信念状態の表現としてはよく節約されている。そしてこれは最低限のサ
イズと信じられている—最悪の場合、 O(2n ) ビットが表現に必要。
1
ブール命題が n 個あるので、一個の信念状態の要素は n 個の論理式の連言。そして、それぞれの真理値
の組合せは O(2n ) ある。一番少ない表現は、すべてのブール命題の真理値が分かっている状況であり、一番大
きな表現は、何も分かっていない状況。
2
命題の真理値は、真、偽、未知の 3 通りあり、全体で n 個の命題があるから、全体で 3n 通りある。
3
物理状態は真か偽の値を取り、 n 個あるので、全体で 2n 通り。信念状態は知っているか知らないかとい
n
う 2 通りであるので、22 通りある。
9
• センサーについて。二つの選択肢
1. 自動知覚 (automatic sensing)—どの時点でもエージェントは可能な知覚情報を
得る
2. 能動知覚 (active sensing)—特定のセンサー行為をしたときのみ、知覚情報が得
られる
• 知識命題を用いた行為の記述。「別な二重マーフィ─」掃除機世界で自動局所ごみセ
ンサーが働いているとし、Left にエージェントが移動: 規則によればエージェントは
立ち去った区画にごみを残すことがある。物理効果としてこれは選言的だが、知識と
してはエージェントの知識から CleanR を削除することに相当。また Left に移動し
たので CleanL が真かどうかも、 AtL と同様に分かる:
Action(Lef t,Precond:AtR,
Effect:K(AtL) ∧ ¬K(AtR) ∧
when CleanR : ¬K(CleanR)∧
when CleanL : K(CleanL)∧
when ¬CleanL : K(¬CleanL))
ここで when 条件が知識命題ではなく普通の命題であることに注意— 行為の結果は
実世界に依存。
すべてが知識命題であったとすれば、どのようにその真理値を調べたらよいか？—
エージェントが K(α) を知っていれば、実世界でも α は真。
• (自動知覚に対して) 能動知覚の場合。Left にエージェントが移動した後、その区画
が汚いかどうかを知るために CheckDirt を用いる:
Action(CheckDirt, Effect: when AtL ∧ CleanL : K(CleanL)∧
when AtL ∧ ¬CleanL : K(¬CleanL)∧
when AtR ∧ CleanR : K(CleanR)∧
when AtR ∧ ¬CleanR : K(¬CleanR))
能動知覚において Left の後 CheckDirt をした場合、自動知覚における Left と同様、
二つの信念状態を導くことは簡単に示せる (練習問題)
• ここまで述べてきた、状態空間の and-or 探索に基づく条件付きプランニングに対
するアプローチ: 古典的プランニングよりも困難な複雑性クラスに属す—古典的プラ
ンニング問題は NP、条件付きプランニングはそれより難しい
問題を簡単化する唯一の方法は、プランニングフェーズに起きる偶発的なもののうち
いくつかは無視し、それらが実際に起こった場合にだけ対処
12.5
実行モニタリングと再プランニング
• 実行モニタリングエージェント: 計画通りに物事が進んでいるかどうかを調べるた
め、知覚したものを調べる—非限定不確定性
2 種類の実行モニタリング:
1. 行為モニタリング (action monitoring): 次の行為が実施されることを確認する
よう、環境を調べる
10
2. プランモニタリング (plan monitoring): 残りのプラン全体を確認
• 再プランニングエージェント: 何か予期せぬことが起こったときの対処法を知ってお
り、ゴール到達のための新プランを提案するためにプランナエージェントを呼ぶ
• 実行モニタリングと再プランニングの一般的な戦略: 図 12.13
プランニングエージェントはゴールを目指して出発、それを達成するための初期プラ
ンを作成。一つずつ行為を実行。
function Replanning-Agent (percept) returns action
static: KB, 知識ベース
plan: plan, 初期値は {}
whole plan: plan, 初期値は {}
goal: 目標
Tell(KB, Make-Percept-Sentence(percept, t))
current ← State-Descrption(KB, t)
if Preconditions(First(plan)) が KB で現在のところ真でない then
candidates ← Sort(whole plan) — current への距離でソート
find 状態 s in candidates such that
f ailure = repair ← Planner(current, s, KB)
continuation ← s から始まる whole plan の末端
whole plan ← plan ←Append(repair, continuation)
return Pop(plan)
図 12.13 行為モニタリングと再プランニングをするエージェント
再プランニングエージェントは行為モニタリングを行う—プラン plan の行為を行う
前に、どの前提条件も満たされていることをセンサーによって確認。満たされていな
ければ、whole plan 上のあるポイント (repair) に戻る一連の行為を再プランニング
し、そのポイントに戻る
図 12.14—プロセスの図式的な例
• 再プランニングによって、椅子とテーブルの色を合わせる例題を考える—完全観察環
境を仮定。初期状態では椅子は青、テーブルは緑とし、青ペンキと赤ペンキの缶があ
るとする。
問題記述:
Init(Color(Chair, Blue) ∧ Color(T able, Green)
∧ContainsColor(BC, Blue) ∧ P aintCan(BC)
∧ContainsColor(RC, Red) ∧ P aintCan(RC))
Goal(Color(Chair, x) ∧ Color(T able, x))
Action(P aint(object, color),
Precond:HaveP aint(color)
Effect: Color(object, color))
Action(Open(can),
Precond:P aintCan(can) ∧ ContainsColor(can, color)
Effect: HaveP aint(can))
エージェントのプランナがたてるべきプラン: {Start; Open(BC); P aint(T able, Blue); F inish}
11
エージェントがテーブルの一部を塗り損ねて Finish の前提条件が満たされていない
と知覚した場合は、 whole plan 上で目的の位置をとらえ、一連の行為を修正して目
標を達成する
• 行為モニタリングは時に知的でない行為を導く— 赤で塗り始めたとしたとき、その
量が足りない場合、椅子を塗ってからしか足りないことい気づかない
本当にすべきことは、残りのプランがうまく行かない状態になったときに失敗を検出
すること—プランモニタリング (plan monitoring): 残りのプランすべてが成功する
ための前提条件を調べることで問題に対処
• プランモニタリングの修正—プランの各ポイントに、残りのプランが成功するため
の前提条件の注釈をつける
• 部分観測環境の場合: エージェントが間違いを発見できなければうまくいかない、「前
提条件を調べる」には知覚行為の実行が必要のため、プランニング時間や実行時間に
プランされていなければならない
• 未知の前提条件や効果によって失敗する場合 (例: 間違ったカードキーで部屋を開け
ようとする場合) の解決策: 同じ計画を繰り返すのではなく、可能性のある修正プラ
ンの中からランダムに選択する—一般的には多様性のある修正プランが役立つ
• 失敗する場合の別な解決策: 学習 (learning)。
• 再プランニングエージェントの欠陥: 実時間環境では遂行不能、複雑な環境では持続
不能
12.6
連続プランニング
• 環境の中で持続可能なエージェントの設計— 常に変化するゴールの定式化、プラン
ニング、行為という一連のフェーズを通して存続: 連続プランニングエージェント
(continuous planning agent)
• 連続プランニングエージェントは、実行可能なプランの部分実行、未解決な前提条件
の充足や矛盾解消のためのプラン修正、常に世界をモニターし、たとえ計算中であっ
ても世界モデルを新たな知覚を考慮して更新
• 例による Continuous-Pop-Agent(連続 POP エージェント) の説明: 意図的行為を
表現する半順序プランを用いる。簡単のため、完全観測環境を仮定
• 11.1 節の積み木の世界からの問題を用いて説明 (図 12.15(a))。必要な行為は M ove(x, y)
— 積み木 x を積み木 y の上に x も y も clear なら (上にものが乗っていなければ) 移す。
そのアクションスキーマ:
Action(M ove(x, y),
Precond: Clar(x) ∧ Clear(y) ∧ On(x, z)
Effect: On(x, y) ∧ Clear(z) ∧ ¬On(x, z) ∧ ¬Clear(y)
• エージェントは自分でゴールを記述—ここでは On(C, D) ∧ On(D, B) を達成するよ
う命令されたとする。これによりプラン作成を始める—増進的 (incremental) なプラ
ン作成。プラン作成ごとにその行為として N oOp を返し、知覚情報を検査しなおす。
12
• 知覚情報には変化なく図 12.16 に示すプランを作成すると仮定。M ove(D, B) と M ove(C, D)
という行為の前提条件は Start で充足されているがその間には順序制約がある—
Clear(D) の条件が M ove(D, B) 達成に必要だから。
• エージェントが行為する前に、外部（例えば人間）からの介入を想定。図 12.15(b) に
なったとする。エージェントはこれを知覚し、Clear(B) と On(D, G) が現状態で真
ではないことを認識し、現状態のモデルを更新。M ove(D, B) 行為の前提条件が無効
になり、プランから削除される—新しいプランが図 12.17。
• 因果リンクの拡張 (extension): 前のステップにより新たな矛盾が引き起こされるこ
となく条件が満たされる場合は、Start から Finish への直接リンクで置き換える (注:
Start はいつでも現状態を表す)
• 冗長ステップ (redundant step)—いかなる因果リンクも与えない行為—はプランから
除かれる。その結果が図 12.18。
M ove(C, D) が実行可能なので、エージェントがこれを行う。しかし、間違って A の
上に C を落としてしまう
エージェントは未解決条件のためのプラン作成を行う。M ove(C, D) はゴール条件を
満たし、その前提条件は Start からの新たな因果リンクで充足される—新たなプラン
は図 12.20
ふたたび M ove(C, D) が実行可能になり、実行の結果図 12.15(d) に示すゴール状態
に至る。
• 連続プランニングは部分順序プランニングににている。各試行では、修正を必要とす
るプラン (つまり欠陥プラン (plan ﬂaw)) を見つけ、修正する。
POP アルゴリズムは、未解決前提条件と因果の矛盾という二つの欠陥プランを序興
するアルゴリズムとみなせたが、この連続プランニングは以下のような広い欠陥プラ
ンを対象とする:
– ゴールの欠如 (missing goal): 新たなゴールを Finish ステップに追加可能。
– 未解決の前提条件 (open precondition):新たな行為や既存の行為を選んで、 (POP
と同様に) 未解決の前提条件に因果リンクを付け加える
p
– 因果の矛盾 (causal conﬂict): 因果リンク A −→ B と効果 ¬p を持つ行為 C が
あったとすると、この矛盾を解消するよう (POP と同様に) 順序制約や変数制約
を加える
p
– 不支持リンク (unsupported link): 因果リンク Start −→ A があり、p がもはや
Start で真でなければ、このリンクを除去する
– 冗長行為 (redundant action): 行為 A が因果リンクを与えなければ、この行為
と関連するリンクを除去
– 非実行行為 (unexecuted action): F inish 以外の行為 A の前提条件が Start で
充足され、他に (Start 以外の) 行為がその前になく、それと矛盾するような因
果リンクがなければ、 A とその因果リンクを除去し、これを実行すべき行為と
して返す
– 不要な歴史的ゴール (unnecessary historical goal): (すべての因果リンクが Start
から F inish に直接つながっているように) 未解決の前提条件も行為もプランに
13
なければ、現在のゴールは達成されている。そこで、ゴールとリンクを除去し、
新たなゴールの作成を許す。
図 12.22 が連続 POP エージェントのアルゴリズム。「知覚、欠陥除去、行為」のサイ
クルをもつ。
function Continuous-POP-Agent (percept) returns action
static: plan, 最初は Start と Finish だけをもつプラン
action ← NoOp (これがデフォルト)
Effect[Start] =Update(Effects[Start], percept)
Remove-Flaw(plan) //更新行為
return action
図 12.22 連続 POP エージェント
12.7
マルチエージェントプランニング
• 単一エージェント環境 (single-agent environment) vs. マルチエージェント環境 (multiagent environment)
• 協調的 (cooperative)、競争的 (competitive)
協調: 共同ゴールとプラン
• ダブルスのテニスにおけるチームプランニングを例に— 同じチームの二人は「試合
に勝つ」という共同ゴールを持つ
ゲームのある時点で自陣に打ちこまれたボールを打ち返し、少なくとも一人はネット
でカバーするという共同ゴールをもつと仮定。図 12.23 にマルチエージェントプラン
ニングとして表現
Agents(A, B)
Init(At(A, [Lef t, Baseline]) ∧ At(B, [Right, N et])∧
Approaching(Ball, [Right, Baseline]) ∧ P artner(A, B) ∧ P artner(B, A)
Goal(Returned(Ball) ∧ At(agent, [x, N et]))
Precond: Approaching(Ball, [x, y]) ∧ At(agent, [x, y])
P artner(agent, partner) ∧ ¬At(partner, [x, y])
Effect: Returned(Ball)) Action(Go(agent, [x, y]),
Precond: At(agent, [a, b])
Effect: At(agent, [x, y]) ∧ ¬At(agent, [a, b]))
図 12.23 ダブルステニス問題
• 記法の注意: Agents(A, B) — 二人のエージェント A, B
マルチエージェントプランニング問題の解は、個々のエージェントの行為からなる
「共同プラン (joint plan)」で、それを行ってゴールが達成されるもの。例:
Plan 1:
14
A: [Go(A, [Right, Baseline]), Hit(A, Ball)]
B: [NoOp(B), NoOp(B)]
両方のエージェントが同じ知識ベースを持ち、上記が唯一の解ならばうまくいく。し
かし、次もゴールを満たす別なプラン。
Plan 2:
A: [Go(A, [Left,Net]), NoOp(A)]
B: [Go(B, [Right, Baseline]), Hit(B, Ball)]
ここで、A がプラン 2、B がプラン 1 を選ぶとボールを打ち返すものがおらず、A が
プラン 1、B がプラン 2 を選ぶと二人は衝突する。
このように、正しい共同プランが存在してもゴールが達成されるとは限らない。「同
じ」共同プランに到達するために「調整 (coordination)」メカニズムが必要
マルチボディプランニング
• 共同プランの構築—マルチボディプランニング (multibody planning): いくつかの物
理的実体に行為を命令する単一の中央集権型エージェントが直面する本質的なプラン
ニング問題
• 半順序プランニングに基づく。
単一エージェントの場合に生じない問題: 環境が動的—他のエージェントによって環
境が変化する =⇒ 同期 (synchronization)
簡単化のため行為に要する時間は同じ、共同プラン上の個々の行為は同時に起こるも
のと仮定
個々のエージェントはどの時点でも NoOp を含む一つの行為を実行
• 共同行為 (joint action): 同時に起こる行為の集合
例: Plan2 の表現:
Go(A, [Lef t, N et]), Go(B, [Right, Baseline])
N oOp(A), Hit(B, Ball)
すべての可能な共同行為の集合に普通の POP アルゴリズムを適用してプランニング
することは可能であるが、サイズが大きすぎ、非効率
• 代替案: 個々の行為がどのように他の行為と相互作用するかを記述することで、暗黙
的に共同行為を定義する—実際に相互作用するのは少数なので効率的（なはず）
• Strips や ADL 行為記述に、同時発生行為リスト (concurrent action list) を追加拡
張してこれを可能にする
同時発生禁止制約の例:
Action(Hit(A, Ball))
Concurrent: ¬Hit(B, Ball)
Precond: Approaching(Ball, [x, y]) ∧ At(A, [x, y])
Effect: Returned(Ball)
15
同時発生行為の要求の例:
Action(Carry(A, cooler, here, there))
Concurrent: Carry(B, cooler, here, there)
Precond: At(A, here) ∧ At(cooler, here) ∧ Cooler(cooler)
Effect: At(A, there) ∧ At(cooler, there) ∧ ¬At(A, here) ∧ ¬At(cooler, here)
POP 半順序プランナとの違い
1. 時間順序関係 A ≺ B に加え「同時発生」「同時発生あるいはそれ以前」を意味
する A = B, A B の導入
2. 新しい行為が同時発生行為を要求するとき、プラン上の新たな行為が既存の行
為を用いて同時発生行為を具体化する
3. 禁止された同時発生行為は追加制約。個々の制約は衝突する行為を前か後ろに
移すことで解決される
調整メカニズム
• 協定 (convention、規約とも): 共同プランの選択に関する制約。共同プランの同意を
確実にする方法の一つ。
• 問題領域特有な実施法: 行為記述から協定違反を排除する
• 進化の過程で発生する協定の例: コロニーに住む昆虫の遺伝構造、取りの群れ行動
• boid の行動ルール: 分離、凝集、整列
• コミュニケーション: 実行可能な共同プランの共通知識を得る手段
• プラン認識 (plan recognition): 行動プランの最初の部分を一人のエージェントが実
行することで、他のエージェントに好ましい共同プランが伝えられる—単一行為ある
いは一連の短い行為によって共同プランを決定
• 成功する共同プランへの到達可能性—エージェントの設計者に依存する場合 (プラン
の前に成功することを示すべき)、もしくはエージェント自身に依存する場合 (他の
エージェントの推論を考慮しながら自分のプランの効果性を示すべき)
• 共通意図 (joint intention)
競争
• 競争 (competition) 状況: 矛盾する効用関数を持つ複数のエージェントがいる環境。
例: チェスのようなゼロ和ゲーム
• 競争環境のエージェントのタスク: (a) 他のエージェントの存在の認識、(b) 他のエー
ジェントの可能なプランの計算、 (c) 他のエージェントのプラント自分のプランとの
相互作用の計算、 (d) これらの相互作用から最良の行為を選択
他のエージェントのプランにおけるモデルが必要、共同プランは不要
• 図 12.10 の条件付きプランニングアルゴリズムはエージェントが成功か失敗かだけ
に関心がある競争的状況に適用可能。「コスト」を考慮する場合はミニマックス法が
適切。
16
12.8
まとめ
略。自分なりのまとめを作ってみよ
文献と歴史ノート
1. 連続時間のプランニングは Deviser (Vere, 1983) が最初の使用。プラン上の時間
の表現問題は Forbin システム (Dean et al., 1990) で取り組む。Nonlin+(Tate &
Whiter, 1984) と Sipe(Wilkins, 1988, 1990) は制限された資源配分の推論を扱う。
O-Plan (Bell & Tate, 1985) は HTP プランナ、時間と資源に関する制約の表現を
有する—いろいろなところで採用された
2. 1980 年代後半に時間プランニング研究が復活—Sapa(Do & Kambhampati, 2001) と
T4(Haslum & Geﬀner, 2001) は時間と資源を持つ行為を扱うためにヒューリスティ
クスと前向き状態空間探索を使用。
3. 航空宇宙工学におけるスケジューリングの歴史—T-Sched (Drabble, 1990), O-Plan
に基づく Optimum-AIV, Plan-ERS1, Spike. スペースシャトルの地上処理スケ
ジューリングシステム (Deale, et al., 1994)、リモートエージェント (Muscettola et
al., 1998)
4. Strips におけるマクロオペレータの学習 −→ 階層
階層の使用—階層プランニング (Fikes, Hart & Nilsson, 1972)、Lawaly(Siklossy &
Dreussi, 1973)
Abstrips(SAacerdoti, 1974) では抽象的階層の導入
HTN プランニングの基礎—Tate(1975b)、 Earl & Sacerdoti (1977)
5. 階層的プランニングのゴールの一つ — 一般化されたプランの形で前のプランニング経
験の再利用 −→ 説明に基づく学習 (explanation-based learning) は Soar や Prodigy
などに応用
事例に基づくプランニング (case-based planning): 前に計算したプランを記憶し、そ
れに類似した問題の解決に利用する
6. 実環境における予測困難性と部分観測性—Shakey や Freddy 研究で認知、 McDermott (1978a) の Planning and Acting で注目
7. 条件付きプランニングの概念を初期のプランニングでは認識していなかった—環境
の不確実性に即応する強制 (coercion) に頼る。例: Sacerdoti の Noah
8. 順応プランニング (conformant planning): GOldman & Boddy (1996) が導入、世界
を既知の状態に強制することで不確実性を扱うセンサーなしプランナを対象。セン
サーなしプランは「センサあり」でも有効
順応グラフプラン (Conformant Graphplan: CGP)—Smith & Weld (1998) による
Ferraris & Giunchiglia (2000)、Rintanen (1999) は SAT プランに基づく順応プラン
ナの開発
Bonet & Geﬀner (2000) は信念状態空間におけるヒュウ─リステイック探索に基づ
く順応プランナ
17
HSCP (Bertoli, Cimatti & Roveri, 2001a): 信念状態を表すために二部決定グラフ
(binary decision diagram: BDD) を使用した CGP よりもかなり早い信念状態に基づ
くプランナ
9. Warpplan-C (Warren, 1976): 条件付き行為を用いた初期のプランナ
10. 条件付きプランニングと自動プログラム合成との関係
密接な関係があるが、ロボットなどの行為の実行コストと計算機命令の実行コストと
の間に差があり、別々の研究
11. 歴史的には、古典的プランニングアルゴリズムが、不確実性を伴う問題領域に対処す
るために拡張されてきた: 検索に基づく技術は信念空間における探索へ、 SATplan
は確率的な SATplan と限量化されたブール論理のプランニングへ、半順序プラン
ニングは UWL, CNLP, Cassandra へ発展。Graphplan はセンサグラフプランや
SGP に発展したが、完全確率 Graphplan は未開発
12. 実行モニタリングの本格的な扱いは Shakey を制御するために Strips プランナを用
いた Planex が最初
Nasl プランナ (McDermott, 1978a) は実行とプランニングを統合、複雑な行為の推
論のために定理証明を利用
13. Sipe(System for Interactive Planning and Execution monitoring) (Wilkins, 1988,
1990): 再プランニング問題を系統的に扱う最初のプランナ
14. Ipem (Integrated Planning, Execution, and Monitoring )(Ambros-Ingerson & Steel,
1988): 半順序プランニングと実行を統合した最初のシステム
Continous-POOP-Agent は Ipem, Puccini, Cypress のアイデアの統合
15. 即応プランイング (reactive planning): 内部状態を持つ反射エージェント、条件-行為
ルールを用いて実装。半順序プランニングでは実世界エージェントで効果的な行為を
早く生成することができないと考えられていたための代案
Brooks (1986) の包摂アーキテクチャ(subsumption architecture): 階層的な有限状態
機械により、歩行ロボットの制御などを行う
16. 普遍的プラン (universal plan) (Schoppers, 1987): 即応プランイングのためのテーブ
ル参照手法、マルコフ決定仮定で用いられるポリシーの再発見。
17. ハイブリッドアプローチについて: PRS や RAP などは、適切な階層により、即応的
な反応時間と複雑な長期プランニングの行為を扱う
18. マルチエージェントプランニングについて:長い歴史と高い人気。Konolige (1982) は
一階述語論理による定式化、 Pednault (1986) は Strips スタイルの記述
共同意図は、伝達行為の研究に基づく
19. マルチエージェントのレビュー: Weiss (1999)
練習問題
18

Download Report