「箱を隣の部屋へ運んで」と言われたら、人はまず箱の位置や通り道を確かめるでしょう。ところが機械には、箱、部屋、移動、運ぶという操作の関係から教える必要があります。さらに、どの順序で動けば目的を達成できるかも決めなければなりません。
初期の人工知能が発展させた探索や計画は、この問題に取り組む技術でした。状態を記号で表し、許された操作で状態を変え、目標までの道筋を求める。後の学習型AIと見た目は違いますが、「候補を作り、良い候補を選ぶ」という発想は、現在のゲームAIや推論システムにも受け継がれています。
答えを計算する代わりに、答えへ至る道を探す
掛け算なら、決まった計算手順を進めれば答えに着きます。一方、パズルでは、ある操作が後で行き詰まりを生むことがあるでしょう。今の配置から可能な操作を考え、その先の配置からまた操作を考える。この分岐をたどることが、探索の基本です。
たとえば、三つの箱を指定の場所へ動かす課題を考えます。赤い箱を先に動かすと青い箱への通路を塞ぐなら、赤い箱を動かせるというだけでは不十分。青い箱を先に移し、その後で赤い箱を置くといった順序が必要になります。AIにとって重要なのは、個々の操作の正しさと、操作列全体の成功を区別することなのです。
探索では、現在の状況を「状態」、一つの操作による変化を状態間の移動として扱います。すべての問題を本物の迷路に変えるわけではありません。証明の途中の式、ゲームの盤面、ロボットの位置も、問題に合わせた状態として表せるという意味です。
候補が10通りなら、10手先で100億通り
総当たりの弱点は、分岐が重なることです。説明用に、どの段階でも選択肢が10通りあり、途中で重複や行き止まりがないとしましょう。1手先は10通りでも、2手先は100通り、10手先の操作列は100億通りになります。これは実在のAIの性能値ではなく、分岐の増え方を示す単純な計算例です。
コンピュータを少し速くしただけでは、この増え方に追い付けない場合があります。処理速度を10倍にしても、この条件なら探索を1手深くするだけで使い切る。小さなパズルが解けたから、大きな問題も同じ方法で解けるとは限らない理由がここにあります。
そこで必要になるのが、ヒューリスティックです。必ず正しい答えを直接教える規則ではなく、調べる候補の有望さを見積もる手がかり。地図上の直線距離を使って目的地に近そうな方向を優先する、といった発想が典型になります。
重複や枝刈りがない仮定で、10の手数乗を計算した例です。実測の性能値ではありません。
遠回りも必要になる、ヒューリスティックの役割
目的地に近づく方向だけを選べばよいなら、探索は簡単です。けれども川に橋が一つしかなければ、いったん目的地から離れて橋へ向かう必要があるでしょう。目先の近さと、最後までの道の短さは一致しません。
有望な道を優先しても、他の道をすべて捨てる必要はありません。ここまでの費用と残りの見積もりを組み合わせ、後から別の候補へ戻れる探索法もあります。さらに、見積もりに一定の条件を課せば、最短経路を保証できる場合もある。単なる勘で選ぶのではなく、計算を減らしながら何を保証するかまで設計するのです。
この考え方は、学習型AIと競合するだけではありません。過去の例から学んだモデルを、有望さの見積もりに使うこともできます。探索そのものと、探索を案内する評価を分けることで、古い方法と新しい方法を組み合わせる余地が生まれます。
探索で使う地図に、何を含めるか
同じ道順探しでも、状態の定義を変えると別の問題になります。現在地だけを記録する地図なら、同じ駅に戻ってきた経路は同じ状態として扱えます。ところが乗換回数を減らしたい場合には、今どの路線に乗っているかも重要でしょう。
さらに、到着時刻によって次の便に乗れるかが変わるなら、時刻も状態へ入れる必要があります。現在地が同じでも、午前9時と午後11時では可能な行動が違う。必要な情報を省くと、短い道は見つかっても実際には使えない経路になるのです。
一方、関係のない情報をすべて含めれば、同じとして扱える状態が減り、探索は重くなります。通学経路を調べるのに、駅の広告の色まで毎回区別する必要はないでしょう。問題に必要な違いを残し、不要な違いを捨てる表現の設計が、探索の前にあるのです。
この点は学習型AIにも共通します。入力として何を見せるか、過去の情報をどこまで保持するかを決めると、区別できる状況の範囲も変わるでしょう。計算を速くする以前に、どんな世界の模型を計算へ渡しているのかが重要になります。
Shakeyがつないだ、見ることと行動の計画
SRIで1966年から1972年に研究されたShakeyは、移動するロボットに認識と計画を組み合わせた重要な例です。周囲の状況を捉え、目標に必要な行動を考え、実際に移動する。人が車輪の動かし方を一つずつ指示するだけの装置とは違う方向を示しました。
計画を作るには、操作の前提条件と結果を表す必要があります。「箱を押す」という操作なら、箱の近くにいることや、進む先に空間があることが前提になるでしょう。押した後は箱の位置が変わる。そのような記述を組み合わせて、現在の状態から目標の状態へ至る操作列を考えます。
ただし、計画に成功することと、現実で失敗なく動くことは同じではありません。床が滑る、箱の位置を見誤る、通路に人が入るといった変化があれば、計画の前提が崩れます。ロボット研究は、頭の中に相当する計算だけでなく、環境を観測し直す必要も突き付けたのです。
ELIZAの会話とSHRDLUの積み木世界
言語の分野では、異なる意味で「話せる」プログラムが登場しました。ジョセフ・ワイゼンバウムが1966年に論文で紹介したELIZAは、入力中の手がかりを見つけ、文の形を組み替えて応答する仕組みです。応答が会話としてつながることと、話題について豊かな知識を持つことが別だと示す例にもなりました。
たとえば「家族のことで悩んでいます」に対して「家族について教えてください」と返せば、人は話が通じたと感じるかもしれません。これは仕組みを説明するための例で、原論文の会話の転載ではありません。相手の言葉をうまく利用すると、内容の理解が限定的でも、会話の印象は自然になるのです。
一方、テリー・ウィノグラードのSHRDLUは、色や形のある積み木の限定された世界で、言語と対象の関係を扱いました。「赤い物体」や「その上」といった表現を、操作できる世界の状態と結び付ける方向です。ELIZAとSHRDLUを、単に昔のチャットボットとして一括りにすると、この大切な差が失われます。
閉じた世界での理解と、日常の常識
積み木の世界では、物体の種類、色、位置、可能な操作をあらかじめ絞れます。何が存在するかをシステムが把握できるため、言葉の指す先も決めやすい。これに対し、現実の「それを片付けて」には、捨てるのか、棚へ戻すのか、触ってよいのかという省略が含まれます。
人間同士なら、物の用途や相手の意図を使って不足を補うでしょう。機械にその前提をすべて書こうとすると、例外が次々に現れます。紙なら重ねられるが、濡れた絵は重ねてはいけない。コップは持ち上げられるが、中身をこぼさない持ち方が必要。操作名が同じでも、物と状況によって適切さが変わるのです。
さらに、行動で変わることだけでなく、変わらないことも扱わなければなりません。箱を一つ動かしたからといって、離れた棚の本まで移動するわけではない。この種の問題は、行動と世界の記述をめぐるフレーム問題につながります。データの不足だけでなく、何をどう表すか自体が難題でした。
記号的AIが残した、検査できる手順の価値
計画の途中で必要だった条件、証明に使った規則。記号に基づく方法では、こうした前提や操作を明示して追跡できます。説明があるから必ず正しいとは限りませんが、どこを調べればよいかという手がかりは残ります。
弱点は、現実を記号にする作業が重いことでした。見たことのない物体を画像から認識する問題と、認識済みの箱をどう動かすかという問題は、得意な方法が違います。後の学習研究は前者を大きく進めましたが、それで後者の計画や検査が不要になったわけではありません。
現在のAIが候補を生成し、外部の計算や検査を使い、結果を見てやり直すとき、そこには探索・計画の発想が残っています。初期AIは、現代AIに置き換えられただけの古い道具ではなく、能力を組み合わせるための設計原理も残したのです。