Trajectory planning for multiple robots in shared environments is a challenging problem especially when there is limited communication available or no central entity. In this article, we present Real-time planning using Linear Spatial Separations, or RLSS: a real-time decentralized trajectory planning algorithm for cooperative multi-robot teams in static environments. The algorithm requires relatively few robot capabilities, namely sensing the positions of robots and obstacles without higher-order derivatives and the ability of distinguishing robots from obstacles. There is no communication requirement and the robots' dynamic limits are taken into account. RLSS generates and solves convex quadratic optimization problems that are kinematically feasible and guarantees collision avoidance if the resulting problems are feasible. We demonstrate the algorithm's performance in real-time in simulations and on physical robots. We compare RLSS to two state-of-the-art planners and show empirically that RLSS does avoid deadlocks and collisions in forest-like and maze-like environments, significantly improving prior work, which result in collisions and deadlocks in such environments.
翻译:在共享环境中规划多个机器人的轨迹是一个具有挑战性的问题,特别是在有限通信或没有中央实体的情况下。在本文中,我们提出了Real-time planning using Linear Spatial Separations (RLSS):一种用于静态环境下协作式多机器人团队实时去中心化轨迹规划算法。该算法需要相对较少的机器人能力,即无需高阶导数地感知机器人和障碍物的位置,并能够区分机器人和障碍物。不需要通信,考虑机器人动力极限。RLSS生成和解决凸二次优化问题,这些问题在运动学上是可行的,并且如果问题的解是可行的,则保证避免碰撞。我们在模拟和物理机器人上实时演示了算法的性能。我们将RLSS与两种最先进的规划器进行比较,并在森林型和迷宫型环境中实证地表明RLSS确实避免了死锁和碰撞,显著提高了之前的工作,它会在此类环境中导致碰撞和死锁。