基于马尔可夫决策过程的群体动画运动轨迹生成
|
摘要
近些年来,群体动画在机器人学、电影、游戏等领域得到了广泛的研究和应用,但传统的群体动画技术均涉及复杂的运动规划或碰撞避免操作,计算效率较低.本文提出了一种基于马尔可夫决策过程(MDPs)的群体动画运动轨迹生成算法,该算法无需碰撞检测即可生成各智能体的无碰撞运动轨迹.同时本文还提出了一种改进的值迭代算法用于求解马尔可夫决策过程的状态-值,利用该算法在栅格环境中进行实验,结果表明该算法的计算效率明显高于使用欧氏距离作为启发式的值迭代算法和Dijkstra算法.利用本文提出的运动轨迹生成算法在三维(3D)动画场景中进行群体动画仿真实验,结果表明该算法可实现群体无碰撞地朝向目标运动,并具有多样性.
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' collisionfree 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(3 D) 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.
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' collisionfree 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(3 D) 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.
引文
1黄东晋,雷雪,蒋晨凤,等.基于改进JPS算法的电影群体动画全局路径规划.上海大学学报(自然科学版),2018,24(5):694-702.
2Molná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]
3McPhail 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/0894439 39201000101]
4Sewall 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]
5Henry 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]
6Loscos 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.
7Ond?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.
8Weiss 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.
9Dutra TB,Marques R,Cavalcante-Neto JB,et al.Gradientbased 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.
11Lee 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.
12Ferguson 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.
13Pashenkova 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.
16Sutton RS,Barto AG.Reinforcement learning:An introduction.Cambridge,Massachusetts,London,England:MIT Press,2018.82-85.
17Hansen EA,Zilberstein S.LAO:A heuristic search algorithm that finds solutions with loops.Artificial Intelligence,2001,129(1-2):35-62.
2Molná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]
3McPhail 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/0894439 39201000101]
4Sewall 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]
5Henry 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]
6Loscos 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.
7Ond?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.
8Weiss 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.
9Dutra TB,Marques R,Cavalcante-Neto JB,et al.Gradientbased 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.
11Lee 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.
12Ferguson 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.
13Pashenkova 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.
16Sutton RS,Barto AG.Reinforcement learning:An introduction.Cambridge,Massachusetts,London,England:MIT Press,2018.82-85.
17Hansen EA,Zilberstein S.LAO:A heuristic search algorithm that finds solutions with loops.Artificial Intelligence,2001,129(1-2):35-62.