Supervisor: Prof. Kenji Ohmori
関数型言語 Haskell を用いた役割指向エージェントベース シミュレーションシステムのプロトタイプ開発
Prototype Development of a Role-Oriented Agent-Based Simulation System using Haskell
女部田 雅俊 Masatoshi Onabeta
法政大学大学院情報科学研究科情報科学専攻
E-mail: [email protected]Abstract
The agent-based social simulation system simulates various phenomena, such as economical or traffic ones.
These phenomena are characterized by interactions among agents who make their decisions autonomously. However, a large scale social has problems with readability and maintainability because the program implementing the social system tends to be complicated because of complicated interactions among a huge number of agents.
Moreover, as the number of agents increases, the execution time becomes longer in geometric order.
In this paper, a role-based model implemented using Haskell is introduced. The method enables to makes the developed program readable and maintainable. The execution speed is also improved using concurrency by taking advantage of Haskell functions. The role-based model divide a social system into three basic elements:
agents; stages; and roles. An agent is defined how to play his role in each stage. Haskell is characterized by a pure functional programming language, in which a program is designed by describing the structure of a developing social system, which is totally different from the conventional imperative programming languages that describe computational algorithm included in the system.
Using the role-based model, social systems such as Prisoner’s dilemma have been implemented, which leads to succeed in providing the readable and maintainable programs and reducing execution time.
1. はじめに
エージェントベース社会シミュレーションは，自律的な 意思決定を行うエージェントをシステムの基本的な構成要 素とし，エージェント同士の相互作用から人工市場または
人工社会の振る舞いをコンピュータ内でモデル化するため の手段である．エージェントベース社会システムは，複雑 化する社会システムをコンピュータの中に再現し，有益な 情報を生み出してくれる有益な道具である．しかし，様々 なエージェントが高度に絡み合った人工市場や人工社会を エージェントベースシミュレーション(ABS)で表現する場 合，プログラムが複雑になることが多く，デバッグや拡張 性等，保守性の維持が困難となる．
実行速度も問題となる．社会シミュレーションではエー ジェントは他のエージェントやエージェントが行動する場 の環境等と絡み合って動作する．そのため，エージェント 数が大規模となった社会シミュレーションを模擬する場合，
実行に時間がかかってしまう．
シミュレーションを実装する際には，シミュレーション 結果を効率的に扱えるようにする必要がある[3]．開発者は 解析に必要な結果の収集や集計そして閲覧を容易に行える ように備える必要があり，またそのシミュレーション結果 を外部に広める際にも，その表現方法は重要なものとなり 得る．エージェントベース社会シミュレーション(以下 ABS)に用いられる言語はエージェントの状態保持やユーザ ーとの対話的なシミュレーションを行う観点から，C++や Javaといった手続き型言語がよく用いられるが，プログラ ムが煩雑になってしまうような場合，プログラムを小さく 簡潔に記述できる関数型言語が有用であると考えられる．
そこで本研究では，関数型言語Haskellによる役割指向に 基づいたプログラミング手法によってABSを構築する手法 を示す．Haskellでは強力に型付いた言語であるため，バグ を早期に発見することができる．また，関数を小さく作る ことが可能であるという関数型言語の特徴や，関数合成等 を用いることで可読性や拡張性を高めることができる．加 えて，関数型言語の特徴である参照透過性を維持すること で，並列・並行化を容易に行うことができるため，実行速 度を向上させることができる．さらに，パターンマッチン
グを用いることで，シミュレーション結果を容易に選別可 能であり，シミュレーション結果の可読性も高めることが 可能である．
2.役割指向ABS
一般に，社会システムは相互に影響を受けながら自身で 意思決定を行うエージェントを中心に成り立っていると考 えられる．例えば，シミュレーションを必要としている社 会システムは，交通や経済といったものから，森林の広が り方，季候の変異による移り変わりによる地域の変化等の 自然のシステムまで，多岐にわたる．これらの社会システ ムでは，車や人，会社，木などをエージェントとし，車同 士の行動や会社間での取引，木と環境とのやり取りといっ たエージェント間の相互作用を設計し観察することで，社 会システムを忠実に再現したシミュレーションが可能にな る．このため，本エージェントベース社会シミュレーショ ンでも，自律的に意思決定を行うエージェントを基本的な 構成要素とする．
しかし，大規模なシミュレーションを記述する際にはエ ージェント同士の相互作用や環境への相互作用，またシミ ュレーションの内容が複雑になる．また，それをプログラ ムする際にはプログラムが複雑なものになり，保守性や拡 張性の維持が困難となる．
そこで本研究では，役割指向の概念を用いることで，シ ミュレーションを整理して記述する．役割指向は，社会シ ミュレーション言語SOARS[1][2]のベースとなる記述法で ある．そこでは，シミュレーションモデルは，ステージと 呼ばれる場面に区切られている．エージェントはステージ 別にそこで行うべき振る舞いが定められている．この振舞 いを「役割」という．シミュレーションはあるステージで 始まり，エージェントは，そのステージでの役割を演じ，
次のステージへと移る．次のステージでも同じことが行わ れる．即ち，エージェントがそれぞれの場面で定められた 役割を演じながらステージを遷移していくことで，シミュ レーションが実行される．
交通のシミュレーションを例に挙げれば，エージェント である車は，あるステージでは右に曲がり，別のステージ で左に曲がる，といった「役割」を演じ，全体のステージ の流れの中で右に曲がるステージでは右に曲がり，左に曲 がるステージでは左に曲がる，といった振る舞いを演じ る．この振る舞いと他のエージェントとの相互作用から，
社会システムがシミュレーションされる．
2.1. 役割指向
これまで説明してきたように、社会システムはエージェ ント、ステージ、役割の三つを基本的な構成要素として記 述できる。これらの基本構成要素について詳しく説明する。
2.1.1. エージェント
エージェントは自律的な意思決定を行うオブジェクトで ある．エージェントは状態を表す属性を保持し，役割に定 義された振る舞いによって自身の状態を変化させたり，外 部とのインタラクションを行ったりする．
2.1.2. ステージ
ステージはルールの実行順序を規定したものであり，社 会シミュレーションでは1ティックを細分化したものに当 たる．ティックはシミュレーション内での時間の経過を表 す単位であり、シミュレーション内での1日や1時間など を表す。シミュレーション全体の流れは，複数のステージ の流れによって表現される．
2.1.3. 役割
役割はエージェントの振る舞いをステージ別に定義した ものである．役割指向では，エージェントは役割を持ち，
シミュレーション全体を表すステージの流れの中で，役割 に定義された振る舞いを行う．
2.2. 役割を用いたシミュレーション
役割指向エージェントベース社会シミュレーションでは，
エージェントはステージごとに役割として定義された振る 舞いを演じる．また，全体のシミュレーションは，複数の ステージを繰り返し実行することで行う．エージェントが 特定のステージで決められた役割に応じた振る舞いをする ことでシミュレーションを行う．これを示したものが図 1 である。
囚人のジレンマを例に挙げて説明を行う．囚人のジレン マはゲーム理論のモデルの一つであり，各プレイヤーが利 得の大きい選択肢を選ぶ場合，協力した場合よりも悪い結 果を招いてしまうゲームである．
囚人はそれぞれ自白か黙秘を行うことができ，選んだ選 択によって双方の勝敗が決まる．
今回は囚人が2人いるとし，それぞれA,Bとする．囚人 Aは意思決定の際に自白を選び，Bは黙秘を選ぶとする．
例とする役割指向における囚人のジレンマでは，意思決 定を行うステージ，勝敗を判定するステージ，囚人に勝敗 を記憶させるステージがあるとする．
ステージ 1では，囚人が自白か黙秘かの意思決定を行う．
この際，Aは自白を，Bは黙秘を選択する．
次に，ステージ2では勝敗を判定する．Aは自白し，Bは 黙秘しているため，このステージでAの勝利が決定する．
ステージ 3では囚人に勝敗を記憶させる．Aには勝利を，
Bには敗北を記憶させる．
これらの 3ステージを繰り返し実行することで，有限回 繰り返し型の囚人のジレンマを実行することができる．
図 1. 役割指向ABS
3. 提案手法
本研究では，役割指向によるエージェントベースシミュ レーションの構築を行う．2節で示したように，役割指向 は，役割，ステージ，エージェントを基本的な構成要素と する．また，役割指向ABSでは，エージェントが役割を 持ち，全体のステージの流れの中で，役割に定義されたス テージを実行することでシミュレーションを実現する．
本節では，関数型言語Haskellで役割指向ABSを実現す る際に，それぞれの構成要素をどのように設計するかを説 明する．また，実行速度向上のための並列化の手法につい ても説明する．さらに，結果をより分かりやすくまとめる ための手法についても説明を行う．
3.1. 役割
役割指向ABSでは，エージェントがそれぞれ役割を持つ．
役割は特定のステージでエージェントが実行するべきステ ージを定義したものであるため，あるエージェントに実行 してほしいステージを関数として定義し，その関数をエー ジェントに持たせる．その後，特定のステージでエージェ ントが持っている関数を実行することで，役割を実現する ことができる．
3.2. ステージ
役割指向におけるステージを関数合成により合成するこ とでシミュレーションを構築し，プログラムの可読性を高 めることができる．複数のステージからなるシミュレーシ
ョンをHaskellで記述する場合，以下のように書ける．
この例のステージは型宣言のみだが，Haskellではパター ンマッチを用いることで関数に与えられた値を選別するこ
とが出来るため，型に合わせて新たに関数を定義する必要 がない．
また，単一のエージェントを対象とした関数を複数のエ ージェントに適用する際にはmap関数を利用するだけでよ い．map 関数は，リスト内のすべての要素に対し，引数と して渡した関数を適用する関数である．以下のように，エ ージェントをリストにまとめ，そのリストに対してステー ジを表す関数を map関数により適用するという記述を行う ことで，煩雑な繰り返し文等を利用する必要がなくなる．
そのため，プログラムを簡潔に，直感的に記述することが でき，保守性の向上を見込むことができる．
3.3. エージェント
エージェントを定義する際には，レコード構文を用い る．レコード構文はデータ型を宣言するための1つの手法 であり，以下のように記述することでエージェントを容易 に定義できる．
それだけでなく，その要素にアクセスするための関数も自 動的に生成してくれるため，簡潔な記述を行うことができ る．
また，Haskellでは遅延評価を基本的な評価戦略としてい る．遅延評価は，式の評価をその式が必要となるまで行わ ず，また評価する必要のない式は評価しないという評価方 法である．この性質により，Haskellでは無限の要素を持っ たリストを扱うことが可能となる．遅延評価を利用するこ とで，理論上無限のエージェントを扱うことが可能となる ため，大規模なシミュレーションを行う際に有用となる．
3.4. ABS
の並列化
参照透過性を維持することで，比較的容易に並列化を行 うことができる．参照透過性は、入力に対する結果は不変 という性質であり、これを維持できている限り、並列に動 かしたとしても個々の結果は変わらず、互いにお互いに影 響もない。そのため、他に対する影響を考慮せずに並列化 を行うことができる。
3.4.1. 参照透過性
参照透過性とは，変数は最初に定義した値から常に不変 であり，関数は同じ変数を引数として与えられれば常に同
agentList = [agent1, agent2, agent3..]
stage :: Agent -> Agent
simulation = map stage agentList
data Agent = Agent { name :: String, role :: Role }
let agent1 = Agent "agent1" role (name agent1) -- get "agent1"
agent1 { name = "agent2" } -- set
"agent1" -> "agent2"
stage1 :: Agent -> Agent stage2 :: Agent -> Agent stage3 :: Agent -> Agent simulation :: Agent -> Agent
simulation = stage3 . stage2 . stage1
じ値を返すという性質である．この性質を維持することで，
意図しない変数の書き換え等のバグを予防できるだけでな く，手続き型言語のように変数が書き換えられる経過を追 う必要がなくなるため，保守性の向上にもつながる．さら に，この性質を維持している限り，プログラムを並列に動 かしたとしても個々の結果は変わることがなく，お互いに 影響することはないため，並列化も容易に行うことが可能 となる．
3.4.2. 並列化
参照透過性を維持している関数であれば，周りの影響を 考えずに並列化することができるが，今回はその中でも map 関数の並列化を行う．map関数はリストのすべての要 素に関数を適用するという関数であるため，適用する関数 が参照透過性を維持している限り，容易に並列化すること ができる．
図 2. map関数の並列化
3.5. 結果の選別
パターンマッチを用いる事で，効率的に結果を収集，解析 する事ができる．
3.5.1. パターンマッチ
パターンマッチは分岐のための一つの手段である．
Haskellでは，通常の条件による分岐の他にも，データ構造
に対するパターンマッチや，ガード構文を用いた分岐等を 提供しており，様々な条件分岐を直感的に記述することが できる．以下に，フィボナッチ関数を例として示す．
パターンマッチを用いることで，分岐をより直感的に理 解することができるプログラムを書くことができると考え られる．また，条件に範囲を用いる場合には，ガード構文 を用いて記述することができる．
このように，パターンマッチとガード構文を用いること で，条件分岐を理解しやすく記述することができる．
3.5.2. パターンマッチを用いた結果選別
以下のように，エージェントの状態に応じた処理を簡潔 に記述できるだけでなく，同じ関数を用いてエージェント の種類に応じた結果の選別も行うことができる．そのため，
コードが簡潔になるだけでなく，新たにエージェントを追 加したとしても，同じ関数にそのエージェントに応じた処 理を加えるだけで良いため，拡張が容易である．
また，Haskellはリスト操作にも強く，エージェントの状態 遷移をリストに保持しておくことで，シミュレーションの 遷移を効率的に収集，解析できる．
4. 実験
本研究では，Haskellを用いた役割指向エージェントベー スシミュレーションの例として，単純な移動モデルを作成 した．本節では，今回作成した移動モデルについて説明し た後，その実装，並列化法について説明を行う．
4.1. 移動モデル
今回作成した移動モデルでは，エージェントがそれぞれ 役割を持っており，特定のステージで決められた役割に応 じていくつかの場所を行き来する，という単純なモデルで ある．以下のように，今回作成したモデルでは，エージェ ントが Student, Worker, Patientの 3種類おり，場所として Home, Hospital, School, Officeの4種類が用意されている．
(プログラムの見易さのため，エージェントが持つ状態をい くつか省略している)
レコード構文を用いることで，様々な状態のエージェン トを容易に作成することができる．また，エージェントに fib :: Integer -> Integer
fib 0 = 1 fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
fib :: Integer -> Integer fib n
| n < 2 = 1
| otherwise = fib (n-1) + fib (n-2)
result (AgentType_1 )
| 状態1 <= … = 処理
| 状態1 > … = 処理
result ( AgentType_2) = …
data Agent = Student { name :: String…
role :: Role}
| Worker { name :: String…
role :: Role}
| Patient { name :: String…
role :: Role}
deriving (Show)
student = Student "s1" "Home" "" []
(Role [sStage1, sStage2, sStage3])
役割を持たせることで，エージェントがどのような行動を 行うのかをステージの流れとして定義することができる．
そのため，エージェントがどのような振る舞いを行うのか が理解しやすく，可読性，保守性において有用となる．
次に，シミュレーションの流れについて説明を行う．シ ミュレーションは3つのステージで構成されている．
ステージ 1では，エージェントが持つ役割に応じ，次の 場所を決定する．以下のように，パターンマッチを用いる ことで条件を直感的に理解することができる．
ステージ 2は，エージェントが自分の今いる場所を記憶 するステージである．エージェントが移動した軌跡をリス トに保持しておくことで，エージェントがどのように移動 したかを簡単に追跡することが可能となる．
ステージ3では，ステージ1で決定した場所へと実際に 移動する．
これらのステージを繰り返し実行することでシミュレー ションを行う．
4.2. 並列化
Control.Parallelモジュールを用いることで，容易に並列
化を実現することができる．本研究では，以下のようにリ ストを4分割し，それぞれ並列に実行させるという実装を 行った．rpar・rseq関数はそれぞれControl.Parallel.Strategies モジュールに含まれる関数であり，rpar関数によって並列 に実行させ，rseq関数を適用することで結果を待つ．
今回マップ関数を用いて適用している関数はresult関数 であり，エージェントの状態によって出力するものを変え るという関数である．この関数はエージェントの状態によ ってのみ結果が決定し，ほかの何にも影響を及ぼさないた め，参照透過性が維持されている．
このように，map関数に適用する関数が参照透過性を維 持している限り，並列化を容易に行うことができる．
4.3. 結果の集計・選別
今回のモデルでは，エージェントが最終的にいた場所に よって出力を変える関数を作成した．以下のように，パタ ーンマッチを用いることでエージェントの様々な状態を判 定できるだけでなく，エージェントの種類によって処理を 変えることもできる．
これだけでなく，パターンマッチを用いることでエージ ェントが持つリストを表示したり，そのリスト内の要素に よって何らかの処理を行ったりすることが可能である．
5. 結果
シミュレーションを実装し，実行した結果を示す．コー ド量に関しては，一つのステージにつき 3~4行程度で記述 することができ，簡潔に記述できる結果となった．コード が短く，またパターンマッチやレコード構文等，直感的に 理解できる記述が出来るため，可読性や保守性も高くなる．
次に，拡張性について考える．新たなエージェントを追 加する際でも，レコード構文の利用や，パターンの追加等 を行うことで，追加に容易に対応することができる．たと えば，新たに Teacherというエージェントをシミュレーシ ョンに追加する際には，以下のようにレコード構文に追加 する．
その後，このエージェントに行わせたい振る舞いを定義 した役割を持たせる．
このように，新たにエージェントを追加する際でも，変 更を加える箇所が限定されており，また簡潔に記述できる ため，バグの発生や意図しない振る舞いが発生しにくい．
これらのことから，拡張性も高いといえる．
sStage1 :: Agent -> Agent
sStage1 (Student name pos next record role)
| pos == "Home" = Student name pos
"School" record role
| otherwise = Student name pos "Home"
record role
res = runEval $ do
as' <- rpar (force (map result $ simN as)) bs' <- rpar (force (map result $ simN bs)) cs' <- rpar (force (map result $ simN cs)) ds' <- rpar (force (map result $ simN ds)) rseq as'
rseq bs' rseq cs' rseq ds'
return (as' ++ bs' ++ cs' ++ ds')
result :: Agent -> (String, String)
result (Student name pos next record role) | pos == "Home" = (name, "Home") | pos /= "Home" = (name, "Learning") result ( Worker name pos next record role ) | pos == "Home" = (name, "Home") | pos /= "Home" = (name, "Working") result ( Patient name pos next record role ) | pos == "Home" = (name, "Home remedy") | pos /= "Home" = (name, "Hospital")
data Agent = Student {name :: String…
role :: Role}
| Teacher {name :: String … role::Role}
deriving (Show)
tStage1 :: Agent -> Agent
tStage1(Teacher name pos next record role)
| pos == "Home" = Teacher name pos "School"
record role
| otherwise = Teacher name pos "Home" record role
teacher = "t1" "Home" "" [] (Role [tStage1, tStage2, tStage3])
続いて，結果の選別についての結果を示す．4.3節で示し たように，パターンマッチとガード構文を用いることで，
どのような結果が欲しいのか，どのように出力してほしい かが直感的に記述できるだけでなく，一目で理解できる．
ここで，エージェントを各1，ステージ1から3までを実行 した際の出力結果を以下に示す．
図 3. 実行結果1
それぞれのエージェントの種類に対して，異なる処理が行 われていることがわかる．
また，エージェントによって欲しい状態が異なるような 場合に対してもパターンマッチは有用である．例えば，エ ージェントPatientに関しては状態recordが必要，という場 合は，以下のような変更を加えるだけで実現できる．
加えて，新たなエージェントを追加した場合でも対応が容 易である．先に説明した Teacherを新たに加えた場合でも，
以下のように記述することで対応することができる．
これらのことから，パターンマッチを用いることでシミュ レーションの結果を容易に選別することができるといえる．
最後に，実行速度の結果を示す．今回このシミュレーシ ョンを実行した環境は以下のとおりである．
・ Intel Core i7-4770 (4コア，8スレッド)
・ メモリ4GB
シミュレーション内容は，4.1節で示した移動モデルにお いて，ステージ1からステージ3を100回，エージェント
数150000で行った．結果は以下のとおりである．並列化は，
4.2節で示したもののみとした．
表 1. 実行速度の比較
スレッド数 実行時間(s)
1 31.84
4 15.02
実験結果から，map関数の並列化を行うという単純な記 述を行うだけで，約2.11倍の速度向上を実現することがで きた．
6. 考察
提案手法により，簡潔で拡張性の高いABSを構築できる ことが分かった．役割指向の概念を用いることでエージェ ントが行う振る舞いをステージごとに整理して記述できる．
また，Haskellを用いることでエージェントや役割，ステー ジの定義等を整理して記述できるだけでなく，それぞれの 構成要素をレコード構文やパターンマッチ等を用いて記述 することで，簡潔に記述出来る．これにより，バグの発生 個所や意図しない動作を行っている箇所を特定しやすくな る．さらに，レコード構文やパターンの追加等を行うだけ で，新たなエージェントを容易に追加できる．加えて，参 照透過性を維持することで並列化を容易に実現することが できるため，大規模なエージェントベースシミュレーショ ンを実行する際の速度向上も容易である．
しかし，参照透過性を維持しなければならないため，エ ージェントの状態の更新等の値の書き換えを行う際には冗 長なコードを書かなければならない結果となった．Haskell ではモナドを用いて参照透過性を維持したまま手続き型言 語のような記述もできるが，それは今後の課題とする．
また，今回は結果の出力にテキストを用いたが，よりよ く結果を見せるには可視化の処理が必要である．パターン マッチを用いることでエージェントの状態によって出力を 変えられることから，結果出力までをHaskellで行い，それ 以降は外部のソフトウェアを用いる等の方法が考えられる．
7. おわりに
関数型言語Haskellを用いた役割指向ABSの構築手法を 示した．役割指向の概念を用いることで，シミュレーショ ンをいくつかの構成要素に分割して記述できる．また，
Haskellを用いることで一つ一つの要素を簡潔に，直感的に
記述できるため，可読性，保守性の向上を見込める．ま た，パターンマッチを用いることで新たなエージェントの 定義にも容易に対応できるため，拡張性も高いといえる．
さらに，参照透過性を維持することで並列化を容易に行 えるため，実行速度の向上も容易に行うことができる．
今後の課題としては，エージェントの状態の保持の手法 や，結果の可視化が挙げられる．
文 献
[1] 田沼英樹，出口弘，エージェントベース社会シミュレ ーション言語 SOARS の開発, 信学会論文誌，Vol.J90- D, No.9, 2415/2422 (2007)
[2] Manabu Ichikawa, Hideki Tanuma, Yuhsuke Koyama and Hiroshi Deguchi, SOARS for simulations of social interactions and gaming, Introduction as a social microscope, Proc. 38th Annual Conference of the International Simulation and Gaming Association, P-36, (2008)
[3] 女部田雅俊，佐々木晃，役割指向テンプレートジェ ネレータを用いたエージェントシミュレーション実験環境 の構築手法，情報科学技術フォーラム講演論文集，12(2)，
337-338，2013 result :: Agent -> String
…
result ( Patient name pos next record role ) = show record
result :: Agent -> String
result ( Teacher name pos next record role )
= 欲しい結果の出力
