機械に行動を計画させるには、一つ一つの行動を先に書き表しておく必要があります。それを実行できるのはどういう状態のときか。実行した結果、状態のどこが変わるか。この書き方をはっきりさせたのが STRIPS です。そして、行動の並びを、人が普通の英語で頼めるところまで持っていったのが SHRDLU です。
| 用語 | 何のことか |
|---|---|
| プランニング | いまの状態（初期状態）から望む状態（ゴール）までを、実際に実行できる行動の並びとして求めること |
| STRIPS | スタンフォード研究所（SRI）で、動き回るロボットに行動計画を立てさせるために作られたプログラム。行動を「前提条件」と「削除リスト・追加リスト」で書き表す |
| SHRDLU | テリー・ウィノグラードが MIT で作った対話プログラム。画面の中の積み木の世界を相手に、人が普通の英語で打ち込んだ指示を実行した |
探索木・節点・展開・初期状態・ゴールという言葉は探索木と幅優先探索・深さ優先探索で、相手のいる対戦ゲームの探索はミニマックス法とαβ法・モンテカルロ法で扱っています。STRIPS も SHRDLU も第1次AIブームの時代のもので、その流れはAIブームと冬の時代にあります。
プランニングとは：行動の並びを機械自身に見つけさせる
いまの状態から、望む状態へ。その間を埋める行動の並びを機械自身に見つけさせることを、プランニングと呼びます。出発点にあたる状態が初期状態、たどり着きたい状態がゴールです。求める答えは、初期状態からゴールまで、実際に実行できる行動を順に並べたものです。人が日程や段取りを組み立てることは指しません。
この「実行できる」が、思っているより厳しい条件です。上から順に本当に実行できなければ、計画としては使えません。箱の前にいないのに箱を押すことはできませんし、押したあとは機械のいる場所も変わっています。一つ前の行動の結果が、次の行動を実行できるかどうかを決めています。
だから、並べる前に行動そのものを書き表しておく必要があります。一つ一つについて、あらかじめ決めておくのは次の2つです。
- それを実行できるのは、どういう状態のときか
- 実行した結果、状態のどこが変わるのか
STRIPS とは：行動を「前提条件」と2つのリストで書く
その形をはっきりさせたのが STRIPS です。もともとは、アメリカのスタンフォード研究所、SRI で、動き回るロボットに行動計画を立てさせるために作られたプログラムの名前でした。STanford Research Institute Problem Solver の頭文字をとっています。そのプログラムで使われた、行動を前提条件と結果で書き表すやり方も、STRIPS と呼ばれます。
STRIPS では、1つの行動を3つの部分で書きます。行動の名前、前提条件、そして結果です。前提条件は、その行動を実行できるのはどういう状態かを表します。結果はさらに2つに分かれます。その行動によって成り立たなくなることを並べたのが削除リスト、新しく成り立つようになることを並べたのが追加リストです。
部屋の中を動き回って物を運ぶ機械で書くと、こうなります。
| 内容 | |
|---|---|
| 行動 | ある物を、場所xから場所yへ押す |
| 前提条件 | その物が場所xにある／ロボットも場所xにいる |
| 削除リスト | その物が場所xにある／ロボットが場所xにいる |
| 追加リスト | その物が場所yにある／ロボットが場所yにいる |
この書き方には、もう1つ決めごとがあります。削除リストにも追加リストにも書かれていないことは、その行動では変わらない。箱を押しても部屋のほかのことはそのまま、とあらかじめ決めておきます。
箱を別の場所へ押したら、元の場所から無くなるのは当たり前じゃない？ なんで削除リストをわざわざ書くの？
人には当たり前でも、機械は書かれていないことを自分では消せません。「その物が場所xにある」を消しておかないと、押したあとも場所xと場所yの両方に物があることになってしまいます。
行動をこう書いておくと、探索木をたどる問題になる
前提条件を見れば、いまの状態でどの行動を実行できるかが分かります。2つのリストを見れば、その行動を実行したあとの状態が作れます。つまり、節点を展開できます。
そこまで書けていれば、あとは探索と同じです。いまの状態を節点にして、そこで実行できる行動の数だけ枝を分ける。枝の先には、その行動を実行したあとの状態がある。その木をたどって、ゴールの状態を表す節点にたどり着けばいい。計画を立てる問題が、木をたどる問題になりました。そう変えられるのは、行動を前提条件と2つのリストで書き表しておいたからです。
SHRDLU とは：積み木の世界に、普通の言葉で指示を出す
ここまでは、機械が何をするかの話でした。では、何をしてほしいかを、人のほうはどう伝えるのか。
SHRDLU は、1968年から1970年にかけて、テリー・ウィノグラードが MIT で作った対話プログラムです。相手にしたのは小さな世界でした。画面に表示された積み木や箱などの物と、それを動かす腕。あるのはそれだけです。実物ではなく、計算機の中に作られた世界です。人はそこへ、普通の英語を打ち込んで、指示や質問をしました。
SHRDLU は何ができたのか
やり取りを3つ挙げます。実際のやり取りは英語で、図と表の日本語は、その内容を日本語にしたものです。
| 人が打ち込んだ指示・質問（日本語訳） | SHRDLU の反応 |
|---|---|
| 大きい赤い積み木を持ち上げて | その上に載っていた緑の積み木をまずどけて、それから赤い積み木を持ち上げ、「はい」と答えた |
| ピラミッドをつかんで | この世界にはピラミッドが3つあったので、どのピラミッドのことか分からない、と答えて聞き返した |
| 箱の中には何が入っている？ | 青いピラミッドと青い積み木、と答えた |
1つめでは、緑の積み木をどけてくれ、とは言われていません。持ち上げるにはまずどける必要がある、というところを自分で補っています。3つめでは、いま世界がどうなっているかを中に持っていて、それを見て答えています。
指示に足りない行動を自分で補い、あいまいなら聞き返し、いまどうなっているかを答える。人が普通の言葉で機械に仕事を頼むやり取りが、1970年前後にここまで動いていました。
ここまでできたのは、世界が小さかったから
SHRDLU の世界に出てくる物は、積み木、箱、ピラミッド、それを動かす腕。起こりうることは、持ち上げる、載せる、どこかへ置く。物の種類も、起こりうることも、あらかじめ全部決まっています。だからこそ、打ち込まれた言葉が何を指しているのかも、その指示を実行すると世界がどうなるのかも、その中で確かめられました。
ウィノグラード自身も、後にこう書いています。限られた範囲の対話であれば、意味をかなりよく扱えた。けれども、積み木の世界の外にある、日常の常識にあたる知識まで書き表して、そこから判断することは、SHRDLU のやり方では足りなかった、と。
STRIPS の側にも、世界を単純にする前提がありました。行動を前提条件と結果で書けたのは、世界は誰かが行動しない限り変わらず、行動するのも一つの主体だけ、と決めていたからです。だからこそ、書かれていないことは変わらない、と決めておけました。
ポイント
世界を限っていたから、この2つはだめだった。そう読む必要はありません。この2つが相手にしていたのは、規則がはっきりしていて小さく作られた問題、トイ・プロブレムです。それでも、その小さな世界の中では、人が普通の言葉で出した指示どおりに機械が動くところまで、実際に到達していました。
まとめ
プランニングは、初期状態からゴールまでの、実際に実行できる行動の並びを機械自身に見つけさせることです。そのために行動を前提条件と削除リスト・追加リストで書き表すのが STRIPS で、書けていれば、状態を節点、行動を枝にした木をたどる探索の問題になります。
SHRDLU は、その行動の並びを人が普通の英語で頼めるところまで来ていました。足りない行動を補い、あいまいなら聞き返す。ただし、それができたのは、出てくる物も起こりうることもあらかじめ決まった小さな世界だったからです。
次は、第2次AIブームの中心、専門家の知識をルールとして持たせたエキスパートシステムを取り上げます。