题目：大规模路径规划与群体运动控制的研究与实现

大规模路径规划与群体运动控制涉及GIS、计算机图形学、计算机网络及人工智能等多个领域的研究内容，在大型虚拟仿真及三维游戏等娱乐产业中有着广泛的应用需求，已成为一个研究热点与难点。其中，在基于真实地理信息数据的分布式军事演练仿真领域，虚拟实体的路径规划范围往往多达几千平方公里，虚拟实体在运动过程中需进行实时的地形匹配与碰撞检测，虚拟作战群体在不同的任务执行过程中需要保持相应的队形，并且需要根据即时作战环境信息（人工障碍、化学沾染区等信息）进行自主规避；这类应用具有数据量大、实时性高、群体自主运动灵活多变等特性，因此，针对大规模路径规划与群体运动控制方法展开研究，具有重要的实用意义，本文的研究重点主要围绕上述内容展开。本文采用分层次的策略来实现大规模路径规划。首先，对大规模地表属性数据进行分块预处理，并对预处理的文件进行高效的组织管理。其中，预处理数据主要包括分块地表属性文件、分块地图代价文件、分块路径规划文件及粒度较粗的高层地图代价文件。预处理分块文件通过自动生成配置文件的形式进行组织管理，可实现文件的高效映射访问。在数据预处理的基础上，通过采用基于高层次地图代价文件进行粗粒度路径规划与使用分块路径规划文件的方式，实现了大规模数据环境下的路径规划。对于数据文件的访问，在基于运动趋向进行数据预测的基础上，采用LRU的页面置换算法进行多线程异步调度， 保证了数据调度的效率，满足了系统实时平稳运行的需要。本文在群体的运动控制方面主要研究了虚拟群体行进过程中队形的保持及其碰撞检测和规避策略。群体队形的建立编队规则立足于真实的军事需求，本文主要研究并实现了一字、前三角、后三角、蛇形机动、W型展开、疏开攻击以及各类后勤保障分队的开设等多种队形。队形变换主要是指虚拟群体在任务执行的不同阶段自主的从当前队形变换成另一种队形，本文主要通过建立数学模型，采用逼近的方法实现队形变换。对于碰撞感知和碰撞响应，本文主要采用基于包围盒的刚体碰撞检测算法来实现，并采用分割子区域的方法提高了碰撞检测的效率；我们对当前物体所在子区域为中心的九个子区域中的所感知到的潜在碰撞实体采用不同的规避策略，同一子区域采用等待避碰，周围的子区域采用绕行避碰。本文方法能够较好的实现大规模地形的动态路径规划和虚拟群体的自主运动控制，虚拟实体能够按照军事模型要求的进行群体运动，并且在运动中能够及时变换队形，通过障碍物。系统的实际应用表明，本文方法的使用取得了良好的效果。