1．は じ め に
サイバー（仮想）空間とフィジカル（現実）空間を高 度に融合させる社会変革の重要性が認識されている [ 内 閣府 16]．1990 年代以降のインターネットの普及は，「ア トムからビットへ」をテーマに [Negroponte 96]，物理 的な実体から独立した情報をサイバー空間に集約して処 理するアプローチを加速し，多くの技術革新をもたらし た．2010 年代を迎えると，Internet of Things，3D プ リンタ，スマート工場，ドローン，自動運転，物流自動 化などの新しいキーワードが次々に登場し，飛躍的に発 展した人工知能技術の普及と相まって，サイバー空間で 確立された高度な情報処理技術をフィジカル空間におけ る物理的実体を伴う対象の運用上の諸問題の解決へと応 用する，いわば「ビットからアトムへ」のアプローチに よる技術革新への期待が高まっている．しかし，これら のアプローチは「ビット」と「アトム」を峻別し，サイバー 空間とフィジカル空間を異質で断絶したものとして規定 するチューリング機械以来の計算パラダイムに基づいて いるため，両空間をそのまま接続することは容易ではな い．「フレーム問題」は，実社会において自律的に活動 できることを期待される人工知能ロボットが，その頭脳 のサイバー空間中で実現される情報処理能力の有限性ゆ え，無際限の複雑性をはらむフィジカル空間中で直面す る想定外の状況に臨機応変に対応できる能力を獲得する ことには原理的に困難であると予見する [Dennett 87]． フレーム問題の回避が実用的レベルで可能かどうかは議 論の分かれるところであるが [柴田 04]，少なくともす でにサイバー空間とフィジカル空間の狭間では，新たな 可能性とともに新たな問題群も生じつつある [三木 16]． 問題が先鋭化しているのは物流の分野である [国交省 17]．サイバー空間で大量の商品をワンクリックで注文 可能になった一方で，フィジカル空間でそれらを宅配す る業者は深刻な労働力不足に直面している．自動運転ト ラックによる無人配送に期待が集まっているが，トラッ クから宛先玄関までの「ラストマイル」の荷物運搬を担 うのは，依然として人である [林 17]．ラストマイルの 労働力となり得る自律ロボットも多数提案されている が，いまだ人を代替できる段階にはない．それらは平坦 な路面を走行したり規則的な階段を昇降したりはできる ものの，各戸で異なる未知の複雑な物理的条件をもつ環 境を，既知の制御情報のみに基づいて走破することが困 難なのである．こうした従来のロボットは，環境の情報 として物質から独立した「ビット」のみをセンサから取 り込んで処理し，そこからの状況判断に環境とコンタク トするアクチュエータを構成する「アトム」が直接関与 することはない [新山 18, Pheifer 07]．このように「ビッ ト」と「アトム」が断絶したままでサイバー空間におけ る情報処理能力をどれだけ向上させても，フィジカル空サイバー空間とフィジカル空間を癒合する
アメーバ計算パラダイム
Amoeba-inspired Computing Paradigm for Bridging the Gap between
Cyber and Physical Spaces
青野 真士
慶應義塾大学環境情報学部，Amoeba Energy 株式会社Masashi Aono Faculty of Environment and Information Studies, Keio University. / Amoeba Energy Co., Ltd. [email protected], http://web.sfc.keio.ac.jp/~aono/
[email protected], http://www.amoebaenergy.com/
鯨井 悠生
Amoeba Energy株式会社Yusei Kujirai Amoeba Energy Co., Ltd.
[email protected], http://www.amoebaenergy.com/
野﨑 大幹
（同 上）Hiroki Nozaki [email protected], http://www.amoebaenergy.com/
Keywords:
natural computing, combinatorial optimization, amoeba-inspired computing, non-Neumann typecomputer, soft robotics.
間の無際限の複雑性を乗り超えることは難しいだろう． 本来，情報と物質は分かちがたく結び付いている [堀 08]．情報としての属性をもつ物質，例えば，状況に対 する知識を蓄えて正しい判断をできる物質は存在し得る し，質量や体積をもち物体を動かす力を伝達できる信号， すなわち，物質としての属性をもつ情報も想定できるだ ろう．これを実証しているのは生物やそれを構成するさ まざまな生体システムである．本稿で紹介するアメーバ 生物・粘菌（以降「アメーバ」）は，単細胞ながら置か れた環境に適応できる高度な情報処理能力を有してい る．そこでは，センサ系，情報処理系，アクチュエータ 系が明確に分離していない．言うなれば，「アトム」と 「ビット」が未分化なシステムである．我々がこうした 始原的なシステムに注目するのは，もちろん懐古趣味か らではない．環境とコンタクトする身体の物質の複雑な 運動をも情報として取り込んで処理することで，事前に 規定しきれない環境の無際限の複雑性を懐柔する，現実 的な解決策の可能性を探るのである． 本稿では，アメーバの情報処理原理に着想を得た新た な計算パラダイムに関する著者らの研究をいくつか紹介 する．まず，アメーバの変形行動を光刺激により誘導す ることで組合せ最適化問題「巡回セールスマン問題」の 解を探索させる実験システムである「アメーバ計算機」 [Aono 07, Aono 09, Iwayama 16, Zhu 13]，およびその解 探索プロセスの数理モデル [Zhu 18] を紹介する．そして， より抽象度の高い「充足可能性問題」の解を探索する「ア メーバ型最適化アルゴリズム」[Aono 12, Aono 15a] に ついて説明したうえで，このアルゴリズムをアナログ電 子回路 [Kasai 13, Saito 18] やディジタル電子回路 [Ngoc 18，Takeuchi 18] により実装する「アメーバ型最適化チッ プ」の研究開発の現状を紹介する．最後に，伸縮素材の 膜が外界形状に適合しようとする物理過程とそれを柔軟 に制御できるアメーバ型最適化チップを組み合わせるこ とで，未知の複雑な環境をも走破し荷物を運搬する仕事 を担う「アメーバ型移動ロボット」の開発構想について 述べ，サイバー空間とフィジカル空間の高度な融合に資 する技術革新の可能性を展望する．
2．アメーバ計算機
2･1 真性粘菌変形体 真性粘菌（Physarum polycephalum）変形体は，不 定形でネットワークのような形状になることもできる単 細胞のアメーバ生物である（図 1）．アメーバの構造（図 2（a））は，内部隔壁のない 1 枚の細胞外質（一種の膜）と， それが取り囲む原形質（流体）から成る．細胞外質はア クトミオシン系が架橋することで構成されており，その 各所は収縮と弛緩を周期的（1 ∼ 2 分）に繰り返している． そこから，細胞全体の時空間振動ダイナミクスが生じる． このダイナミクスは，細胞外質に局所的な収縮力勾配を もたらし，それにより原形質が受動的に流動する．細胞 外質の振動の時空間パターンに応じて，原形質の流動方 向は繰り返し反転する．この往復流動がアメーバの足（体 の一部）の伸長・縮退運動を駆動し，全体の変形や移動 （速度：∼時速 1 cm）をもたらす．よって，アメーバの 変形や移動に関する判断は，時空間振動ダイナミクスの 自己組織化により実現しているといえる [Iwayama 16]． アメーバは，中枢神経系のような中央集権型の情報処 理ユニットをもたないにもかかわらず，全体として高度 な情報処理機能を発揮することができる．例えば，複数 のエサを空間的に配置すると，それらを結ぶ最短経路を とる形状に変形することで，栄養物質の吸収効率などの 生存に有利になる複数の指標を最適化できる [Nakagaki 00]．これは，この単細胞生物が環境の情報（エサの位置 関係）を処理し，ある種の最適化問題を自律分散的なや り方で解く計算能力を有していることを意味している． 2･2 アメーバ計算機 Aonoらは，培地上にアメーバが足を伸縮できる溝を もつ障壁構造（図 2（b））を設置し，各溝にアメーバが 忌避応答を示す光刺激を照射できるシステム（図 2（a）） を構築した [Aono 07]．アメーバは栄養吸収量を最大化 するべくすべての足を伸ばしたいが，光照射されると縮 退を促される．このとき，光照射のオンオフをアメーバ の形状に応じて更新するフィードバック規則を適切に設 図 1 単細胞の粘菌アメーバ． 時空間振動ダイナミクスの自己組織化により環境を知覚し， 判断し，移動する 図 2 アメーバ計算機． （a）光照射システム，（b）障壁構造定すると，アメーバが被照射リスクを最小化できる組 合せの足だけを伸ばそうと試行錯誤する過程で，組合 せ最適化問題の近似解を探索できる [Aono 07, Aono 09,
Iwayama 16, Zhu 13]．
「巡回セールスマン問題（Traveling Salesman Problem： TSP）」とは，n 個の都市と各都市間の移動距離を定め た地図を与えられたセールスマンが，すべての都市を一 度だけ訪問して出発都市に戻る巡回ルートのうち，総移 動距離が最短になるものを求める組合せ最適化問題であ る（図 3）．n の増大に伴い許容解（巡回ルート）の総数（n− 1）!/2 は階乗的に成長するが，NP 困難問題である TSP の厳密解を多項式時間で得るアルゴリズムは知られてい ない． アメーバ計算機は，TSP の近似解を探索できるリカ レントニューラルネットワークである Amari-Hopfield-Tankモデル [甘利 78, Hopfield 86] の定式化にならい， 都市名 V とその訪問順 k を示すラベル Vk で識別される n2本の溝をもつ障壁構造を用いる（図 3）．状態 X Vk（t） ∈ [0.0, 1.0] は，時刻 t に溝 Vk 中で伸びているアメーバ 足の面積の割合を表す．溝 Vk に照射される光の強度は LVk（t）∈（0.0, 1.0）で表される．照射パターン（すべて の LVkの状態）は , 次式（1）∼（3）によりΔt＝6 秒ご とに更新される [Aono 09]． LVk(t+ t) = －1 , WVk,Ul 35, 0.6( XUl(t)) Ul Δ σΓ Θ σ （1） , (x)=1/ (1+exp (－ (x－ ))) （2） WVk, Ul= if V= ≠ U and k l ( ) if V U and k=l ( ) dst(V, U) (if V U and|k l|=≠ − 1) 0 (otherwise) − − − μ ν ≠ （3） σΓ, Θ（x）∈（0.0, 1.0）はシグモイド関数で，パラメータΓと Θにより，それぞれ傾きとしきい値を調節する．Γ＝ 1 000， Θ＝− 0.5 である．WVk,Ulは溝 Vk と Ul の結合強度で， パラメータλ＝0.5，μ＝0.5，νは，それぞれ同一都市の 再訪問禁止，複数都市の同時訪問禁止，都市 V-U 間の距 離 dst（V, U）に比例した被照射リスクを調節する．νは， 都市間距離の差をできるだけ大きく反映しつつすべての 巡回ルートを探索可能にするため，最遠距離で隣接する 三都市 {V＊, V＊, V＊}＝argmax {V＊, V＊, V＊（dst} （V＊, V＊）＋ dst（V＊, V＊））が決める上限ν＊＝− Θ（dst（V/ ＊, V＊）＋ dst（V＊, V＊））を超えない，できるだけ大きな値に設 定する [Zhu 18]． 実験に先立ち，まずアメーバを障壁構造中央の円形部 分を埋め尽くすよう広がらせ，全初期値を XVk（0）＝0 に そろえる．そして，式（1）∼（3）に基づく照射パター ンの更新を有効にすることで，探索が開始される．アメー バの足は，原則として光照射オフの溝で伸長し，光照射 オンの溝で縮退する．しかし，アメーバの時空間振動ダ イナミクスは，その位相が決める原形質流動の方向によ 図 3 アメーバ計算機が導出した TSP の近似解． 異なる n に対し，アメーバおよび実験環境の物理的サイズ を固定するべく，64 本の溝をもつ障壁構造を用い，n2本の 溝（黒字ラベル）のみが利用可能となるよう，64−n2本の 溝に常に光を照射しアメーバが侵入できないようにした
り，足を光照射オンの溝で伸ばしたり，オフの溝で縮め たりする動作を確率的に発生させる．こうした「揺らぎ 動作」がアメーバの形状を多様化し，広範な解空間を探 索できる．アメーバは，どの組合せの足を伸ばせば被照 射リスクを最小化できるか判断する試行錯誤を重ね，光 刺激に関する情報を蓄積し，最終的に n 本の光照射オ フの溝の中でその足を完全に伸長できることを発見する （図 3）．このとき，伸長した（XVk＝ 1.0 となる）足の組 合せが，巡回ルートに対応する近似解を表現する．図3（a） の n＝4 の例では，4 本のアメーバ足 D1, C2, B3, A4 の みが伸長し，最短の巡回ルート D → C → B → A → D を 表現している． TSPの許容解の総数は都市数 n に対し組合せ爆発を 起こすが，アメーバはそれにどう対抗し，探索の時間と 質（ルート長の短さ）は n の関数としてどう変化するだ ろうか？ こうした疑問から，Aono と Kim らは n を 4 ∼ 8 まで変えて実験を行った [Zhu 18]．この実験の目的 は，解空間の増大（図 4（a））が探索の時間と質に与え る影響を評価することであり，それは物理空間の拡張に よる影響とは区別されなければならない．そこで，異な る n に対しても同サイズの障壁構造を用いることで，足 どうしの距離やそれらの間の情報伝達に要する時間は変 わらない状況で，環境（解くべき問題）の複雑性の増大 にアメーバがどう対応するかに焦点を当てた（図 3）．一 方，より大きな n の実験も原理的には可能である．アメー バ個体は数平方メートルにも広がるので，必要なサイズ の障壁構造と光照射システムを構成すれば，n は数百ま で拡大できるだろう． 図 3 で示される実験で用いた地図は，すべての n に対 し，距離 100 の最短ルートと距離 200 の最長ルートが一 意に存在し，解の分布が平均ルート距離 150 をとる正規 分布に近くなるように設定した．n＝4, 5, 6, 7, 8 につき， それぞれ 12, 11, 12, 11, 23 回の実験を行った．90％に近 い割合で，アメーバは少なくとも一つの許容解を発見で きた（図 4（b））．図 4（c）と図 4（d）は，それぞれ許 容解を発見するまでの時間の平均値とその許容解のルー ト長の評価値を n の関数として示したものである．前者 は，最初に照射が点灯した時点から巡回ルートを表現す る照射パターンが現れるまでの経過時間をカウントして いる．後者は，図 3 の地図をもとに列挙される全許容解 のルート長の平均値（白）を 1 としたときの，実験で発 見された許容解のルート長の平均値の割合（黒）を示し ている．これらの結果は，アメーバ計算機は，TSP のそ こそこ質の良い近似解を，n が増大してもその質を劣化 させることなく（図 4（d）），探索に要する時間の増大 を n のほぼ線形関数に抑えながら発見できている（図 4 （c））という事実を示している． このアメーバ計算機において，アメーバの足やそれら のハブとなる部分（障壁構造中央の円形部分）は，そこ で発生する大自由度の複雑な時空間振動ダイナミクスに より，光照射の経験を記憶し，光刺激応答の適切な揺ら ぎを生成する役割をもつ．実際，アメーバのハブ部分を 分断する対照実験を行うと，発見できた解の質とその探 索に要した時間が著しく劣化した [Zhu 13]．また，アメー バのハブ部分の時空間振動ダイナミクスの時系列を解析 すると，ダイナミクスがよりコヒーレントである（同位 相で同期する傾向が強い）ほど，より質の高い解が発見 されることがわかった [Iwayama 16]．このことは，本 システムの制御ダイナミクスは時間的・空間的相関をも つ揺らぎを発生するダイナミクスとカップルすること で，より高い探索性能を発揮し得ることを示唆している． 2･3 アメーバ計算機の数理モデル TSPの近似解を線形時間で探索できるアメーバの情 報処理はどのような原理だろうか？ Aono と Kim ら は，アメーバ計算機では許容解到達時の全状態値の総和 が n になること（ VkXVk＝n）に注目した [Zhu 18]． もし光照射が導入されない状況で，単位時間当たりにア メーバのハブ部分からすべての足に対し供給される原形 質量の総和が一定値Δinであるなら，時刻 t ＝ n/Δinには VkXVk（n/Δin）＝n が実現される．このときすべての足 は均等に n−1だけ伸び，許容解を表現しない．しかし， この一定の原形質供給の原則が，もし照射パターンが更 新される状況で，光照射によりアメーバの足からハブ部 分に戻される原形質量を勘定に入れてもなお遵守される 図 4 アメーバ計算機およびその数理モデルの TSP 解探索性能
なら，線形時間 t ＝ n/Δin後には VkXVk（n/Δin）＝n が 実現し，かつ，許容解を表現する n 本の足のみが伸びて XVk（n/Δin）＝1 となるはずである． この仮説を数値シミュレーションで検証するため，ア メーバ足の時間発展を次のようにモデル化した [Zhu 18]． XVk(t+1) = XVk( ) Ot－ Vk(t+1)+ Vk(t+1) if L( Vk(t+1) > 0.5) XVk( ) + It Vk(t+1)+ Vk(t+1) (if LVk(t+1) 0.5≦ ) （4） 全初期値は式（2）のシグモイド関数がσ35, 0.6（X0）＝ （n2−1）−1となる X Vk（0）＝X0とし，ξVk∈ [−δ, δ]はノイズ で，最大振幅をδ＝ 0.003 と設定する．OVkは溝 Vk が 光照射オン（LVk＞ 0.5）のときアメーバの足 Vk からハ ブ部分に流出する原形質量であり，次式（5）で定義さ れる． ≦ OVk(t+1) 2 out 20, 0.6(XVk( )t) if L( Vk(t+1) > 0.5) 0 (if LVk(t+1) 0.5) = Δ σ （5） Δout＝0.001 は，光照射により単位時間当たりにアメー バ足 Vk から流出する原形質量を調節する定数である． 式（4）の IVkは光照射オフ（LVk≦ 0.5）のときハブ部 分からアメーバ足に流入する原形質量であり，次式（6） で定義される． IVk(t+1) ( in+S t( )) / Loff(t+1) if L( off(t+1) > 0) 0 (if Loff(t+1) = 0) = Δ （6） Δin＝0.001 は，単位時間当たりに全アメーバ足に流 入する原形質量の総和を調節する定数である．S（t）は， 次式（7）で定義されるアメーバのハブ部分にストック されている原形質量で，単位時間にすべて消却され得る と仮定している．Loff∈ {1, 2, …, n2}は光照射オフの溝の 数を表す． S t( +1) OVk(t+1) Vk if L off(t+1) >0 ( ) S t( ) + in+ O Vk(t+1) Vk if L off(t+1) =0 ( ) = Δ （7） すなわち，アメーバのハブ部分から原形質を供給可能 な光照射オフの足が 1 本もないとき，原形質流入定数 と全足からの原形質流出量の総和がストックに累積され る． 式（4）∼（7）に基づきアメーバ足の状態を更新しな がら式（1）∼（3）に基づいて照射パターンを更新する モデル（ただし，Δt ＝1）の解探索性能を，n を 10 ∼ 20 まで変えて図 3 と同様の方法で作成した地図を用いて検 証した．図 4（e）と図 4（f）は，それぞれ許容解を発 見するまでの反復回数（時間ステップ t）の平均値とそ のルート長の評価値を示しており，図 4（c）と図 4（d） の実験結果をよく再現している．これらの結果は，一定 の原形質供給の原則を遵守できるような物理デバイスを 用いれば，NP 困難問題の近似解をその質を維持しつつ 線形時間で探索できる新たな組合せ最適化マシンを構築 できる可能性を示唆している．そのような物理デバイス としては，一定の電流を循環できるアナログ電子回路な どが考えられる． 式（4）で導入された揺らぎξVkは無相関白色ノイズ であり，アメーバの時空間振動ダイナミクスから生じる 時間的・空間的相関をもつ揺らぎを表現していない．今 後こうしたダイナミクスを表現できるモデルやデバイス を用いることで，探索性能の向上を見込めるかもしれな い．
3．アメーバ型最適化アルゴリズム
Aonoらは，アメーバ計算機の研究から得られた知見 をもとに，より抽象度の高い組合せ最適化問題「充足可 能性問題（Satisfiability Problem：SAT）」の解を探索 するアルゴリズム「AmoebaSAT」を定式化した [Aono 12]．SAT とは，複数の論理的制約条件を満たすように 論理変数 xi（ i ∈ {1, 2, …, N}）に真偽値（1 または 0） を割り当てられるかを判定する一種の制約充足問題であ る．図 5 の問題例は，SAT 解（x1, x2, x3, x4）＝（1, 1, 1, 1） をもつ．N に対し解候補の数は指数関数的（2N）に増大 するが，NP 完全問題である SAT を多項式時間で解くア ルゴリズムは知られていない． AmoebaSATは，各変数 xiの真偽値 xi＝v（v＝0 または v＝1）を，アメーバの足 Xi, v∈{−1, 0, 1} が伸びた状態 Xi, v＝1もしくは縮んだ状態Xi, v≦0により表現するため， N変数の SAT を解くのに 2N 本の足が必要になる（図 5）． 図 5 （a）AmoebaSAT のバウンスバック制御と（b）SAT 解 到達状態変数割当て x＝（x1, x2, …, xN）は，時間ステップ t の状態 X（t）＝（X1, 0（t），…，XN, 1（t））から次のように判定される． xi( )t 0 1 xi(t 1) (otherwise) if Xi, 0( )t =1 and ( if Xi, 1( )t =1 and ( Xi, 0( )t ≦0) Xi, 1( )t≦0) － = （8） 各足 Xi, vの時間発展は，その伸長と縮退を決定する変 数 Yi, v∈ {0, 1} の関数として，次式（9）で定義される． Xi, v(t+1) otherwise ( ) = Xi, v( ) +1 if Yt ( i, v(t+1) =1 and Xi, v( ) <1t ) Xi, v( ) 1t Xi, v( )t if Yi, v(t+1) =0 and ( Xi, v( ) > 1)t － － （9） 各足 Xi, vは，「バウンスバック信号」と呼ばれる抑制信 号 Li, v∈ {0, 1}（光照射の類推）が適用されるとき（Li, v ＝1）縮退し（Yi, v＝0），適用されなければ（Li, v＝0） 伸長する（Yi, v＝1）．ただし，後者のとき（Li, v＝0）， 伸長すべきところで伸長しない（Yi, v＝0）「揺らぎ動作」 が確率的に発生する必要がある．Xi, vが三値を取るのは， 二値ではバウンスバック信号が連続して適用された経験 を記憶できないからである．Yi, vの時間発展は次のよう に定義される． Yi, v(t+1) 0 (if Li, v(t+1) = 1) sgn 1( －－Zi, v(t+1)) if L( i, v(t+1) = 0) = （10） εは揺らぎパラメータ，Zi, v∈ [0.0, 1.0] は揺らぎ源か ら発生する時系列，sgn（z）＝1（if z ＞ 0），0（otherwise） であり，Zi, vが 1−εより大きな値をとるときに揺らぎ 動作が発生する．ここでは，ロジスティック写像Zi, v（t＋1） ＝4Zi, v（t），（1−Zi, v（t））が生むカオス振動を用い，ε＝ 0.24とした．Zi, vの時系列がもつ時間的・空間的相関や εの設定は，解探索性能に大きな影響を与える興味深い 研究対象である [Aono 15a]． 時間ステップ t のすべてのバウンスバック信号 Li, v（t） は，問題例に応じ定義される「バウンスバック規則」と 呼ばれる禁止則に従い，すべての Xi, v（t）を参照し決 定される．例えば，図 5（a）の例では X2, 1（t）＝1 と X3, 0（t）＝1 が成立しており，これは x2＝1 と x3＝0 とい う割当てを含意する．ここで条件（¬ x2∨x3∨¬ x4）に 注目すると，これを充足するには x4＝1 は許されない． そこで，x4＝1 を禁じるバウンスバック信号 L4, 1（t）＝1 を適用する．同様に，条件（x1∨¬ x2）と（x1∨x3）か ら L1, 0（t）＝1 が，（x3∨¬ x4）から L4, 1（t）＝1 が決定さ れる．図 5（a）では，x2＝1 と x3＝0 に対する無矛盾律 を成立させるため，L2, 0（t）＝ 1 と L3, 1（t）＝ 1 にも信号 が適用されている．こうした方針に従い，全条件につき 変数間の相互依存関係を調査し，バウンスバック規則が 定義される． バウンスバック規則とそれに基づくバウンスバック制 御を正確に定義しておく．すべてのバウンスバック規則 の集合 B の要素は（P, Q）の形をしており，集合 P に含 まれるすべてのアメーバ足（j, u）が伸長している（Xj, u＝ 1）ならば，集合 Q で指定されるすべての足（i, v）にバ ウンスバック信号（Li, v＝1）を適用する意味をもつ．こ れを以下で定義する． Li, v(t+1) = 1
if (P, Q) B such that (i, v) Q
and ( j, u)∀ P( Xj, u( ) =1t ) 0 (otherwise) （11） すべてのバウンスバック規則の集合は B＝INTRA ∪ INTER∪ CONTRA として定義される．各変数内での 無矛盾律を担う INTRA は，すべての i につき，INTRA ∋（{（i, v）}，{（i, 1−v）}）が成り立つよう構成される． SAT問題例が複数のリテラルの論理和である節を複数 もつ論理積標準形で与えられるとき，各節 C がリテラ ル xiと ¬ xiを含むことを i ∈ C と−i ∈ C と書くことに する．図 5（a）で説明された方針に則り，INTER はす べての節 C につき変数間の相互依存関係を参照し，次の ように定義される．すべての i ∈ C に対し，集合 P を， j≠i となるすべての j ∈ C につき P ∋（ j, 0），すべて の−j∈ C につき P ∋（ j, 1）として構成し，INTER ∋ （P, {（i, 0）}）を追加する．すべての−i ∈ C に対し，上 と同様に P を構成し，INTER ∋（P，{（i, 1）}）を追加す る．一方，こうして構成された INTER がある変数 i に 対し（P, {（i, 0）}）と（P, {（i, 1）}）を含む場合，P に含ま れる全足が伸長すると Li, 0＝Li, 1＝1 となり，変数 i は 0 と 1 のいずれの値も許されなくなる．こうした相反を排 除するため，その原因をつくった P 中の全足自身にバウ ンスバック信号を適用するのが CONTRA である．すな わち CONTRA は，すべての i に対し，集合 Pi, 0＝{P｜（P, {
（i, 0）}）∈ INTER} と Pi, 1＝{P｜（P, {（i, 1）}）∈ INTER}
をつくり，それらの直積の全要素（Pi, 0, Pi, 1）∈ Pi, 0×Pi, 0 について，CONTRA ∋（Pi, 0∪ Pi, 1, Pi, 0∪Pi, 1）となる よう構成される． AmoebaSATのダイナミクスは，望ましくない状態遷 移をバウンスバック規則により禁じられる環境下で，す べての足が同時並行的に伸び縮みすることで，試行錯誤 を反復しながら解を探索する過程である．そして，バウ ンスバック信号が適用されないすべての足が伸びた状態 を維持できる安定状態に到達したとき，SAT 解が発見
される（図 5（b））．AmoebaSAT の状態 Xi,v（t）は，す
べての（i,v）について Xi,v（t）＝1 ⇒ Li,v（t）＝ 0 または
Li,v（t）＝ 1 ⇒ Xi,v（t）≦ 0 が成り立つとき安定である．こ のとき，AmoebaSAT のダイナミクスが安定することと， その状態が SAT 解を表現することが同値であることが， 数学的に証明されている [巳波 14]．バウンスバック規 則は不正解に関する部分的な既知の情報であり，それら に抵触しない足の伸ばし方が発見されるとき，全体的に 整合性のとれた未知の正解が得られる．アメーバ計算は 既知の断片的な不正解の否定を通して未知の正解に遭遇 しようとするのである． AmoebaSATを CPU による実装のために洗練したア
ルゴリズムと，SAT Competition 2013 の Random SAT 部門優勝の確率的局所探索アルゴリズム「ProbSAT」 [Balint 12]を，同条件の CPU 上で実行したときの探索 性能を比較した．ここでは SATLIB[Hoos 00] が公開す る，N ＝ 50 で節の数 M ＝ 218 の Uniform Random-3-SATの例「uf50-100.cnf」に注目した．この問題例は， SAT解をただ一つもつ．そこで，h 個コピーした uf50-100.cnfを変数の共有がないよう連結すると，N＝h･50 で M＝h･218 の唯一解をもつ問題例を構成できる．この 特殊な方法で問題例を生成すると，解探索時間が N の 関数としてどう成長するか外挿して見積もりやすくな る．図 6 は，N が 50 ∼ 6 000 までの範囲で，各アルゴ リズムが解探索に要した反復回数の平均値（500 回試行） を示している． ProbSATの反復回数は O（N）で成長した．この結果 は，この問題例が N に比例する数の独立な部分問題に 分割されること，ProbSAT の 1 回の反復処理が一つの 変数状態のみを更新する逐次動作であることを考えれ ば，妥当である．一方，AmoebaSAT は O（Log N）で 成長する圧倒的に少ない反復回数で解を探索できた． AmoebaSATでは，全アメーバ足の変数状態が並列的に 更新されることが功を奏していると見られる．この並列 動作は，しかし，逐次動作の CPU による実装では擬似 的にしか表現できない．実際，CPU 時間での比較では， AmoebaSATは ProbSAT より長い探索時間を要する． よって，並列に動作する物理デバイスで AmoebaSAT を 実装すれば，CPU 実装時と比較して 1 回の反復処理の 時間を大幅に短縮でき，SAT 解探索を劇的に高速化でき る可能性がある．
4．アメーバ型最適化チップ
Kasaiらは，コンデンサを並列接続して AmoebaSAT を実装する「アナログ電子アメーバ」[Kasai 13]（図 7） を開発し，小規模の SAT（N ＝ 12）で解探索動作を実証 した [Saito 18]．この回路を大規模集積化する技術基盤は すでに確立しており，大規模問題への適用も可能である． Kasaiらは，室温の熱揺らぎを利用し確率的に動作する 半導体ナノワイヤ素子「電子ブラウンラチェット」を用 い，小型・低消費電力で動作する電子アメーバも提案し ている [Aono 15a]．一方，Hara らは，AmoebaSAT をディ ジタル電子回路（Field Programmable Gate Array： FPGA）で実装し，N ＝ 50 の SAT 解探索を実証した [Ngoc 18]．Takeuchi らは，断熱的超伝導論理回路と その確率的論理演算を用い，簡単な制約充足問題の解 を探索している [Takeuchi 18]．さらに Takeuchi らは， AmoebaSATの条件分岐を簡略化し論理ゲートの組合せ で表現する「ディジタル電子アメーバ」を考案し（特許 出願済），その FPGA 実装により，従来の逐次動作アル ゴリズムの CPU 実装を上回る高速な SAT 解探索の実現 を見込んでいる． これらの「アメーバ型最適化チップ」はアーキテクチャ が簡潔であり，小型・低消費電力化が可能である [Aono 15a, Kasai 13]．アナログ電子アメーバは，センサやア クチュエータからアナログ信号として流れてくる環境情 報を探索プロセスに直接取り込めるため，ロボット制御 などの即応性を要するエッジ処理に好適である．実際， 多足歩行ロボットに組み込むと，未知の環境を踏破でき る運足パターンを探索できる [Saito 18]．バウンスバッ ク制御は，実社会の多様な応用問題を容易に回路にマッ図 6 AmoebaSAT（黒）および ProbSAT（白）の SAT 解
ピングできる．Aono らは，化学反応を原子集団による 安定な制約充足解の探索過程として表現する反応シミュ レータを提案した [Aono 15b]．さらに，バウンスバック 制御は，更新が必要な（制約未充足）変数状態のみが確 率的に揺らぐよう導くので，要求が動的に変化する状況 でも，揺らぎレベルを一定に保ちながら，更新が不要な 変数状態を改悪せずに探索を進行でき，常に質の良い解 を提示し続けられると期待される．著者らは，電子アメー バのこれらの特長を生かし，要求変化の激しいスマート 工場内の搬送経路最適化や，複雑な環境への適応を要求 される自律ロボットの制御最適化に応用する研究開発を 開始している．
5．アメーバ型移動ロボット
サイバー空間における情報技術の応用範囲が拡大し続 ける現代にあっても，ロボットの活動空間は依然として 限定的である．ロボットがフィジカル空間で活躍するに は，不確実性や多様性が高い複雑な環境であっても，そ の機能をロバストに発揮できる必要がある．しかし，従 来の工業用ロボット制御の延長上にある現在のフィード バック制御によっては，そのために要求される動作の速 度と精度を保証することが難しい．そこで注目されてい るのが，フィジカル空間で歩行，走行，飛行などの複雑 な運動をロバストに実現している，生物に学んだロボッ トの制御・設計パラダイムである [新山 18, Pheifer 07]． 著者らは，生物がロバスト性を実現できるのは，その 身体を構成する素材の柔軟性と，それらを制御する頭脳 の情報処理原理の柔軟性が併立しているからであると考 える．そこで，空気圧により自在に膨張・収縮する幕で 区画化された空気室が複数設置されたクローラ（図 8（a）） を柔軟に変形させることにより，接地面の凹凸などの複 雑性を懐柔しながら，未知の階段や畦道であっても重た い荷物を載せながらロバストに走破できる「アメーバ 型移動ロボット」（図 8（b））の研究開発を進めている． こうしたクローラを制御する頭脳には，動的に変化する 環境中で複数の空気室への加圧・減圧の最適な組合せを 高速に探索できるアメーバ型最適化チップを組み込む． 複雑な環境からセンサやアクチュエータを介してアナロ グ信号として流れてくる情報は，バウンスバック信号と してアメーバ型最適化チップが解くべき問題の制約条件 を直接規定する．こうすることで，ロボットは未知の複 雑地形をも踏破できる創造的な動作パターンを高速に探 索できるようになるかもしれない．これが実現すれば， 物流「ラストマイル」において，ロボットが人に代わっ て荷物を運搬できる場面を少なからず拡大できると期待 している．6．お わ り に
アメーバのように，情報としての属性をもつ物質であ り，物質としての属性をもつ情報でもあるような人工シス テムを構築することで，サイバー空間とフィジカル空間 の断絶した傷口を癒合することができないだろうか？ 著者らは，アメーバのようにその身体を環境に応じて柔 軟に変形させられる「ソフトロボット」[新山 18] の開 発を通し，状況に対する知識を蓄え正しい判断をできる 物質や，質量や体積をもち物体を動かす力を伝達できる 信号が活躍するプラットフォームを構築し，従来技術で は難しい，フィジカル空間中で発生する想定外の事態に も臨機応変に対応できる能力を具現化することを目指し ている．◇ 参 考 文 献 ◇
[甘利 78] 甘利俊一：神経回路網の数理，産業図書（1978） [Aono 07] Aono, M., Hara, M. and Aihara, K.: Amoeba-basedneurocomputing with chaotic dynamics, Commun. ACM, Vol. 50, No. 9, pp. 69-72（2007）
[Aono 09] Aono, M., Hirata, Y., Hara, M. and Aihara, K.: Amoeba-based chaotic neurocomputing: Combinatorial optimization by coupled biological oscillators, New Generation Computing, Vol. 27, pp.129-157（2009）
[Aono 12] Aono, M., Kim, S.-J., Zhu, L., Naruse, M., Ohtsu, M., Hori, H. and Hara, M.: Amoeba-inspired SAT solver, Proc.
NOLTA 2012, pp.586-589（2012）
[Aono 15a] Aono, M., Kasai, S., Kim, S.-J., Wakabayashi, M., Miwa, H. and Naruse, M.: Amoeba-inspired nanoarchitectonic computing implemented using electrical Brownian ratchets,
Nanotechnology, Vol. 26, 234001（2015）
[Aono 15b] Aono, M. and Wakabayashi, M.: Amoeba-inspired heuristic search dynamics for exploring chemical reaction paths, Origins of Life and Evolution of Biospheres, Vol. 45, No. 3, pp. 339-345（2015）
[Balint 12] Balint, A. and Schöning, U.: Choosing probability distributions for stochastic local search and the role of make versus break, LNCS of SAT 2012, Vol. 7317, pp. 16-29（2012） [Dennett 87] Dennett, D.: Cognitive wheels: The frame problem
of AI, Pylyshyn, Z. W.（ed.）: The Robot’s Dilemma, Praeger
（1987）
[林 17] 林 克彦：宅配便革命，マイナビ出版（2017）
[Hoos 00] Hoos, H. H. and Stutzle, T.: SATLIB: An online resource for research on SAT, Proc. SAT2000, pp. 283-292, IOS Press （2000）
[Hopfield 86] Hopfield, J. J. and Tank, D. W.: Computing with neural circuits: A model, Science, Vol. 233, No.4764, pp. 625-633（1986）
[堀 08] 堀 裕和：電子・情報・通信のための量子力学，コロナ社（2008） [Iwayama 16] Iwayama, K., Hirata, Y., Aono, M., Zhu, L., Hara, M. and Aihara, K.: Decision-making ability of Physarum 図 8 アメーバ型移動ロボットの構成（a）と動作（b）の模式図
polycephalum enhanced by its coordinated spatiotemporal
oscillatory dynamics, Bioinspiration & Biomimetics, Vol. 11, 036001（2016）
[Kasai 13] Kasai, S., Aono, M. and Naruse, M.: Amoeba-inspired computing architecture implemented using charge dynamics in parallel capacitance network, Appl. Phys. Lett., Vol. 103, 163703（2013） [国交省 17] 国土交通省：物流を取り巻く現状について（2017） [三木 16] 三木良雄：IoT ビジネスをなぜ始めるのか？，日経 BP 社（2016） [巳波 14] 巳波弘佳，青野真士，成瀬 誠，葛西誠也：粘菌アメーバ 型解探索アルゴリズムとそのナノデバイスによる実現，信学技 報，Vol. 113, No. 488, COMP2013-71, pp. 77-82（2014） [Nakagaki 00] Nakagaki, T., Yamada, H. and Toth, A.:
Intelligence: Maze-solving by an amoeboid organism, Nature, Vol.407, No. 470（2000）
[内閣府 16] 内閣府：科学技術基本計画（2016）
[Negroponte 96] Negroponte, N.: Being Digital, Knopf（1996） [Ngoc 18] Ngoc, A. H. N., Aono, M. and Hara-Azumi, Y.:
Amoeba-inspired SAT solvers on FPGA through high level synthesis, 信学技報，Vol. 117, No. 455, VLD2017-93, pp. 25-30（2018） [新山 18] 新山龍馬：やわらかいロボット，金子書房（2018） [Pheifer 07] Pfeifer, R. and Bongard, J.: How the Body Shapes the
Way We Think, MIT Press（2007）
[Saito 18] Saito, K., Suefuji, N., Kasai, S. and Aono, M.: Amoeba-inspired electronic solution-searching system and its application to finding walking maneuver of a multi-legged robot, IEEE Symp. on Multi-Valued Logic（ISMVL） 2018, pp. 127-131（2018）
[柴田 04] 柴田正良：ロボットがフレーム問題に悩まなくなる日， 信原幸弘（編）：シリーズ心の哲学，勁草書房（2004）
[Takeuchi 18] Takeuchi, N., Aono, M. and Yoshikawa, N.: Superconductor amoeba-inspired problem solver for combi-natorial optimization（submitted）
[Zhu 13] Zhu, L., Aono, M., Kim, S.-J. and Hara, M.: Amoeba-based computing for traveling salesman problem: Long-term correlations between spatially separated individual cells of Physarum polycephalum, BioSystems, Vol. 112, pp.1-10（2013）
[Zhu 18] Zhu, L., Kim, S.-J., Hara, M. and Aono, M.: Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism（submitted） 2018年 7 月 17 日 受理
