こんにちは．hoshina roboticsの保科です．

今回は倉庫内の複数台ロボットの経路計画アルゴリズムであるMAPF問題について，比較的新しい手法である．RHCRアルゴリズムについて記載いたします．

RHCRアルゴリズムは,Jiaoyang Liさんらによって提唱されたアルゴリズムで，ロボットのマルチエージェントパスファインディング問題（通称,MAPF問題）において，全エージェントの解を同時に求めなければ行けないと行った問題点を解消したアルゴリズムです．処理内容としては，タイムステップごとにウィンドウ化したMAPFソルバーを使用して数秒先の経路探索を行うと行ったものになります．

MAPF問題は例えば,amazon roboticsのkibaシステムと行った物流倉庫内の複数ロボットの行動計画と行った部分で役立つアルゴリズムです．それぞれのロボットの目的地までの距離は異なりますので，各エージェントの目標位置を動的に変更できる今回のアルゴリズムはより実用的な手法だなと考えています．アルゴリズムについての理解を記載していき，可能だったらプログラムを自由に扱えるようにできればと考えています．

以下，理解した内容や試してみた内容を記載していけたらと考えています．

周辺手法から紐解く

本項目では，RHCRを理解するためにまず周辺の手法から調査していった内容を記載します．

「自動倉庫用搬送機の排他制御への交渉アルゴリズムの導入」[2023,飯田]

• 既存MAPF手法：最適解法としてCBSアルゴリズム，準最適解法としてCA*などがある．

• MAPD：MAPFは各エージェントにスタート地点とゴール地点が１つずつ割り当てられる”one-shot”の問題であるが，現実の倉庫等は連続的にタスクが割り当てられるため，MAPFを発展させたMAPD( Multi-Agent Pickup and delivery, Lifelong MAPF)が提案されている．全てのMAPDが解を持つわけではないが
• MAPDの解法種類
  • Well-formed MAPD instance とその解法 [Ma 17]：解の存在が保証されている
  • TPTS(Token Passing with Task Swaps)[Ma 17]:
  • 時間幅を決め Windowed MAPF instances として解く RHCR[Li 21] ← RHCRはMAPD問題の解法という立ち位置らしい
• MAPDのタスクの割当
  • TP では事前に計算された h-value が最も小さいタスクを選択
  • RHCRにおいてもランダムまたは最も近いものを選択
  • TPTS は割り当て済みの未実行タスクも含めて最も近いものを選択

ソースコードを調べる

RHCRアルゴリズムのソースコード URL