【爆速化】計算時間が180秒から0.04秒に！！「高密度環境のロボット経路計画」がすごい

ネット通販の普及で大活躍している「自動倉庫の搬送ロボット」。しかし、限られたスペースにロボットを増やしすぎると、お互いにぶつからないルートを計算するのに膨大な時間がかかってしまうのが課題でした。

そんな中、豊田中央研究所がこの計算を「180秒から0.04秒」へ劇的に短縮するアルゴリズムを開発。

これまでは「整数計画法（ILP）」という数理モデルが使われていましたが、ロボットが増えたり空間が狭くなったりすると、すべてのロボットの組み合わせを計算するため、計算時間が爆発的（指数関数的）に増えてしまう致命的な弱点がありました。

今回開発された「MAPF-HD」という新手法は、一度にすべてを計算しようとはせず「経路計画を段階的に分ける」「ロボットと目の前にある空きスペースをパズルのように入れ替えていく」という、負荷の非常に軽い計算を繰り返すアプローチを採用。これにより、複雑な環境でも計算時間が爆発せず、処理できるようになりました。

この技術が実用化されれば、自動倉庫内の通路を狭くして、その分ギリギリまで商品を保管できるようになるなど、効率の向上が期待されます。

『参考資料』