研究了基于最大完工时间(最后到达时间)准则的图上多机器人最优路径规划问题。采用A*搜索算法求解。在MPP实例中，机器人被唯一标记(即可区分)，并被限制在nxn平方连通图中。在不发生碰撞的情况下，机器人可以在一个时间步内从一个顶点移动到相邻的顶点。MPP公式的一个显著特点是，我们允许机器人在完全占用的周期内同步旋转。

为了解决上述问题，我们采用A*算法从给定的初始3x3机器人位置和期望的3x3机器人位置找到最优路径。首先，算法开始构建图形，其连接显示可能的运动。然后我们将其扩展为基于时间的图。根据时间扩展图，对每一个时间步长进行节点倍增。这意味着，如果给定示例中我们有3x3个节点，我们将在ts时间跨度分析的时间扩展图中有3x3xts节点数量，因为我们将演示设置为ts=7。t层中的每个节点在(t+1)层中都有自己的节点，但它也与(t+1)层中的一个远节点相连。