Multi-Robot-Path-Planning-on-Graphs:基于A*算法的图解多机器人路径规划-matlab开发

我们研究了在 makespan（最后到达时间）标准上的图（MPP）上的最优多机器人路径规划问题。 我们实现了 A* 搜索算法来寻找解决方案。 在 MPP 实例中，机器人被唯一标记（即，可区分）并被限制在 nxn 平方连接图中。 在没有碰撞的情况下，机器人可能会在一个时间步长内从一个顶点移动到相邻的一个顶点，这可能发生在两个机器人同时移动到同一顶点或沿同一条边向不同方向移动时。 我们的 MPP 公式的一个显着特点是我们允许机器人在完全占用的循环中同步旋转。 为了解决上述问题，我们实施了 A* 算法，以从给定的初始 3x3 机器人位置和所需的 3x3 机器人位置中找到最佳路线。 第一个算法开始构建图，其连接向我们展示了可能的运动。 然后我们将其扩展为基于时间的图。 根据时间扩展图，每个时间步长都复制所有节点。 这意味着如果我们有 3x3 节点作为给定的例子，我们将在我们的时间扩展图中有 3