问题是这样的：已经给了“n”个机器人一个带有障碍物的二维网格。机器人可以在一个时间周期内在相邻的单元中移动。机器人有多种限制，例如它们不能同时位于同一个单元中。然而，它们可以同时移动。需要为每个机器人制定一个行动计划，将机器人从起点移动到目的地，使得满足约束条件并且机器人所花费的总时间最少。
我似乎无法理解这个问题是否是一个NP难题
快速搜索可以找到有关该主题的最新论文：
在有向图的这种特殊情况下，问题是 NP 困难的。在许多情况下都有多项式时间算法来寻找解决方案，但即使在无向图上寻找最优解决方案也是 NP 困难。 （滑动瓷砖谜题是 NP 难的，多智能体寻路是一个特例。）