技术文档

当前位置:

Pathfinder中的新寻路技术和支持研究

Pathfinder中的新寻路技术和支持研究

Charles Thornton,  Richard O'Konski , Bryan Klein , Brian Hardeman, Daniel Swenson 

Thunderhead Engineering ,403 Poyntz Ave STE B, Manhattan , KS,66503 ,USA

{thornton , okonski , klein , swenson}@thunderheadeng.com


摘要,本文介绍了路径查找器出口模拟器所使用的寻路算法和门选择算法。我们将Pathfinder局部UI快算法的发展,以及不可预见的后果的初步尝试。给出了新模型的验证,以及使模型漆验证成为可能的第三方研究的特点。


Pathfinder是一个基于商业代理的紧急出口的模拟器。该软件包括用户界面、模拟器和三维可视化系统。本文所讨论的寻路方法是模拟器的一个方面。

模拟agent或居住者,从他们的其实位置移动到出口时,必须选择一条在向他们选择的出口步行时要遵循的路线。此路线选择过程(路径查找)显著影响总体模拟结果,因为排队等待的时间控制了所有agent实现其目标所需的时间。

以前,Pathfinder使用一个简单的过程来执行这个寻路任务。使用AStar(A*)搜索算法,Pathfinder将为每个agent计算agent退出模型时可能采用的最短路径。由于此AP-Proach不考虑门口的队列形成,选择路由沿线的瓶颈以及等效的替代路由,因此有必要使用各种工作回合来使agent走几个额外的步骤以避免较长的排队时间。图1 显示了这个问题的一个例子。


图1 、仅最短路径agent无法利用分隔门的全宽度


图1显示了一个案例,其中模拟的代理程序视图使用一个独立的门退出一个房间。起初,agents被安置在房间的较低部分。在这种情况下,只有一个agent是用了分隔门的上部。这是因为基于最短路径的寻路算法只依赖于agent的初始起始位置和最近的预定出口之间的距离。该计算没有考虑到拥堵对总路程时间的影响。

在任何时候,当agents需要通过多个出口(例如,一个走廊桐乡包含一排出口门的入口区域)的瓶颈时,都会发生类似的问题。在这种情况下,路径规划算法在到达一个公共点后对每个agent执行相同的计算。这导致所有的agents都只会去寻找许多可用门中最近的一扇。


2、Locally最快

本地最快算法旨在克服上一节中提到的问题。Locally Quickest算法不是在模拟开始时计算出口的完整路径,而是选择一个同乡当前房间的门。每次代理agent进入新房间是都会重复此过程,直到agent退出此模拟。在评估当前房间的路线是,agent会计算好每条路线(即门)的时间估算值。该估计考虑以下参数:

  • 估计到达并通过当地门需要多长时间

  • 估计到达当地门后到达有效出口需要都长时间 

选择本地门时,agent将哦通过最短时间路径到门的时间与通过门上形成的队列所需的时间进行比较。

进入房门意外所需的时间被假定为这两个值中较大的一个。为了计算达到本地门外的出口的时间,Pathfinder基于A*路径搜索执行距离计算。agent使用距离计算的结果及其最大速度来估算时间。

次计算假设agent不了解其他房间中的队列,因此结果表示agent当前房间之外的最快时间。在估计当地路程时间和当前房间之外的时间之后,agent选择提供总时间最快的门。如果多个本地门似乎提供非常相似的路程时间,agent将选择通过最近的等效门的路径。


2.1、本地移动时间

本地移动时间对于确保智能地利用当前房间内的所有可用出口门非常重要。ALGO-RIM的一元素为agent提供了一种方法,以便在最短的Availa-ble路由拥塞时决定使用较长的路由。

计算空房间中的本地移动时间是一个简单的过程,可以使用A*搜索确定到下一个门道的距离,并且可以使用agent的速度从该距离移动时间。然而,其他agent的优先级使得这个过程更具有挑战性。agents有必要估计在排队等候时到达门口需要多长时间。早期的犯法基于这样的假设,即拥塞主要发生在门周围(例如,在代理等待通过门的区域),并且细粒度密度计算可以指示拥塞区域。这种方法的一个例子如图2和图3所示。

图2. 一个Pathfinder模拟,其中一个大组转过一个拐角,然后通过一系列旋转门退出。



图3. 在图2所示的模拟中用于确定密度的基于Voronoi图的细粒度密度计算的可视化。


图二中所示的模型是具有十二个出口门的L形房间。出口门的结构类似于0.5米深的分裂的十字转门。所有agent最初都装在模型的左上部分,使得顶部出口最接近大多数agent。图3是当agent开始到达出口门时基于Voronoi图的细粒度密度计算的可视化。使用细粒度密度信息实现的本地最快方法比原始较短路径算法产生更好的门道利用率,但它有严重的缺点。

由于该算法在直线路径上集成了密度,因此对另一扇门队列远端的门的估计将接收组合多个门的时间估计。

此外,密度计算的计算速度不够快,无法扩展到体育场大小的模型。


2.2 Door队列近似

由于基于密度估计方法的困难,提出了一种基于门队列估计的局部路程时间计算方法。要估计到达门的等待时间,座席最多使用两个值:

  • 基于最小旅行距离和代理速度的简单估计

  • 估计在该门的队列中等待的时间

要估计在门的队列中等待的时间,Pathfinder需要一种估计队列大小的方法,这由于每个agent进行门选择的不同时间而变的复杂。在队列排列良好之前(即当其他agent仍在靠近其选定的门时),agent必须选择一扇门。

所选择的方法是村相互每个房间内那些agent正在使用每个门的记录。然后agent需要测量门的队列大小时,可以通过计算等待agent并比agent离门更近的agent来决定该值。一旦确定了此计数,Pathfinder就可以使用SFPE手册[2]中较大特定流量估计值来计算门处的等待时间。此计算中较大部分和纯移动时间随后被用作到达的本地时间估计。对于每个agent,定期重复此计算,以说明其他代理所做的不断变化的门决定。


3、Backtrack预防

agent只知道当前房间中的队列大小。当他们进入一个新房间时,最后一个房间的信息被当前房间的信息所取代。在没有任何类型的回溯防止的情况下,大型队列可能导致agent在两个房间之间来回移动,直到队列状况发生改变。

为了防止这些变化,当选择允许在考虑退出计划时评估的门时,本地最快算法使用以下规则:

可用的本地本必须具有到agent目的的较短路径,而不是agent进入当前房间的门。

本地门可能无法返回agent之前占用的房间。

如果先前的标准消除了所有可用的门(例如,已经推动了agent进入一个壁橱)或者agent被人推进了一个非预期的门,回溯预防被禁用。所有当地门都可用。

4个下游队列某些平面图发生的另一个问题是未能在下游应用排队知识。以前,从本地门道目的地的时间一直是作为优化值讨论。但是,因为算法放置了这么多强调当前房间,当前房间也是随后的情况房间要求将当前房间的信息应用于任何时间估计当地门通过当前房间后的路段。图4显示了一个包含较小房间和两个门的房间。agent表示通过字母“A”必须在三个可用门之间进行选择。俩扇门属于小房间包含在较大房间的左上象限。第三道门是右边的目标门。


当最快算法的当前表明,字啊评估超出小房间门的时间是一个最小的,基于距离的时间计算使用。但是在这种情况下,这将导致agent通过消防架,相信一旦出现右边的大排队就会消散。如果您在此配置中初始化模拟,则会有许多agent从队列后面剥离,然后排队等待通过这个小房间在“真正的”门后面再出现并排队。

Pathfinder通过存储爆出每个的极佳路线来解决此问题。如果路由通过agent的当前房间,则agent替换基于的更准确版本的路线段的时间估计agent对当前房间的了解。该进的估计是完全准确的与初始门排队时间近似相同,通过比较他的时间将段距离移动到等待队列和保持所花费的时间最大值。


5、门选择案例研究

为了测试本地最快移动算法agent选择门的影响,来自VTTResearch Notes2562[3]的门选择案例研究被使用。在这研究中心,大学生在从一个集结地区搬到地方受到监控走廊和演讲厅。演讲厅有两个入口门连续沿着同一堵墙。将Pathfinder与进行的研究人员的一般观察结果进行了比较测试,“......人们在右边(相对于运动方向)上的启动网格选择[第二门]。网格左侧或中心的人前排选择了第一扇门:门1.在后排,有一种倾向使用门2.”图5显示了案例研究的平面图


图5 中的平面图显示了Pathfinder的起始位置和移动路径该测试用例的仿真模型

模拟结果如图6所示

在图6 中,第一扇门表示为“Top”,第二扇门表示为“底部”向左、向右和向后的人表示为“Right(red)”、“Left(蓝色)”和“背面(黑色)”。这些结果表明Pathfinder中的结果与一般观察结果一致。有Rinne,Tillander和Grnberg提供。此案例研究的成功代表了。对于Pathfinder来说,这是向前迈出的重要一步。在所有情况下都会对第一扇门产生明显差异。




PetraSim软件支持模型介绍
Golden Surfer软件绘制地质图件的技巧

2019-06-24

上一篇:

下一篇:

分享到: 0