膨大な数の空間点データからなる現象を少数のセンサ情報から表現する

最適なセンサ位置を決定する新たなアルゴリズムを開発

広範な学術・産業応用や実用化前進に期待

発表のポイント

少数のセンサで複雑な現象を計測する技術が昨今注目を集めていますが、効率良く効果的に最適なセンサ位置を決定するための既存の計測手法は、コストや計測精度に難があり実用化に課題が多く存在していました。

一度に全センサ位置の最適な組み合わせを選択する新たなアルゴリズムを開発しました（図１）。この新たな計測手法を用いて、ノイズを多く含む実験データで精度検証を行い、その有効性を実証しました。

新たな計測手法の課題となる計算コストを低減するため、量子インスパイアード技術である富士通の「Fujitsu Quantum-inspired Computing Digital Annealer」(以下、「デジタルアニーラ」)を用いたことで、高速に解を得ることができました。

早稲田大学大学院創造理工学研究科修士課程の井上智輝（いのうえともき）と同大学理工学術院教授の松田佑（まつだゆう）、ならびに東北大学流体科学研究所教授の永井大樹（ながいひろき）と同大大学院工学研究科博士課程後期の伊神翼（いかみつばさ）、愛知工業大学工学部教授の江上泰広（えがみやすひろ）らの研究グループ（以下、本研究グループ）は、センサ位置最適化問題を解消するため、従来研究されてきた方法論とは全く異なるアプローチで、60万点強の空間点データからなる多自由度の現象を、数十から数百点でのデータ情報を基に表現するための位置選択アルゴリズムを開発しました。また、実際にノイズを多く含む実験データへの応用を行い、その有効性を実証しました。さらに、組合せ最適化問題を高速に解く量子インスパイアード技術^*1である富士通の「デジタルアニーラ」^*2を用いることで、高速に解を得ました。

本研究成果は、オランダのエルゼビア社が発行する『Mechanical Systems and Signal Processing』に2022年12月8日（木）（現地時間）に掲載されました。

(1)これまでの研究で分かっていたこと（科学史的・歴史的な背景など）

少数のセンサで複雑な現象を計測する技術が注目を集めています。少数のセンサでの計測が実現できれば、低コストで現象を把握できます。またデータ取得・解析を高速に行うことができるため、これにより迅速な意思決定も可能になります。しかし少数のセンサで効果的な計測を行うためには、センサの位置を適切に決定する必要があります。このような問題はセンサ位置最適化問題^*3と呼ばれています。

センサ位置最適化問題を解く方法として、凸緩和法^*4や貪欲法^*5が提案されています。しかし凸緩和法では計算コストが大きく、多くの空間点からなるデータの解析には不向きです。また凸緩和法は、ノイズを多く含む実際の実験データには有用でないことが指摘されていました。一方、貪欲法は計算コストが小さいものの局所解に陥ることが多いことが知られており、特にセンサ数が一定数を超えた場合、センサの位置をランダムに決定する乱択法よりも推定精度が低下してしまうという問題がありました。

(2)今回の研究で新たに実現しようとしたこと、明らかになったこと

貪欲法においてはセンサ位置を1点ずつ順にその選定時に最適となるように決定していきます。このとき、互いに似通った情報をもつ点を選択するようになると、貪欲法はセンサ位置の推定精度が悪化する特徴を有することに本研究グループは着目しました。

そこで本研究では、互いに近傍となる位置を選ばないように、またセンサ位置を１点ずつ順に選ぶのではなく、一度に全センサ位置の最適な組み合わせを選択することで貪欲法の問題点を解決できると考えました。例えば図2のように、貪欲法では１点ずつ順に1から５までの５点を選ぶときに各時点で最適な位置を選択します。このとき以前に選択した位置を考え直すということを行いません。これに対して本研究で提案した手法では、１点ずつ順に選ぶよりも５つの点の組み合わせとしてより適切な組み合わせが得られるのではないかと考えました。

(3)そのために新しく開発した手法

センサ位置最適化問題は、現象を効率的に表現する少数のセンサを選択する問題です。これは特徴的な挙動を示す位置を選ぶことであると言えます。本研究グループは、特徴的な挙動を示す位置を選びつつ、一方で似たような特徴を示す位置を選ばないような、センサ位置の組み合わせを選択するアルゴリズムを考えました。

そこで、任意の2つの空間位置に対して、現象の特徴を良く表し、かつ互いに類似性が低い場合に大きな値をとる重みを考えました。このように考えると、各空間位置をノード^*6とし各ノード間を結ぶエッジ^*7を上記の重みとするグラフと捉えることができます（図3）。すると目的とするセンサ位置の組み合わせは、一定値以上の重みをもったエッジを残した無向グラフにおいて、最大クリーク問題^*8の解を与える組み合わせと考えることができます。最大クリーク問題は、その補グラフ^*9に対する最大独立集合問題^*10と等価であることが知られており、この最大独立集合問題を解くことでセンサ位置の組み合わせを決定しました。

なお、最大クリーク問題も最大独立集合問題もNP困難^*11であることが知られています。本問題を通常のコンピュータで計算するには、たくさんの候補点からセンサ位置の組み合わせを決定することになり、計算コストが大きく困難です。そのため、本研究では、量子コンピュータなどで注目度の高い組み合わせ最適化問題に特化した新しいコンピュータの１つである富士通「デジタルアニーラ」を用いることで高速に解を得ました。

本研究では、提案した手法によって得られた解の妥当性を評価するために、NOAA-STTデータ（National Oceanic and Atmospheric Administration（アメリカ海洋大気庁）の提供している海水面温度変化データ）を用いた精度検証を行いました。これにより従来法と遜色なく少数の点での温度データのみから元の海水面温度分布を再現できることを示しました（図4）。

また実際にノイズを多く含む実験データに提案手法を適用しました。実験データは流れに直角に置かれた角柱後方にできるカルマン渦^*12を感圧塗料法^*13によって計測したもので、60万点強の空間点からなるデータであり非常に大きなスケールの対象です。またこのデータには非常に大きなノイズが含まれています（図5の左図）。本論文では、このような複雑な現象について、数十から数百点でのデータ情報を基に表現するためのセンサ位置の最適な配置を決定しました(図5の中図のピンク色の点)。そして、選択されたセンサ位置の情報を基にノイズを低減したデータを再構成しました（図5の右図）。この再構成されたデータを、半導体圧力センサによって計測したデータと比較しました。ここで半導体圧力センサは、感圧塗料法とは異なり計測点を設置した場所での計測値しか得られませんが、非常に精度が高いことが知られています。提案手法によって再構成したデータは、この半導体圧力センサでの計測結果と0.3%以下のずれであり非常によく一致することを確認し、本研究の有効性を示しました。

(4)研究の波及効果や社会的影響

センサ位置最適化問題では凸緩和法の高速化と貪欲法の高精度化の研究が主に行われていますが、本研究グループはこれらとは本質的に異なる新しいアプローチを提案するとともにその有効性を示しました。今後、センサ位置最適化問題の学術・産業応用へ大きなインパクトを与えると期待されます。

あわせて、センサ位置最適化問題は、NOAA-STT（海水面温度変化）のセンシングや流体力学に留まらず広範な応用が期待されています。同様に、本研究で応用例として扱った感圧塗料法は航空機・鉄道・自動車の空力設計への応用を通じ、安全性の向上や空力抵抗の低減に大きく貢献することが期待されています。これまで、感圧塗料法では計測ノイズが障害となり鉄道・自動車分野への応用は難しいとされてきました。しかし、本アルゴリズムによって感圧塗料法はこれらの問題への応用へ向けて前進すると考えられます。

量子コンピュータ、デジタルアニーラなど新しいタイプのコンピュータが注目されています。ただし上記のような実応用を見据えた技術への応用例はまだ数が少なく、このたびの研究成果は、これらのコンピュータの新しい応用としてもインパクトが大きいと考えています。

(5)今後の課題

複雑な現象を対象としたときに、どの程度の現象再現能に対してどの程度のセンサ数が必要なのか明らかにしたいと考えています。これによって実際の機械や環境モニタリングへの応用を行う際に、必要なセンサ数を決定することが可能となります。また実応用では事前に得られる情報に制限があることが想定されるため、このような場合にも有効なセンサ位置最適化についても研究を重ねたいと考えています。

(6)研究者のコメント

本研究では、センサ位置最適化問題に対して新しいアプローチを提案いたしました。センサ位置最適化問題はこれまで凸緩和法や貪欲法などを用いた解法が提案されています。このたび開発した新たな手法はこれらの手法と同等以上の結果を得ることができます。特に、従来の手法に比べてもセンサが満たすべき条件を素直に立式した直感的に理解しやすい方法となっているところが特長です。仮に問題や条件がかわっても、新手法のコンセプトを用いることで、比較的容易に問題に合わせて定式化を行い、解を得ることができる点が特に優れていると考えています。

(7)用語解説

※1　量子インスパイアード技術

量子現象に着想を得たコンピューティング技術で、現在の汎用コンピュータでは解くことが難しい「組合せ最適化問題」を高速で解く技術

※2　Fujitsu Quantum-inspired Computing Digital Annealer（デジタルアニーラ）

現在の汎用コンピュータでは解くことが困難な組合せ最適化問題を高速に解く富士通独自の量子インスパイアード技術。https://www.fujitsu.com/jp/digitalannealer/index.html

※3　センサ位置最適化問題

少数の位置でのデータから効率的に現象の表現を実現するための位置を決定する問題。

※4　凸緩和法

非凸の目的関数を凸関数で近似表現し計算する方法。

※5　貪欲法

一つ一つ順にその時に最適になるように解を決定する方法。

※6　ノード

グラフの頂点。本稿ではセンサ位置の候補点。

※7　エッジ

ノード間を結ぶ辺。

※8　最大クリーク問題

全てのノードの組にエッジが存在するグラフの部分をクリークと呼び、最大の大きさのクリークを見つける問題を最大クリーク問題という。本研究では全てのセンサ位置候補同士が、現象の特徴を良く表し、かつ互いに類似性が低い場合に大きな値をとる重みでつながれている必要があるためにクリークを考える。最大クリークを見つけることで、現象を表現するセンサ位置をもれなく選定することができる。

※9　補グラフ

エッジの有無を入れ替えたグラフ。すなわち元のグラフにおいて存在するエッジを削除し、エッジがないノード間にエッジを設けたグラフ。

※10　最大独立集合問題

どのノードもクリークに含まれないような集合のうち最大のものを見つける問題。エッジの有無を入れ替えたグラフ（補グラフ）に対する最大独立集合問題を考えることは、もとのグラフの最大クリーク問題を考えることと同じになる。

※11　NP困難

NPはNondeterministic Polynomialの頭文字。問題の大きさに対して、その多項式で表される時間で解くことができる問題をクラスNPと呼ぶ。これらの問題よりも多くの時間を要する問題をNP困難と呼び、問題が大きくなるほど膨大な計算時間を要する。近年、NP困難を解くためのツールとして量子コンピュータをはじめ新しいコンピュータが提案されている。

※12　カルマン渦

流れの中に角柱や円柱を置いたときに、これらの物体の後方で見られる特徴的な渦。角柱、円柱の両端から交互に渦が出ているように見える。

※13　感圧塗料法（Pressure-sensitive paint; PSP）

感圧塗料（PSP）は、一般に酸素消光作用を有するりん光分子とこれを模型表面に保持固定するためのバインダから構成される。PSP計測法では、このりん光分子の放つ発光の強度が圧力に応じて変化することから、PSPの発光強度分布を計測することで圧力分布を計測する。

(8)論文情報

雑誌名：Mechanical Systems and Signal Processing
論文名：Data-Driven Optimal Sensor Placement for High-Dimensional System Using Annealing Machine
執筆者名（所属機関名）：井上智輝（早稲田大学大学院生）、伊神翼（東北大学大学院生）、江上泰広（愛知工業大学教授）、永井大樹（東北大学教授）長沼靖雄（富士通株式会社）、木村浩一（富士通株式会社）、松田佑*（早稲田大学教授）
掲載日時（現地時間）： 2022年12月8日（木）
掲載URL： https://www.sciencedirect.com/science/article/pii/S0888327022010251
DOI： https://doi.org/10.1016/j.ymssp.2022.109957

(9)研究助成（外部資金による助成を受けた研究実施の場合）

研究費名：科学技術振興機構（ＪＳＴ） 戦略的創造研究推進事業個人型研究（さきがけ）
「計測技術と高度情報処理の融合によるインテリジェント計測・解析手法の開発と応用」（研究統括：雨宮 慶幸）

研究課題名：圧縮センシングを活用した高精度空力診断システムの構築　JPMJPR187A
研究代表者名（所属機関名）：松田佑（早稲田大学）
研究費名：東北大学流体科学研究所一般公募共同研究：J22I020
研究課題名：構造化照明を用いた高精度PSP計測手法の開発
研究代表者名（所属機関名）：松田佑（早稲田大学）、永井大樹（東北大学）