■ はじめに
前回、A*と言う迷路特化型のアルゴリズムを使って、自分マップの配送ルートを決定できました。
ちなみに、迷路特化型は少ないらしく、僕の借りた本には、A*しか載ってませんでした。
後は、A*ルートをエージェントに渡せば、第一段階成功です。
（アルゴリズムを考えているプロンプト・ウサギとアドバイスをするChatGPTさん）
■ フォーマットが違う！
A*のフォーマットは、ルートの座標をくれますが、エージェントの動きは、前進・右回転・左回転 (と使ってないけど後退)
このままでは、入らないのでフォーマット変換が必要です。
一発変換が理想ですが、ここは初心者らしくわかりやすいアルゴリズムを目指します。
■考えたアルゴリズム
考え方はこうしました。
A*は、座標表現、エージェントは、前進・回転で表現するためビットローテーションによる変換をいれます。
本ブログではマップ座標 (0,0) を左上、rowは下方向に増える配列座標系を前提としています
それを踏まえて以下に、
A*座標配列 (row(i),col(i))
→axisWithDirect(dir(i),row(i) ,col(i))変換
の詳細を示します。
ここで、axisWithDirect は「位置」と「進行方向」を1つの状態としてまとめた中間表現になってます
①A*座標を確認: (row(i),col(i))
②次のA*座標(row(i+1), col(i+1))に対し、
col差分で東西、row差分で南北を判定
col軸が-1ならば、dir(i)=0010B(西)
col軸が+1ならば、dir(i)=1000B(東)
row軸が-1ならば、dir(i)=0001B(北)
row軸が+1ならば、dir(i)=0100B(南)
(ここで方角の情報が入ります)
③①と②からaxisWithDirect()に変換
次に、axisWithDirect()からエージェントの
動きに変換します。
①axisWithDirect(dir(l),row(i),col(i))を読み込み
②エージェントの方向とdir(i)の方角から
次のエージェントの動きを決定します。
同方向 :前進
ROLで同方向 :左回転,前進
RORで同方向 :右回転,前進
ここで左回転／右回転アクションは、強化学習に合わせて1stepあたりの意味を揃え、回転＋前進を1stepとしています。
RORとROLと言うのはビットローテーションで下のような変換を言います。
・左ローテーション(ROL)
0001 (北)
↓ ROL
0010 (西)
↓
0100 (南)
↓
1000 (東)
↓
0001 (北) ← 循環
・右ローテーション(ROR)
0001 (北)
↑ ROR
1000 (東)
↑
0100 (南)
↑
0010 (西)
↑
0001 (北)
東西南北をムリなく簡単に表そうとすると、こうなりました。こうやって、A*ルートとエージェントを繋げています。
・A*方向（ビット対応）
0: 北 (0001)
1: 西 (0010)
2: 南 (0100)
3: 東 (1000)
・エージェント動き定義
0: 前進
1: 左回転
2: 右回転
3: 停止(信号待ち)
A*からエージェントへのアルゴリズムコードは、
Githubへのリンクを上げておきます。Googleの検索窓から入いつてCodeを選択してね。
github.com/logicmaker256-prog/A_star_to_agent/blob/main/a_star_to_agent.ipynb
■結果：
今回は、自作マップ上に配達ポイントA,B,Cを作っておいて、配達してもらいます。
=== 自作マップ ===
■■■Ｂ・・▲▲▲▲・・Ａ■■■
■■■■・・▲▲▲▲・・■■■■
■■■■・・▲▲▲▲・・■■■■
■■■■・・②＃＃＃・・■■■■
■■■■・・＃＃＃②・・■■■■
■■■■・・▲▲▲▲・・■■■■
・・・・・・▲▲▲▲・・・・・・
・・・・・・▲▲▲▲・・・・・・
▲＃①▲▲▲▲▲▲▲▲▲▲＃①▲
▲＃＃▲▲▲▲▲▲▲▲▲▲＃＃▲
▲＃＃▲▲▲▲▲▲▲▲▲▲＃＃▲
▲①＃▲▲▲▲▲▲▲▲▲▲①＃▲
・・・・・・▲▲▲▲・・・・・・
・・・・・・▲▲▲▲・・・・・・
■Ｃ■■・・②＃＃＃・・受■■■
■■■■・・＃＃＃②・・■■■■
A*ルートを出しますとA,B,Cと配達して
「受」に戻っています。
=== A*ルート ===
■■■☆☆☆▲▲▲▲☆☆☆■■■
■■■■☆☆▲▲▲▲☆☆■■■■
■■■■☆☆▲▲▲▲☆☆■■■■
■■■■☆☆☆☆☆☆☆☆■■■■
■■■■☆・＃＃＃②・☆■■■■
■■■■☆・▲▲▲▲・☆■■■■
・☆☆☆☆・▲▲▲▲・☆☆☆・・
・☆・・・・▲▲▲▲・・・☆・・
▲☆①▲▲▲▲▲▲▲▲▲▲☆①▲
▲☆＃▲▲▲▲▲▲▲▲▲▲☆＃▲
▲☆＃▲▲▲▲▲▲▲▲▲▲☆＃▲
▲☆＃▲▲▲▲▲▲▲▲▲▲☆＃▲
・☆・・・・▲▲▲▲・・☆☆・・
・☆☆☆☆☆▲▲▲▲・・☆・・・
■☆■■・☆☆☆☆☆☆☆☆■■■
■■■■・・＃＃＃②・・■■■■
エージェントにも、A*の情報が渡せているので、作ったアルゴリズムが何とか動いていることが確認できます。
=== エージェント軌跡 ===
■■■◀▶▲▲▲▲▲◀◀▶■■■
■■■■▼▲▲▲▲▲▼▲■■■■
■■■■▼▲▲▲▲▲▼▲■■■■
■■■■▼◀◀◀◀◀▼▲■■■■
■■■■▼・＃＃＃②・▲■■■■
■■■■▼・▲▲▲▲・▲■■■■
・◀◀◀▼・▲▲▲▲・◀◀▲・・
・▼・・・・▲▲▲▲・・・▲・・
▲▼①▲▲▲▲▲▲▲▲▲▲▲①▲
▲▼＃▲▲▲▲▲▲▲▲▲▲▲＃▲
▲▼＃▲▲▲▲▲▲▲▲▲▲▲＃▲
▲▼＃▲▲▲▲▲▲▲▲▲▲▲＃▲
・▼・・・・▲▲▲▲・・▲▶・・
・▲▶▶▶▶▲▲▲▲・・▲・・・
■▼■■・▼▶▶▶▶▶▶▶■■■
■■■■・・＃＃＃②・・■■■■
A*ルートとエージェントルートを出すコードのリンク(GitHubリンクアドレス)
■ 今回の学び:
自然言語でコーディングできないか考えていたのですが、仕様を詳細に書くと言うのが近いかもしれません。
なんか詳細に書いた方が、エラーの発生も減るような気がします。
コーディングを自然言語で詳細に書いて、ChatGPTさんに渡すのか今のところの正解なのかな。
■ まとめ
こう見ると、まるで出来たようにアルゴリズムを語ってますが、実はSLAMする為の準備、場所コストの定義が出来てません。
と言う事で次は、場所コストを定義して人かわしたり、信号待ちしたりまでいけたらいいな。