知識に基づいた行動決定のアルゴリズムについて

はじめに

タイトルが地味〜すぎて読む人がいるかちょっと心配。

以下に述べるのは、AIが人間から命令の羅列（アレしてコレしろ）を与えられたとき、それを遂行するための行動をどのように決定するのかについての私案である。と言っても俺はAIの専門家でもなんでもないので、とっくに誰かが思いついていることかもしれないw

仕組みとしては非常に単純であり、なおかつサンプルとして提示するコードも非常にしょぼく、それだけだと言わんとするところが伝わらない懸念がある。なので前置きを少し長く述べたい。

そもそもの発想の原点としては、以下のツイートを読んだことによる。

昔から、多分、十代の頃から、辞書というものの不思議さを感じていた。

辞書は、言葉を、単に言い換えているのにすぎない。

しかし、その「言い換え」が知識の本質なのだ。

あらゆる知識は言い換えに過ぎない。広義のトートロジーである。

そう考えると、違った風景が見えてくる。

— わっしー教授(ロボット、ドローン芸) (@wassiisg) January 25, 2019

これが厳密にそう言えるのについては正直分からないが、俺は確かにそうだなと思ったのだった。例えば俺が何かの辞書でAについて調べたとき、

A: BがCしたものである。

とかなんとか説明があったとする。このとき俺がBについて知らなければ、それについて再帰的に調べればよい。

B: DにおけるFである。

Fが分からなければさらに調べる…ということを単純に繰り返すことにより、最終的に俺は単なる言葉の置き換えの集合にすぎない辞書からAについての理解を得る、ことが期待できるw

このとき、辞書の編纂者は俺がどのように読み進めるかを想定していない。彼らがやっているのは言葉の置き換えを網羅することであり、それゆえ辞書はどこからでも読み始められる。

つまり、辞書は文明の礎たる知識の集積物であるが、実のところはそれを読むのも書くのも半ば機械的な作業によって成り立つ。いや、本気でそう言っているわけじゃないけど、上のツイートにもあるように、そう考えると違った風景が見えてくる。

例えば人手不足により大工さんロボットを作らなければならなくなったとする。大工さんの親方は情報処理の技術を持たないので、ロボットには人間と同じように指示を受け、それを遂行することが求められる。

ここでロボットが何かの作業をこなすには、大工さんの業務知識に基づき現場の状況に応じて行動しなければならない。この知識に基づいた行動決定のアルゴリズムをどのように実装するのかというのが以下の内容である。

リンゴをゲットせよ

プログラムそのものはC++で書かれているが、前に紹介したs7という処理系を組み込んでおり、schemeのコードで設定する。全く難しい内容ではないから、C++やschemeの知識がなくても雰囲気で目を通してもらえれば他の言語に移植するのは容易い、はずw

s7とそれをC++に組み込むためのs7wrapは上のリンクの場所にアップロードしてないから、実際に動かしたい人は以下も読んでね。

最初に述べたように、サンプルとして提示する内容は非常にしょぼい。エージェントに求められるのは、文字によって作られた迷路を探索し、どこかにあるリンゴを取得し元の位置に帰ってくること。

;map0.scm
(define map_w 5)
(define map_h 3)
(define map_str "\
@# ##\
 #  $\
   ##")

上記のマップデータで#は壁であり移動できない。マップの外周は全て壁で囲まれているものとする。@はエージェントの初期位置、$はリンゴだ。

エージェントが得られる情報は自分のいる場所とその周囲の計９マスのみ。そのため移動しながら知識を更新しマップを把握しなければならない。

エージェントはターン毎に1つの行動を行える。このサンプルでエージェントが行える行動は２つのみで、一つは上下左右に移動すること、もう一つは現在位置にあるリンゴを取得すること。

; test0.scm
(load "map0.scm")
(api_set_map map_w map_h map_str)
(api_comm_move 0 0)
(api_comm_get API_APPLE)
(api_start 100)

こちらのコードでは上記マップを読み込み、エージェントに二つの指示を与える。まずリンゴを取得せよ。次に初期位置に移動しろ。順番が逆なのはご愛嬌だ。

これらのAPIを定義するS式のファイルは以下のようになる。

(set_map void "マップをセットする"
  (w int "横のブロック数")
  (h int "縦のブロック数")
  (s str "改行を含まない文字列形式のマップデータ"))

(comm_move void "移動命令を追加する"
  (x int "X座標")
  (y int "Y座標"))

(comm_find void "探索命令を追加する"
  (what int "API_APPLE"))

(comm_get void "取得命令を追加する"
  (what int "API_APPLE"))

(start void "処理を開始する"
  (cnt int "処理を打ち切るターン数"))

C++のクラスにはState/Agent/Mission/Act/Mapがある。それぞれ簡単に説明すると、

State ... シミュレーション世界の状態
Agent ... エージェント
Mission ... 行動命令
	MissionMove ... 移動命令
	MissionGet ... 取得命令
	MissionFind ... 探索命令
Act ... 行動
	ActMove ... 移動行動
	ActGet ... 取得行動
Map ... グローバルマップ（エージェントの知識ではない）

このうち、本題の行動決定アルゴリズムはMissionとして実装されている。

Missionはsub_missionsのメンバを持つ。sub_missionsはある行動命令を遂行するための副次命令である。アルゴリズムでは、まず目下の状況でそのミッションが達成されているかを調べる。真ならそのミッションは消去される。偽ならそれが目下の状況で行動可能であるかを調べる。真なら対応するActを返し、偽ならそれを達成するための手順をsub_missionsに展開する。

上の例ではまずMissionGetの処理を求められるが、Agentのいる場にリンゴはなく、どこにリンゴがあるかも分からない。そのため、MissionGetはsub_missionsにMissionFindを展開し、これにActを要求する。

MissionFindもどこにリンゴがあるか分からず、そもそもマップがどのような形状かも知らないため、とりあえず適当に移動する。具体的には行ったことがない移動可能地点(0,1)へのMissionMoveをsub_missionsに展開し、これにActを要求する。

ここで地点(0,1)へのMissionMoveは行動可能であるため、これがActMoveを返し、それが処理されることで最初のターンが終わる。これを繰り返し、リンゴのある地点に移動することでMissionFindが達成され、次いでMissionGetが達成される。

上記test0.scmを実行してみると、

$ ./mazeai test0.scm
**TURN0**
set_surround(): x=0, y=0
###
# #
# #
ActMove::process()
**TURN1**
set_surround(): x=0, y=1
# #
# #
#
add route (0, 2)
ActMove::process()
**TURN2**
set_surround(): x=0, y=2
# #
#
###
ActMove::process()
**TURN3**
set_surround(): x=1, y=2
 #

###
ActMove::process()
**TURN4**
set_surround(): x=2, y=2
#
  #
###
add route (2, 1)
ActMove::process()
**TURN5**
set_surround(): x=2, y=1
# #
#
  #
ActMove::process()
**TURN6**
set_surround(): x=3, y=1
 ##
  $
 ##
ActMove::process()
**TURN7**
set_surround(): x=4, y=1
###
 $#
###
ActGet::process()
**TURN8**
set_surround(): x=4, y=1
###
  #
###
add route (0, 1)
add route (0, 2)
add route (1, 2)
add route (2, 2)
add route (2, 1)
add route (3, 1)
ActMove::process()
**TURN9**
set_surround(): x=3, y=1
 ##

 ##
ActMove::process()
**TURN10**
set_surround(): x=2, y=1
# #
#
  #
ActMove::process()
**TURN11**
set_surround(): x=2, y=2
#
  #
###
ActMove::process()
**TURN12**
set_surround(): x=1, y=2
 #

###
ActMove::process()
**TURN13**
set_surround(): x=0, y=2
# #
#
###
ActMove::process()
**TURN14**
set_surround(): x=0, y=1
# #
# #
#
ActMove::process()
**TURN15**
set_surround(): x=0, y=0
###
# #
# #
All missions achieved.

まあよく分からんと思うけど、一応エージェントがリンゴを求めて迷路をさまよい、これをスタート地点に持ち帰る様を確認できた俺はw

この知識ベースの行動決定アルゴリズムは、前置きで述べた辞書を読む過程とよく似ているのが分かると思う。

辞書を読む場合、ある単語についての説明を読み、そこで用いられている単語の意味が不明ならさらにそれを調べる。それと同じように、このアルゴリズムではある行動命令が目下の状況で達成できるか調べ、できないならそれを達成するための行動命令を展開し、その末尾に行動を求める。

別の言い方をすると、辞書がある言葉を別の言葉に置き換えるように、このアルゴリズムはある行動命令を別の行動命令に置き換える。

このサンプルは非常に単純だが、もしこれがある業務領域の行動命令を網羅したものであればどうかということだ。辞書がどこから読み始めどう読み進めても良いように、どのような命令に対しても知識に基づき状況に応じて行動できるAIを実現できるのではないか？

アルゴリズムの発展

現実というものを想定すると、上記の仕組みだけでは足らないことに気づく。

一つは優先順位で、多くの仕事はいくつかの行動を優先順位に基づき並行して行なっている。優先順位の高い行動が待ち状態になると優先順位の低い行動に移る。これはsub_missionsを2次配列にすることで実装できる。

もう一つは状況変化への対応で、sub_missionsを順番に処理していくうちにその中の一つが達成不可能になってしまったらどうするか。これにはsub_missionsを破棄して展開し直すことが必要になる。

もしこのアルゴリズムに興味を持ってもらえたら、ぜひ改造して遊んでみてほしい。エージェントを増やして協調させたり、マップを動的に変化させたりw

おわりに

とはいえ、業務知識ってのは日々更新されるものだし、それをプログラマが都度ヒアリングしてコーディングしてテストするのを繰り返せるわけもないから、実際は往年のエキスパートシステムと同じようになかなかうまくいかないだろうなw

このアルゴリズムは俺が趣味でやろうとしてた社会経済シミュレータでエージェントの行動決定をどのように行えばいいか考えて思いついたものだ。そのシミュレータは俺が社会についても経済についても何にも知らんとゆうことが明らかになり頓挫してしまったんだけど、まあせめてアルゴリズムだけでも誰かにとってのヒントや刺激になったらいいなと思い投稿してみました。

いじょう