The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

1A1-04

状況的行為に基づいた近似計画手法

Post-hoc Reconstruction of Plans by Situated Actions∗1

イ セリン∗1

久保田 孝∗2中谷 一郎∗3

Serin Lee

Takashi Kubota

Ichiro Nakatani

東京大学大学院

The University of Tokyo∗2∗3

宇宙航空研究開発機構・宇宙科学研究本部
JAXA-Institute of Space and Astronautical Science

The approaches to make an agent generate intelligent actions in the AI ﬁeld might be very roughly categorized
into two ways—the classical planning and situated action system. However, each system actually has its ownapplication ﬁeld as well as its strength and weakeness, and, in particular, the application of the situated action
system is usually restricted to the ﬁeld such as the navigation of mobile robots which is not directly related to
the logical problem. This paper proposes a novel action generator to situatedly extract a set of actions from therelaxed logical space, which is likely to help to achieve the goal at the current situation. After performing theaction set, the agent should recognize the situation for deciding the next likely action set. The empirical result insome planning domains shows that the quality of the resultant path to the goal, post-hoc reconstruction of plans, ismostly acceptable as well as deriving the fast response time. Therefore, this approach could make the agent suchas mobile robots and web agents in the dynamic environment respond to the environment fast.

1.

はじめに現状況で実行できる行動から，目的の達成に要求されると見なされる行動のみを抽出して, それを実行するという過程を繰り返せば最終的に目的が達成できる.

エージェントは問題解決，又は目的達成のため自ら適切な行動を生み出すことが要求される．このような行動の発生の手法を提案したり, 又は生物でのそのような現象を説明することを目的に多くの研究分野が発達してきた. 特に人工知能 (AI)分野では大きく分けて次の二つのアプローチで研究が進んできた.

引き続き, 第 2 章では最近のプランニング手法について簡単に紹介し, 第 3 章に上述の提案について詳しく述べる. 第 4 章
では, 提案されたアプローチの実験結果を示す.

プランニング 目的達成までの全過程を決める手法であり, 状況と行動に関する推論から目的までの一貫した行動パターン, 即ち計画を立てる.

2.

プランニング

2.1

Notation

状態 S は論理的な要素 (事実) の有限な集合から構成されている. プランニング問題は P = (O, I, G) である. ここで，O はエージェントのアクションに関する記述, I は世界の初期状態に関する記述, G はエージェントに与えた目的に関する記述を示す. アクション o ∈ O は STRIPS アクションであり，o = {pre(o), add(o), del(o)} で定義される．ここで，pre(o)は行動 o の前提条件, add (o) は o が状態に加える要素, del (o)は状態から消去される要素を示す. 一つの STRIPS アクションの結果は前提条件が満たされれば, 即ち pre(o) ⊆ S の場合に Result(S, < o >) = (S ∪ add(o)) \del(o) になる. 前提条
件が満たされない場合は定義されない.
現時点で実行できる行動によって現状態に加えられる要素の中，目的の達成に要求されると見なされる事実の集合を Fagと示す．ここで, Fag を形成する行動の集合 Aag は現時点で同時に実行可能な行動だけを含んでいるものではない．即ち, 互いに排他的な行動も含む可能性があるため，Aag の中で矛盾がなく同時に実行できる行動のみの集合を別に L ⊆ Aag と定義する．即ち, エージェントは毎状況から L を抽出し, L の要素を実行することを繰り返せば最終的に目的の状態に到達できると期待される．

状況的行為 (Situated action) プランニングの抽象的な推論に対する反発として提案されたとみなすことができ, 現状況だけを考慮して行動を生み出す [Lucy 87]．
プランニング手法は現状態から目的を満たす状態までの経路をエージェントの行動に関する論理的な推論から求める．一
般的にそのような推論は膨大な情報とリソースを必要とするため，計画を立てるためには比較的長い時間を必要とする．従って，動的な環境では状態の変化に追い付かない場合が生じる．
一方, 状況的行為に基づいた手法は抽象的な推論より現状況の考察を重視するため，一般的に行動を引き出す時間が速い．従って，未知の動的な環境のように将来の予測が難しい場
合には, プランニングより高い状況性を期待できるが，目的までの一貫した行動のパターンを引き出すことは難しい．また，実際にはこのような概念を応用する際の様々な難しさのため，プランニング手法が対象としている論理的な問題を扱えない．
従って，このようなアプローチは主に論理的な問題から幾何学的な問題に置き換えられる移動ロボットのナビゲーションに適用されている [Arkin 98][Brooks 86]．
本研究では，動的な環境で複雑な論理的問題を解くことができるエージェントの開発を目的としている．そのため，上記の二つのアプローチを次のように兼ね合わせた手法を提案する.

2.2

探索による計画手法

1969 年 Green の手法以来様々な計画アルゴリズムが提案されてきた．その中で, 最近のほとんどの計画手法は O, I, G から作られたプランニング空間で探索を行うことによって計画を引き出すアプローチを取っている．このような計画手法の中でGraphplan の例を図.1 に示す [Weld 99][Blum 97]．

連絡先: イ セリン, 宇宙科学研究本部中谷研, 〒 201-0015 神奈川県相模原市由野台 3-1-1, tel: 042-759-8311, e-mail:srlee@nnl.isas.ac.jp1

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005
• 他のレベルに対しては，P  = (O , F1 , G). ここで，O ={(pre(o), add (o), ∅) | (pre(o), add (o), del (o)) ∈ O},
F1 = F1 \del(oi ) (∀oi ∈ A0 )• ただ，o ∈ level i なら, o は level j > i には登場しない．
• 最後の状態レベルは G の全ての要素 (事実) を含んでいる．

最近には Bonet によって提案されたヒューリスティック探索によるアプローチ，即ち近似化されたプランニング空間からヒューリスティックを求めて，元の空間で高速に探索を行う手法が非常に優れたパプォーマンスを見せている[Bonet 01][Hoﬀman 01][Gerevini 02][Vidal 04].

状況的行為の導出

3.1

近似化された論理空間

L の抽出

4.

経験的な結果近似的な論理空間 R を作った後，最後の状態レベルに含まれている G の要素からレベル 0 に向かって，状態とそれを達成する行動，またその行動の前提条件を抽出する．前節で述べたように，アクションの実行を後に延ばすことは考慮しないため，ある事実を達成するアクションを抽出する時にはできる限り noop を選ぶ．もし，ある事実を達成する noop が存在しない場合には non noop からランダムに選べる．
このような noop first heuristic with randomly selected nonnoop によって抽出されたレベル 1 の事実の集合が Fag , それを達成するレベル 0 の行動の集合が Aag になる．
L は Aag の中から，他の行動を妨害しないものを選ぶことによって求められる．もし，そのような行動が存在しない場合には Aag または，A0 からランダムに行動を選べる∗2 .
しかし，このように L を Aag や A0 からランダムに選ぶことによって，エージェントは論理的空間での行き止まり (deadend) に収束することがある．本稿ではこのような行き止まりを含んでいる問題を考慮しない．また，G まで短い (効率的な)経路を取らない場合も生じる．特に与えられた G 自体に順番が存在する場合には非常に長い経路を取る可能性がある．しかし，近似的に目的の順番を分析し，プランナに並べ換えられた G を与えられる手法によって, この問題は多少解ける [Koehler 00]．

Figure 1: dinner date 問題のプランニンググラフ: プランニ
ンググラフとは有向グラフで, 一つのレベルは状態を示す集合とその状態から実行できるアクションの集合から構成されている. 従って, 最初のレベルの状態は現状態に, 最後のレベルは目標が達成できたと見られる状態に対応している. 細い線
は互いに排他的な関係 (mutex ; mutually exclusion relation)を示している. 以前のレベルの状態の要素は次の状態レベルにnoop(maintain action) を通じて伝播される. プランニンググ
ラフの作成は最終のレベルに G が非排他的に含まれた場合完了し, そのレベルからレベル 0 に向かって探索を行いながらプランを抽出する. もし, その探索の中に排他的な要素が含まれている場合, 前のあるレベルに戻って再び探索を行う.

3.

3.2

本稿では既存のプランニング問題に対して, 提案したアプ
ローチと他の二つの STRIPS プランナ—FF v2.3 と LPGtd(speed) との優劣を比較するため実験を行った. 提案したアプローチと二つのプランナは C で作成され，他の特殊なライブラリは使用していない．
しかし，提案したアプローチと他のプランナの目的が違うため，公平な比較の基準を探すことは難しい．
本稿では，提案したアプローチが目的達成まで L を抽出する時かかった時間，即ち，反応時間の平均と他のプランナが全手順を再プランニングを行わなず決めた時間を比較した．また，提案したアプローチによる事後解析的なプランの長さと，他のプランナが出したプランの長さも比較した∗3 ．
実験は，プランニングの研究で昔から使われてきた domainと最近のプランニング大会で使われた domain を合わせて, 四
つの domain—Block’s domain, Logistics domain, Satellitedomain, Rovers domain で行われた．このような domain は論理的空間で行き止まりを含んでいない．また，Block’s domain
は G 自体に順番が存在するため，この場合には Koehler のGAM(Goal Agenda Management) を，提案したアプローチに適用した [Koehler 00]．

論理空間から L を抽出するために本稿では次のような近似化を提案する．
目的達成のため，ある状況の要素をいつ実行すべきかは考慮しない．ただ，現在達成できる事実の中で，目的に到達するために必要な事実はどのようなものなのかだけを考慮する.

このような近似化では，現状態の後のある時点で実行できる行動によって加えられる事実の優先を求めていない．そのため，そのような行動の消去効果，即ち状態から消去する部分は考慮しない∗1 ．また，目的達成のため必要な事実をいつ実行するかを考慮しないため，一つの行動をどのようなタイミングで実行すべきかについても考慮しない．従って，行動は任意のある時点で一回だけ考慮する．本稿では，ある時点の状態から実行できるアクションをその時点の後に伸ばして実行する場合を考慮しない．
Fi と Ai をそれぞれプランニンググラフの事実レベル i とアクションレベル i で定義すると，上記の近似化は次のプランニング問題に関するグラフ空間で記述できる．

• F0 , A0 , F1 に対して，P = (O, I, G)∗2 実際に Aag ではなく，A0 から L を求めなければならない場合はあまり生じない. そのため，本稿では L を額率 ζ = 0.05 で A0から求める.
∗3 Schuman は計画を状況的行為の post-hoc reconstruction として考えた [Lucy 87]. 本稿でもそのような立場を取っている.

∗1 状態から消去される部分のため，行動の間や事実の間には様々な排他的な関係が生じる．例えば，ある行動の前提条件が他の行動の効果によって消去されると，二つの行動は現時点で排他的な関係になる.

2

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

100
FF
LPG-tdSituated Action Generator

FFLPG-td
Situated Action Generator

300

250

200
Plan length

Time (seconds)

1011501000.1500.01510152025

51015Problems (Blocks)

2025Problems (Blocks)

Figure 2: 時間とプランの長さ (Blocks problems)

1000

900
FF
LPG-tdSituated Action Generator

FF
LPG-tdSituated Action Generator

800

100

700

Plan length

Time (seconds)

600
10500

400

1300

2000.1

100

0.01

02

4

68

1012141618

202468

Problems (Logistics)

101214161820

Problems (Logistics)

Figure 3: 時間とプランの長さ (Logistics problems)

1000

600
FFLPG-td
Situated Action Generator

FFLPG-td
Situated Action Generator
500

100

Plan length

Time (seconds)

400
10300

12000.1
1000.010510152025

510Problems (Rovers)

15Problems (Rovers)

Figure 4: 時間とプランの長さ (Rovers problems)

32025

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005
100900FFLPG-td
Situated Action Generator

FFLPG-td
Situated Action Generator

800

700

10Plan length

Time (seconds)

600

1500

400

300
0.1

200

1000.01

0510152025

510Problems (Satellite)

152025Problems (Satellite)

Figure 5: 時間とプランの長さ (Satellite problems)[Arkin 98] Ronald C. Arkin, Behavior-Based Robotics, TheMIT Press, 1998

全ての実験は Intel Pentium4 の 1.7GHz, 768MB の Linux
2.6 で行った. また，制限時間は 200 秒に設定した．結果を図.2から図.5 に示す．
小さい問題に対しては，状況的行為による事後解析的なプランの長さは，既存のプランナが出したプランの長さと比較してもあまり差が出なかった．
大きい問題に対してはその差が少し大きくなった．しかし，提案したアプローチは使用するリソースが比較的少ないため，既存のプランナが解けない問題を解くことができた．例えば，ある Rover 問題に対しては，提案したアプローチが平均的に総メモリの 30%を使って問題を解いたが，他のプランナは 70%以上のメモリを使っても問題を解けなかった．

5.

[Brooks 86] Rodney A. Brooks, A robust layered control
system for a mobile robot, IEEE Journal of Robotics
and Automation, April, 1986
[Blum 97] Avrim L. Blum, and Merrick L. Furst, Fast Planning Through Planning Graph Analysis, Artificial Intelligence, 1997
[Bonet 01] Blai Bonet, and Héctor Geﬀner, Planning as
Heuristic Search, Artificial Intelligence vol. 129 (1-2),
2001

おわりに

[Hoﬀman 01] Jörg Hoﬀman, and Bernard Nebel, The FF
Planning Systems: Fast Plan Generation ThroughHeuristic Search, Journal of Artificial Intelligence Research 14 253-302, 2001

本稿では論理空間で状況的行為を引き出す手法を提案した．
提案したアプローチは，目的達成のためある事実をいつ実行すべきかは考慮せず，現在達成できる事実の中で，目的に到達するために必要な事実はどのようなものなのかだけを考慮することによって状況的行為を引き出すものである．
引き出された状況的行為を実行した後には，また状態を認識して状況的行為を引き出す過程を繰り返せば，問題が行き止まりを含んでいない限り，最終的に目的が達成できる．
様々な domain での実験結果は，少ないリソースを使用しながらも，環境の変化に瞬時に応じられることを示している．
また，状況的行為による事後解析的なプランの長さは，既存のプランナが出したプランの長さと比較しても受け入れられる程度であることがわかった．
また，提案したアプローチは，エージェントが動的な環境で複雑な作業を行う場合に適切であると思われるが，特に目的までの期待される経路が短く，状況自体が非常に複雑な場合に，優れたパプォーマンスを示すと期待される．我々の毎日の生活もこのような状況に近いであろう．
行き止まりを避けるために既存のプランナと共存する知能構造の開発などが今後の課題である.

[Gerevini 02] Alfonso Gerevini, Alessandro Saetti, and Ivan
Serina, Planning through Stochastic Local Search andTemporal Action Graphs in LPG, Journal of Artificiall
Intelligence Research, 2002
[Vidal 04] Vincent Vidal, A Lookahead Strategy for Heuristic Search Planning, AAAI-04, 2004
[Weld 99] Daniel S. Weld, Recent Advances in AI Planning,AI Magazine, 1999
[Nabeshima 01] Hidetomo Nabeshima, and Katsumi Inoue,
Planning Graph and SAT Planning, Journal of theJapanese Society for Artificial Intelligence, vol. 19, no.
3, 2001[Koehler 00] Jana Koehler and Jörg Hoﬀman, On Reasonable and Forced Goal Orderings and their Use in an
Agenda-Driven Planning Algorithm, Journal of Artificial Intelligence Research, vol. 12, 2000

References[Lucy 87] Lucy Suchman, Plans and Situated Actions - The
Problem of Human-Machine Communication, Cambridge University Press, 1987

4