﻿ 基于马尔可夫决策过程的群体动画运动轨迹生成
 计算机系统应用  2019, Vol. 28 Issue (7): 101-108 PDF

Motion Trajectory Generating Algorithm Based on Markov Decision Processes for Crowd Animation
LIU Jun-Jun, DU Gen-Kui
College of Computer Science, Faculty of Information Technology, Bejing University of Technology, Bejing 100124, China
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.
Key words: crowd animation     Markov Decision Processes (MDPs)     motion trajectory     value iteration

1 基于马尔可夫决策过程的群体动画建模

1.1 马尔可夫决策过程

 ${v_\pi }(s) = {E_\pi }\left( {\sum\limits_{k = 0}^\infty {{\gamma ^k}{R_{t + k + 1}}|{S_t} = s} } \right)$ (1)

 ${v_\pi }(s) = \sum\limits_a {\pi (a|s)\sum\limits_{s',r} {p(s',r|s,a)} \left( {r + \gamma {v_\pi }(s')} \right)}$ (2)

${v_\pi }(s) \geqslant {v_{\pi '}}(s)$ 对所有的 $s \in S$ $\pi '$ 成立时, $\pi$ 为最优策略(后文用 ${v_*}(s)$ 表示最优策略对应的状态-值函数), 即智能体在每个状态都采取的最优动作, 如式(3)所示.

 $\pi (s) = argma{x_a}\sum\limits_{s',r} {p(s',r|s,a)\left( {r + \gamma {V_\pi }(s')} \right)}$ (3)

1.2 群体动画建模

$S$ : 环境中所有的栅格区域及障碍物信息, 即本文所采用的矩阵表示中矩阵的各元素坐标和值;

$A$ : 智能体的动作空间, 对于二维平面空间, $A = (0,1,2,\cdots,7)$ , 即8个移动方向对应的动作, 每个动作可使智能体在单位时间移动到对应方向的下一个栅格区域; 对于三维立体空间, $A = (0,1,2,3,\cdots,25)$ 共26个移动方向对应的动作, 其中与智能体在同一高度含8个移动方向对应的动作, 上下方各9个移动方向对应的动作;

$P$ : 本文假设智能体的运动不受除自身动作以外的因素影响, 即智能体在每个栅格区域 $s$ , 采取任何动作 $a$ 所能达到的栅格区域 $s'$ 是确定的, 即 $P(s,a,s') = 1.0$ , 同时我们规定当动作 $a$ 可使智能体进入障碍物所在区域或穿越环境边界时 $s'$ = $s$ , 即智能体保持在原位置, 当智能体在障碍物所在区域或目标状态区域时, 智能体将永久停留在此区域, 即障碍物所在区域和目标状态所在区域均为吸收状态. 基于此规则和假设, 在使用值迭代算法求解马尔夫决策过程的状态-值时可省略概率 $P$ ;

$R$ : 当动作 $a$ 使智能体在自由区域移动时, 我们将栅格之间的欧氏距离的相反数作为智能体移动所得到的回报; 当动作 $a$ 使智能体进入障碍物所在区域或穿越边界时, 智能体得到负无穷大的回报( $- Inf$ ); 当智能体原来所在状态为障碍物区域或目标状态所在区域时, 任何动作 $a$ 均使智能体收获值为0的回报;

$\gamma$ : 我们取折扣因子为1.0, 以使每个状态的状态-值的绝对值近似于此状态到目标状态的真实最短路径距离, 同时在值迭代算法求解中可省略此折扣因子, 以简化计算.

1.3 值迭代算法

1) 对每个栅格区域初始化状态-值为 $\scriptstyle v(s) = - Inf$ , 初始化目标状态区域的状态-值为 $\scriptstyle v(g) = 0$ , 初始化阈值 $\scriptstyle \theta > 0$ ;

2) $\scriptstyle while$ $\scriptstyle true$ :

3)　　 $\scriptstyle \Delta = 0$ ;

4)　　 $\scriptstyle for$ $\scriptstyle s$ $\scriptstyle in$ $\scriptstyle S$ :

5)　　　 $\scriptstyle v = v(s)$ ;

6)　　　 $\scriptstyle v(s) = \max({R(s,a,s')} + v(s'))$ ;// $\scriptstyle s'$ $\scriptstyle s$ 可到达的下一状态

7)　　　 $\scriptstyle \Delta = \max (\Delta ,|v - v(s)|)$ ;

8)　　 $\scriptstyle end$ $\scriptstyle for$ ;

9)　　 $\scriptstyle if$ $\scriptstyle \Delta < \theta$ :

10)　　　 $\scriptstyle break$ ;

11)　 $\scriptstyle end$ $\scriptstyle if$ ;

12) $\scriptstyle end$ $\scriptstyle while$ ;

13)输出 $\scriptstyle v(s)$ ;

2 改进的值迭代算法和运动轨迹生成算法

2.1 改进的值迭代算法

1) 初始化所有的状态-值 $\scriptstyle v(s) = - Inf$ , 初始化优先列 $\scriptstyle pq$ (按从大到小顺序), 初始化集合 $\scriptstyle block$ 为空集, 初始化目标状态的状态-值 $\scriptstyle v(g) = 0$ , $\scriptstyle pq.put((v(g),g))$ , $\scriptstyle block.add(g)$ ;

2) $\scriptstyle while$ $\scriptstyle not$ $\scriptstyle pq.empty()$ :

3) 　　 $\scriptstyle s = pq.get()[1]$ ;

4) 　　 $\scriptstyle ns = get\_neighbors(s)$ ;//获取状态 $\scriptstyle s$ 可到达的邻近区域

5) 　　 $\scriptstyle for$ $\scriptstyle s'$ $\scriptstyle in$ $\scriptstyle ns$ :

6) 　　　 $\scriptstyle if$ $\scriptstyle not$ $\scriptstyle s'$ $\scriptstyle in$ $\scriptstyle block$ :

7) 　　　　 $\scriptstyle v(s') = v(s) + R(s,a,s')$ ;// $\scriptstyle R$ 为负数

8) 　　　　 $\scriptstyle pq.put((v(s'),s'))$ ;

9) 　　　　 $\scriptstyle block.add(s')$ ;

10) 　　 $\scriptstyle end$ $\scriptstyle if$ ;

11) 　 $\scriptstyle end$ $\scriptstyle for$ ;

12) $\scriptstyle end$ $\scriptstyle while$ ;

13) 输出 $\scriptstyle v(s)$ ;

2.2 运动轨迹生成算法

 $P(k) = \frac{{e^{\frac{v'(k)}{\tau}} }}{{\sum\nolimits_{i = 0}^K {e^{\frac{v'(i)}{\tau}} } }}$ (4)

$v'(k) = v(k) - max(v(0),v(1),\cdots,v(K))$ , $v'(i) = v(i) -$ $max(v(0),v(1),\cdots,v(K))$ 以消除状态-值 $v(s)$ 之间的数量级差异, 同时取 $\tau$ 为常数1, 方便计算同时不影响效果.

1) 随机初始化各智能体的初始状态(均在自由区域), 为每个智能体 $\scriptstyle agent$ 设置一个数组用于存储智能体的轨迹 $\scriptstyle L[agent]$ , 将各智能体初始状态存入对应的 $\scriptstyle L[agent]$ 中, 初始化矩阵block(大小同环境状态矩阵grid), 在block中将各智能体初始状态对应位置的元素置为1, 其余位置的元素置为0,初始化轨迹长度计数 $\scriptstyle length = 0$ ;

2) $\scriptstyle while$ $\scriptstyle length < maxLength$ :

3) 　根据算法1中输出的 $\scriptstyle v(s)$ 对各智能体排序, 获取排序结果 $\scriptstyle Agents$ ;

4) 　 $\scriptstyle for$ $\scriptstyle agent$ $\scriptstyle in$ $\scriptstyle Agents$ :

5) 　　在block中将L[agent]的尾部状态对应位置的元素置为0;

6) 　　根据 $\scriptstyle L[agent]$ 的尾部状态及矩阵 $\scriptstyle block$ 获取 $\scriptstyle agent$ 的可到达区域 $\scriptstyle neighbors0$ (满足 $\scriptstyle v(s') > v(s)$ )和 $\scriptstyle neighbors1$ (满足 $\scriptstyle v(s') \leqslant v(s)$ );

7) 　　当 $\scriptstyle neighbors0$ 不为空时, 按式(4)在 $\scriptstyle neighbors0$ 中选取下一状态, 否则在 $\scriptstyle neighbors1$ 中按式(4)选取下一状态, 将下一状态存入 $\scriptstyle L[agent]$ 尾部;

8) 　　在block中将选取的下一状态对应位置的元素置为1;

9) 　 $\scriptstyle end$ $\scriptstyle for$ ;

10) 　检测是否有障碍物位置发生变化, 若有则更新环境状态矩阵grid, 重新执行算法1获取最新的状态-值 $\scriptstyle v(s)$ ;

11) 　 $\scriptstyle length = length + 1$ ;

12) $\scriptstyle end$ $\scriptstyle while$ ;

13) 输出各智能体的运动轨迹 $\scriptstyle L[agent]$ ;

3 实验分析

3.1 改进的值迭代算法实验及分析

1) 大小: 10×10, 目标: (9, 5), 障碍物区域: (5, 3)到(5, 7)所在直线区域;

2) 大小: 20×20, 目标: (19, 10), 障碍物区域: (10, 5)到(10, 14)所在直线区域;

3) 大小: 30×30, 目标: (29, 15), 障碍物区域: (15, 10)到(15, 19)所在直线区域;

4) 大小: 40×40, 目标: (39, 20), 障碍物区域: (20, 15)到(20, 24)所在直线区域;

5) 大小: 50×50, 目标: (49, 25), 障碍物区域: (25, 20)到(25, 29)所在直线区域.

1) 大小: 10×10×10, 目标: (9, 5, 5), 障碍物区域: (5, 3, 3)到(5, 7, 7)所在平面区域;

2) 大小: 20×20×20, 目标: (19, 10, 10), 障碍物区域: (10, 5, 5)到(10, 14, 14)所在平面区域;

3) 大小: 30×20×30, 目标: (29, 10, 15), 障碍物区域: (15, 5, 10)到(15, 14, 19)所在平面区域;

4) 大小: 40×20×40, 目标: (39, 10, 20), 障碍物区域: (20, 5, 15)到(20, 14, 24)所在平面区域;

5) 大小: 50×20×50, 目标: (49, 10, 25), 障碍物区域: (25, 5, 20)到(25, 14, 29)所在平面区域.

3.2 群体动画仿真实验及分析

 图 1 2D群体动画仿真结果部分片段截图(机器人模型下载网址https://www.3d66.com/reshtml/4768/476880.html)

4 结论与展望

 图 2 3D群体动画仿真结果部分片段截图(无人机模型下载网址https://www.3d66.com/reshtml/5450/545028.html)

 [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.