Slide 1: Champlify
Champlify Character pattern formation generator powered by Amplify 奥村 圭祐 Fixstars Amplify Hackathon Apr. 24th 2021
Slide 2: 作ったもの
2 /12 作ったもの A B t=0 t=1 t=2 エージェント(青点)によって構成された 任意のアルファベット2文字間を最短時間(aka. メイクスパン)で遷移 ターゲット割当 & 経路計画を同時に解く最適化問題 (unlabeled-MAPF; Multi-Agent Path Finding)
Slide 3: Unlabeled-MAPF
3 /12 Unlabeled-MAPF graph given agents (starts) targets target assignment solution paths without collisions objective minimize last arrival timestep (aka. makespan) *時間は離散化, 必ず実行可能解が存在
Slide 4: 応用例
4 /12 応用例 YouTube/Mind Blowing Videos Twitter/@knaohiro1 YouTube/StarCraft 自動倉庫の荷物運搬, ロボットサッカー, デジタルゲームなど種々様々 (かなり実用的な問題)
Slide 5: アプリケーションの構成
5 /12 アプリケーションの構成 user GUI: Eel Electron-like HTML/JS GUI app, アニメーションは CSS3 unlabeled-MAPF に変換 定義済みのフォントデータを使用 … 組合せ最適化を解く
Slide 6: 最適化の方針
6 /12 最適化の方針 メイクスパン T (初期値1) に対して実行可能解を求める Success メイクスパン最適な解が得られた, 後処理して終了 Fail T をインクリメントしてやり直し
Slide 7: 定式化 - 変数
7 /12 定式化 - 変数 𝑢 𝑣 時刻 𝑡 𝑥 !,# ,$ : 辺 (𝑢, 𝑣) を時刻 [𝑡, 𝑡 + 1] で使用するかの二値数
Slide 8: 定式化 - 制約条件
8 /12 定式化 - 制約条件 初期位置から出発 , 𝑥 (,# ,* = 1 ∀𝑠 ∈ スタートの集合 #∈&(() ターゲットへの到達 , 𝑥 !,+ ,,-. = 1 ∀𝑔 ∈ ターゲットの集合 !∈&(+) 頂点から出ていく数の制限 , 𝑥 !,# ,$ ≤ 1 ∀𝑢 ∈ 𝑉, 0 ≤ 𝑡 < 𝑇 #∈&(!) 頂点に入ってくる数の制限 , 𝑥 !,# ,$ ≤ 1 ∀𝑣 ∈ 𝑉, 0 ≤ 𝑡 < 𝑇 !∈&(#) 経路の連続性 , 𝑥 !,# ,$ = , 𝑥 #,! ,$/. ∀𝑣 ∈ 𝑉, 0 ≤ 𝑡 < 𝑇 − 1 !∈&(#)…
Slide 9: 解の後処理
9 /12 解の後処理 制約条件は辺上での衝突回避を課していないので後処理が必要 t t t+1 t+1
Slide 10: 小テク - 枝刈り
10 /12 小テク - 枝刈り {スタートから / ターゲットに} 到達不可能な (頂点, 時刻) のペアは事前に検出 問題を簡易化しておく t≤2 では誰も 𝑢 に辿り着けない (幅優先探索x1で求められる) 𝑥 !,# ,$ = 0 𝑣 ∈ 𝜕(𝑢), 0 ≤ 𝑡 ≤ 2 𝑢 𝑥 #,! ,$ = 0 𝑣 ∈ 𝜕 𝑢 ,0 ≤ 𝑡 < 2 ターゲットに到達できない (頂点, 時刻) も同様に検出可
Slide 11: One more thing
11 /12 One more thing https://vimeo.com/540891573
Slide 12: Take-home Message
12 /12 Take-home Message コア技術 ターゲット割当 & 経路計画の同時最適化 作ったもの 文字遷移の(リアルタイム)アニメーション生成
Slide 13: 感想など
13 /12 感想など 個人的なモチベ 手軽に使えそうな組合せ最適化ソルバを試しておきたかった (Gurobi や Goolge OR-Tools あたりは使用経験あり, Amplify は知りませんでした) 定式化してから実装までがスムーズにできた印象 手法の弱点 API を頻繁に叩くことが前提なので制限が怖い 大きいインスタンスは厳しい (e.g., 1000 agents) その他 最初は (頂点, 時刻) を変数にしようとしたが駄目そう js – python 間の非同期処理はちゃんとはやっていない… もっとヌルヌル動かしたい いい応用例あったら教えてください！