Abstract
Planning for multi-robot teams in complex environments is a challenging problem, especially when these teams must coordinate to accomplish a common objective. In general, optimal solutions to these planning problems are computationally intractable, since the decision space grows exponentially with the number of robots. In this paper, we present a novel approach for multi-robot planning on topological graphs using mixed-integer programming. Central to our approach is the notion of a dynamic topological graph, where edge weights vary dynamically based on the locations of the robots in the graph. We construct this graph using the critical features of the planning problem and the relationships between robots; we then leverage mixed-integer programming to minimize a shared cost that depends on the paths of all robots through the graph. To improve computational tractability, we formulated an objective function with a fully convex relaxation and designed our decision space around eliminating the exponential dependence on the number of robots. We test our approach on a multi-robot reconnaissance scenario, where robots must coordinate to minimize detectability and maximize safety while gathering information. We demonstrate that our approach is able to scale to a series of representative scenarios and is capable of computing optimal coordinated strategic behaviors for autonomous multi-robot teams in seconds.
Abstract (translated)
在复杂的环境中规划多机器人团队是一个挑战性的问题,特别是在这些团队必须协调完成共同目标时。通常情况下,对这些规划问题的最优解决方案是计算不可数的,因为决策空间随着机器人数量的增加呈指数级增长。在本文中,我们提出了一种使用整数混合编程来规划多机器人拓扑图的新方法。我们的 approach 的核心是动态拓扑图的概念,其中edge 权重根据图中的机器人位置动态变化。我们使用规划问题的关键特征和机器人之间的关系构建这个图;然后利用整数混合编程来最小化取决于所有机器人路径的共同成本。为了改善计算可计算性,我们制定了一个完全凸的松弛目标函数,并围绕着消除机器人数量对决策空间的指数依赖性来设计我们的决策空间。我们在一个多机器人侦察场景中测试了我们的 approach,在这个场景中,机器人必须在收集信息时协调,以最小化检测性和最大化安全性。我们证明,我们的 approach 能够扩展到一系列代表性场景,并在秒钟内计算自主多机器人团队的最优协调战略行为。
URL
https://arxiv.org/abs/2303.11966
