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
ルートの質を評価する指標について
Search
NearMeの技術発表資料です
PRO
February 28, 2025
0
37
ルートの質を評価する指標について
NearMeの技術発表資料です
PRO
February 28, 2025
Tweet
Share
More Decks by NearMeの技術発表資料です
See All by NearMeの技術発表資料です
強化学習アルゴリズムPPOの改善案を考えてみた
nearme_tech
PRO
0
2
Apple Containerについて調べて触ってみた
nearme_tech
PRO
0
47
Rust 並列強化学習
nearme_tech
PRO
0
21
並列で⽣成AIにコーディングをやらせる
nearme_tech
PRO
1
130
希望休勤務を考慮したシフト作成
nearme_tech
PRO
0
34
Hub Labeling による高速経路探索
nearme_tech
PRO
0
90
Build an AI agent with Mastra
nearme_tech
PRO
0
77
Rustで強化学習アルゴリズムを実装する vol3
nearme_tech
PRO
0
43
Webアプリケーションにおけるクラスの設計再入門
nearme_tech
PRO
1
110
Featured
See All Featured
The Straight Up "How To Draw Better" Workshop
denniskardys
236
140k
JavaScript: Past, Present, and Future - NDC Porto 2020
reverentgeek
50
5.5k
Designing for Performance
lara
610
69k
ピンチをチャンスに:未来をつくるプロダクトロードマップ #pmconf2020
aki_iinuma
126
53k
Documentation Writing (for coders)
carmenintech
73
5k
Into the Great Unknown - MozCon
thekraken
40
2k
KATA
mclloyd
32
14k
Stop Working from a Prison Cell
hatefulcrawdad
271
21k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
251
21k
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
656
61k
Improving Core Web Vitals using Speculation Rules API
sergeychernyshev
18
1.1k
Scaling GitHub
holman
462
140k
Transcript
1 2025-02-28 第114回NearMe技術勉強会 Futo Ueno ルートの質を評価する指標について
2 背景 ‧タスクでrouting-apiのパラメータチューニングについて考えていた ‧UXと相乗り数(GpT)はトレードオフの関係にある → UXとGpTのバランスが良いパラメータを探索したい UXの良さとは? → UXのうち「ルートの質」を定量化する⽅法についてお話しします
3 ルートの質 start end pick up start end pick up
start end pick up ⾃然なルートで 相乗りできている やや不⾃然
4 フレシェ距離 X, Y : 0 ≤ t ≤ 1でパラメータ付けられた曲線
α, β : [0, 1]から[0, 1]への単調⾮減少な再パラメータ付け d(‧, ‧) : ユークリッド距離
5 フレシェ距離 X, Y : 0 ≤ t ≤ 1でパラメータ付けられた曲線
→ ルート α, β : [0, 1]から[0, 1]への単調⾮減少な再パラメータ付け → 歩き⽅ d(‧, ‧) : ユークリッド距離 → 普通の距離
6 フレシェ距離の解釈 ⽚⽅が直線だとわかりやすい おそらくこの辺り 「曲線X, Y上をなるべく離れないように歩いた時に、どうしても離れてしまう距離」
7 フレシェ距離によるルートの質の評価 start end pick up start end pick up
start end pick up フレシェ距離 ⼩ フレシェ距離 ⼤ フレシェ距離 ⼤?
8 フレシェ距離の弱点① ‧使う道路が変わると必然的にフレシェ距 離は⼤きくなる ‧使う道路が変わってもルートの質に⼤き く差が⽣じない場合であっても、フレシェ 距離には「異常」として反映されてしまう start end ⾼速
1 ⾼速 2 ⼀般道 + ⾼速
9 フレシェ距離の弱点② start end pick up start end pick up
start end pick up ⽬的地から遠ざかっている ⾏ったり来たりしている ⾃然 → これらのフレシェ距離はそれほど⼤きな値にはならず、⾃然な相乗りとの区別がつかない
10 Geodesic Tortuosity start end ‧始点から終点まで辿り着くために必要な 「最⼩限の移動量」が直線距離 ‧あるルートによる「実際の移動量」が 「最⼩限の移動量」に⽐べてどのくらい嵩んで しまうかを表している
𝑙 𝑅
11 GT による評価 start end pick up 𝑅!"#$% 𝑅!&'& 𝑙
12 GTによる評価 start end 𝑅!"#$% pick up 𝑅!&'& ‧ルートの⻑さに差がなければGTにも 差は⽣じない
→ 使う道路が違ってもルートの質が 同⽔準であることを捉えられている
13 start end pick up start end pick up end
⽬的地から遠ざかっている ⾏ったり来たりしている ⾃然 →⽬的地から遠ざかったり⾏ったり来たりするとGTは悪化する GTによる評価 pick up start
14 「迂回係数」との⽐較 ←概ね連動しているが、 迂回係数が⼤きくなるにつ れて差が⽣じている
15 「迂回係数」との⽐較 → 「元々のルートのGT」 が反映されている
16 今後の課題 ‧時間的な質を反映させた指標 ‧最適化に組み込む (制約や⽬的関数) ‧⽬的地から遠ざかったり⾏ったり来たりする部分を 「強調」するような形に拡張 → ルートの異常検知
17 references ‧https://mist.math.chalmers.se/geodesic-tortuosity/ ‧https://www.researchgate.net/figure/Definition-of-the-geodesic- tortuosity_fig16_312874680
18 Thank you