PokemonGo-TSP

最近被滑鐵盧大學分享的一篇PokemonGo最佳路徑規劃文章 [1] 而啟發

剛好最近又很瘋PokemonGo，決定試著動手用模擬退火來解決PokemonGo的TSP問題

What is TSP?

TSP全名Travelling salesman problem，中文翻譯做「旅行商問題」[2]

給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次並回到起始城市的最短迴路

在計算複雜度(Computing Complexity)上 屬於NP-Complete的難題

What is SA?

SA全名Simulated Annealing，中文翻譯做「模擬退火」[3] [4]

一種基於熱力學原理的隨機搜尋演算法，用來在固定時間內在一個大的搜尋空間內找最優解

Usage

Requirement

Linux ( Debian / Ubuntu ):
apt-get install python-matplotlib
pip install -r requirements.txt

Linux ( Fedora / Redhat ):
yum install python-matplotlib
pip install -r requirements.txt

Mac OSX:
pip install matplotlib
pip install -r requirements.txt

Annealing parameters

markov_step = 10 * num_location	# 內循環次數
T = 100					        # 初始溫度
T = 1					        # 最低溫度
T_ALPHA = 0.99			        # 退溫常數

因為是隨機搜尋演算法，不一定能保證每次都得到最佳解答

如果想要得到更好的解，增加markov_step是個好辦法

markov_step = 100 * num_location # 內循環次數

Execute

直接執行python tsp.py, 預設會讀取data/pokestops.csv

跑出結果後會畫出cost function和route, 結果如下

最後再把結果存入data/tsp.db內，方便未來分析

推薦下載 Sqlite Browser GUI管理工具來開啟資料庫

個人都是跑N次 python tsp.py & 放到背景去執行，然後去做自己的事情

等跑完後最後再去sqlite看數據即可

Google Map Visualization

附上一張交大校內Pokemon Stop的最佳路規劃

目前是人工手拉的地圖，希望未來能夠自動整合到地圖上QQ

TODO

• Road TSP (結合Google Map根據實際地理距離來計算)
• 考慮雷達半徑(50m)和5分鐘重置的條件，計算出最佳路線
• 將最佳路徑Link到Google Map上
• Benchmark with other algorithms
• Parallelization
• Reannealing
• Cooling schedule

目前只實現了Geometric TSP，Road TSP [5] 還在克服中

用Google Map API 來計算實際地理距離目前還有點雷，像是操場/壘球場這種地方會繞一大圈而不是直接穿越

希望有經驗的大大能夠提出建議！ 謝謝

歡迎PR!!

Reference

[1] Pokemon Go Traveling Salesman Problem - 國外的Pokemon Go TSP

[2] Travelling salesman problem - TSP背景知識

[3] Simulated annealing - 模擬退火背景知識

[4] 模拟退火算法求解旅行商问题 - 詳盡的模擬退火解說 ＋ Java實現，提到了三種產生新狀態的方式

[5] Queen of College Tours - 從Geometric TSP 到 Road TSP

[6] PokemonGo-Map - 地圖掃描工具，開啟後放置一段時間，再把pogom.db拿出來，即可取得道館/補給站座標