概要
この記事は、スポーツクライミングのボルダリングのルートをCGの人間が登る研究のコース探索アルゴリズムをMoon Board用に再実装した記録です。
現状、クライミングにおいてはMoon Boardの課題が最も機械学習に向いていると思いますので、興味のある方のお役に少しでも立てますと幸いです。
元の論文（私は論文の著者とは何の関係もないです）
A*を実装する際に参考させていただきました
よくわかるA*(A-star)アルゴリズム (Unity2Dのサンプルコードつき)
環境
OS X： 10.15.1
Python: 3.7.5
Moon Boardって何？
MoonBoardの公式HP
今、世界中で（おそらく）大流行中のボルダリング。
TOKYO2020オリンピックにもスポーツクライミングの一種として追加されたり、すごい勢いがあります。
そんなボルダリングをするための施設ボルダリングジムを街で見たことある方も多いんじゃないかなと思います。
ボルダリングジムは各お店ごとにいろんな特色があって、壁の高さや広さ、ターゲットもまちまちです。
それはとても面白いことでもありますが、他のボルダリングジムを利用している人と同じ課題を登れないという問題もあったりします。
そこで登場するのがMoon Boardです。
イギリスの伝説的クライマーBen Moonさんが世に出したこのクライミングウォールは世界中で同一規格の壁を使ってみんなで同じ課題に登ることができます。
ただし、中級くらいからの人じゃないとトライすることも難しめなコースが多く、登り方が分からない…となってしまうことも。
そこで、アルゴリズム的にアプローチしてみたいというのが今回の趣旨です。
入力と出力
Moon Boardのホールドはアルファベットと数字で表示できるので、こんな感じにしました。
lease use letters and numbers and leave a space for each hold. Example: A12 B31
Enter a start hold
H5 F6
Enter a hold other than the start and goal
F8 D10 E13 C16 D4
Enter a goal hold
E18
-------------------- Start ! --------------------
Left Hand: F6, Right Hand: H5, Left Foot: D4, Right Foot: Foot Hold
Left Hand: F6, Right Hand: F8, Left Foot: D4, Right Foot: Foot Hold
Left Hand: F6, Right Hand: F8, Left Foot: D4, Right Foot: H5
Left Hand: D10, Right Hand: F8, Left Foot: D4, Right Foot: H5
Left Hand: D10, Right Hand: D10, Left Foot: D4, Right Foot: H5
Left Hand: D10, Right Hand: D10, Left Foot: D4, Right Foot: F6
Left Hand: D10, Right Hand: D10, Left Foot: F8, Right Foot: F6
Left Hand: D10, Right Hand: E13, Left Foot: F8, Right Foot: F6
Left Hand: E13, Right Hand: E13, Left Foot: F8, Right Foot: F6
Left Hand: E13, Right Hand: E13, Left Foot: F8, Right Foot: D10
Left Hand: E13, Right Hand: E13, Left Foot: C16, Right Foot: D10
Left Hand: E13, Right Hand: E18, Left Foot: C16, Right Foot: D10
Left Hand: E18, Right Hand: E18, Left Foot: C16, Right Foot: D10
-------------------- Goal ! ---------------------
元の論文と違うところまとめ
元の論文では両手両足を同時に探索していました。これはクライミングの技術であるランジやダブルダイノと呼ばれる手足が同時に動くダイナミックな動きを再現するためです。
論文中で探索アルゴリズムとして使用しているA*アルゴリズムは最良優先探索ですが、両手両足分の4手を一気に探索してしまうと無理な移動（＝コストが大きくなる移動）でも最後の一手はゴールにつくので探索がそこで終わりになってしまい、導き出されるべきだった最適な移動が計算できなくなってしまうと実装して感じました。
本来は下の図のようになるべきところが
こうなってしまうということが出てきてしまう可能性があります
上の例は極端な例ですが、実際にゴールでは必ずこれに近いことが起きてしまったため私の実装では探索の際は両手両足のどれか一つだけが動くようになっています。
（良い解決方法があれば是非教えてください…！）
それに伴って、いくつかのコスト計算も修正してあります。
また、パラメータは論文と同じものをなるべく使いましたが、足が浮いている際のコストC_FREE_FOOTは20→125に挙げています（Gitのコードにはコメントで横に20を記載しているので、自由に変えてください）
ちなみにもしもパラメータを20にすると上と同じコースでもこんな感じになります。
Noneがホールドを使っていないフリーな状態を指しています。
Please use letters and numbers and leave a space for each hold. Example: A12 B31
Enter start holds
H5 F6
Enter holds other than the start and goal
F8 D10 E13 C16 D4
Enter goal holds
E18
-------------------- Start ! --------------------
Left Hand: F6, Right Hand: H5, Left Foot: D10, Right Foot: None
Left Hand: F6, Right Hand: E13, Left Foot: D10, Right Foot: None
Left Hand: E13, Right Hand: E13, Left Foot: D10, Right Foot: None
Left Hand: E13, Right Hand: E18, Left Foot: D10, Right Foot: None
Left Hand: E18, Right Hand: E18, Left Foot: D10, Right Foot: None
-------------------- Goal ! ---------------------
論文中にはパラメータの選定理由に触れていなかったです。良かったらいろいろいじってみてください。
（身長はデフォルトでは170cmになってますが自分の身長に合わせてみると面白いと思います）
Github