连续环境中的多代理路径查找
想象一下,如果我们所有的汽车都可以驾驶自己 - 自动驾驶变得可能成为可能,但是在多大程度上?如果路线清晰且定义良好,则将车辆本身放到某个地方似乎并不那么棘手,但是如果有更多汽车,每辆车都试图到达另一个地方怎么办?和[…]
来源:RobohubKristýnaJanovská和Pavel Surynek
想象一下,如果我们所有的汽车都可以驾驶自己 - 自动驾驶变得可能成为可能,但是在多大程度上?如果路线清晰且定义良好,则将车辆本身放到某个地方似乎并不那么棘手,但是如果有更多汽车,每辆车都试图到达另一个地方怎么办?如果我们为元素添加行人,动物和其他未划分的行人,该怎么办?最近对这个问题进行了越来越多的研究,并且已经用于仓库物流等方案,其中一组机器人在仓库中移动箱子,每个机器人都有自己的目标,但是所有这些都可以在尽可能短的同时移动,并确保不碰撞并制作路线 - 路径 - 尽可能短。但是如何形式化这样的问题呢?答案是MAPF - 多代理路径发现[Silver,2005]。
多代理路径查找多代理路径发现描述了一个问题,我们有一组代理商(机器人,车辆甚至人),他们每个人都试图立即从起步姿势到自己的目标位置,而无需碰撞(同时处于同一位置)。
通常,此问题已在图表上解决。图是能够使用其焦点和它们之间的互连来简化环境的结构。这些点称为顶点,可以表示例如坐标。它们通过边缘连接,后者连接相邻的顶点并表示它们之间的距离。
但是,如果我们试图解决现实生活中的情况,我们会尽力模拟现实。因此,离散表示(使用有限数量的顶点)可能不够。但是,如何搜索一个连续的环境,即基本上有无限小尺寸边缘连接的无限顶点的环境?
Janovská和Surynek,2024 等。这项研究得到了捷克科学基金会(22-31346)的支持。
您可以在这里阅读我们的论文。
在这里