直線数最適化障害物回避問題
解きたい問題
- 障害物のある平面において起点と終点を結ぶ経路を探索し直線数を最小化したい。
- 障害物は線分で与えられる。
- 経路の長さは目的としない。
この画像は問題の単なる一例であり、障害物は平面上に自由に置けるものとする。
解決手順
- 適当な細かさのGridに対応させて考える。
- 障害物により格子点の連結を切断する。
- BeamSearchを用いて起点から終点までの経路を求める。
- 得られた点列をGreedyに直線列に変換。
- 焼きなまし法(SimulatedAnealing)で直線数を減らす。
考察
- 与える問題のパラメータによってGridの細かさなどを変更する必要がある。
- BeamSearchは驚くほど便利。
- SimulatedAnealingは「近傍をどう生成するのか」が難しい。
- 今回は、「経路のうちの一点を選ぶ」「移動先としてランダムに新しい格子点を選択」「障害物に当たらないかを検査」「当たらないなら前後の直線を縮約できればやる」として近傍を生成した。
- はじめGridなどを考えずにデカルト平面上でSA法を適用し経路探索と直線数最小化を一度にしようとしたが精度や計算量的に失敗だった。
- 残る問題としては交差判定に時間がかかっている点。SA法の中で近傍探索する際にすべての障害物と着目する直線との交差判定をしている。BoundingBoxなどで不必要な交差判定をなくしたほうが良い。
結果
可視化について
- D3.jsを用いて描画した。
- ソルバはJSON形式で結果を出力。
ruby -run httpd -- . -p 8000によりHTTPサーバを立てる。- カレントディレクトリにJSONファイルとそれを表示するHTMLファイルを置く。
- SVGをPNGに変換し保存。変換用コードは下に示すJavaScriptコード。
