2024年2月19日发(作者：)
高效率的多智能体路径规划
摘要：启发式的目标驱动智能体在有障碍物的环境中显得相当费时，尤其是智能体数量庞大时。在本文中，我们引入一种有效的算法，使其能为运动在用户定义的终点和不碰到障碍物的点之间移动的物体生成路径规划。此外，系统允许淘汰一些对不可见的智能体的计算，即仅仅当智能体对用户可见时才能被精确地模拟，而对那些不可见的智能体做适当地估算。这些估算确保了智能体的行为匹配那些发生在已经被完全模拟之外的情况，并且实现了相对于对所有智能体做精确模拟有很大程度的速度上的超越。
关键字：路径规划，虚拟智能体，代理模拟，模拟的详细程度
1.简介
对成千上万的相互制约的智能体的模拟在以下方面有很大的需求：娱乐应用（游戏[7]和电影[16]），模拟训练和科学可视化[2]。路径规划问题是要确定每个智能体应在每个动态的框架内移动 。路径规划算法负责维护拟合理的智能体行为的许多基本方面，包括避免碰撞和目标满意。路径规划也消耗了相当一部分计算时间去做许多模拟，特别是在高动态环境中，大部分智能体在同一时间内沿着变化的目标移动。由于它的视觉质量和高仿真结果的影响 ，这项工作是不可避免的。（例如，智能体必须出示延时是由于避障的证据）。
路径规划通常是对一个智能体进行一次，并细分为至少两个任务。首先是关注全局路径规划，确定一种从智能体的当前位置到目标位置的理想的路径。典型的全局路径规划忽视局部的短暂的障碍，如其他移动的物体。第二，局部任务关注的是使智能体以合理的速度沿既定路径移动并重新考虑到全局路径规划忽视的障碍。
一个关键点，如果相关的智能体不出现在视野之内，局部任务就变得不那么重要了。例如，如果局部模拟主要是关于智能体之间的避障，并且观察者不能看见此类碰撞，那么几乎没有任何点能招致计算成本去回避它们。这种情况类似于在底稿上进行几何去噪时，而一些隐藏的几何图不是通过描绘器仔细绘制的。
局部看不见的相互作用会影响全体的模拟，即使它们发生在视线以外。例如，一个正在通过智能体相互拥挤地区的智能体比独立的智能体要花费更长的时间来达到目标。速度上的差别完全归咎于局部智能体的相互作用。由此，忽略视线以外的运动是相当有缺陷的。然而，我们可以估计它。观察者不能实际看见此相互的作用，所以只要它们积累的作用仍然能被观察者感知，模拟还是可以接受的（例如，智能体们将花费更多的时间它们相互拥挤的地方）。
本文我们介绍一种为大量同时移动需要绕过固定障碍物和绕过彼此的智能体们巧妙设计的高效路径规划。我们的方法由一个为视线以内智能体设计的模拟器和一个改良模拟器——代理模拟器，对视线以外智能体进行操作的模拟器。代理模拟器用整体代价的一个微小部分定量地近似的模拟结果，而精确的模拟则不能有效地影响观察者对环境的经验。
第2节将简要讨论路径规划和有效模拟的相关工作。 然后，我们描述了准确的路径规划（第4节）和代理规划（第5节）。
2 相关工作
早期对单个智能体的全局路径规划描述此类问题为通过定义支持更短路径并且添加回避碰撞的约束条件的价值函数进行强制优化。梯度下降法也许可以找到最小价值路径，但容易陷于局部最小值，不一定达到理想状态。Barraquand，Latombe，Overmars和Kavraki [1，13，9，15] 提出一种临时的随机导航作为从局部最小值恢复的方法。不幸的是，大部分随机的或被动的最优化路径规划算法在特殊的环境中是昂贵的，甚至可能无法达到目标状态。
以前的多智能体路径规划算法也作为最优化问题被建造。约束条件被用于阻止智能体之间的碰撞[12]。显然这些方法至少像单智能体情况一样昂贵和趋向局部最小值。在陆上路径规划执行和质量基于依赖由同一水平设计者布置的路标位置的系统。尽管A*算法和其变体确保给出最优路径，但对于大的环境，它们显得太慢，尤其在本文中我们使用那些型号的环境中。
对路径规划的二维计算几何算法用一个对环境的多边形描述并且在可见的障碍物最高点图表上进行操作（见[复审11]）。由于它不涉及用路标离散化环境并且不容易遭受局部最小值问题，在我们的工作中采用此类的规划。
最后，作者[4]所描述的模拟代理：此模拟意图对视线以外的物体进行处理
以大幅降低整体成本。本文侧重此项工作的一个特殊方面：对大规模路径规代理模拟器的设计。一个廉价的模拟方法在[4]中被提到。
3系统综述
我们的系统面向实时计算机策略游戏或相关应用里存在的路径规划问题。代表性地，一场实战可以通过模拟移动在二维地形或根据操作者命令攻击其他物体的每一个个体的行为被模仿。在这样的游戏中，由于个体数量庞大并且路径规划和障碍侦查算法的高复杂度，路径规划和个体之间的避障组成了模拟器工作量。在大部分的战役游戏中，用户在任何时候是不允许看到整个战场的，所以一个近似的代理的模拟器可以取代精确的路径规划并且避免与不可见的个体之间的碰撞。我们介绍这样的代理模拟器，它可以允许我们模拟在同一平面内移动的数量庞大的个体。在这种情况下路径规划具有以下属性：
*空间是二维的并且由两部分构成：自由空间和由封闭的简单多边形定义的固定障碍物；
*空间的智能体都有固定的大小，并且以匀速按用户的命令向目标地点移动。没有命令，智能体留在同一地点，并且要停止。在我们的实验中，用户被随机选择个体并给它们命令的程序取代；
*个体应当沿最短路径移动到它们的目标地。为了避免与固定的静止的和其他动态的障碍物碰撞，它们可以偏离这条路径；
*观察者只能看到空间里有限的地区。
基于以上规则，模拟器可以在空间里沿一帧到另一帧移动智能体。我们工作的目标是在受约于在所有时间里观察者都经历到合理的行为的条件下，尽可能简单地演示这个模拟器。这种情况下，合理的行为包括：对象采取时间才能到达目的地，与空间内的其它对象的运动相协调，它们运动的限制条件还有它们的命令。我们不能关心在空间内视线以外的瞬时运动是正确的。这个想法会在第5节进一步探究。
4 全局路径规划
路径规划和避障问题为了解决单个智能体收到命令从当前位置到新的目标点的运动。这条路径分三步构成——每一步回避一种障碍物。
1 当第一次收到命令时，一个绕过空间内所有固定障碍物的路径被构建。这
步制作出有广泛应用的预先计算出的数据结构，正如以下描述。预先计算在这里是合适的，因为固定的障碍物在整个模拟过程都不改变。
2接下来智能体绕过停在它的投影路径上的智能体群。这一步同样是命令给出时演示，但不依赖预先计算因为它不能提前知道对象停留在哪里。这一步过后对象将开始自由移动。
3在帧对帧移动基础上，智能体检查与其它移动的智能体或由于被给出命令而停止的智能体的碰撞。如果碰撞被检测到，路径计划将会根据以下的指导方而被校正。
图1，在二维界面内颜色较暗的多边形代表障碍物。实心圆是障碍物的顶点并且排列在可见图表的节点上。虚线对于障碍物是可见图表的边缘。A和B之间的各顶点分别被折线和填充物包围。既然两点之间的最短路径必须先到达起始点视野内的一个顶点，从一个目的点视野内的一个顶点穿过零条或更多条边到达最终目的点。A和B之间的最短路径已出示在图中。既然C点不能在从B或到B点的最短路径上，因为B能看见两条边附带这些顶点。但由于B不能看见D的两条边，它可以在一条最短路径上，并且其中的一条已经被绘出。
对象停留也就是到达它路线终点时，它从模拟器中被移走直到它接到另外的运动指令，这样停留对象不消耗任何动力学时间。
智能体也可以在中途适当的点处建造局部的路径计划，沿着这条路径可以到达最终目标地点。这给路径规划者在建造全局路径之前就有对局部的选择权。如果对象到达局部规划的终点，另一个从当前路径终点到最终终点的路径就会生成。将要被建造的路径的长度受限于一个参数-计划的时间。
4.1固定的障碍物
在我们的模拟器里，像水和岩石这样的固定障碍物用平面里简单的多边形表示。我们通过障碍物各顶点预先计算出多边图形：如果没有与其它任何固定障碍物交叉，智能体可以沿着它们通过，那么这样的两点之间形成一条边。尽管假设所有对象都有一样的尺寸，但它不是很难的限制，因为它可以被对路径规划的局部矫正所包围。在任何成对的两个顶点之间的最短路径通过Dijkstra算法预先计算出来，对每一个顶点运行Dijkstra算法直到它对每一个其它点最短路径被求出为止（图1）。在障碍物顶点之间最短路径和它们的长度存储在紧凑的图表中，表中入口（i,j）指出在从i到j点最短路径上剩余的障碍物顶点。寻找障碍物图形边缘的算法具有on复杂度[14]，其中n是图形边缘的数量。图形中任何一对顶点之间的最短路径以on3计算并存储在on2的表里。考虑这只是预算，所以复杂度不影响运行时间。我们未优化的计划在高性能PC机上对典型复杂的游戏地图执行这个估计在5到10分钟之间。
由于计算可见图形和最短路径，平面被分割成许多视野区域。每一个视野区域包括有相同视野的点组成或是可见的障碍物顶点的集合（图1）。在此背景下，如果在两点之间没有和其它固定障碍物交叉，对象可以沿直线通过，那么这两点是可见的。渐渐地，形成视野区域的顶点数量可以近似环境中所有障碍物的顶点数量。环境中视野区域的数量随着障碍物顶点数量以指数形式增长并以onn存储。
忽略每一个视野区域的复杂度和区域可能的指数数量的最坏情况，在我们的测试地图中视野内顶点的数量约为4-8并且典型视野的数量约为数百。这些计算机游戏环境中的地图拥有典型的复杂度。此外，如果一个障碍物顶点的两条相关边都在视野区域内，那么这个点不一定包括在视野区域内，因为它在那个区域不可能是最短路径的开头或结尾，从而削弱了视野区域的尺寸（图1）。视野区域展示了大量的空间相关性，也就是说相邻的区域通常会相同的一段视野，并且可以用空间数据结构有效地存储。
预先计算的产生的可见图形，其中的最短路径和分解环境的视野区域构成计算最短路径的运行时间。每一个命令包括起始点，Pstart（智能体当前位置）和
终点，Pend。为了生成路径，我们首先获得Pstart,Hstart的视野内顶点集合和Pend,Hend.这些集合从预先计算视野区域是有用的。然后我们发现这对（Vstart,Vend),VstartHstart,VendHend所以这条路径PstartVstartVendPend有最短距离。Vstart和Vend的最短路径可以由对全部Vstart，Vend得预先估计而得来。
最佳路径可以用（Vstart,Vend)描述。实际路径是连接Pstart和Vstart的直线段，然后存储紧接着连接Vend到Pend线段的从Vstart到Vend的最短路径（图1）。而Vstart和Vend可能会是同一点。此外，如果从Pstart看Pend是可见的，那么最短路径简单地就是连接着两点的直线段。（通过注释一种情况被检测到）。 最糟糕情况下，寻找视野范围内最近一2o(h)其中h是障碍物的顶点数。然而如上文所述，视野区域对顶点的复杂度是趋向与小尺寸，所以计算有比较快。在我们的路径规划系统中，绕过固定障碍物的路径规划在实时计算方面是很廉价的，即使在最复杂的地图里。在渐进价值方面，再多边形环境中存在on的空间和ologn复杂度的算法计算两点间的最短距离[6, 8]。然而渐进优化算法的常数因子是很大的，在我们的系统里运行得更坏。
4.2停下来的对象
当对象停止运动（重新开始时，移动它们），将它们插入视野区域数据结构的价值是相当昂贵的。相反，我们通过过联机规划绕过停下来对象的路径。一旦绕过固定障碍物的全局路径规划生成时，它将被检查是否与其它智能体有任何的碰撞。如果有停下来的智能体在已定的路径上，那么这条路径将被矫正使其绕过此障碍。这些停下来对象被分割成一些对象群，不同的群组里的任何两个对象间的距离要足够可以使一个对象通过才可以。这样如果一个对象群阻碍路径，唯一的选择是绕过群组里所有的对象。
图2 有静态的物体组1和组2在移动物体的目的路径上（显示为一个虚线）。可能的路径是通过遍历列举的左，右两边考虑对阻碍组（1）和持续的过程递归。请注意，对阻碍组（1）的遍历可能会遇到（2）组中的其他障碍物。用这种方式做出的路径可以表示为叶子是候选路径的二叉树。
障碍物周围的所有路径可以通过递归考虑障碍物组的左右子树来枚举（图2）。请注意，此枚举过程还必须考虑到固定的障碍。枚举过程可以在所有可能的回避模式的发现和评价最优或足够长的路径区段发现之后停止（由路径预置的时间参数来控制）。在第一种情况，虽然我们能够保证最佳路径，但是获取路径的成本是可观的。在第二种情况下，局部路径可能不会最优，但局部路径规划的成本要低得多，允许我们就任何一个拥有更多的对象的单一框架生成这种部分路径规划。
在此枚举步骤中，为了避免通过他们的路径，路径必须对固定障碍进行核对。如果没有路径不通过固定障碍被发现，那么我们就必须放弃原来的路径规划，因为它不能带我们通过障碍。如果一个桥梁被其他物体挡住的话就可能发生这种情况，所以为了通过这个桥梁必须使用另一路径，可以通过搜索见度图来找到这样一条不包含被阻挡的原始路径的路径。由于这一步通常是耗时，我们还可以预先计算和存储第二和第三随着每两地平线顶点之间最短路径，只有当三条道路都被封锁再进行搜索。
请注意，当规避的路径计算出来之后停止的物体可能会开始运动。因此，新的条件下，已经计算出的路径可能不是最佳。在我们的模拟器中我们已经取得
可以接受的结果，没有再为这种情况规划。
4.3 运动的物体
对于一个给定对象的目的路径可以进一步被其他移动的物体阻碍。通过在每个时间步长核对一个移动对象的新位置，模拟器中出现了这种碰撞。如果两个动态物体会发生碰撞，我们停止随机选中的其中一个，等待另一个移动并扫清道路。如果等待相互作用的一方不能解决问题，我们暂时停止一个物体，并迫使另外一个对它周围进行路径规划，利用前一节对停止的物体进行路径规划的算法。如果一个物体已经停止（如可发生在当最初的路径被规划之后智能体停止），那么我们也必须重新为还在运动的智能体规划路径。
在一个有很多运动物体的环境中，我们很可能会遇到非常多潜在的智能体碰撞，所以这一步需要很多路径再规划来找到其他物体周围的路径。这是最主要的花费时间的地方。但是，如果智能体不可见，我们就不用关心他们避开其他物体所走的具体的局部路径。我们只需关心的是他们走了一些弯路，由于其他的智能体的存在而延误了一些时间。在下一节中，我们描述了一种改进算法
要避免为不可见的碰撞进行的重新规划，但仍然抓住了重新规划会在智能体的行为上的影响。
5代理模拟
在虚拟环境中最重要的是观察者有合理的在这种环境中的经验。观察者通常只能感受到他们看到的东西，所以我们可以自由的对待环境中的看不见的动作，认为它对能看见的没有显著的影响。最后，任何能够影响到观察者的因素都要进入视野，所以我们主要关注的是这些查看条目在仿真中捕获我们看不见的。我们可能还需要进行捕获其他看不见的事件，以确保我们得到一个合理的查看条目流。
我们指的是能够生成查看条目的模拟器，作为一个代理模拟器。为了高效率的模拟，我们将允许代理模拟器近似看不见的动作，但这样一种方式观察者不会经历到有什么不同。在电脑游戏环境，这意味着我们必须确保知道代理模拟器的玩家不会比不知道的玩家占有优势。因此，近似模拟应该满足下列每个单独的可辨认的物体的要求：
·在战场上的任何物体都不应该通过固定障碍物（否则知情的玩家就能够
通过墙或河流进行远距传物)。
·物体间的相互作用，必须加以说明。例如，一个物体应
不能穿过入口已被其他静态物体封锁的桥梁。
·物体具有的速度应与周围环境相一致。例如，如果一个物体跟很多其他动态物体之间有联系的话，那么它的平均速度不应该太大。其他动态物体最近。这意味着物体应该（1）他们到达目的地的时间与整个的模拟环境相一致（二）沿其路径有相一致的阻力。例如，物体应遭遇相一致的埋伏。
5.1 追踪智能体的位置
为了确定何时智能体应重新进入，我们将跟踪其大概位置。这使我们能够确定如果观察者移动，哪些物体应该是可见的，也使我们发现和解释看不见的智能体和他们所在环境的相互作用。我们把战场细分为矩形小块，作为我们处理的单元格。对战场观察者有一个矩形视角，所以只能看到跟这个矩形区域相互作用的单元格。只有在这些单元格内的物体是可见的。另外，只有在同一单元格同一时间的物体可以相互影响。
路径规划和避免碰撞代理模式是一种离散事件模拟器，被用于管理每个单元格的每个对象的成员身份信息。更具体地说，使用代理，以确保每个单元格中包含的对象列表都被打上了他们将进出单元格的时间。在每一帧，进入的任何可见单元格的动态对象是从代理模拟器模拟和代理模拟器对这些对象是关闭的。同样，离开可见单元格的对象被切换到代理模拟。我们用离散事件模拟器所使用的事件和它对事件的处理来定义它的行为。我们首先描述三个事件，并稍后提出另一事件。我们还推迟了如何对这些事件的时间预测的讨论。
Stop: 代理模拟器中的对象已到达了目的地。当此事件发生的时候，代理模拟器将对象从动态转到静态，并在与它有关的所有单元格中将它移除。请注意，stop事件可能形成了一个阻止其他动态事件运动的障碍。因此，当我们处理stop事件的时候，我们要注意能够与停止的物体碰撞的动态物体，如果有必要就重新计算它们的事件。
Replan: 由于对象可能也有部分路径的规划，一个路径规划可能会在它到达目的地之前就失去了它的有效性。在这种情况下，代理模拟器必须生成一个从当前的规划的最后一点到该对象最终目标点的新的路径规划。
Entry: 这个事件是为智能体在代理模拟器中预定的，将进入一个可见的单元格。当这个事件发生的时候，代理模拟器从所有单元格将这个智能体删除。它还被指定为一个完全运动状态。这是通过根据智能体进入单元格的时间随机指定的状态和它在单元格内预期的行为（如下所描述）来实现的。
5.2设置事件时报
代理模拟器需要能够预测何时智能体结束它的规划，这样就可以预先安排stop或replan事件，或者当智能体到达可见单元格的时候，使进入的事件可以被预先安排。这是通过使用能够确定哪些对象可能相互影响的分层数据结构和一个概率模型来估计事件时间上的交互影响。
在固定和停止的物体周围发命令以及规划的过程没有被代理模拟器更改。这些行动已经很快了，它们提供很有用的信息关于对象将去的目的地以及到达那里的时间。特别是，考虑到该对象的匀速，我们可以使用基本计划计算最快发生的事件。 代理模拟器避免了在运动的智能体之间的碰撞进行的重新规划，这是精确的模型中最主要的仿真花费。这些相互作用只能增加延迟智能体的飞行时间。
代理模拟器收集这些对象的路径规划，用来模拟并将每个对象插入到与它的预定轨道相交的单元格中。代理模拟器也为对象预定安排要访问的所有的单元格将每一个对象标记上相应的出入时间。时间邮票的计算是通过考虑物体的速度和与它预计将沿路径交互的其他物体。
这些相互作用被发现使用的是对每个单元格四叉树的分解，用于消除不交叉的物体的路径。每当一个对象插入到单元格，该单元的四叉树的根都会为其他对象而被研究。如果另一个对象也占同样的四叉树节点，然后这两个对象会被插入同时作为孩子节点。请注意，已经在节点的对象可以直接放到树中的一个较低的节点，因为它不能与另一碰撞对象——如果它能够碰撞，它就会是一个较低的节点。
这个过程按序继续进行遍历，直到没有其他对象的节点存在于节点，这意味着对象将不会发生冲突，或到了树的最大深度，就有可能碰撞。请注意，由于道路计划是分段线性，插入可以通过遍历每个线性部分和按序把它插入到跟它相交的节点中。如果我们一直降到叶子，我们再为碰撞检查一下叶子节点。树的最大深度是一个用户指定的参数，可以根据单元格和对象的大小进行调节。
通过对两个相互作用的原始的路径规划来近似检测相互作用。这是合理的，因为一个动态的对象不是移动扫清道路，就是相互作用的一方在另一个的周围进行规划，通常能够解决碰撞不会滞留。
延误是从概率混合分布抽样获得的。这种分布通过抽样在全面模拟由对象相互作用产生的延迟和拟合EM算法而获得。由此产生的分布通常是足够好，可以为动态对象捕捉到精确的速度关系。
在一个物体的规划中引入延迟可能会使一些之前已经计算的相互作用失效，特别是所有那些之前会跟这个延迟的物体有相互作用的物体。因此，在引入了延迟后所有未来的相互作用必须重新检查。由于对象可以有很长的路径规划 ，这一步骤可能包括对很多已在代理模拟器的对象进行重新相互作用的计算。我们通过只对一段特定时间和再检查计算相互作用解决这个问题。我们计算的时间的长度取决于最新的相互作用时间参数。这就引入了另外一个事件：
Reinsert: 此事件为每个对象产生，当他们最新的相互作用时间被击中并导致代理模拟器沿着智能体的路径寻找更多的相互作用。
上述过程为模拟器提供了足够的信息来估计事件时间。在给出一个命令和计算出基本的路径规划之后运行上述过程。沿着路径标记相互作用，对每一个相互作用的延迟进行取样，然后加到飞行的最小时间为事件来获取估计时间。
关于物体会遇到的延迟的本质，延迟时间上对分布的使用做了一些假设。主要假设是，延迟跟路径上智能体的数目成线性关系。在我们的特殊情况里这似乎是一个合理的假设。如果它是无效的，那么影响分布的参数就是相互作用的数量，尽管这对学习过程和存储都会花一些代价。另一个假设是，延迟不依赖于模拟已经运行了多久或其他跟时间相关的参数，这一点在这种情况下无疑是合理的并很可能在大多数环境是有效的。
在这个框架里，可以通过对在单元格里正在变得可见的物体的状态取样来提供观察者的动作。由于我们知道进入的时间和每一个在单元格里物体积累的延迟时间，我们可以有效地估计他们的位置。由于观察者的动作不需要特殊对待，物体变得可见，而且可以通过计算必要的事件，将它们插入到即将去的单元格里来控制它们。
5.3 讨论
代理模拟器最主要的错误来源是在延迟上对动态物体的相互作用的近似。但是，这些延迟是在全模型的数据基础上估计的，所以平均下来就抵消了。一个罕见的情况是代理模拟器会严重出错当两个物体都试图通过的时候就停下来了。当两个物体同时传过一个比较窄的桥的时候就会出现这种情况，这是由于在我们的路径规划器里缺少一个“备份”逻辑。如果一个桥只能通过一个物体，那么这两个物体都会等另外一个物体先通过, 因为现行的重新路径规划没有在另一个物体周围规划。这种情况可以通过检查交互方是否成功的找到回避的路径规划。这种僵局可以通过一个更好的可以让物体后退为其他物体让路的办法来解决。但是目前我们忽略了这一情况，因为从整体来说它所造成的影响很小。狭窄的间隙通常比较罕见，而且出现这种同时反方向穿过间隙的情况的概率也比较小。
请注意，代理模拟器不需要对精确模拟很精确地给出相同的结果。单个物体可以同时有不同的状态，而且在精确的模拟器下会按照不同路径走，只要不违反用户的期望。举例来说，一个对象不应该在用户的屏幕上突然出现或消失，或到达它的目的地太快或太慢。大多数情况下我们的代理模拟器都能够满足要求，但是，它也可能出现令人难以满意的局面，当它在完全模拟情况下产生不一致的状态。代理模拟器真正意义上的成功必须经过大量的人去实验，而我们只在我们的研究小组里做过试验。
6 结果
我们已经在不同的地形上用不同数量的智能体测试过我们的代理模拟器。图4出示了用代理的模拟器计算1600智能体的动力学计算时间的总量，比较了全局模拟的数量。图3出示了在奔腾 III 800兆赫兹计算机上根据固定密度智能体数量模拟动力学1秒钟的动力学时间的总量。对于所有模拟，智能体在地图上随机分布，并随机选择目的点。随着智能体数量增加，通过增长地域尺寸的方式保持智能体密度恒定。由于全局模拟为了避免碰撞需要再规划，可能不得不处理改进规划一起的额外碰撞，导致为每一个需要规划改进的相互作用的额外成本。相反，代理模拟器用概率延迟估计这些相互作用，从而不需要再规划。即使代理模拟器仍然观测所有的动态智能体间的相互作用，掌控者些相互作用的成本已经较全局模拟有相当程度的低廉。
7 结论
我们已经推出了一种为大量操作在实际环境中的智能体新奇的路径规划算法。我们的算法特别有效因为我们利用视线外的运动来降低模拟成本。
图3.根据均匀密度地域对象数量的记录，实际时间要求模拟模拟时间的1秒。高处的曲线（折线）表示未用代理的模拟，低处的曲线（完整的）表示用代理的模拟。点状水平线是实时的中断。既然对象的密度是恒定的，用户在视野内应该看到近似相同数量的对象。由于代理模拟器不是针对不可见对象且它们的相互作用用离散事件模拟器操作，模拟成本的增加远低于整体的模拟。全局模拟成本非常快速的增长源于回避动态对象之间碰撞的路径规划矫正像滚雪球一样。而代理模拟用概率模型估计动态对象之间的相互作用，从而避免局部路径矫正。
我们不能一直确保代理模拟的正确性，因为它可能会与精心设计的精确模拟相冲突（例如，沿着相反方向通过一条窄桥的对象们）。然而代理模拟是模仿那些对精确模拟来说太大的环境的唯一方法，或者剪切在虚拟分布式环境中不得不被传播的数据。注意模拟器可扩展性的渐渐获得只有通过代理才有可能实现。如
此，确保模拟代理器有好的行为是很重要的研究热点。
最后我们的目的是提供帮助建造代理模拟器的工具。这些工具在某些形式上接受精确模拟，并伴随用户介入，建造一个存储估算但保留原始模拟模型重要性能的代理。
图4 动力学计算时间在纵轴上通过全局模拟（顶部）需要3小时对比代理模拟（底部）实际模拟的一秒。此模拟用1600智能体在适度稠密地图上放在随机的位置上而运行。
参考文献
1. J. Barraquand and J. Latombe. A monte-carlo algorithm for path planning
with many degreesof freedom. In IEEE Int. Conf. Robot. & Autom., pages
1712–1717, 1990. 257, 1990.
2. Michael Batty, Bin Jiang, and Mark Thurstain-Goodwin. Working paper
4: Local movement:Agent-based models of pedestrian flows. Working
Paper from the Center for AdvancedSpatial Analysis, University College
London, 1998.
3. Christopher M. Bishop.
Neural Networks for Pattern Recognition. Oxford
University Press,1995.
4. Stephen Chenney, Okan Arikan, and h. Proxy simulations for
efficient appear in Eurographics 2001, Short
Presentations.
5. B. Faverjon and P. Tournassoud. A local based approach for path
planning of manipulatorswith a high number of degrees of freedom, int.
conf. robotics & automation, 1987.
6. Guibas and Hershberger. Optimal shortest path queries in a simple
polygon. In
COMPGEOM:Annual ACM Symposium on Computational Geometry,
1987.
7. Demis Hassabis. Level-of-detail ai. Lecture at the 2001 Game
Developers Conference.
8. Joseph O’Rouke Jacob E. Goodman.
Discrete and Computational Geometry.
The CRCPress, Boca Raton, New York, 1997.
9. Lydia Kavraki, Petr Svestka, Jean-Claude Latombe, and Mark Overmars.
Probabilisti croadmaps for path planning in high-dimensional
configuration spaces. IEEE Transactions on Robotics and Automation,
1996.
10. Jean-Paul Laumond.
Robot Motion Planning and Control. Lectures Notes
in Control and Information Sciences. Springer Verlag, 1998.
11. J. Mitchell. Shortest paths and networks. In J. E. Goodman and J.
O’Rourke, editors, Handbook of Discrete and Computational Geometry,
CRC Press LLC, Boca Raton, FL, 1997.
12. L. Overgaard, H. Petersen, and J. Perram. Reactive motion planning:
a multi-agent d Artificial Intelligence, 10(1), 1996.
13. M. Overmars. A random approach to motion planning. Technical Report
RUU-CS-92-32,Department of Computer Science, Utrecht University, The
Netherlands, 1992.
14. S. N. Maheshwari Sanjiv Kapoor. Efficiently constructing the
visibility graph of a simple polygon with obstacles. In
SIAM Journal
on Computing, volume 30(3), pages 847–871,August 2000.
15. Dimitris Metaxas Siome Goldenstein, Edward Large. Special issue on
real-time virtual worlds: Non-linear dynamical system approach to
behavior modeling. In
The Visual Computer,volume 15, pages 341–348,
1999.
16. Marjolaine Tremblay and Hiromi Ono. Multiple creatures choreograhy
on Star Wars:Episode I “The Phantom Menace”. SIGGRAPH 99 Animation
Sketch. In Conference Abstracts and Applications, page 205, August
1999
发布评论