Nothing Special   »   [go: up one dir, main page]

CN101739509A - 一种大规模虚拟人群路径导航方法 - Google Patents

一种大规模虚拟人群路径导航方法 Download PDF

Info

Publication number
CN101739509A
CN101739509A CN200910260146A CN200910260146A CN101739509A CN 101739509 A CN101739509 A CN 101739509A CN 200910260146 A CN200910260146 A CN 200910260146A CN 200910260146 A CN200910260146 A CN 200910260146A CN 101739509 A CN101739509 A CN 101739509A
Authority
CN
China
Prior art keywords
potential energy
individual
grid
static
path navigation
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN200910260146A
Other languages
English (en)
Other versions
CN101739509B (zh
Inventor
卢光辉
罗伟平
陈雷霆
谭浩
蔡洪斌
何晓曦
曹跃
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
University of Electronic Science and Technology of China
Original Assignee
University of Electronic Science and Technology of China
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by University of Electronic Science and Technology of China filed Critical University of Electronic Science and Technology of China
Priority to CN2009102601469A priority Critical patent/CN101739509B/zh
Publication of CN101739509A publication Critical patent/CN101739509A/zh
Application granted granted Critical
Publication of CN101739509B publication Critical patent/CN101739509B/zh
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Landscapes

  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

本发明涉及了一种大规模虚拟人群路径导航方法,该方法包括:步骤1,处理静态场景物体,生成“静态局部势能”;步骤2,根据“静态局部势能”,针对每个“目标点”,生成对应的“全局势能场”;步骤3,处理“面”型动态物体,生成“动态局部势能”;步骤4,处理“点”型动态物体,更新“碰撞检测网格”;步骤5,对每个个体,计算得到各种势能作用力,求得最终导航力,并根据最终导航力更新个体状态。本发明的有益效果是:采用静态局部势能场生成全局导航势能,简化了全局势能的运算过程,能够快速对目标点进行全局最优路径导航;将动态物体分类考虑,能够快速进行动态物体间的碰撞避免;群体中的个体采用独立的感知和决策,允许表现多样的行为特征。

Description

一种大规模虚拟人群路径导航方法
技术领域
本发明涉及一种大规模虚拟群体在复杂环境下的路径导航方法,特别涉及一种高效率的多层次局部碰撞避免和全局最优路径寻找方法。
背景技术
群体动画在游戏领域、群体心理学、交通仿真及城市规划等方面有着广泛的应用。然而,实时的群体行为仿真一直是个具有挑战性的课题,这是因为群体行为模型中不仅包含单个角色的运动和环境约束,而且存在个体与个体之间的大量动态交互影响,更为重要的是群体行为必须及时反应动态变化的各种环境。另外,人群不同于动物群体,由于人类智能的复杂性,致使对人群的仿真不得不更多的考虑个体的行为多样性。这使得人群路径导航运算变得异常复杂。特别是在群体规模增大的时候,复杂度将呈非线性增长。
路径导航技术已经被广泛研究,大体上可以将其分为三类:路径图(roadmaps)、单元分解(cell decomposition)和势能场。路径图方法通过路径连接自由空间,表示成网络拓扑图,然后搜索该数据结构从而找到一条行走路径。这种方法一般基于特定的应用,难于对复杂环境进行灵活表示和扩展。单元分解法将自由空间分解成特定单元,从而使用单元间的邻接信息进行路径搜索。这种方法由于要针对每个起点进行复杂的运算,针对大规模人群的寻径难于保证实时效率。势能场方法将环境细分成规则网格,网格单元中存储势能信息。障碍物对其周围的单元产生排斥势能;同时目标点对单元产生吸引势能。只要对势能进行梯度计算,沿着梯度方向行进便能实现目标点导航。基于这种方式的碰撞避免能够灵活反应每个个体的特殊状况及当前环境。然而,对目标寻径存在局部极小值问题,不能保证到达最终目标点。“流群体”方法提出针对特定目标点的耗费势能场计算,将拥塞避免、碰撞避免统一到全局路径规划当中,有效解决了大规模群体的运动,而无需显式的碰撞避免运算。然而,由于要及时对势能场进行更新计算,当目标点个数和势能场表示精度增加时,无法满足实时要求。
发明内容
为了克服现有技术中路径导航技术存在的不足,本发明提供了一种大规模虚拟人群寻径导航方法,提高大规模虚拟群体在复杂环境下的路径导航效率,实现灵活平滑的导航路径。
本发明所采用的技术方案是:
步骤1,处理静态场景物体(如:地形、树木、房屋),生成“静态局部势能”。
步骤2,根据“静态局部势能”,针对每个“目标点”,生成对应的“全局势能场”。
步骤3,处理“面”型动态物体(如:汽车),生成“动态局部势能”。
步骤4,处理“点”型动态物体(如:人),更新“碰撞检测网格”。
步骤5,对每个个体,计算得到各种势能作用力,求得最终导航力,并根据最终导航力更新个体状态。
步骤3到步骤5将循环执行,直到用户要求停止路径导航。
其中,步骤1包括:
步骤1.1:使用地形计算出一个初始的静态势能场。
步骤1.2:使用其他静态对象的包围盒求解其势能影响,并叠加到原有静态势能场上。
进一步地,在步骤2中,将全局网格精度设为局部网格的1/3,构建路径拓扑图,并计算图中每条线段的权值。当完成对每条线段的权值计算后,就可以通过Dijkstra最短路径算法求出整个全局势能场。为了便于计算,在每个网格点上存储一个指向其最近邻接点的向量作为全局路径导航作用力
Figure G2009102601469D00021
而不是存储到达目标点A的单独路径,最终求得全局目标导航势能。各个网格顶点上的全局路径导航作用力
Figure G2009102601469D00022
构成二维全局势能场Gg
进一步地,在步骤3中,“面”型动态物体的势能作用力计算与静态物体非常类似,考虑运动物体速度因素的影响,其计算模型稍微进行了些调整。假设考虑速度在s秒内的影响,物体从A点,s秒后运动到B点,其在该过程中所占用的地理面积形成的几何图形记为AB,则该“面”型物体的动态局部势能计算模型即为几何图形AB的静态局部势能计算模型,求得的势能作用力为动态局部势能作用力
Figure G2009102601469D00023
具体计算过程如步骤2所示。
进一步地,在步骤4中,“点”型物体(个体)被放入“碰撞检测”网格,网格大小一般取个体的感知半径大小。个体根据其当前所在位置,将其信息索引放入相应格子中。每个个体直接从其附近的格子中获悉周围个体的信息,从而避免复杂的碰撞检测运算。当个体从一个格子走入另外一个格子后,个体从前一个格子中注销,然后注册到另外一个格子中。为了解决个体在网格边缘来回晃动带来的感知“抖动”,采用阀值区域控制的方法,只有超过某个模糊边界后才进行更新。更新步骤如下:
步骤4.1,取得个体之前所在格子,并求得格子中心位置P1
步骤4.2,令P2为个体当前位置,计算个体到该格子中心的距离S,根据S的数值考虑是否需要更新,否则个体从之前所在格子中注销,并根据个体当前位置P2求得新格子索引,并将信息注册到新格子中。
进一步地,步骤5包括:
步骤5.1,求解个体所受周围其他个体的避免作用力。
步骤5.2,求解个体所受静态局部势能作用力、动态局部势能作用力及全局路径导航作用力。
步骤5.3,求得最终导航力并更新个体状态。
进一步地,在步骤5.2中,设个体所在位置为x,则点x的静态局部势能作用力、动态局部势能作用力及全局路径导航作用力均采用双线性插值方式求得。
进一步地,步骤5.3包括:
步骤5.3.1,根据个体所在的位置计算最终导航力。
步骤5.3.2,更新个体状态。个体状态更新包括个体速度、个体朝向、个体位置更新。
与现有技术相比,本发明的有益效果是:对场景进行预处理,生成静态局部势能场,能够对任意复杂场景进行有效的碰撞避免,碰撞避免运算复杂度与场景复杂度无关;采用静态局部势能场生成全局导航势能,简化了全局势能的运算过程,能够快速对目标点进行全局最优路径导航;将动态物体分类考虑,能够快速进行动态物体间的碰撞避免,碰撞避免复杂度与动态物体数目趋于线性关系;群体中的个体采用独立的感知和决策,允许表现多样的行为特征。
附图说明
图1为本发明所述一种大规模虚拟人群路径导航方法的流程图;
图2为本发明所述求解地形势能的顶点及向量;
图3为本发明所述方形、圆形、线形及其复合体的势能作用方式
图4为本发明所述全局势能的构建过程;
图5为本发明所述动态物体的势能作用方式;
图6为本发明所述碰撞检测网格;
图7为本发明所述双线性插值方式。
具体实施方式
为使本发明的目的、技术方案和优点更加清楚,下面结合附图对本发明作进一步的详细描述。
该群体路径导航方法主要是通过将事物分类,分层构建各种势能场,最终通过求得各种导航向量并加权叠加求得最终路径方向。系统中场景首先离散为2维网格。在系统运行过程中,步骤3到步骤5将循环执行,直到用户要求停止路径导航。
参见图1所示的流程图给出了本方法的实现过程
在本实施例中,环境采用鬼火引擎(irrlicht)编辑器生成的场景,并转换成能识别的行为对象。同时,加入行人、车辆及各种障碍物等。
步骤1,处理静态场景物体(如:地形、树木、房屋),生成“静态局部势能”。
步骤1.1:使用地形计算出一个初始的静态势能场。计算方式如下:
如图2所示v1...v8为某网格顶点X周围的八个顶点。将该九个平面顶点垂直映射到地形上,求得3维空间向量
Figure G2009102601469D00041
V max → = Max ( V → 1 . . . V → 8 ) , Max函数表示求出与水平面夹角最大的向量。
V grd → = V max → * V max → . y | V max → | * V max → . x 2 + V max → . z 2 ;
则该点的地形势能作用力为: F → = - λ * V grd → , 其中λ为地形行走难度,例如λ=0.7。
步骤1.2使用其他静态对象的包围盒求解其势能影响,并叠加到原有静态势能场上。计算方式如下:
采用物体包围盒边沿及其平行扩展作为势能等高线,势能作用力方向垂直几何边缘,参见如图3。作用力大小采用类似库伦力的方式计算。引入两个参数——影响范围δ和影响力度λ。影响范围δ表示几何体对其边界以外周围δ单位以内的点存在影响;影响力度λ表示几何体对影响范围以内的点的影响程度比例参数。设以几何体外部某点P为终点且距离其边缘最短的距离向量为
Figure G2009102601469D00045
则该几何体对点P处的势能影响为:
情形1.2.1,当 &delta; < = | S &RightArrow; | 且P处于物体外部,则 F &RightArrow; = 0 ; 情形1.2.2,当 &delta; > | S &RightArrow; | 且P处于物体外部,则 F &RightArrow; = S &RightArrow; * ( &lambda; * ( &delta; - | S &RightArrow; | ) ) | S &RightArrow; | 2 ; 情形1.2.3,当P处于物体内部,则 F &RightArrow; = S &RightArrow; * &infin; .
所有处于几何体边缘或内部的点所受力大小为无穷大;所有处于物体作用范围δ外的点所受力大小为0。图3显示了方形、圆形、线形及其复合体的势能作用方式。
至此,各个网格顶点上的静态局部势能作用力
Figure G2009102601469D000412
构成二维静态局部势能场Gs
步骤2,根据“静态局部势能场”,针对每个“目标点”,生成对应的“全局势能场”。
如图4所示,a图是采用步骤1构建好的静态局部势能场Gs。现要求解对目标点A的全局导航势能。这里将全局网格精度设为局部网格的1/3,构建路径拓扑图(图4b),图中每条线段的权值采用如下公式计算:
Figure G2009102601469D000413
WXY是线段XY的权值,
Figure G2009102601469D000414
是在位置i的静态势能值,因此
Figure G2009102601469D000415
表示从点X到点Y的静态势能模值的和,Len(XY)表示从点X到点Y的距离,ω1、ω2分别代表局部势能和距离对全局势能的影响权值,例如ω1=ω2=0.5。
当完成对每条线段的权值计算后,就可以通过Dijkstra最短路径算法求出整个全局势
各个网格顶点上的全局路径导航作用力
Figure G2009102601469D00051
构成二维全局势能场Gg
步骤3,处理“面”型动态物体(如:汽车),生成“动态局部势能”。
“面”型动态物体的势能作用力计算与静态物体非常类似,考虑运动物体速度因素的影响,其计算模型稍微进行了些调整。如图5所示,假设考虑速度在s秒内的影响,物体从A点,s秒后运动到B点,其在该过程中所占用的地理面积形成的几何图形记为AB,则该“面”型物体的动态局部势能计算模型即为几何图形AB的静态局部势能计算模型,求得的势能作用力为动态局部势能作用力
Figure G2009102601469D00052
具体计算过程如步骤2所示。
记求解到的动态局部势能场为Gd,由各个网格顶点上的动态局部势能作用力
Figure G2009102601469D00053
构成。
步骤4,处理“点”型动态物体(如:人),更新“碰撞检测网格”。
“点”型物体(个体)被放入“碰撞检测”网格,网格大小一般取个体的感知半径大小。个体根据其当前所在位置,将其信息索引放入相应格子中。每个个体直接从其附近的格子中获悉周围个体的信息,从而避免复杂的碰撞检测运算。如图6所示,处于A点的个体从其所在格子及周围的九个格子中获得个体信息。当个体从一个格子走入另外一个格子后,个体从前一个格子中注销,然后注册到另外一个格子中。为了解决个体在网格边缘来回晃动带来的感知“抖动”,采用阀值区域控制的方法,只有超过某个模糊边界后才进行更新。令θ为区间[0,1]的模糊控制参数(例如θ=0.5);Sgrid为网格单元大小。更新步骤如下:
步骤4.1,取得个体之前所在格子,并求得格子中心位置P1
步骤4.2,令P2为个体当前位置,计算个体到该格子中心的距离S=|P1-P2|。当S<(1.0+θ)*Sgrid时,无需更新;否则个体从之前所在格子中注销,并根据个体当前位置P2求得新格子索引,并将信息注册到新格子中。
步骤5,对每个个体,计算得到各种势能作用力,求得最终导航力,并根据最终导航力更新个体状态。
步骤5.1,求解个体所受周围其他个体的避免作用力。
假设某个体的位置为Px;速度为朝向为在碰撞检测网格中,从该个体周围的九个格子中读取其他个体的信息。设该个体周围有n个个体,位置分别为P1...Pn,速度分别为
Figure G2009102601469D00056
朝向分别为
Figure G2009102601469D00057
则所受周围的第i(i=1...n)个个体避免作用力
Figure G2009102601469D00058
的叠加求解过程如步骤5.1.1到步骤5.1.3所示。fSigma为个体之间的作用范围,例如取fSigma=1.2,初始时避免作用力
Figure G2009102601469D00059
的值为0,步骤5.1.1到步骤5.1.3执行n次,
Figure G2009102601469D000510
的最终结果为该个体所受周围的n个个体避免作用力。
步骤5.1.1,求个体间距离向量: S &RightArrow; i = P x - P i . | S &RightArrow; i | > fSigma , 则对第i个个体的避免作用力计算结束;否则执行步骤5.1.2。
步骤5.1.2,令
Figure G2009102601469D000513
的垂直单位向量;若夹角小于90度且
Figure G2009102601469D000517
夹角小于45度,则 K &RightArrow; i = K &RightArrow; i * ( - 0.5 ) ;
步骤5.1.3,令 fTemp = ( fSigma - | S &RightArrow; i | ) / ( | S &RightArrow; i | * | S &RightArrow; i | ) , 叠加避免作用力: F &RightArrow; a + = ( S &RightArrow; i / | S &RightArrow; i | ) * ( fLambda * fTemp ) + K &RightArrow; i * fTemp , 其中fLambda表示个体间的避免作用强度,例如fLambda=1.0;
步骤5.2,求解个体所受静态局部势能作用力、动态局部势能作用力及全局路径导航作用力。
设个体所在位置为x,则点x的静态局部势能作用力、动态局部势能作用力及全局路径导航作用力均采用双线性插值方式求得。如图7所示,
Figure G2009102601469D00064
Figure G2009102601469D00065
分别代表x周围4个网格顶点上的某种势能作用力(静态局部势能作用力、动态局部势能作用力或者全局路径导航作用力),K为网格大小,m、n分别代表距格子边的距离,则点x的势能作用力为:
F &RightArrow; x = [ ( ( K - m ) F &RightArrow; 1 + F &RightArrow; 2 m 2 ) ( K - n ) + ( ( K - m ) F &RightArrow; 3 + m F &RightArrow; 4 ) n ] / K
步骤5.3,求得最终导航力并更新个体状态。
步骤5.3.1,个体所在的位置计算最终导航力
Figure G2009102601469D00067
其中α、β、γ和
Figure G2009102601469D00068
为混合因子,体现的是场景中各种作用力的影响程度,α是个体所受周围的其他个体避免作用力的影响程度因子、β是静态局部势能作用力影响程度因子、γ是全局路径导航作用力影响程度因子,
Figure G2009102601469D00069
是动态局部势能作用力影响程度因子,具体值根据个体当前所关心的不同侧重点进行适当调整。例如当个体在等待交通灯时,不需要全局路径导航,则可取α=0.5、β=0.5、γ=0.0和
Figure G2009102601469D000610
步骤5.3.2,更新个体状态。个体状态更新包括个体速度、个体朝向、个体位置更新。
个体速度
Figure G2009102601469D000611
更新: V &RightArrow; a = V &RightArrow; a + t * &eta; * F &RightArrow; all . 其中t为更新时间间隔,例如t=2,η为作用力迭代影响程度,例如η=0.05;
个体朝向
Figure G2009102601469D000613
更新: D &RightArrow; a = D &RightArrow; a + t * &omega; * V &RightArrow; a / | V &RightArrow; a | . 其中t为更新时间间隔,例如t=2,ω为转身速度,例如ω=0.1;
个体位置Pa更新: P a = P a + t * V &RightArrow; a . 其中t为更新时间间隔,例如t=2。
本发明不限于上述实施例,对于本领域技术人员来说,对本发明的上述实施例所做出的任何显而易见的改进或变更都不会超出仅以举例的方式示出的本发明的实施例和所附权利要求的保护范围。

Claims (12)

1.一种大规模虚拟人群路径导航方法,其特征在于:该方法包括的步骤如下:
步骤1,处理静态场景物体,生成“静态局部势能”;
步骤2,根据“静态局部势能”,针对每个“目标点”,生成对应的“全局势能场”;
步骤3,处理“面”型动态物体,生成“动态局部势能”;
步骤4,处理“点”型动态物体,更新“碰撞检测网格”;
步骤5,对每个个体,计算得到各种势能作用力,求得最终导航力,并根据最终导航力更新个体状态。
2.根据权利要求1所述的一种大规模虚拟人群路径导航方法,其特征在于:步骤1还包括:
步骤1.1:使用地形计算出一个初始的静态势能场;
步骤1.2:使用其他静态对象的包围盒求解其势能影响,并叠加到原有静态势能场上。
3.根据权利要求1所述的一种大规模虚拟人群路径导航方法,其特征在于:在步骤2中,将全局网格精度设为局部网格的1/3,由静态局部势能场构建路径拓扑图,并计算图中每条线段的权值。
4.根据权利要求3所述的一种大规模虚拟人群路径导航方法,其特征在于:在步骤2中当完成对每条线段的权值计算后,通过Dijkstra最短路径算法求出整个全局势能场。
5.根据权利要求1所述的一种大规模虚拟人群路径导航方法,其特征在于:在步骤4中,“点”型物体被放入“碰撞检测”网格,网格大小一般取个体的感知半径大小。
6.根据权利要求5所述的一种大规模虚拟人群路径导航方法,其特征在于:在步骤4中,个体根据其当前所在位置,将其信息索引放入相应格子中,每个个体直接从其附近的格子中获悉周围个体的信息,从而避免复杂的碰撞检测运算。
7.根据权利要求6所述的一种大规模虚拟人群路径导航方法,其特征在于:在步骤4中,当个体从一个格子走入另外一个格子后,个体从前一个格子中注销,然后注册到另外一个格子中。
8.根据权利要求7所述的一种大规模虚拟人群路径导航方法,其特征在于:在步骤4中,为了解决个体在网格边缘来回晃动带来的感知“抖动”,采用阀值区域控制的方法,只有超过某个模糊边界后才进行更新,更新步骤如下:
步骤4.1,取得个体之前所在格子,并求得格子中心位置;
步骤4.2,取得个体当前位置,计算个体到该格子中心的距离,根据个体当前位置求得新格子索引,并将信息注册到新格子中。
9.根据权利要求1所述的一种大规模虚拟人群路径导航方法其特征在于:步骤5包括以下步骤之一:
步骤5.1,求解个体所受周围其他个体的避免作用力;
步骤5.2,求解个体所受静态局部势能作用力、动态局部势能作用力及全局路径导航作用力;
步骤5.3,求得最终导航力并更新个体状态。
10.根据权利要求9所述的一种大规模虚拟人群路径导航方法,其特征在于:在步骤5.2中,设个体所在位置为x,则点x的静态局部势能作用力、动态局部势能作用力及全局路径导航作用力均采用双线性插值方式求得。
11.根据权利要求9所述的一种大规模虚拟人群路径导航方法,其特征在于:步骤5.3包括:
步骤5.3.1,根据个体所在的位置计算最终导航力;
步骤5.3.2,更新个体状态。个体状态更新包括个体速度、个体朝向、个体位置更新。
12.根据权利要求2-11中所述的任一种大规模虚拟人群路径导航方法,其特征在于:步骤3到步骤5将循环执行,直到用户要求停止路径导航。
CN2009102601469A 2009-12-25 2009-12-25 一种大规模虚拟人群路径导航方法 Expired - Fee Related CN101739509B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN2009102601469A CN101739509B (zh) 2009-12-25 2009-12-25 一种大规模虚拟人群路径导航方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN2009102601469A CN101739509B (zh) 2009-12-25 2009-12-25 一种大规模虚拟人群路径导航方法

Publications (2)

Publication Number Publication Date
CN101739509A true CN101739509A (zh) 2010-06-16
CN101739509B CN101739509B (zh) 2012-11-14

Family

ID=42462985

Family Applications (1)

Application Number Title Priority Date Filing Date
CN2009102601469A Expired - Fee Related CN101739509B (zh) 2009-12-25 2009-12-25 一种大规模虚拟人群路径导航方法

Country Status (1)

Country Link
CN (1) CN101739509B (zh)

Cited By (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101950432A (zh) * 2010-09-10 2011-01-19 北京水晶石数字科技有限公司 一种基于非均匀场的群体模拟方法
CN102750450A (zh) * 2012-06-21 2012-10-24 北京像素软件科技股份有限公司 网络游戏中的场景管理方法和装置
WO2013082779A1 (en) * 2011-12-08 2013-06-13 Thomson Licensing System and method for crowd simulation
CN103473114A (zh) * 2013-09-04 2013-12-25 李乐之 一种通过人流模拟测算建筑空间活跃度的方法
CN104299265A (zh) * 2014-10-22 2015-01-21 电子科技大学 一种流体环境影响下的群体行为控制技术
CN105825540A (zh) * 2016-02-01 2016-08-03 北京工业大学 一种人群路径编辑方法
US9460540B2 (en) 2010-11-26 2016-10-04 Thomson Licensing Method for animating characters, with collision avoidance based on tracing information
CN108714303A (zh) * 2018-05-16 2018-10-30 深圳市腾讯网络信息技术有限公司 碰撞检测方法,设备及计算机可读存储介质
CN108984781A (zh) * 2018-07-25 2018-12-11 北京理工大学 一种无人车区域探索的地图边缘检测规划方法及装置
CN110209191A (zh) * 2019-05-16 2019-09-06 湖州师范学院 一种群体队形快速变换的控制方法

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB0407336D0 (en) * 2004-03-31 2004-05-05 British Telecomm Pathfinding system
CN100410030C (zh) * 2006-07-07 2008-08-13 中国科学院力学研究所 一种基于虚拟场景的机器人避障路径规划方法

Cited By (16)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101950432B (zh) * 2010-09-10 2012-07-04 北京水晶石数字科技股份有限公司 一种基于非均匀场的群体模拟方法
CN101950432A (zh) * 2010-09-10 2011-01-19 北京水晶石数字科技有限公司 一种基于非均匀场的群体模拟方法
US9460540B2 (en) 2010-11-26 2016-10-04 Thomson Licensing Method for animating characters, with collision avoidance based on tracing information
WO2013082779A1 (en) * 2011-12-08 2013-06-13 Thomson Licensing System and method for crowd simulation
CN102750450A (zh) * 2012-06-21 2012-10-24 北京像素软件科技股份有限公司 网络游戏中的场景管理方法和装置
CN103473114A (zh) * 2013-09-04 2013-12-25 李乐之 一种通过人流模拟测算建筑空间活跃度的方法
CN103473114B (zh) * 2013-09-04 2016-08-17 李乐之 一种通过人流模拟测算建筑空间活跃度的方法
CN104299265A (zh) * 2014-10-22 2015-01-21 电子科技大学 一种流体环境影响下的群体行为控制技术
CN104299265B (zh) * 2014-10-22 2017-07-25 电子科技大学 一种流体环境影响下的群体行为控制方法
CN105825540A (zh) * 2016-02-01 2016-08-03 北京工业大学 一种人群路径编辑方法
CN105825540B (zh) * 2016-02-01 2019-06-04 北京工业大学 一种人群路径编辑方法
CN108714303A (zh) * 2018-05-16 2018-10-30 深圳市腾讯网络信息技术有限公司 碰撞检测方法,设备及计算机可读存储介质
CN108714303B (zh) * 2018-05-16 2023-04-18 深圳市腾讯网络信息技术有限公司 游戏中的碰撞检测方法,设备及计算机可读存储介质
CN108984781A (zh) * 2018-07-25 2018-12-11 北京理工大学 一种无人车区域探索的地图边缘检测规划方法及装置
CN108984781B (zh) * 2018-07-25 2020-11-10 北京理工大学 一种无人车区域探索的地图边缘检测规划方法及装置
CN110209191A (zh) * 2019-05-16 2019-09-06 湖州师范学院 一种群体队形快速变换的控制方法

Also Published As

Publication number Publication date
CN101739509B (zh) 2012-11-14

Similar Documents

Publication Publication Date Title
CN101739509B (zh) 一种大规模虚拟人群路径导航方法
CN111780777B (zh) 一种基于改进a*算法和深度强化学习的无人车路径规划方法
Abd Algfoor et al. A comprehensive study on pathfinding techniques for robotics and video games
Sun et al. AGV path planning based on improved Dijkstra algorithm
WO2018176596A1 (zh) 基于权重改进粒子群算法的无人自行车路径规划方法
Huang et al. A new dynamic path planning approach for unmanned aerial vehicles
CN110181508A (zh) 水下机器人三维航路规划方法及系统
Ben Amarat et al. 3D path planning, routing algorithms and routing protocols for unmanned air vehicles: a review
CN112539750B (zh) 一种智能运输车路径规划方法
CN106705975A (zh) 一种基于万有引力搜索的水面无人艇航路规划方法
CN112000126B (zh) 一种基于鲸鱼算法的多无人机协同搜索多动态目标方法
CN113391633A (zh) 一种面向城市环境的移动机器人融合路径规划方法
Yao Path Planning Algorithm of Indoor Mobile Robot Based on ROS System
CN114415652B (zh) 一种轮式机器人路径规划方法
Cui et al. Path planning of autonomous agricultural machineries in complex rural road
Bosse Self-adaptive traffic and logistics flow control using learning agents and ubiquitous sensors
Platanitis et al. Safe flyable and energy efficient UAV missions via biologically inspired methods
Hliwa et al. Optimal path planning of mobile robot using hybrid tabu search-firefly algorithm
Wolinski et al. Generalized WarpDriver: Unified Collision Avoidance for Multi-Robot Systems in Arbitrarily Complex Environments.
Motorin et al. A study of a trajectory synthesis method for a cyclic changeable target in an environment with periodic dynamics of properties
Guo et al. Research on the mobile robots intelligent path planning based on ant colony algorithm application in manufacturing logistics
Zhang et al. Research on the Prediction of the Operational Risk Field of Intelligent Vehicles Based on Dual Multiline LiDAR
Saadi et al. Unmanned Aerial Vehicles Path Planning Based on an Enhanced Whale Optimization Algorithm
Liao et al. USV path planning based on sparse visibility graph
Zhao et al. An improved ant colony algorithm based on Q-Learning for route planning of autonomous vehicle

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
C14 Grant of patent or utility model
GR01 Patent grant
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20121114

Termination date: 20171225

CF01 Termination of patent right due to non-payment of annual fee