動機

ノービッグ先生の略称PAIPと呼ばれる本は私にとってバイブルです。特に論理プログラミングの章とSchemeインタプリタ・コンパイラを作る章はボロボロに擦り切れるほど熟読しました。ところで本に収録されている初期の人工知能の題材のうちGPS（一般問題解決器）について理解が浅かったので、この際、ISLispで自分なりの理解に基づいて書き直してみることにしました。Easy-ISLispのテストも兼ねています。

歴史的背景

本の解説によれば１９５７年のニューウェルとサイモンの研究開発だそうです。マッカーシー博士がLispを公表したのが１９５８年ですから、そのちょっと前です。IPLという言語で書かれていたそうです。マッカーシー博士に関する書籍で、なぜLispを開発したのか？という解説がありました。IPLより良い開発環境を作りたかったのではないかとのことでした。ノーヴィッグ先生の本でもIPLのわかりにくさが余計に複雑さを増す結果になったと記されています。もっともLISPもPrologも登場する前の話です。その後の発展を促す先駆者的な意味合いがあったのだろうと思います。一般問題解決器というすごい名前がついていますが、実際にはそんなにすごいことはできなかったというのが実際のところのようです。

ISLispでの書き換え

GPSは問題を４つデータからなるオペレーターの集合で記述します。action precond add-list del-listです。Common-Lisp版はストラクチャが使用されています。ISLispだとdefclassでクラスを定義してインスタンスを生成すればできますが、そこまでするほどのことはないと思い、単純に４つの要素から成るリストで表現しています。

Common-Lisp版は推論をするのにsome every といった組み込み関数を使っています。これらは１変数のカリー化された関数を扱うには便利なのです。バージョン１では状態を表す変数を動的スコープの変数とすることにより推論を１変数関数にしてsome everyにより記述しています。私にとってはこれはわかりにくかったので状態を表すstateもオペレーターの集合のopsも局所変数にして関数プログラミングのスタイルで書いています。

推論は後ろ向き推論です。GPSは最終ゴールを与えられど推論を開始します。ゴールを満たすadd-listをもつオペレーターを見つけてそのprecondを取り出してサブゴールとします。サブゴールはさらにサブゴールを見つけ出して再帰的に推論します。アクションが可能がオペーレーターを見つけたときに順次アクション操作をして状態を書き換えつつ再帰を戻していきます。

テスト

デバッグを終えてテストしてみました。本にある息子を車で学校に送るという例題です。

(defun school1 ()
    (use *school-ops*)
    (gps '(son-at-home car-needs-battery have-money have-phone-book)
         '(son-at-school)))

Easy-ISLisp Ver3.46
> (load "./example/gps.lsp")
T
> (school1)
executing LOOK-UP-NUMBER
executing TELEPHONE-SHOP
executing TELL-SHOP-PROBLEM
executing GIVE-SHOP-MONEY
executing SHOP-INSTALLS-BATTERY
executing DRIVE-SON-TO-SCHOOL
T
>

なんとか動作するところまでできました。

「シブリング目標を打ち消す」問題

学校に息子を送りつつも翌日のためにお金を残しておく、という問題がCommon-Lisp版と同様に正しくありません。

(defun school3 ()
    (use *school-ops*)
    (gps '(son-at-home car-needs-battery have-money have-phone-book)
         '(have-money son-at-school)))

> (school3)
executing LOOK-UP-NUMBER
executing TELEPHONE-SHOP
executing TELL-SHOP-PROBLEM
executing GIVE-SHOP-MONEY
executing SHOP-INSTALLS-BATTERY
executing DRIVE-SON-TO-SCHOOL
T
>

Common-Lisp版では動的変数でstateを管理しているので、この状態を検出できそうですが、関数型プログラミングでstateを局所変数にしてあるのでISlisp版ではこの方法が使えません。どうしたものでしょう。じっくり考えてみます。

モンキーバナナ

モンキーバナナ（特定の状況で去るが椅子を使ってバナナを得て食べるという例題）は動くのだろうか？　スクール送迎問題と同様にオペレーターを記述して試してみました。タイプミスをデバッグしてどうやら動作しているようです。

(defun banana ()
    (use *banana-ops*)
    (gps '(at-door on-floor has-ball hungry chair-at-door)
         '(not-hungry)))

> (banana)
executing PUSH-CHAIR-FROM-DOOR-TO-MIDDLE-ROOM
executing CLIMB-ON-CHAIR
executing DROP-BALL
executing GRASP-BANANAS
executing EAT-BANANAS
T
>

難しさ

一般問題解決器というくらいですから、いろいろな問題が解けないといけません。特殊な場合でもちゃんと解決しようとすると解かないといけないことがたくさんありそうです。

STRIPSプログラム

ノーヴィッグ先生の解説を読みますと1972年のニューウェルとサイモンの著作での実装STRIPSプログラムに基づいていりうのだそうです。これは初耳。なんでしょう？　ChatGPTに聞いてみました。1971年にスタンフォード大学で開発されたものだそうです。以下ChatGPTから教わったことです。

ここから
STRIPS形式は、以下の要素から構成されます：

初期状態（Initial State）: 問題の開始時点での状態を述べる述語論理の文で表現されます。例えば、「ボトル1は空である」といった状態情報が含まれます。

目標状態（Goal State）: 問題の解決を目指す状態を述べる述語論理の文で表現されます。例えば、「ボトル1とボトル2が共に満たされる」などが含まれます。

アクション（Action）: 問題の解決に使用可能なアクションが述べられ、それぞれのアクションが適用可能な条件と効果を持ちます。アクションは事前条件と効果を持つことで、どのアクションがどの状態で適用可能かを判断するための基準となります。
ここまで

CHatGPTは解けるかな？

「次の状況でモンキーがバナナを食べられる方法を考えてほしい。
空腹のモンキーが部屋の入口に立っている。部屋の中央には一房のバナナが天井からロープで吊るされている。モンキーには手が届かない高さである。ドタの近くには椅子がおいてある。この椅子はモンキーが押せる程度の軽さであり、この上に経てばバナナまでもう少しのところまでの高さがある。モンキーは玩具のボールをもっている。一度に１つのものしか持てないと仮定する。」

ChatGPTには失礼かと思ったものの、この質問をすると直ちに次の回答をしてきました。

ここから
モンキーがバナナを食べるためには、以下の手順でアプローチできます。

モンキーは椅子をバナナに向かって移動させることができます。しかし、バナナにはまだ届かない高さです。

モンキーは椅子の上に乗り、ボールを手に持っています。これにより、ボールを持つ手が1つ空くことになります。
モンキーはもう片方の手で、ボールをバナナに向かって投げることができます。すると、ボールがバナナと接触し、ロープを当てる可能性があります。

モンキーは続けて、もう一度ボールをバナナに向かって投げます。このプロセスを繰り返すことで、何度かボールがロープに当たり、ロープが揺れるかもしれません。
ロープが揺れることで、バナナが少し下がる可能性があります。モンキーはこれを狙って行動します。

バナナがモンキーの手の届く高さまで降りてきたら、モンキーは片方の手でバナナをつかむことができるようになります。

以上の手順によって、モンキーはボールを利用してバナナを手に入れることができるかもしれません。ただし、モンキーがこのような複雑な手順を実行するかどうかは、モンキーの行動や能力に依存します。
ここまで

1957年から現在2023まで66年。人工知能は大きく進歩したものですね。