RSJ2022

価値反復による準静的な障害物を 考慮した実時間経路計画 上田隆一，池邉龍宏，林原靖男（千葉工大） 第40回 日本ロボット学会学術講演会 2022年9月6日 本研究はJSPS 科研費JP20K04382 の助成を受けた

移動ロボットの経路計画・障害物回避 • 現在よく用いられるもの: ROS navigation stackで標準のもの • 大域計画: A*[Hart 1968] • 局所計画（障害物回避）: DWA[Fox1997] • 路上の障害物を避けるには十分だが 大きな迂回は？ • デフォルトのものでは無理 • 反射的な回避行動を試してあきらめ • 障害物込みで大域計画を行えば 可能なはずだが，大域/局所の切り替えが実は難しい 大域計画器と局所計画器を統一的に扱えないか？ 2022年9月6日 RSJ2022 2

価値反復を利用した行動計画 [Ueda 2003, 2005, 2007, 2014, 2015] • 全通りの状況に対してロボットの 最適な行動を計算 2 = 9 1 = 9 9 1 = 9 2 = 9 9 9 = 92 9 9 9 9 9 9 9 9 9 9 • A*が部分的に解くものを空間全域で解く • 得られるもの 初期値 （実際は3次元） • 最適状態価値関数V*: 任意の(x,y,q)からゴールまでの時間 • 最適方策P*: V*の実現のために任意の(x,y,q)でとるべき行動 3 • ロボカップでのオフライン利用[Ueda 2003, 2005, 2007] • 目的地ごとに事前にP*を全部計算しておく 5 2 3 4 6 問題: 計算量が大きい （一瞬で計算できればオンラインでも使える） 2022年9月6日 RSJ2022 6 1 2 3 4 5 2 1 5 4 3 4 収束したV* 3

計算量の問題の解決（力づく）[上田ロボシン2022] • 現在（未来）の計算機の性能を信じる • 高性能のCPUをマルチスレッドで利用 • シンプルに実装（浮動小数点を使わないなど工夫） • 得られたもの: ryuichiueda/value_iteration • 100[㎡]超の環境で3秒以下の計算コスト • ノートPC，Core i9-10885H • 離散化の解像度50[mm]，5[deg]，284万状態 • 行動の選択肢: 6 • 大きな障害物も価値反復で回避 大域/局所計画器を統一的に扱えた 2022年9月6日 RSJ2022 4

• https://github.com/ryuichiueda/value_iteration

障害物に対する迂回の仕組み [上田ロボシン2022] • V* のコピー（𝑉 + とする）を生成 • 発見した障害物を地図に記録 • ロボット近傍の𝑉 + の値を価値反復で更新 • すぐに経路が発見できない場合も、 ロボットが動き回ると𝑉 + が収束して迂回路生成 3 5 2 3 4 6 6 3 1 2 3 4 5 2 1 5 4 3 3 4 6 4 6 2 1 3 1 2 3 4 5 未知障害物がないときの𝑉 + 2022年9月6日 5 2 5 4 3 4 2 1 1 2 9 3 4 2 3 84 75 3 6 4 4 6 5 85 未知障害物発見 ある範囲「窓」の値を書き換え RSJ2022 5

障害物回避を実装したところ生じた疑問 • 「局所計画器で障害物回避」という頭で実装していたが 大域計画器で考慮可能ではないか 価値反復の走査 3 5 2 3 4 6 6 3 1 5 3 4 窓に限定しなくても 3秒以下のコスト 未知障害物発見 2022年9月6日 1 1 2 9 4 3 2 3 84 75 3 6 4 4 6 5 2 4 2 85 3 4 5 2 1 RSJ2022 6

研究の目的 • 価値反復ROSパッケージの改良 • 大域計画器で，未知障害物を価値関数の計算で考慮 • 速度は0と仮定 • 局所計画器も残す • 大域計画器と同じ計算をロボットの周辺で行い，突然の障害物に対応 • 得られる成果 • ロボットの性能には関係ないが， コードが単純化してメンテナンスのコストが低下 • （大域計画器が回りっぱなしになるので消費電力は増加） 2022年9月6日 RSJ2022 7

実装の結果1 • 条件 • p.4と同じ • 遷移可能な 状態の数: 284万 • 6種類の行動 • 前進，後退， 右/左前進， 右/左旋回 • CPU: Intel Core i9-10885H • 計算時間 • 大域: 3[s]以内 • 局所: 0.2[s]以内 2022年9月6日 RSJ2022 8

実装の結果2 • 障害物を行動計画用の地図に描き込まずに実行 • 障害物を記録しては価値関数を書き換え 2022年9月6日 RSJ2022 9

結論 • 大域計画器での障害物回避を実装 • V* のコピー処理，そのための同期処理が消滅 • 今後 • 局所計画器の次元を上げる • 1: AMDPの実装 • 自己位置推定のあいまいさを 系の変数に付加 →位置がよくわからないのに通路の 端を移動して脱輪する事故を減少 • 2: 障害物の速度を系の変数に付加 • 共同開発者/研究者を見つける • ぜひGitHubに 2022年9月6日 RSJ2022 10

補足: 発見した障害物の記録 • 窓内の物体にセンサが反応した場合 障害物の検出位置 （LiDARのレーザーの端点など） 塗りつぶし • 当該セルを塗りつぶし • 塗りつぶし: ロボットが入ったときの コストを大きな値に • 窓内のセルに物体がない場合 • コストを半減 • 窓外のセル • 放置 2022年9月6日 RSJ2022 窓外のセルのコストは そのまま残す 11

補足: CPUの使い方 • CPU: Intel Core i9-10885H • 8コア16スレッド • 大域計画に6スレッド • 局所計画に2スレッド 2022年9月6日 RSJ2022 12