论文标题
优化的定向路线图用于使用随机梯度下降的多试路径查找
Optimized Directed Roadmap Graph for Multi-Agent Path Finding Using Stochastic Gradient Descent
论文作者
论文摘要
我们提出了一种名为“优化有向路线图”（ODRM）的新颖方法。这是一种构建有向路线图图的方法，可以在多机器人导航中避免碰撞。这是一个高度相关的问题，例如工业自动驾驶指导车辆。 ODRM的核心思想是，有向路线图可以编码环境的固有属性，当代理在同一环境中互相避免时，这很有用。像概率路线图（PRMS）一样，ODRM的第一步是从C空间生成样品。在第二步中，ODRM通过随机梯度下降（SGD）优化顶点位置和边缘方向。这导致了新兴的特性，例如与墙壁平行的边缘和类似于两车道街道或回旋处的图案。然后，代理可以通过独立搜索其路径并在运行时求解发生的代理代理碰撞来导航。与非优化图相比，使用ODRM生成的图发生了明显较少的代理代理碰撞。我们通过集中和分散的计划者评估了我们的路线图。我们的实验表明，使用ODRM，即使是简单的集中计划者也可以解决其他多代理计划者无法解决的大量代理的问题。此外，我们将模拟机器人与分散的规划师和在线碰撞避免使用，以显示路线图的代理比在标准网格地图上要快得多。
We present a novel approach called Optimized Directed Roadmap Graph (ODRM). It is a method to build a directed roadmap graph that allows for collision avoidance in multi-robot navigation. This is a highly relevant problem, for example for industrial autonomous guided vehicles. The core idea of ODRM is, that a directed roadmap can encode inherent properties of the environment which are useful when agents have to avoid each other in that same environment. Like Probabilistic Roadmaps (PRMs), ODRM's first step is generating samples from C-space. In a second step, ODRM optimizes vertex positions and edge directions by Stochastic Gradient Descent (SGD). This leads to emergent properties like edges parallel to walls and patterns similar to two-lane streets or roundabouts. Agents can then navigate on this graph by searching their path independently and solving occurring agent-agent collisions at run-time. Using the graphs generated by ODRM compared to a non-optimized graph significantly fewer agent-agent collisions happen. We evaluate our roadmap with both, centralized and decentralized planners. Our experiments show that with ODRM even a simple centralized planner can solve problems with high numbers of agents that other multi-agent planners can not solve. Additionally, we use simulated robots with decentralized planners and online collision avoidance to show how agents are a lot faster on our roadmap than on standard grid maps.
