STRIPS

ロボットの行動の順番を組み立てるプログラム

STRIPSは、ロボットに与えられた目標を達成するために、どの行動をどの順番で実行すればよいかを自動で見つけ出す問題解決プログラムです。名前は STanford Research Institute Problem Solver の頭文字から取られています。スタンフォード研究所(Stanford Research Institute)のファイクスとニルソンが、1971年に学術誌 Artificial Intelligence に発表した論文「STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving」で示しました。

プログラムに与えるものは3つです。いまの世界の様子、達成したい目標、そしてロボットが実行できる行動の一覧です。STRIPSはこれらをもとに、いまの様子から出発して目標が成り立つ様子にたどり着くまでの行動の並びを探し、その並びを答えとして返します。

世界の様子を論理式の集まりで表す

STRIPSは、ある時点での世界の様子を「世界モデル」と呼び、一階述語論理の論理式の集まりとして表します。一階述語論理は、記号を使って、「ロボットが部屋Aにいる」「箱1が部屋Bにある」のような物と物の関係や性質を厳密に書くための形式です。論文では、決まりどおりに組み立てられた論理式を wff(well-formed formula) と呼んでいます。

世界モデルは、その時点で成り立っている事実を並べた一覧だと考えると分かりやすくなります。ロボットが行動するたびに、この一覧の中身が書き換わっていきます。

オペレータを3つの部分で書く

STRIPSでは、ロボットが実行できる一つ一つの行動をオペレータと呼びます。オペレータには、それを実行したときに世界モデルがどう変わるかを次の3つの部分で書いておきます。

1つ目は前提条件(precondition)です。そのオペレータを実行する前に、世界モデルの中で成り立っていなければならない条件です。2つ目は削除リスト(delete list)です。実行したあとに成り立たなくなるため、世界モデルから取り除く論理式を並べます。3つ目は追加リスト(add list)です。実行したあとに新しく成り立つため、世界モデルに書き加える論理式を並べます。

説明のための例として、「ロボットが部屋Aから部屋Bへ移動する」というオペレータを考えます。前提条件は「ロボットが部屋Aにいる」と「部屋Aと部屋Bがドアでつながっている」です。削除リストには「ロボットが部屋Aにいる」を入れ、追加リストには「ロボットが部屋Bにいる」を入れます。このオペレータを実行すると、世界モデルから「ロボットが部屋Aにいる」が消え、「ロボットが部屋Bにいる」が加わります。「箱1が部屋Bにある」のように削除リストに載っていない事実は、何も書かなくてもそのまま新しい世界モデルに残ります。

変わらない事実を定理証明で導かずに済ませる

STRIPSの考え方は、それ以前に試みられていた方式と比べると分かりやすくなります。それ以前には、問題解決のすべてを定理証明で行おうとする方式がありました。定理証明とは、与えられた論理式から、ある論理式が成り立つことを規則に従って導き出す処理です。この方式では、行動の前後で世界がどう変わるかも、論理式として書いた公理から証明しなければなりません。

ファイクスとニルソンは論文の中で、この方式が「フレーム問題」(frame problem)のために行き詰まったことを挙げています。フレーム問題の元の意味は、行動によって変わらない事実まで論理で一つずつ書き下そうとすると、記述の数が行動と性質の組み合わせの数だけ増えてしまうという問題です。部屋を移動しただけで、箱の位置も、ドアのつながり方も、ほかのすべての事実も変わっていないことをそのつど証明しなければならなくなります。

そこでSTRIPSは、二つの処理を分けました。一つは、ある世界モデルの中で条件が成り立つかどうかを確かめる処理で、ここには定理証明を使います。もう一つは、オペレータを当てはめて世界モデルを作り替えながら、目標に届く行動の並びを探す処理です。世界モデルの作り替えは削除リストと追加リストで機械的に行うので、変わらない事実を証明によって一つずつ導く必要がありません。

違いを減らす行動から探す手段目標分析

どのオペレータから試すかを決めるために、STRIPSは手段目標分析(means-ends analysis)と呼ばれる探索の進め方を使います。論文は、この進め方がGPS(General Problem Solver)という先行の問題解決プログラムのものに似ていると述べています。

手段目標分析では、まず目標と、いまの世界モデルとの違いを見つけます。次に、その違いを減らせるオペレータを選びます。先の例で目標が「ロボットが部屋Bにいる」なら、追加リストにこの事実を持つ移動のオペレータが候補になります。選んだオペレータの前提条件がまだ成り立っていなければ、その前提条件を成り立たせることが新しい目標になり、同じ手順を繰り返します。目標と関係のあるオペレータから試すので、あらゆる行動の並びを片端から試すよりも探す範囲を絞り込めます。

このページで扱っていないこと

このページが根拠にした資料は、1971年のファイクスとニルソンの論文の要旨と前半の節です。STRIPSがその後どのような研究に受け継がれたのか、実際のロボットでどこまで使われたのかは、この資料の範囲を超えるため扱っていません。

学習の段階では、次の二点を押さえておくと理解しやすくなります。一つは、STRIPSが行動を前提条件・削除リスト・追加リストの3つで書き、世界モデルをその3つに従って書き換えることです。もう一つは、定理証明だけに頼る方式がフレーム問題で行き詰まったことを受けて、条件を確かめる処理と行動の並びを探す処理を分けたことです。