Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
侵入者の特性を考慮した相互情報量に基づく巡回経路の評価 / Evaluation of pat...
Search
konakalab
August 29, 2023
Science
0
190
侵入者の特性を考慮した相互情報量に基づく巡回経路の評価 / Evaluation of patrol route based on mutual information considering characteristics of intruders
令和五年度 電気・電子・情報関係学会 東海支部連合大会で発表したスライドです.
konakalab
August 29, 2023
Tweet
Share
More Decks by konakalab
See All by konakalab
システム数理と応用分野の未来を切り拓くロードマップ・エンターテインメント(スポーツ)への応用 / Applied mathematics for sports entertainment
konakalab
0
200
実力評価性能を考慮した弓道高校生全国大会の大会制度設計の提案 / (konakalab presentation at MSS 2025.03)
konakalab
2
94
Masseyのレーティングを用いたフォーミュラレースドライバーの実績評価手法の開発 / Development of a Performance Evaluation Method for Formula Race Drivers Using Massey Ratings
konakalab
0
85
科学で迫る勝敗の法則(電気学会・SICE若手セミナー講演 2024年12月) / The principle of victory discovered by science (Lecture for young academists in IEEJ-SICE))
konakalab
0
80
Design of three-dimensional binary manipulators for pick-and-place task avoiding obstacles (IECON2024)
konakalab
0
150
科学で迫る勝敗の法則(名城大学公開講座.2024年10月) / The principle of victory discovered by science (Open lecture in Meijo Univ. 2024)
konakalab
0
290
五輪球技5競技10種目に対する一対比較モデルの予測性能の継続的調査 / Paird comparison prediction model for ball games in recent Olympic Games
konakalab
0
59
作業領域内の障害物を回避可能なバイナリマニピュレータの設計 / Design of binary manipulator avoiding obstacles in workspace
konakalab
0
220
様々な侵入者タイプに対応した適切な警備計画の策定 / Patrol route design considering various types of intrudes
konakalab
0
240
Other Decks in Science
See All in Science
マテリアルズ・インフォマティクスの先端で起きていること / What's Happening at the Cutting Edge of Materials Informatics
snhryt
1
210
03_草原和博_広島大学大学院人間社会科学研究科教授_デジタル_シティズンシップシティで_新たな_学び__をつくる.pdf
sip3ristex
0
240
Healthcare Innovation through Business Entrepreneurship
clintwinters
0
200
Snowflakeによる統合バイオインフォマティクス
ktatsuya
0
640
非同期コミュニケーションの構造 -チャットツールを用いた組織における情報の流れの設計について-
koisono
0
230
学術講演会中央大学学員会八王子支部
tagtag
0
290
FRAM - 複雑な社会技術システムの理解と分析
__ymgc__
1
120
統計的因果探索: 背景知識とデータにより因果仮説を探索する
sshimizu2006
3
750
点群ライブラリPDALをGoogleColabにて実行する方法の紹介
kentaitakura
0
100
Trend Classification of InSAR Displacement Time Series Using SAE–CNN
satai
3
190
MoveItを使った産業用ロボット向け動作作成方法の紹介 / Introduction to creating motion for industrial robots using MoveIt
ry0_ka
0
350
【健康&筋肉と生産性向上の関連性】 【Google Cloudを企業で運用する際の知識】 をお届け
yasumuusan
0
510
Featured
See All Featured
The Straight Up "How To Draw Better" Workshop
denniskardys
232
140k
The MySQL Ecosystem @ GitHub 2015
samlambert
251
12k
A designer walks into a library…
pauljervisheath
205
24k
YesSQL, Process and Tooling at Scale
rocio
172
14k
Fashionably flexible responsive web design (full day workshop)
malarkey
407
66k
Writing Fast Ruby
sferik
628
61k
Code Review Best Practice
trishagee
67
18k
Documentation Writing (for coders)
carmenintech
69
4.7k
Art, The Web, and Tiny UX
lynnandtonic
298
20k
Designing Experiences People Love
moore
140
23k
No one is an island. Learnings from fostering a developers community.
thoeni
21
3.2k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
50
2.4k
Transcript
侵入者の特性を考慮した 相互情報量に基づく 巡回経路の評価 坂倉健太* 小中英嗣 名城大学大学院 理工学研究科 情報工学専攻 令和五年度 電気・電子・情報関係学会
東海支部連合大会
研究背景 ➢ 警備ロボットの巡回警備の実用化 https://www.knightscope.com/k5/ 警備の自動化 警備員の負担の軽減・警備の質の向上 警備員の代わりに警備ロボットを導入
➢ 巡回警備の目的:火災・不審者・事故の早期発見と拡大防止 研究背景 これらの事象を総称してインシデント ➢巡回警備の考慮すべき点: ➀巡回経路が単一の経路 ➁訪問間隔が長い地点が 存在する 侵入者によって ➀経路が予測される
➁インシデントの発生 が容易となる
➢ 本研究の目的: 研究背景 • 訪問間隔を警備の一周毎に変化させる手法の提案 • 警備ロボットの訪問間隔を観測しインシデントを起こす侵入者のモデル化 本研究の提案手法を相互情報量に基づいて評価し 単一の巡回経路との比較を行う
➢ 巡回警備の条件: • 地図上での全ての通路を少なくとも一回は通る • 経路の始点と終点が同じ CPP(中国人郵便配達問題) CPPに帰着 地図が無向グラフ ➢
CPP(中国人郵便配達問題): 無向グラフの全ての道を少なくとも一度通り、出発点に戻る経路 のうち総経路長が最小のものを求めるグラフ問題
1. 地図を無向グラフに変換 2. 最小重み最大マッチングを用いた多重グラフの生成 3. 多重グラフに対してオイラー回路を求める CPPの解法
地図上の通路を辺、通路同士の交差点を頂点、頂点間の距離を辺の重み 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 2.0 地図を無向グラフに変換 与えられた元の地図 変換した無向グラフ
1.0 1.0 2.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 • 次数(頂点に繋がっている辺の数)が奇数の頂点間のみで 最小重み最大マッチングを求める ➢ マッチング 次数が奇数の頂点6個を2個ずつ の三組に分ける 最小重み最大マッチングを用いた多重グラフの生成
1.0 1.0 2.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 • 次数(頂点に繋がっている辺の数)が奇数の頂点間のみで 最小重み最大マッチングを求める ➢ マッチング 次数が奇数の頂点6個を2個ずつ の三組に分ける 最小重み最大マッチングを用いた多重グラフの生成 マッチングは15通り存在
1.0 1.0 2.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 ➢ 結果 • マッチング:(1,2) (4,9) (6,7) • マッチングの重みの総和:4.0 最小重み最大マッチングを用いた多重グラフの生成
1.0 1.0 2.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 ➢ 結果 • マッチング:(1,2) (4,9) (6,7) • マッチングの重みの総和:4.0 最小重み最大マッチングを用いた多重グラフの生成 15通りの中で最小のもの
1.0 1.0 2.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 ➢ 結果 • マッチング:(1,2) (4,9) (6,7) • マッチングの重みの総和:4.0 最小重み最大マッチングを用いた多重グラフの生成 15通りの中で最小のもの ➢ 最小重み最大マッチング: 重みの総和が最小となるマッチング
• 元のグラフにマッチングを追加し多重グラフを生成 • 多重グラフ 最小重み最大マッチングを用いた多重グラフの生成
• 元のグラフにマッチングを追加し多重グラフを生成 • 多重グラフ 最小重み最大マッチングを用いた多重グラフの生成 全ての頂点の次数が偶数
多重グラフに対してオイラー回路を求める ➢ オイラー回路を求め巡回経路を生成: 地図上での全ての通路を少なくとも一回は通る、最短の経路
多重グラフに対してオイラー回路を求める ➢ オイラー回路を求め巡回経路を生成: 地図上での全ての通路を少なくとも一回は通る、最短の経路 ➀
多重グラフに対してオイラー回路を求める ➢ オイラー回路を求め巡回経路を生成: 地図上での全ての通路を少なくとも一回は通る、最短の経路 ➀ ➁
多重グラフに対してオイラー回路を求める ➢ オイラー回路を求め巡回経路を生成: 地図上での全ての通路を少なくとも一回は通る、最短の経路 ➀ ➁ ③
多重グラフに対してオイラー回路を求める ➢ オイラー回路を求め巡回経路を生成: 地図上での全ての通路を少なくとも一回は通る、最短の経路 ➢ 問題点 単一の経路なため巡回経路を予測される ➀ ➁ ③
多重グラフに対してオイラー回路を求める ➢ オイラー回路を求め巡回経路を生成: 地図上での全ての通路を少なくとも一回は通る、最短の経路 ➢ 問題点 単一の経路なため巡回経路を予測される ➀ ➁ ③
➢ 提案手法: 最小重み最大マッチングに着目し、 前の周と異なる複数の巡回経路を生成
提案手法の概要 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 2.0 16.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 2.0 マッチングをランダムで一つ選択
提案手法の概要 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 2.0 16.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 2.0 重みを非常に大きな値に変更 マッチングをランダムで一つ選択
提案手法の概要 1.0 1.0 2.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 16.0 ➢ 結果: • マッチング:(1,7) (2,6) (4,9) • 次数が奇数の頂点間のみで最小重み最大マッチングを求める
提案手法の概要 1.0 1.0 2.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 16.0 ➢ 結果: • マッチング:(1,7) (2,6) (4,9) • 次数が奇数の頂点間のみで最小重み最大マッチングを求める (6,7)を選ばないマッチング • マッチングの重みの総和:6.0
提案手法の概要 新しく生成された経路 前の周の経路 ➀ ➀
提案手法の概要 新しく生成された経路 前の周の経路 ➀ ➀ ➁ ➁
提案手法の概要 新しく生成された経路 前の周の経路 ➀ ➀ ➁ ➁ ③ ③
提案手法の概要 新しく生成された経路 前の周の経路 ➀ ➀ ➁ ➁ ③ ③ 提案手法によって生成される
巡回経路は 一周毎に変化している
侵入者モデル ➢ 侵入者がインシデントを発生させるのに要する時間 𝑇𝑐 を設定 𝑇𝑐 間警備ロボットが来ないと確信 侵入者は目的の辺で警備ロボットの 訪問間隔時間を観測し続ける 侵入者が目的の辺でインシデントを発生
観測
侵入者モデル 𝑇𝑐 = 500 観測 𝑆𝑠 ∆𝑡 ≤ 𝑇𝑐 𝑆𝑙
∆𝑡 > 𝑇𝑐 ∆𝑡𝑖 = {400,500,800,150} ∆𝑡𝑖 :𝑖番目の訪問間隔時間 𝑆 ∊ { 𝑆𝑠 , 𝑆𝑙 }:状態 𝑇𝑐 :インシデント発生に要する時間 侵入者モデル 𝑺𝒊 から𝑺𝒊+𝟏 を予測 𝑆𝑖 = { 𝑆𝑠 , 𝑆𝑠 , 𝑆𝑙 , 𝑆𝑠 }
侵入者モデル 𝑇𝑐 = 500 観測 𝑆𝑠 ∆𝑡 ≤ 𝑇𝑐 𝑆𝑙
∆𝑡 > 𝑇𝑐 ∆𝑡𝑖 = {400,500,800,150} ∆𝑡𝑖 :𝑖番目の訪問間隔時間 𝑆 ∊ { 𝑆𝑠 , 𝑆𝑙 }:状態 𝑇𝑐 :インシデント発生に要する時間 𝑺𝒊 から𝑺𝒊+𝟏 を予測 𝑆𝑖 = { 𝑆𝑠 , 𝑆𝑠 , 𝑆𝑙 , 𝑆𝑠 } ➀ ➀ 侵入者モデル
侵入者モデル 𝑇𝑐 = 500 観測 𝑆𝑠 ∆𝑡 ≤ 𝑇𝑐 𝑆𝑙
∆𝑡 > 𝑇𝑐 ∆𝑡𝑖 = {400,500,800,150} ∆𝑡𝑖 :𝑖番目の訪問間隔時間 𝑆 ∊ { 𝑆𝑠 , 𝑆𝑙 }:状態 𝑇𝑐 :インシデント発生に要する時間 𝑺𝒊 から𝑺𝒊+𝟏 を予測 𝑆𝑖 = { 𝑆𝑠 , 𝑆𝑠 , 𝑆𝑙 , 𝑆𝑠 } ➀ ➀ ➁ ➁ 侵入者モデル
侵入者モデル 𝑇𝑐 = 500 観測 𝑆𝑠 ∆𝑡 ≤ 𝑇𝑐 𝑆𝑙
∆𝑡 > 𝑇𝑐 ∆𝑡𝑖 = {400,500,800,150} ∆𝑡𝑖 :𝑖番目の訪問間隔時間 𝑆 ∊ { 𝑆𝑠 , 𝑆𝑙 }:状態 𝑇𝑐 :インシデント発生に要する時間 𝑺𝒊 から𝑺𝒊+𝟏 を予測 𝑆𝑖 = { 𝑆𝑠 , 𝑆𝑠 , 𝑆𝑙 , 𝑆𝑠 } ➀ ➀ ➁ ➁ ③ ③ 侵入者モデル
侵入者モデル 𝑇𝑐 = 500 観測 𝑆𝑠 ∆𝑡 ≤ 𝑇𝑐 𝑆𝑙
∆𝑡 > 𝑇𝑐 ∆𝑡𝑖 = {400,500,800,150} ∆𝑡𝑖 :𝑖番目の訪問間隔時間 𝑆 ∊ { 𝑆𝑠 , 𝑆𝑙 }:状態 𝑇𝑐 :インシデント発生に要する時間 𝑺𝒊 から𝑺𝒊+𝟏 を予測 𝑆𝑖 = { 𝑆𝑠 , 𝑆𝑠 , 𝑆𝑙 , 𝑆𝑠 } ➀ ➀ ➁ ➁ ③ ③ 相互情報量 侵入者モデル
評価指標 𝐽 = σ𝑒∈𝐸 𝐼𝑒 𝑆𝑖+1,𝑆𝑖 𝐸 (1) 𝐼𝑒 𝑆𝑖+1
, 𝑆𝑖 = 𝐻 𝑆𝑖+1 − 𝐻 𝑆𝑖+1 𝑆𝑖 (2) 𝑆𝑠 ∆𝑡 ≤ 𝑇𝑐 𝑆𝑙 ∆𝑡 > 𝑇𝑐 E:グラフの辺集合 𝐼𝑒 𝑆𝑖+1 , 𝑆𝑖 :辺𝑒の状態𝑆𝑖+1 と𝑆𝑖 の相互情報量 評価指標 J :警備ロボットの訪問間隔の予測しづらさ 𝑃 𝑆𝑖+1 = 𝑆𝑙 ȁ𝑆 𝑖 = 𝑆𝑠
評価指標 𝐽 = σ𝑒∈𝐸 𝐼𝑒 𝑆𝑖+1,𝑆𝑖 𝐸 (1) 𝐼𝑒 𝑆𝑖+1
, 𝑆𝑖 = 𝐻 𝑆𝑖+1 − 𝐻 𝑆𝑖+1 𝑆𝑖 (2) 𝑆𝑠 ∆𝑡 ≤ 𝑇𝑐 𝑆𝑙 ∆𝑡 > 𝑇𝑐 E:グラフの辺集合 𝐼𝑒 𝑆𝑖+1 , 𝑆𝑖 :辺𝑒の状態𝑆𝑖+1 と𝑆𝑖 の相互情報量 評価指標 J :警備ロボットの訪問間隔の予測しづらさ 𝑃 𝑆𝑖+1 = 𝑆𝑙 ȁ𝑆 𝑖 = 𝑆𝑠 Jの値は侵入者に与える情報量が 大きいほど大きくなり、 訪問間隔時間が乱雑であると言えるので 大きい方が望ましい
数値実験 ➢ 評価する巡回経路 (1) 本研究の提案手法で生成する巡回経路 (2) CPPの解法で生成する単一の巡回経路 ➢ 実験条件: •
それぞれ100周分の巡回経路を生成 • ロボットの速度を1 [m/s] • 𝑇𝑐 = 800𝑠 実験で使用する無向グラフ
数値実験 各辺の𝑆𝑖+1 と𝑆𝑖 の相互情報量 (1) 本研究の提案手法で生成する巡回経路
数値実験 (1)の J の値0.7068 各辺の𝑆𝑖+1 と𝑆𝑖 の相互情報量 (2)の J の値0.0
(1) 本研究の提案手法で生成する巡回経路
数値実験 (1)の J の値0.7068 (2)の J の値0.0 各辺の𝑆𝑖+1 と𝑆𝑖 の相互情報量
(2) CPPの解法で生成する単一の巡回経路
数値実験 (1)の J の値0.7068 各辺の𝑆𝑖+1 と𝑆𝑖 の相互情報量 (2)の J の値0.0
(1) 本研究の提案手法で生成する巡回経路 提案手法によって生成される 巡回経路は訪問間隔が多様で 侵入者の予測を難しくしている
まとめ・今後 • まとめ ➢ 本研究では訪問間隔を警備の一周ごとに変化させる手法の提案と侵入者の モデル化をした ➢ 訪問間隔時間の相互情報量からCPP の解である単一の経路に比べ本研究の提 案手法によって生成される巡回経路は侵入者の予測を難しくすることが分
かった • 今後 ➢ 侵入者のモデル化をより具体的にする