AWS Robot Delivery Challenge 2022 に出場できなかった話 : ダイクストラ法

概要を読んでいない方は先にこちらを読んでください！
目次のページ

ダイクストラ法とは

グラフ理論におけるアルゴリズムの一つで、グラフ上の2頂点間の最短経路を決定するアルゴリズムです。今回はコース上の２点間を最速で移動する経路を導くアルゴリズムとして使用しました。頂点の位置は下図のように決定し、各辺の重みは各ノード間を移動するのにかかる所要時間となります。これらの所要時間は最適制御によって計算されたものになっています。

アルゴリズム

この記事を参考にしました。
https://myenigma.hatenablog.com/entry/20140502/1399001915

全体としての位置付け

実装

1. commanderから通過するノードの順序を受け取る(始点、中継点、中継点、、、終点)
2. 始点から中継点を通過して終点に最短で到達するためのノードの順序をダイクストラ法で導く。
3. ダイクストラ法で導いたノードの順序通りに、経路を繋ぎ最適経路を生成する。(ノード間の経路はあらかじめ最適制御で計算されていて、離散化された座標、各座標でのロボットの目標速度、目標角加速度がcsvファイルの形式で格納されている。)
4. 生成した最適経路の情報（離散化された座標、ロボットの目標速度、目標角加速度）を黄金探索に渡す。