Motion Trajectory Generating Algorithm Based on Markov Decision Processes for Crowd Animation
CSTR:
Author:
  • Article
  • | |
  • Metrics
  • |
  • Reference [17]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    Crowd animation has been researched and applied in many domains in recent years, such as robotics, movies, games, and so on. But the traditional technologies for creating crowd animation all need complex calculating for motion planning or collision avoidance, the computing efficience is low. This paper presents a new algorithm for generating motion trajectory based on Markov Decision Processes (MDPs) for crowd animation, it can generate all agents' collision-free motion trajectories without any collision detecting. At the same time, this paper presents a new improved value iteration algorithm for solving the state-values of MDPs. We test the performance of the new improved value iteration algorithm on grid maps, the experimental results show that the new alogithm outperforms the value iteration algorithm using Euclidean distance as heuristics and Dijkstra algorithm. The results of crowd animation simulating experiments using the motion trajectory generating algorithm in three-dimensional (3D) scenes show that the proposed motion generating algorithm can make all agents move to the goal position without any collision, meanwhile, agents' motion trajectories are different when we run the algorithm at different time and this effect makes the crowd animation much more alive.

    Reference
    [1] 黄东晋, 雷雪, 蒋晨凤, 等. 基于改进JPS算法的电影群体动画全局路径规划. 上海大学学报(自然科学版), 2018, 24(5):694-702
    [2] Molnár P, Starke J. Control of distributed autonomous robotic systems using principles of pattern formation in nature and pedestrian behavior. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2001, 31(3):433-435.[doi:10.1109/3477.931538
    [3] McPhail C, Powers WT, Tucker CW. Simulating individual and collective action in temporary gatherings. Social Science Computer Review, 1992, 10(1):1-28.[doi:10.1177/089443939201000101
    [4] Sewall J, Wilkie D, Merrell P, et al. Continuum traffic simulation. Computer Graphics Forum, 2010, 29(2):439-448.[doi:10.1111/j.1467-8659.2009.01613.x
    [5] Henry J, Shum HPH, Komura T. Interactive formation control in complex environments. IEEE Transactions on Visualization and Computer Graphics, 2014, 20(2):211-222.[doi:10.1109/TVCG.2013.116
    [6] Loscos C, Marchal D, Meyer A. Intuitive crowd behavior in dense urban environments using local laws. Proceedings of 2003 Theory and practice of computer graphics. Birmingham, UK. 2003. 122-129.
    [7] Ondřej J, Pettré J, Olivier AH, et al. A synthetic-vision based steering approach for crowd simulation. ACM Transactions on Graphics, 2010, 29(4):123
    [8] Weiss T, Litteneker A, Jiang CFF, et al. Position-based multi-agent dynamics for real-time crowd simulation. Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Los Angeles, CA, USA. 2017. Article No. 27.
    [9] Dutra TB, Marques R, Cavalcante-Neto JB, et al. Gradient-based steering for vision-based crowd simulation algorithms. Computer Graphics Forum, 2017, 36(2):337-348.[doi:10.1111/cgf.2017.36.issue-2
    [10] 张超, 魏三强, 陈伟. 一种基于萤火虫算法的群体动画行为控制仿真设计. 重庆理工大学学报(自然科学), 2017, 31(1):100-106
    [11] Lee J, Won J, Lee J. Crowd simulation by deep reinforcement learning. Proceedings of the 11th Annual International Conference on Motion, Interaction, and Games. Limassol, Cyprus, 2018
    [12] Ferguson D, Stentz A. Focussed processing of MDPs for path planning. Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence. Boca Raton, FL, USA, 2004:310-317
    [13] Pashenkova E, Rish I, Dechter R. Value iteration and policy iteration algorithms for Markov decision problem. Proceedings of 1996 Workshop on Structural Issues in Planning and Temporal Reasoning. 1996. 1-15.
    [14] 杨兴, 张亚. 基于改进栅格模型的移动机器人路径规划研究. 农家科技, 2016, (3):416
    [15] 王殿君. 基于改进A*算法的室内移动机器人路径规划. 清华大学学报(自然科学版), 2012, 52(8):1085-1089
    [16] Sutton RS, Barto AG. Reinforcement learning:An introduction. Cambridge, Massachusetts, London, England:MIT Press, 2018. 82-85.
    [17] Hansen EA, Zilberstein S. LAO:A heuristic search algorithm that finds solutions with loops. Artificial Intelligence, 2001, 129(1-2):35-62
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

刘俊君,杜艮魁.基于马尔可夫决策过程的群体动画运动轨迹生成.计算机系统应用,2019,28(7):101-108

Copy
Share
Article Metrics
  • Abstract:1542
  • PDF: 2336
  • HTML: 1328
  • Cited by: 0
History
  • Received:January 10,2019
  • Revised:February 03,2019
  • Online: July 05,2019
  • Published: July 15,2019
Article QR Code
You are the first990789Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-3
Address:4# South Fourth Street, Zhongguancun,Haidian, Beijing,Postal Code:100190
Phone:010-62661041 Fax: Email:csa (a) iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063