High-quality trajectory planning for heterogeneous individuals

Abstract

Based on trajectory planning with maximum velocity and acceleration constraints, a novel high-quality trajectory planning method was proposed for heterogeneous individuals in crowd simulation. The proposed method ensured that the individual’s path was smooth and its velocity was continuous. Based on the physiological constraints of humans with maximum velocity and acceleration, time-optimal trajectory and feasible region were derived by solving kinodynamic planning problem. Subsequently, a high-quality trajectory planning algorithm was designed to compute the trajectory with appropriate variation of velocity. The simulation results demonstrate that the proposed trajectory planning method has more authenticities and can generate high-quality trajectories for virtual humans in crowd simulation.

Keywords

heterogeneous crowd / trajectory planning / bounded velocity and acceleration / visual variety / authenticity

References

[1] Symmetry-Basel, 2017, 9(10

[2] LeP T, HoangH V, SangH A, SeungG L, DongH K, TaeC C. Univector field method-based multi-agent navigation for pursuit problem in obstacle environments [J]. Journal of Central South University, 2017, 244): 1002-1012

[3] XuM-l, LiC-c, LvP, ChenW, DineshM, DengZ-g, ZhouBing. Crowd simulation model integrating physiology-psychology-physics factors [J]. Computing Research Repository (CoRR), 2018, 18(1): 1-14

[4] BellomoN, ClarkeD, GibelliL, TownsendP, VreugdenhilB J. Human behaviours in evacuation crowd dynamics: From modelling to big data toward crisis management [J]. Physics of Life Reviews, 2016, 18: 1-21

[5] ChosetH M, HutchinsonS, LynchK M, KantorG, BurgardW, KavrakiL E, ThrunSPrinciples of robot motion: Theory, algorithms, and implementations [M], 2005

[6] NarangS, BestA, FengA, KangS H, ManochaD. Motion recognition of self and others on realistic 3D avatars [J]. Computer Animation and Virtual Worlds, 2017, 28(34): e1762

[7] KapadiaM, PelechanoN, AllbeckJVirtual crowds: Steps toward behavioral realism [M], 2015

[8] LiM, LiangJ-h, LiS-lei. Flocking behavior with multiple leaders and global trajectory [J]. Journal of Central South University, 2014, 2162324-2333

[9] WallarA, PlakuE. Path planning for swarms by combining probabilistic roadmaps and potential fields [C]. 14th Annual Conference on Towards Autonomous Robotic Systems, 2013417428

[10] LiuQian. The effect of dedicated exit on the evacuation of heterogeneous pedestrians [J]. Physica A-Statistical Mechanics and Its Applications, 2018, 506: 305-323

[11] CharalambousP, ChrysanthouY. The PAG Crowd: A graph based approach for efficient data-driven crowd simulation [C]. Computer Graphics Forum, 2014, 33(8): 95-108

[12] KremyzasA, JaklinN, GeraertsR. Towards social behavior in virtual-agent navigation [J]. Science China Information Sciences, 2016, 59(11): 1-17

[13] BestA, NarangS, CurtisS, ManochaD. Densesense: Interactive crowd simulation using density-dependent filters [C]. Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 201497102

[14] MarceloK, MubbasirK. Geometric and discrete path planning for interactive virtual worlds [C]. ACM SIGGRAPH 2016: the 43rd International Conference and Exhibition on Computer Graphics & Interactive Techniques, 2016

[15] NormanJ, AngelosK, RolandG. Adding sociality to virtual pedestrian groups [C]. Proceedings of the 21st ACM Symposium on Virtual Reality Software and Technology, 2015163172

[16] YanZ-p, LiuY-b, YuC-b, ZhouJ-jia. Leader-following coordination of multiple UUVs formation under two independent topologies and time-varying delays [J]. Journal of Central South University, 2017, 24(2): 382-393

[17] MarbleJ D, BekrisK E. Asymptotically near-optimal is good enough for motion planning [J]. Robotics Research, 2017419436

[18] RahmaniV, PelechanoN. Improvements to hierarchical pathfinding for navigation meshes [C]. Proceedings of the Tenth International Conference on Motion in Games, 201728

[19] NinomiyaK, KapadiaM, ShoulsonA, GarciaF, BadlerN. Planning approaches to constraint-aware navigation in dynamic environments [J]. Computer Animation and Virtual Worlds, 2015, 26(2): 119-139

[20] AgarwalP K, FoxK, SalzmanO. An efficient algorithm for computing high-quality paths amid polygonal obstacles [J]. ACM Transactions on Algorithms (TALG), 2018, 14(4): 46-67

[21] LinoC, ChristieM. Intuitive and efficient camera control with the toric space [J]. ACM Transactions on Graphics, 2015, 34(4): 1-12

[22] LiB, WangK-x, ShaoZ-jiang. Time-optimal maneuver planning in automatic parallel parking using a simultaneous dynamic optimization approach [J]. IEEE Transactions on Intelligent Transportation Systems, 2016, 17(11): 3263-3274

[23] LiB, LiuH, XiaoD, YuG-z, ZhangY-min. Centralized and optimal motion planning for large-scale AGV systems: A generic approach [J]. Advances in Engineering Software, 2017, 106: 33-46

[24] BroganD C, JohnsonN L. Realistic human walking paths [C]. Proceedings of the 16th International Conference on IEEE Computer Animation and Social Agents, 200394101

[25] TohfehF, FakharianA. Polynomial based optimal trajectory planning and obstacle avoidance for an omni-directional robot [C]. Proceedings of the 5th Conference on Artificial Intelligence and Robotics, 20155359

[26] ButlerS D, MollM, KavrakiL E. A general algorithm for time-optimal trajectory generation subject to minimum and maximum constraints [C]. Proceedings of the Workshop on the Algorithmic Foundations of Robotics, 2016116

[27] ButlerS DGeneral algorithms for the time-optimal trajectory generation problem [D], 2017, Houston, USA, Rice University

[28] ChenY-x, PengH, GrizzleJ. Obstacle avoidance for low-speed autonomous vehicles with barrier function [J]. IEEE Transactions on Control Systems Technology, 2018, 26(1): 194-206