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个下游队列某些平面图发生的问题是未能在下游应用排队知识。以前，从本地门道目的地的时间一直是作为optimize值讨论。但是，因为算法放置了这么多强调当前房间，当前房间也是随后的情况房间要求将当前房间的信息应用于任意时间估计当地门通过当前房间后的路段。图4显示了较小房间和两个门的房间。agent表示通过字母“A”需在三个可用门之间进行选择。俩扇门属于小房间在较大房间的左上象限。第三道门是右边的目标门。
当算法的当前表明，评估超出小房间门的时间是相对较小的，基于距离的时间计算使用。但是在这种情况下，这将agent通过消防架，相信一旦出现右边的大排队就会消散。如果您在此配置中初始化模拟，则会有agent从队列后面剥离，然后排队等待通过这个小房间在“真正的”门后面再出现并排队。
Pathfinder通过存储出路线的数据来解决。如果路径通过agent的当前房间，则agent替换基于的更有用版本的路线段的时间估计agent对当前房间的了解。与初始门排队时间近似相同，通过比较他的时间将段距离移动到等待队列和保持所花费的时间较大值。
5、门选择案例研究
为了测试本地移动算法agent选择门的影响，来自VTTResearch Notes2562[3]的门选择案例研究被使用。在这研究中心，大学生在从会和地区搬到地方受到监控走廊和演讲厅。演讲厅有两个入口门连续沿着同一堵墙。将Pathfinder与进行的研究人员的观察结果进行了比较测试，“......人们在右边（相对于运动方向）上的启动网格选择[Door 2]。网格左侧或中心的人前排选择了一门：门1.在后排，有一种倾向使用门2.”图5显示了案例研究的平面图
图5中的平面图显示了Pathfinder的起始位置和移动路径该测试用例的仿真模型
模拟结果如图6所示
在图6 中，一号门表示为“”，门2表示为“底部”向左、向右和向后的人表示为“Right（red）”、“Left（蓝色）”和“背面（黑色）”。这些结果表明Pathfinder中的结果与观察结果。有Rinne，Tillander和Grnberg提供。此案例研究的成功代表了。对于Pathfinder来说，这是向前迈出的紧要一步。在以上情况下都会对一扇门产生明显差异。
