移動速度の時間変化と不確実性を考慮したマルチロボット自動倉庫の経路計画:問題定式化とアルゴリズム
Path Planning Considering Time-Varying and Uncertain Movement Speed in Multi-Robot Automatic Warehouses: Problem Formulation and Algorithm
自動倉庫のマルチロボット経路計画において、ロボットの移動速度が時間変化し不確実である場合を扱い、A*に衝突確率を組み込んだ経路探索と、衝突検出・再計画、スケジューリングを組み合わせた手法を提案した。
著者: Jingchuan Chen, Wei Chen, Jing Li, Xiguang Wei, Wenzhe Tan, Zuo-Jun Max Shen, Hongbo Li
分類: cs.RO
原文アブストラクト
Path planning in the multi-robot system refers to calculating a set of actions for each robot, which will move each robot to its goal without conflicting with other robots. Lately, the research topic has received significant attention for its extensive applications, such as airport ground, drone swarms, and automatic warehouses. Despite these available research results, most of the existing investigations are concerned with the cases of robots with a fixed movement speed without considering uncertainty. Therefore, in this work, we study the problem of path-planning in the multi-robot automatic warehouse context, which considers the time-varying and uncertain robots' movement speed. Specifically, the path-planning module searches a path with as few conflicts as possible for a single agent by calculating traffic cost based on customarily distributed conflict probability and combining it with the classic A* algorithm. However, this probability-based method cannot eliminate all conflicts, and speed's uncertainty will constantly cause new conflicts. As a supplement, we propose the other two modules. The conflict detection and re-planning module chooses objects requiring re-planning paths from the agents involved in different types of conflicts periodically by our designed rules. Also, at each step, the scheduling module fills up the agent's preserved queue and decides who has a higher priority when the same element is assigned to two agents simultaneously. Finally, we compare the proposed algorithm with other algorithms from academia and industry, and the results show that the proposed method is validated as the best performance.
