高效率的多智能体路径规划.docx

高效率的多智能体路径规划.docx高效率的多智能体路径规划摘要:启发式的目标驱动智能体在有障碍物的环境中显得相当费吋,尤其是智能体数量庞大时。在本文中,我们引入一种有效的算法,使其能为运动在用户定义的终点和不碰到障碍物的点之间移动的物体生成路径规划。此外,系统允许淘汰一些对不可见的智能体的计算,即仅仅当智能体对用户可见时才能被精确地模拟,而对那些不可见的智能体做适当地估算。这些估算确保了智能体的行为匹配那些发生在已经被完全模拟之外的情况,并且实现了相对于对所有智能体做精确模拟有很大程度的速度上的超越。关键字:路径规划,虚拟智能体,代理模拟,模拟的详细程度1•简介对成千上万的相互制约的智能体的模拟在以下方面有很大的需求:娱乐应用(游戏[7]和电影[16]),模拟训练和科学可视化[2]。路径规划问题是要确定每个智能体应在毎个动态的框架内移动。路径规划算法负责维护拟合理的智能体行为的许多基本方面,包括避免碰撞和目标满意。路径规划也消耗了相当一部分计算时间去做许多模拟,特别是在高动态环境中,大部分智能体在同一时间内沿着变化的目标移动。由于它的视觉质量和高仿真结果的影响,这项工作是不可避免的。(例如,智能体必须出示延时是由于避障的证据)。路径规划通常是对一个智能体进行一次,并细分为至少两个任务。首先是关注全局路径规划,确定一种从智能体的当前位置到冃标位置的理想的路径。典型的全局路径规划忽视局部的短暂的障碍,如其他移动的物体。第二,局部任务关注的是使智能体以合理的速度沿既定路径移动并重新考虑到全局路径规划忽视的障碍。一个关键点,如果相关的智能体不出现在视野之内,局部任务就变得不那么重要了。例如,如果局部模拟主要是关于智能体之间的避障,并且观察者不能看见此类碰撞,那么几乎没有任何点能招致计算成本去回避它们。这种情况类似于在底稿上进行几何去噪时,而一些隐藏的几何图不是通过描绘器仔细绘制的。局部看不见的相互作用会影响全体的模拟,即使它们发生在视线以外。例如,一个正在通过智能体相互拥挤地区的智能体比独立的智能体要花费更长的吋间來达到日标。速度上的差别完全归咎于局部智能体的相互作用。由此,忽略视线以外的运动是相当有缺陷的。然而,我们可以估计它。观察者不能实际看见此相互的作用,所以只要它们积累的作用仍然能被观察者感知,模拟还是可以接受的(例如,智能体们将花费更多的时间它们相互拥挤的地方)。本文我们介绍一种为大量同时移动需要绕过固定障碍物和绕过彼此的科能体们巧妙设计的高效路径规划。我们的方法由一个为视线以内智能体设计的模拟器和一个改良模拟器一一代理模拟器,对视线以外智能体进行操作的模拟器。代理模拟器用整体代价的一个微小部分定量地近似的模拟结果,而精确的模拟则不能有效地影响观察者对环境的经验。第2节将简要讨论路径规划和有效模拟的相关工作。然后,我们描述了准确的路径规划(第4节)和代理规划(第5节)。2相关工作早期对单个智能体的全局路径规划描述此类问题为通过定义支持更短路径并且添加回避碰撞的约束条件的价值函数进行强制优化。梯度下降法也许可以找到最小价值路径,但容易陷于局部最小值,不一定达到理想状态。Barraquand,Latombe,OvermarsKavraki[1,13,9,15]提出一种临时的随机导航作为从局部最小值恢复的方法。不幸的是,大部分随机的或被动的最优化路径规划算法在特殊的环境中是昂贵的,甚至可能无法达到目标状态。以前的多智能体路径规划算法也作为最优化问题被建造。约束条件被用于阻止智能体之间的碰撞[12]。显然这些方法至少像单智能体情况一样昂贵和趋向局部最小值。在陆上路径规划执行和质量基于依赖由同一水平设计者布置的路标位置的系统。尽管A*算法和其变体确保给出最优路径,但对于大的环境,它们显得太慢,尤其在本文中我们使用那些型号的环境中。对路径规划的二维计算几何算法用一个对环境的多边形描述并且在可见的障碍物最高点图表上进行操作(见[复审H])o由于它不涉及用路标离散化环境并H不容易遭受局部最小值问题,在我们的工作中采用此类的规划。最后,作者[4]所描述的模拟代理:此模拟意图对视线以外的物体进行处理以大幅降低整体成本。本文侧重此项工作的一个特殊方面:对大规模路径规代理模拟器的设计。一个廉价的模拟方法在[4]中被提到。3系统综述我们的系统面向实时计算机策略游戏或相关应用里存在的路径规划问题。代表性地,一场实战可以通过模拟移动在二维地形或根据操作者命令攻击其他物体的每一个个体的行为被模仿。在这样的游戏中,由于个体数量庞大并且路径规划和障碍侦查算法的高复杂度,路径规划和个体之间的避障组成了模拟器工作量。在大部分的战役游戏中,用户在任何时候是不允许看到整个战场的,所以一个近似的代理的模拟器可以取代精确的路径规划并且避免与不可见的个体之间的碰撞。我们介绍这样的代理模拟器,它可以允许我们模