时间：2023-05-28 09:24:44
开篇：写作不仅是一种记录，更是一种创造，它让我们能够捕捉那些稍纵即逝的灵感，将它们永久地定格在纸上。下面是小编精心整理的12篇路径规划典型算法，希望这些内容能成为您创作过程中的良师益友，陪伴您不断探索和进步。
【关键词】智能交通系统 蚁群算法 信息素 最优路径 组合优化
交通运输的现代化使人们享受便利的同时，也面临道路拥堵、事故频发等问}。近年来，智能交通系统越来越受到人们的重视，它涉及到交通领域诸多方面，如最优路径选择、车辆路径规划、动态车辆调度、交通流量控制等。其中一个重要的应用是一类典型的以数学理论为基础的组合优化问题，而蚁群算法具有内在的搜索机制及正反馈性，适合求解一系列的组合优化问题。
1 蚁群算法描述
蚁群算法源于20世纪90年代初意大利学者M.Dorigo首次提出的蚂蚁系统。它是基于种群的启发式放生进化系统，是通过对蚁群觅食过程中其行为的研究而得出的一种算法。主要思路是蚂蚁借助自己路径寻优的能力可以找到巢穴与食物之间最短的途径。在寻找过程中主要依靠的是每个蚂蚁在行进过程中留下的挥发性分泌物――信息素，依靠信息素，蚁群的蚂蚁之间可以相互合作，相互配合，因此形成的正反馈可以使每只蚂蚁找到所有路径中最短的路径。
蚂蚁a从节点j移动至k的转移概率可以从式（1）中获取：
（1）
（2）
（3）
2 蚁群算法的应用优势
蚁群算法，又名蚂蚁算法，蚂蚁可以利用信息素的浓度大小从而寻找到觅食的最优路径。该算法的优点可以总结为：
2.1 并行分布式计算
每个蚂蚁都是独立的个体，在觅食过程中属于多起点同时启动，互不影响，从根本上分析该过程属于分布式的多Agent系统，整体蚁群最终任务的顺利完成不会由于某些个体的缺陷而受到影响。该算法具有真实可用性，并且可用于解决对单目标的优化或者对多目标的优化等重要问题。此外，蚂蚁算法还可进行并行计算。
2.2 鲁棒性
蚁群算法的最终结果与蚂蚁最初选择的路径无太大关系，在利用人工仿真蚂蚁进行问题求解过程中，不需要对其进行人工的修整。把问题简单化，可以和其他算法相互结合求解最优问题。
2.3 自组织性
蚁群算法组织指令的来源为系统内部，它不受外界环境的干扰，因此该算法具有自组织性。
2.4 正反馈性
蚂蚁对于最优路径的选择主要依靠路径上信息素浓度的多少，信息素的堆积是正反馈的过程，路径上信息素的含量越多则该路径被选择的几率就会越大，正反馈的作用是使整体能够更快的寻找到最优途径，正反馈在蚁群算法中处于重要地位。
2.5 易于实现
它是一种启发示算法，其计算复杂性为，整个算法的空间复杂度是：。
3 蚁群算法在智能交通领域的应用空间
蚁群算法在解决组合优化问题方面有着明显的优势，从而在智能交通领域也有着广泛的应用空间。
3.1 车辆路径导航
根据行车人员的需要，根据对实时路况信息的统计，系统可以智能的为其推荐最优路径，节省时间，节省资源。
3.2 动态车辆调度
当客户需要调度中心为其进行车辆服务时，调度中心要考虑到客户的情况，要考虑到效率的问题，要考虑到行车路线、行驶时间等问题。蚁群算法便可迅速得到合理的解决方案，使客户和调度中心均可受益。
3.3 车辆路径规划
面对多个客户不同的要求时，配送中心要根据实际情况进行车辆的配送，通过蚁群算法系统获取整体的最优路线，根据路线规划，及时进行车辆出发以满足客户要求，同时充分利用了道路资源和车辆资源。
3.4 公共交通智能化调度
利用先进的技术手段、大型数据库技术等动态地获取实时交通信息，实现对车辆的实时监控和调度，最终建立集运营指挥调度、综合业务通信及信息服务等为一体的智能化管理系统。
3.5 交通流量控制
通过蚁群算法简化复杂的道路交通网络，尽量使交通流量在各个道路上分布均匀，避免因流量过大而造成车辆的阻塞。及时了解交通流量情况，缓解了交通拥挤，降低了交通事故的发生率。
参考文献
[1]M.Dorigo，V.Maniezzo，A.Colom.Ant System：Optimization by a colony of cooperating agents.IEEE trans on SMC，1996，26（01）：28-41
[2]Eric BONABEAUB， Marco DORIGO，Guy THERAULAZ.AWARM intelligence： from natural to artificial systems[M].New York：Oxford University Press，1999
[3]杨海.蚁群算法及其在智能交通中的应用[D].济南：山东师范大学，2008：14-18
作者简介
白晓（1979-），女。工学硕士学位。现供职于厦门软件职业技术学院软件工程系。主要研究方向为软件工程、智能算法。
王娅（1983-），女。工学硕士学位。现供职于厦门软件职业技术学院软件工程系。主要研究方向为网络工程，软件设计。
摘 要：在查阅大量文献的基础上对多机器人路径规划的主要研究内容和研究现状进行了分析和总结，讨论了多机器人路径规划方法的评判标准，并阐述了研究遇到的瓶颈问题，展望了多机器人路径规划方法的发展趋势。
关键词：多机器人；路径规划；强化学习；评判准则
Abstract:This paper analyzed and concluded the main method and current research of the path planning research for multirobot.Then discussed the criterion of path planning research for multirobot based large of literature.Meanwhile，it expounded the bottleneck of the path planning research for multirobot，forecasted the future development of multirobot path planning.
Key words:multirobot；path planning;reinforcement learning;evaluating criteria
近年来，分布式人工智能(DAI)成为人工智能研究的一个重要分支。DAI研究大致可以分为DPS（distributed problem solving）和MAS（multiagent system）两个方面。一些从事机器人学的研究人员受多智能体系统研究的启发，将智能体概念应用于多机器人系统的研究中，将单个机器人视做一个能独立执行特定任务的智能体，并把这种多机器人系统称为多智能体机器人系统（MARS）。因此，本文中多机器人系统等同于多智能体机器人系统。目前，多机器人系统已经成为学术界研究的热点，而路径规划研究又是其核心部分。
机器人路径规划问题可以建模为一个带约束的优化问题，其包括地理环境信息建模、路径规划、定位和避障等任务，它是移动机器人导航与控制的基础。单个移动机器人路径规划研究一直是机器人研究的重点，且已经有许多成果[1~3]，例如在静态环境中常见的有连接图法、可视图法、切线图法、Voronoi图法、自由空间法、栅格法、拓扑法、链接图法、DempsterShafer证据理论建图等；动态环境中常见的有粒子群算法、免疫算法、遗传算法、神经网络、蚁群算法、模拟退火算法、人工势场法等。然而，多机器人路径规划研究比单个机器人路径规划要复杂得多，必须考虑多机器人系统中机器人之间的避碰机制、机器人之间的相互协作机制、通信机制等问题。
1 多机器人路径规划方法
单个机器人的路径规划是找出从起始点至终点的一条最短无碰路径。多个机器人的路径规划侧重考虑整个系统的最优路径，如系统的总耗时间最少路径或是系统总路径最短等。从目前国内外的研究来看，在规划多机器人路径时，更多考虑的是多机器人之间的协调和合作式的路径规划。
目前国内外多机器人路径规划研究方法分为传统方法、智能优化方法和其他方法三大类。其中传统方法主要有基于图论的方法（如可视图法、自由空间法、栅格法、Voronoi图法以及人工势场方法等）；智能优化方法主要有遗传算法、蚁群算法、免疫算法、神经网络、强化学习等；其他方法主要有动态规划、最优控制算法、模糊控制等。它们中的大部分都是从单个机器人路径规划方法扩展而来的。
1）传统方法 多机器人路径规划传统方法的特点主要体现在基于图论的基础上。方法一般都是先将环境构建成一个图，然后再从图中寻找最优的路径。其优点是比较简单，比较容易实现；缺点是得到的路径有可能不是最优路径，而是次优路径。薄喜柱等人[4]提出的一种新路径规划方法的基本思想就是基于栅格类的环境表示和障碍地图的。而人工势场方法的基本思想是将移动机器人在环境中的运动视为一种虚拟人工受力场中的运动。障碍物对移动机器人产生斥力，目标点产生引力，引力和斥力周围由一定的算法产生相应的势，机器人在势场中受到抽象力作用，抽象力使得机器人绕过障碍物。其优点是适合未知环境下的规划，不会出现维数爆炸问题；但是人工势场法也容易陷入局部最小，并且存在丢失解的部分有用信息的可能。顾国昌等人[5]提出了引用总体势减小的动态调度技术的多机器人路径规划，较好地解决了这个问题。
2）智能优化方法 多机器人路径规划的智能优化方（算）法是随着近年来智能计算发展而产生的一些新方法。其相对于传统方法更加智能化，且日益成为国内外研究的重点。
遗传算法是近年来计算智能研究的热点，作为一种基于群体进化的概率优化方法，适用于处理传统搜索算法难以解决的复杂和非线性问题，如多机器的路径规划问题。在路径规划中，其基本思想是先用链接图法把环境地图构建成一个路径节点链接网，将路径个体表达为路径中一系列中途节点，并转换为二进制串；然后进行遗传操作（如选择、交叉、复制、变异），经过N次进化，输出当前的最优个体即机器人的最优路径。遗传算法的缺点是运算速度不快，进化众多的规划要占据很大的存储空间和运算时间；优点是有效避免了局部极小值问题，且计算量较小。
孙树栋等人[6，7]在这方面较早地展开了研究，提出的基于集中协调思想的一种混合遗传算法来规划多机器人路径方法较好地解决了避障问题。但不足的是该方法必须建立环境地图，在环境未知情况下的规划没有得到很好的解决；且规划只能保证找到一个比较满意的解，在求解全局最优解时仍有局限。
文献[8]中提出的一种基于定长十进编码方法有效降低了遗传算法的编码难度，克服了已有的变长编码机制及定长二进制编码机制需特殊遗传操作算子和特殊解码的缺陷， 使得算法更加简单有效。
智能计算的另一种常见的方法——蚁群算法属于随机搜索的仿生算法。其基本思想是模拟蚂蚁群体的觅食运动过程来实现寻优，通过蚂蚁群体中各个体之间的相互作用，分布、并行地解决组合优化问题。该算法同样比较适合解决多机器人的路径规划问题。
朱庆保[9]提出了在全局未知环境下多机器人运动蚂蚁导航算法。该方法将全局目标点映射到机器人视野域边界附近作为局部导航子目标，再由两组蚂蚁相互协作完成机器人视野域内局部最优路径的搜索，然后在此基础上进行与其他机器人的碰撞预测与避碰规划。因此，机器人的前进路径不断被动态修改，从而在每条局部优化路径引导下，使机器人沿一条全局优化的路径到达目标点。但其不足是在动态不确定的环境中路径规划时间开销剧增，而且机器人缺乏必要的学习，以至于整个机器人系统路径难以是最优路径。
强化学习[10，11] (又称再激励学习)是一种重要的机器学习方法。它是一种智能体从环境状态到行为映射的学习，使得行为从环境中获得积累奖赏值最大。其原理如图1所示。
强化学习算法一般包含了两个步骤：a）从当前学习循环的值函数确定新的行为策略；b）在新的行为策略指导下，通过所获得的瞬时奖惩值对该策略进行评估。学习循环过程如下所示，直到值函数和策略收敛:
v0π1v1π2…v*π*v*
目前比较常见的强化学习方法有：Monte Carlo方法、动态规划方法、TD（时间差分）方法。其中TD算法包含Sarsa算法、Q学习算法以及Dyna-Q算法等。其Q值函数迭代公式分别为
TD（0）策略： V(si)V(si)+α[γi+1+γV(si+1)-V(si)]
Sarsa算法： Q(st，at)Q(st，at)+α[γt+1+γQ(st+1，at.+1)-Q(st，at)]Qs′学习算法： Qπ(s，a)=∑Pαss′[Rass′+γVπ(s′)]
近年来，基于强化学习的路径规划日益成为国内外学者研究的热点。M. J. Mataric[12]首次把强化学习引入到多机器人环境中。而基于强化学习的多机器人路径规划的优点主要体现在：无须建立精确的环境模型，简化了智能体的编程；无须构建环境地图；强化学习可以把路径规划、避碰、避障、协作等问题统一解决。
张芳等人[13]提出了基于再激励协调避障路径规划方法，把再励函数设计为基于行为分解的无模型非均匀结构，新的再励函数结构使得学习速度得以提高且有较好的鲁棒性。同时，证明了在路径规划中，机器人的趋向目标和避障行为密切相关，对反映各基本行为的再励函数取加权和来表示总的再励函数要优于取直接和的表示方式，也反映了再励函数设计得合理与否及其确切程度将影响再励学习的收敛速度。王醒策等人[14]在动态编队的强化学习算法方面展开了研究。宋一然[15]则提出了分段再励函数的强化学习方法进行路径规划。其缺点是学习次数较多、效率不高，当机器人数目增加时，它有可能面临维数灾难的困难。所以，基于强化学习的路径规划在多机器人环境下的学习将变得比较困难，需要对传统的强化学习加以优化，如基于人工神经网络的强化学习[16]等。
3)其他方法 除了以上国内外几种比较常见且研究较多的方法外，还有唐振民等人[17]提出的基于动态规划思想的多机器人路径规划，把运筹学中的动态规划思想与Dijkstra算法引入到多机器人的路径规划中，用动态规划的基本思想来解决图论中的费用流问题和路径规划中的层级动态联盟问题。其选择距离邻近法作为联盟参考依据。一个机器人的邻居是指在地理位置上分布在这个机器人周围的其他机器人；与该机器人最近邻的机器人为第一层邻居，第一层邻居的邻居为该机器人的第二层邻居， 依此类推。那么层级越高（即越近)的邻居，它满足协作要求的可能性越大。动态规划算法实质上是一种以空间换时间的技术，它在实现的过程中，必须存储产生过程中的各种状态，其空间复杂度要大于其他算法，故动态规划方法比较适合多机器人的全局路径规划。
孙茂相等人[18]提出了最优控制与智能决策相结合的多移动机器人路径规划方法。其首先构造一个以各机器人最优运动状态数据库为核心的实时专家系统， 在离线状态下完成; 然后各机器人在此专家系统的支持下， 以最优规划策略为基础， 采用速度迁移算法， 自主决定其控制。该方法拥有较好的稳定性与复杂度。焦立男等人[19]提出的基于局部传感和通信的多机器人运动规划框架较好地解决了多机器人路径规划在局部在线规划的系统框架问题。沈捷等人[20]提出了保持队形的多移动机器人路径规划。以基于行为的导航算法为基础，把机器人队列的运动过程划分为正常运动、避障和恢复队形三个阶段。在避障阶段，引入虚拟机器人使队形保持部分完整;当队形被严重打乱时，规划机器人的局部目标位姿使队列快速恢复队形。其算法重点为避障机器人进入避障状态，暂时脱离队列，并以虚拟机器人代替避障机器人。
2 多机器人避碰和避障
避障和避碰是多机器人路径规划研究中需要考虑的重点问题之一。避障和避碰主要讨论的内容有防止碰撞；冲突消解、避免拥塞；如何避免死锁。在路径规划中常见的多机器人避障方法[21]有主从控制法、动态优先法（建立在机器人之间的通信协商上）、交通规则法、速率调整法，以及障碍物膨胀法、基于人工势场的方法等。
目前国内外对于多机器人避障展开的研究还不是很多，比较典型的有徐潼等人[22]以Th.Fraichard的思想为基础，扩充并完善了路径/速度分解方案来协调多机器人，设立集中管理agent进行整体规划，为每个机器人规划路径；并根据优先级规则对运动特征进行分布式规划以避免机器人间的冲突。周明等人[23]提出分布式智能避撞规划系统，将原来比较复杂的大系统转换为相对简单的子系统问题，由各智能机器人依据任务要求和环境变化， 独立调整自身运动状态，完成任务的分布式智能决策体系结构。任炏等人[24]提出了基于过程奖赏和优先扫除的强化学习多机器人系统的冲突消解方法。该算法能够显著减少冲突，避免死锁，提高了系统整体性能。欧锦军等人[25]提出了通过调整机器人的运动速度实现多机器人避碰，将避碰问题转换为高维线性空间的优化问题， 并进一步将其转换为线性方程的求解。该方法的缺点是系统的复杂度较高、计算量太大。
人工势场方法的特点是计算简洁、实时性强、便于数学描述，且适合于多自由度机器人环境，但容易产生抖动和陷入局部极小。为了克服其缺点，景兴建等人[26]提出了人工协调场的方法，在传统排斥力场中增加一个协调力，并将吸引力、排斥力和协调力与局部环境下机器人的运动状态和运动要求结合起来，有效地保证机器人的安全性，提高机器人在复杂动态环境下行为决策的准确性和鲁棒性。
3 多机器人协作和协调机制
多机器人间的运动协调[27~31]是多机器人路径规划的关键，也是多机器人与单机器人路径规划相区别的根本所在。多机器人系统在复杂动态实时环境下，由于受到时间、资源及任务要求的约束，需要在有限时间、资源的情况下进行资源分配、任务调配、冲突解决等协调合作问题，而机器人间的协调与协作，能够大大地提高整个系统的效率和鲁棒性，成为系统完成控制或解决任务的关键。
目前已有的协调方式分为集中式、分布式和混合式三种。在集中式协调中，集中规划器详细地规划出每个机器人的动作，通常的做法是将多个机器人看做一个多自由度的机器人进行规划；而分布式协调规划中，机器人之间进行合作，将一个任务分成多个子任务，根据各自的特点完成不同的子任务，从而共同完成总任务；混合式协调是集中式和分布式混合在一起的形式。
多机器人间典型的协调方法[32]有合同网协议[33]、黑板模型、结果共享的协同方法、市场机制。近年来强化学习在多机器人协作方面也得到很好的应用，陈雪江[32]在基于强化学习的多机器人协作方面展开了研究，提出了多智能体协作的两层强化学习方法来求解在多智能体完全协作、有通信情况下的协作问题。其主要通过在单个智能体中构筑两层强化学习单元来实现：第一层强化学习单元负责学习智能体的联合任务协作策略；第二层强化学习单元负责学习在本智能体看来是最有效的行动策略。陈伟等人[34]提出基于多目标决策理论的多机器人协调方法；通过对环境的拓扑建模，从基于行为的机器人学角度出发，对任务进行分解并设计目标行为，以多目标行为决策理论作为决策支持，从而达到多机器人运动协调的目的。
4 多机器人路径规划方(算)法的判优准则
通常评价机器人路径规划方(算)法的标准文献[35]有正确性、时间/空间复杂度、并行性、可靠性、扩展性、鲁棒性和学习。而多机器人的路径规划除了以上一些衡量标准之外，还需要考虑整个系统的最优化以及机器人间的协调性。
1)正确性 是分析算法的最基本的原则之一。一般来说算法的正确性是指:在给定有效的输入数据后，算法经过有穷时间的计算能给出正确的答案。但在多机器人路径规划算法中，正确性主要指:路径规划算法要生成多个机器人协调运动的无碰安全路径;这条路径是优化的。
2)安全性 一般指多机器人所生成的各路径中节点与障碍物有一定的距离。但在实际的应用背景下，有人认为安全性可以从两个方面来理解：a）狭义地讲，它就是机器人在行走过程中所做的功。在一定的条件下，它与路径长度准则是一致的。b）广义地讲，它是各种优化条件加权综合而得到的结果。
3)复杂度 一个算法的复杂性高低体现在该算法所需要的计算机资源的多少上面。所需要的资源越多，该算法的复杂性越高；反之，所需要的资源越少，该算法的复杂性就越低。算法的复杂性包括时间复杂度和空间复杂度。
在多机器人的路径规划算法中，算法的复杂度分析显得尤为重要。一般地，单机器人路径规划算法的时空复杂度已经颇高，它们的数量级至少是O(n2)；多机器人的路径规划算法不仅是m-O(n2)(即m个机器人路径规划简单地叠加)，它们之间还存在着对运动空间竞争的冲突，面对不断变化的冲突的协调需要花费大量的时间和空间。通常多机器人的路径规划算法与机器人的个数呈指数关系O(km×n2)（k为常数）。这对多机器人路径规划算法的时间/空间复杂度控制是一个很严峻的考验。
4)并行性 算法的并行性从算法设计、编写程序、编译和运行等多个不同的层次来体现。路径规划过程需要大量的计算，当处理的环境比较复杂，机器人工作的环境过于紧凑，尤其是机器人数量很多时，算法的时间/空间复杂度势必会成为算法效率的关键。因此，在算法设计和运行上的并行性是通常考虑的方法。对多个机器人的路径规划尽量采用分布式多进程的规划机制，以实现每个机器人路径规划的并行性。
5)可靠性 把多个机器人及其工作环境看成是一个系统，多机器人处于它们各自的起始点时，称该系统处于初始状态；当它们处于各自的目标点时，称该系统处于目标状态。多机器人的路径规划就是在该系统的这两个状态间建立一串合理的状态变迁。这一状态变迁过程可能会历经许多状态，如果在状态变迁过程中，路径规划算法控制不好各状态间的转移关系，就会导致系统紊乱，出现机器人间的碰撞、找不到路径等恶性后果，使任务失败。所以这就对算法的可靠性和完备性提出了挑战。为了很好地克服这一困难，需要对系统的各种可能状态建模，分析它们相互间的关系，建立有限状态自动机模型或Petri网模型，并以此为指导，按照软件工程的思想，构造恰当的算法输入来对算法的可靠性进行检验。
6)可扩展性 在多机器人的路径规划算法中，可扩展性主要是指一种路径规划算法在逻辑上，或者说在实现上能否容易地从2D空间扩展到3D空间，从低自由度扩展到高自由度，从较少的机器人数到更多的机器人数。可扩展性在各种路径规划算法之间没有一种量的比较标准，只能从实际的具体情况出发、从对环境描述的适宜程度出发、从算法解决这一问题的复杂度出发、从算法本身的自适应出发等来考虑。
7)鲁棒性和学习 鲁棒性对于多机器人系统非常重要。因为许多应用，如路径规划要求连续的作业、系统中的单个机器人出现故障或被破坏，要求机器人利用剩余的资源仍然能够完成任务。学习是在线适应特定的任务。虽然通用的系统非常有用，但将它用于特定应用上时，通常需要调整一些参数。具有在线调整相关参数的能力是非常吸引人的，这在将体系结构转移到其他应用时可以节省许多工作。尤其是多机器人系统中机器人的自身学习和相互间的学习能够大大提高整个系统的效率和系统的稳定性。
8）最优化 对动态环境有优化反应。由于有些应用领域涉及的是动态的环境条件，具有根据条件优化系统的反应能力成为能否成功的关键。
5 结束语
综上所述，国内外研究者在多机器人路径规划取得了一些成果，但是在协作、学习、通信机制等方面仍面临很大的困难和不足。如何进一步提高机器人间的协调性，增强机器人自身以及相互间的学习以提高多机器人系统的效率和鲁棒性都有待深入研究。近年来无线通信技术得到长足发展，但在目前的技术条件下，在多机器人系统中实现所有机器人之间的点对点实时通信还有较大困难，这也是大多数多机器人系统仍然采用集中通信方式的主要原因。因此，如何降低多机器人系统对通信速度的依赖程度也是一个非常重要的问题。
总之，多机器人路径规划设计和实现是一项极其复杂的系统工程，展望其能在结合计算智能方法，如差分进化、遗传算法、粒子群算法、免疫算法、模糊逻辑算法、BP网络、人工势场的改进、模拟退火和环境建模方法等方面取得新的突破。
参考文献：
［1］WEISS G.Multiagent systems:a modern approach to distributed modern approach to artificial intelligence[M].Cambridge， Massachusetts：MIT Press，1999：121-161.
[2]蔡自兴，徐光祐.人工智能及其应用:研究生用书[M].3版.北京：清华大学出版社，2004：124-198.
[3]谭民，王硕，曹志强.多机器人系统[M].北京：清华大学出版社，2005：6-81.
[4]薄喜柱，洪炳熔.动态环境下多移动机器人路径规划的一种新方法[J].机器人，2001，23（5）：407-410.
[5]顾国昌，李亚波.基于总体势减小的动态调度技术解决多机器人的路径规划[J].机器人，2001，23（2）：171-174.
[6]孙树栋，林茂.基于遗传算法的多移动机器人协调路径规划[J].自动化学报，2000，26（5）：672-676.
[7]周明，孙树栋，彭炎午.基于遗传算法的多机器人系统集中协调式路径规划[J].航空学报，2000，21（2）：146-149.
[8]CAI Zixing，PENG Zhihong.Cooperative coevolutionary adaptive genetic algorithm in path planning of cooperative multimobile robot systems[J].Journal of Intelligent and Robotic Systems:Theory and Applications，2002，33(1):61-71.
[9]朱庆保.全局未知环境下多机器人运动蚂蚁导航算法[J].软件学报，2006，17（9）：1890-1898.
[10]SANDHOLM T W，CRITES R H.Multiagent reinforcement learning in the iterated prisoner’s dilemma[J].BioSystems，1996，37(1):147-166.
[11]高阳，陈世福，陆鑫.强化学习研究综述[J].自动化学报，2004，30（1）：
86-100.
[12]MATARIC M J.Interaction and intelligent behavior[D].Massachusetls:Department of Electrical Engineering and Computer Science，MIT，1994.
[13]张芳，颜国正，林良明.基于再励学习的多移动机器人协调避障路径规划方法[J].计算机工程与应用，2003，39（3）：80-83.
[14]王醒策，张汝波，顾国昌.多机器人动态编队的强化学习算法研究[J].计算机研究与发展，2003，40（10）：1444-1450.
[15]宋一然.基于强化学习的多机器人路径规划方法[J].莆田学院学报，2006，13（2）：38-41.
[16]韩学东，洪炳熔.基于人工神经网络的多机器人协作学习研究[J].计算机工程与设计，2002，23（6）：1-3.
[17]唐振民，赵春霞，杨静宇，等.基于动态规划思想的多机器人路径规划[J].南京理工大学学报，2003，27（5）：610-615.
[18]孙茂相，周明，王艳红，等.多移动机器人实时最优运动规划[J].控制与决策，1998，
13（2）：125-130.
[19]焦立男，唐振民.基于局部传感和通讯的多机器人运动规划框架[J].计算机工程与应用，2007，43(17)：89-93.
[20]沈捷，费树岷，郑波.多移动机器人保持队形路径规划[J].东南大学学报，2005，35(3):391-395.
[21]MANSOR M A，MORRIS A S.Path planning in unknown environment with obstacles using virtual window[J].Journal of Intelligent and Robotic Systems，1999，24(3):235-251.
[22]徐潼，唐振民.多机器人系统中的动态避碰规划[J].计算机工程，2003，29(17):
79-81，104.
[23]周明，孙茂相，尹朝万，等.多移动机器人分布式智能避撞规划系统[J].机器人，1999，21（2）：139-143.
[24]任炏，陈宗海.基于强化学习算法的多机器人系统的冲突消解的方法[J].控制与决策，2006，21(4):430-434，439.
[25]欧锦军，朱枫.一种多移动机器人避碰规划方法[J].机器人，2000，22(6):474-481.
[26]景兴建，王越超，谈大龙.基于人工协调场的多移动机器人实时协调避碰规划[J].控制理论与应用，2004，21(5):757-764.
[27]PANAIT L，LUKE S.Cooperative multiagent learning:the state of the art[J].Autonomous Agents and MultiAgent Systems，2005，11(3):387-434.
[28]TZAFESTAS C S，PROKOPIOU P A，TZAFESTAS S G.Path planning and control of a cooperative three robot system manipulating large objects[J].Journal of Intelligent and Robotic Systems，1998，22(2):99-116.
[29]薛宏涛，叶媛媛，沈林成，等.多智能体系统体系结构及协调机制研究综述[J].机器人，2001，23（1）：85-90.
[30]周风余，李贻斌，宋锐，等.基于混合式多智能体系统的协作多机器人系统研究[J].山东大学学报:工学版，2005，35(1):82-87.
[31]夏冰，张佐，张毅，等.基于多智能体系统的动态路径选择算法研究[J].公路交通科技，2003，20（1）：93-96.
[32]陈雪江.基于强化学习的多机器人协作机制研究[D].杭州：浙江工业大学，2004.
[33]SMITH R.The contract net protocol:highlevel communication and control in a distributed problem solver[J].IEEE Trans on Computer，1980，C-29(12):1104-1113.
关键词：物流系统；智能化；车辆路径；规划
中图分类号：P208 文献标识码：A 文章编号：1007-9599 （2013） 02-0000-02
1 概述
物流产业随着基础工业的不断壮大及消费市场的蓬勃发展而快速兴起。而中国的物流企业不论从技术装备还是管理水平与国外仍存在较大差距，概括起来有一下几个方面：对现代物流理念上的差距，企业规模方面的差距，社会需求方面的差距，管理体制方面的差距，专业手段方面的差距，专门人才方面的差距。据对美国物流业的统计与分析，以运输为主的物流企业年平均资产回报率为8.3%（irr），仓储为7.1%，综合服务为14.8%。在中国大部分物流企业的年平均资产回报率仅为1%。这一数据，不仅说明了中国物流效率低下，同时企业仍有很大的空间通过物流来降低成本。
如何应用先进的技术手段来提高物流业的经营效率，及时高效、经济地将商品配送到客户手中，成了大家探讨的话题，这也就是现代物流领域中备受关注的车辆路径问题（vehicle routing problem，VRP）。物流配送路径规划的优化与否，对物流配送效率、费用和服务水平影响较大。而此类问题都涉及如何处理大量的空间数据与属性数据而缩短物流时间、降低成本的问题。
地理信息系统作为不仅具有对空间和属性数据采集、处理和显示功能，而且可为系统用户进行预测，监测、规划管理和决策提供科学依据。它可以有效的结合最优路径、各种VRP模型、车辆行驶成本等要素，在可视化分析以及物流规划路径分析等方面具有不可替代的作用。GIS技术与现代物流工程技术相结合，给现代物流行业提供了巨大的发展空间，为物流企业完善管理手段、减低管理成本、提高经济效益、最终提升核心竞争力提供了机遇。
2 技术实现途径研究
物流配送车辆路线优化问题由Dautzig和Ramser于1959年首次提出，该问题一般定义为：对一系列给定的顾客（取货点或送货点），确定适当的配送车辆行驶路线，使其从配送中心出发，有序地通过它们，最后返回配送中心。并在满足一定的约束条件下（如车辆容量限制、顾客需求量、交发货时间等），达到一定的目标（如路程最短、费用最少等）。配送中心的每次配送活动通常面对多个非固定用户，并且这些用户分布在不同的地点，同时他们的配送时间和配送数量也都不尽相同。如果配送中心不合理规划车辆、货物的运输路线，常会影响了配送服务水平，还会造成运输成本的上升，因此对车辆及货物的配送路线进行规划是配送中心的一项重要工作。
车辆路线优化问题一般可根据空间特性和时间特性分为车辆路线规划问题和车辆调度问题。当不考虑时间要求，仅根据空间位置安排车辆的线路时称为车辆线路或车辆路径规划问题（VRP）。当考虑时间要求安排运输线路时称为车辆调度问题（VSP）。本文不考虑时间要求，主要针对第一类VRP问题，提出相应的技术实现方案研究。
典型的VRP具有以下特征：（1）所有车辆从仓库出发，并最终回到仓库；（2）所有车辆必须满足一定的约束；（3）多辆车负责多个客户；（4）每个客户由一辆车访问一次；（5）车辆的路线上可以取送货。目前研究的车辆路线规划的模型主要有两类，一类为网络图模型，另一类为数学模型。由于VRP难以用精确算发求解，启发式算法是求解车辆运输问题的主要方法，多年来许多学者对车辆运输问题进行了研究，提出了各种各样的启发式方法。
物流公司的业务一般具有配送范围广的特点，本文主要针对大范围跨省配送的案例进行智能路径规划，因此影响因素较多，主要包括：（1）大范围、跨省的配送交通网络图；（2）复杂的车辆运作规则，包括运行时间、运载能力、运行成本计算、驾驶员工作时间限制等；（3）复杂的道路选择优先级；（4）复杂的运输车辆优先级；（5）客户订单及运输车辆数据；（6）取货及分发过程；（7）繁杂的配送规则，如仓库、货物、客户的时间等；（8）运输车辆的重复利用，要求同一辆车在符合多个约束条件下尽可能多的参与到不同路线的配送中。
本文主要基于ArcObjects的网络分析和地图展示等组件进行二次开发，同时对其提供的车辆路径规划算法进行了拓展性研究。
3 功能模块设计方案
3.1 软件架构设计
系统建设遵循SOA架构，由数据资源层、组件层、服务层和表现层组成。数据资源层包括各种数据库、关系型数据库和空间数据库引擎ArcSDE，实现对物流业务数据的存储和管理；组件层包括接口协议、GIS组件、其他中间件；服务层实现计算功能，接受表现层的请求进行计算；表现层采用多种形式展现分析结果。
3.2 软件功能设计
本系统是物流业务管理系统的一部分，主要提供历史数据管理模块、线路优化分析模块、地图操作模块，同时提供与其他相关业务系统的扩展功能。
（1）线路优化分析模块
线路优化分析模块是系统的关键，提供两种分析结果：一种是基于AO自带的网络分析模块设计，计算分析结果；另一种是历次根据具体路况等信息的实际调度结果。
实际调度结果来自车辆GPS监控数据，并将实际调度结果作为输入，用来校正线路优化分析方法，最后生成最优路径规划。
（2）地图展示模块
地图展示模块，在配送交通网络图上展示道路基本信息、周边环境、仓库及客户地点、车辆位置信息等。同时将各种车辆路径规划分析结果以地图形式展示。基于ArcGIS提供的基础地图操作功能，实现地图缩放、浏览、鹰眼、图层控制、测量、选择、标注、信息查询等功能。
（3）历史数据管理模块
历史数据管理主要存储历史客户订单数据、实时路况信息、历史路径规划分析结果、实际运输路径等，可支持对历史数据的查询和修改。
（4）扩展功能模块
提供与其他相关业务系统、车载GPS设备、车辆监控设备等的接口，便于系统的扩展。
3.4 数据库设计
本系统中涉及的数据库主要包括元数据库、基础地理空间数据库、业务数据库、分析模型数据库、历史数据库等。
4 结束语
本文将物流车辆路径规划理论算法的研究与地理信息系统的网络分析模块相结合，经过二次开发，形成了用于实际的物流车辆路径规划信息系统。另外车辆路径规划设计约束较多，本文中不考虑时间要求，仅根据空间位置安排车辆的线路，同时不考虑装箱问题。
车辆路径规划问题是现代物流业的热点问题，但是基本停留在理论算法层面，随着技术的不断进步，必然出现考虑更多约束的先进算法，希望将这些算法真正与现代物流业结合，那将会是一个跨越式的进步。
参考文献：
关键词：无线传感器网络；移动信标；节点定位
中图分类号：TP393文献标识码：A文章编号：1009-3044(2011)21-5080-03
Research on Technology of Nodes Localization Based on Mobile Beacon for Wireless Sensor Network (WSN)
DING Hui, LI Bo-yong, AI Shu-liang
(Chenzhou Vocational and Technical College, Chenzhou 423000, China)
Abstract：Wireless sensor network has been used in many field. Nodes location of WSN has provided the basic information for many applications. Nodes location based on mobile beacon is one of the important research fields. Some basic principles and performance evaluating criterions of nodes localization based on mobile beacon for WSN are introduced. Some issues which need to be resolved in future are discussed.
Key words: wireless sensor network (WSN); mobile beacon; nodes localization
随着传感器技术、无线通信、微电子技术以及嵌入式计算等技术的发展，无线传感器网络(Wireless Sensor Network 简称WSN)得到了广泛应用，成为当今活跃的研究领域。无线传感器网络是新型的传感器网络，同时也是一个多学科交叉的领域，与当今主流无线网络技术一样，均使用802.15.4的标准，由具有感知能力、通信能力和计算能力的大量微型传感器节点组成，具有低成本、低功耗的优点和强大的数据获取和处理能力。
在无线传感器网络的众多应用中,如：国防军事、环境监测、交通管理、医疗卫生、目标跟踪、物流管理、入侵检测、交通流量监控和勘测应用等领域, 监测到事件之后需要确定事件发生的位置，信息融合后得到的相关数据信息如果不包含事件位置信息将毫无意义，只有带有标识位置信息的传感数据才有实际的意义。传感器节点自身的正确定位是提供事件位置信息的前提, 因此节点的精确定位基础而关键[1] 。
1 无线传感器网络节点定位的分类及基本方法
节点定位是指确定传感器节点的相对位置或绝对位置，节点所采集到的数据必须结合其在测量坐标系内的位置信息才有意义。人工部署传感节点和为所有节点安装GPS接收器都会受到成本、功耗、节点体积、扩展性等方面的限制，甚至在某些应用中是根本无法实现的。通常是为部分节点配置定位装置（如GPS接收器）或事先标定其准确位置，这些节点称为信标节点（也称锚节点），再利用信标节点的相关信息采用一定的机制与算法实现无线传感器网络节点的自身定位。目前人们提出了两类节点定位算法[2]：基于测量距离的定位算法与测量距离无关的定位算法。基于距离的定位方法首先使用测距技术测量相邻节点间的实际距离或方位，然后使用三边测量法、三角测量法、最小二乘估计法等方法进行定位。与测量距离无关的定位算法主要包括：APIT、质心算法、DV-Hop、Amorphous等。
1.1 基于无线传感器网络自身定位系统的分类[1,3-5]
1) 绝对定位与相对定位。绝对定位与物理定位类似，定位结果是一个坐标位置，如经纬度。而相对定位通常是以传感区域某点为参考，建立整个网络的相对坐标系统。
2) 物理定位与符号定位。经纬度就是物理位置；而某个节点在某街道的某门牌的建筑物内就是符号位置。一定条件下，物理定位和符号定位可以相互转换。与物理定位相比，符号定位在一些特定的应用场合更加便于使用。
3) 集中式计算与分布式计算定位。集中式计算是指把所需信息传送到某个中心节点，并在那里进行节点定位计算的方式；分布式计算是指依赖节点间的信息交换和协调，由节点自行计算的定位方式。
4) 移动信标与固定信标定位。移动信标节点是一类装备了GPS或其它定位装置的可移动节点，它在移动的过程中周期性自己的位置信息。基于移动信标的未知节点定位有很多优点，如定位成本低，容易达到很高的定位精度、可实现分布式定位计算、易于实现三维定位等。而固定信标节点是一类装备了GPS或其它定位装置的不可移动节点。
1.2 基于距离的节点坐标计算基本方法
待定位节点在获得与邻近信标节点的距离信息后，通常采用下列方法计算自身的位置[3]。
1) 三边测量法：利用网络中三个信标节点的位置坐标以及未知节点到这三个信标节点的距离，运用几何方法求出未知节点的坐标。
2) 三角测量法：利用网络中三个信标节点的位置坐标以及未知节点为角顶点角边分别为三个信标节点的角度，运用几何方法求出未知节点的坐标。
3) 最小二乘估计法：利用未知节点的相邻节点中的多个信标节点的位置坐标以及它们与未知节点的距离或角度，运用最小均方差估计方法求出未知节点的坐标。
1.3 常用的测距方法
1) 信号接收强度（RSSI）测距法
已知发射功率和天线接收增益，在接收节点测量信号接收功率，计算传播损耗，使用理论或经验的无线电传播模型由传播损耗计算出信源与接收者间的距离。通常使用下列对数-常态分布模型来计算节点间的距离[1]。
PL(d)=PL(d0)+10λ・log(d/d0)+X （1）
PL(d0)=32.44+10λ・log(d0)+ 10λ・log(f) （2）
RSSI=发射功率+天线增益-路径损耗(PL(d)) （3）
其中PL(d)[dB]是经过距离d后的路径损耗，X是平均值为0的高斯分布随机变数，其标准差取为4至10，λ为取衰减因子通常为2至3.5，f是频率，取d0=1(m)，这样根据上述3式可得节点间的距离。
2) 到达时间测距法
到达时间(TOA)技术通过测量信号传播时间来测量距离，若电波从信标节点到未知节点的传播时间为t，电波传播速度为c，则信标节点到未知节点的距离为t×c。
3) 时间差测距法
TDOA测距是通过测量两种不同信号到达未知节点的时间差，再根据两种信号传播速度来计算未知节点与信标节点之间的距离，通常采用电波和超声波组合。
4) 到达角定位法
到达角(AOA)定位法采用阵列天线或多个接收器组合来获取相邻节点所处位置的方向，从而构成从接收机到发射机的方位线。两条方位线的交点就是未知节点的位置。
1.4 典型非测距算法
基于距离测量和角度测量的定位算法的缺点是对专用硬件有一定的要求，从而使传感器节点成本和体积加大，限制了它的实用性。非测距的算法不需要测量未知节点到信标节点的距离，在成本和功耗方面比基于测距的定位方法具有一定的优势，但是精度相对不足。
1) DV－hop算法
为了避免对节点间距离的直接测量， Niculescu等人提出了DV－hop算法[3]。该算法基本思想是：用网络中节点的平均每跳距离和信标到待定位节点之间的跳数乘积来表示待定位节点到信标节点之间的距离，再用三角定位来获得待定位节点的位置坐标。
2) 质心法
质心法由南加州大学Nirupama Bulusu等学者提出[3]，该算法是未知节点以所有可收到信号的信标节点的几何质心作为自己的估计位置，它是一种基于网络连通性的室外节点定位算法。
3) APIT 算法
一个未知节点任选3个能够与之通信的信标节点构成一个三角形，并测试自身位置是在这个三角形内部还是在其外部；然后再选择另外3个信标节点进行同样的测试，直到穷尽所有的组合或者达到所需的精度。
4) Amorphous 算法
Amorphous 定位算法[3]采用与 DV-Hop 算法类似的方法获得距信标节点的跳数，称为梯度值。未知节点收集邻居节点的梯度值，计算关于某个信标节点的局部梯度平均值。Amorphous 算法假定预先知道网络的密度，然后离线计算网络的平均每跳距离，最后当获得3个或更多锚节点的梯度值后，未知节点计算与每个锚节点的距离，并使用三边测量法和最大似然估计法估算自身位置。
2 基于移动信标的无线传感器网络节点定位技术
无论是距离相关还是距离无关定位算法，常采用固定信标节点方式测量距离、相对角度、传播时间差及传播时间等进行节点定位[1]。通常参与定位的固定信标节点越多, 定位精度将越高。但是信标节点的成本远远高于普通节点，当定位工作完成后，信标节点将转成普通的传感器节点使用。因此信标点越多，布设整个网络的成本将会增大, 定位算法的计算负荷以及通讯负荷将会增大[1] ，过多的信标节点将会造成较大的浪费。所以利用移动节点发出的虚拟坐标点进行辅助定位的思想将成为节点定位研究的一个重要研究方向。
假定整个WSN由静止节点以及移动节点(如撒播节点完毕的飞机、运动的车辆、移动的小型机器人或普通的能移动的传感器节点等) 两种类型节点构成。根据传感器网络的规模大小, 可以配置一个或者多个移动节点。各移动节点均配置一个GPS接收器用于定位移动信标节点本身, 并有足够的能量自我移动或捆绑移动机器人、移动车辆或三维空间中的飞机等工具。移动节点在传感器区域内按照一定的运动路径移动, 并周期性地发送坐标位置信息, 待定位节点根据接收到的坐标信息与采用适当的定位算法完成定位[6] 。
近几年有一些研究者对移动锚节点路径规划展开研究，提出了一些比较好的路径规划方案。移动锚节点路径规划主要有两个目标：
1) 移动轨迹能够覆盖网络中的所有未知节点；
2) 为未知节点定位提供质量好的信标点。
如果满足网络节点均匀分布的条件，规划路径通常采用静态规划路径，移动锚节点都按照预先规划的路径移动，不具有根据节点分布状况灵活变化的性能。文献[7]针对移动锚节点的路径规划问题利用空间填充线理论提出了SCAN、DOUBLESCAN以及HILBERT路径规划方法，分别如图1、图2和图3所示。在节点通信距离小和空间填充线密度大的条件下， SCAN路径比HILBERT路径的定位结果准确。但是在节点通信距离大、空间填充线密度较小时，HILBERT路径明显优于SCAN路径。
SCAN路径存在明显的缺点就是提供了大量共线的信标点，HILBERT路径通过增加移动路径长度解决了信标点共线性的问题，只要达到一定的密度就可以为定位提供优质的不共线信标点。为了解决信标点存在共线性的问题，文献[8]提出了圆形规划路径和S形规划路径方法，如图4和图5所示。圆形规划路径完全覆盖方形网络区域时必须增加大圆路径，这很大程度增加了路径的长度。而圆形的直径非常大时，在局部带来了信标点的共线性问题。S形路径通过引入S形曲线代替直线，解决了信标点共线性问题。
而对于实际环境中节点非均匀分布的情况，文献[9]提出了提出了宽度优先和回溯式贪婪算法。这种方法能够根据网络信息自适应进行路径规划，规划路径不再是规则的图形，能够充分利用节点分布信息覆盖所有节点，保证路径最短，克服了静态路径规划的缺点。文献[10]提出让一个携带GPS的移动信标采用随机移动模型的方式尽量遍历传感区域，然后采用分布式算法为未知节点定位，该方法结合了基于测距方法的优点，并且无需布置固定的信标节点，节省了成本开销，但是由于移动信标的移动模型采用随机的方式，难以让其移动范围覆盖整个传感区域，从而有些未知节点无法定位。
3 定位算法的评价标准
定位算法设计的优劣通常以下列几个评价标准[11]来评价：
1）定位精度：一般用误差值与节点无线射程的比例表示，是定位技术首要的评价指标。
2）定位覆盖率：指利用定位算法能够进行定位的节点数与总的未知节点个数之比，它是评价定位算法的另外一个重要的指标。
3）信标节点密度：信标节点占所有节点的比例或者是单位区域内信标节点的数目。
4）节点密度：节点密度通常以网络的平均连通度来表示。
5）功耗：功耗是指传感器节点在单位时间内所消耗的能源的数量。由于传感器节点不会始终在工作的，有时候会处于休眠状态，但这同样也会消耗少量的能量，因此，传感器节点的功耗一般会有两个，一个是工作时的功耗，另一个是待机时的功耗。
6）成本：包括时间、空间和费用。时间指一个系统的安装、配置和定位所需的时间。空间包括一个定位系统或算法所需的基础设施和网络节点的数量、安装尺寸等。费用则包括实现某种定位系统或算法的基础设施、节点设备的总费用。
7）鲁棒性：定位系统和算法必须具有很强的容错性和自适应性，能够通过自身调整或重构纠正错误、适应环境、减小各种误差的影响，以提高定位精度。
上述的这些评价指标不仅是评价WSN自身定位系统和算法的标准，也是其设计和实现的优化目标。
4 结束语
使用移动信标节点来完成WSN所有节点的定位，就必须要足够的时间让移动信标节点遍历完整个网络, 为了减小所有节点定位所需的时间以及提高定位效率，如何进一步优化移动信标节点的运动路径将成为基于移动信标的WSN节点定位技术更研究的重要方向。
参考文献：
[1] 孙利民.无线传感器网络[M].北京:清华大学出版社,2005.
[2] A l-Karaki.JN, Kamal.AE. Routing Techniques in Wireless Sensor Networks: A Survey[J].In Wireless Communications,IEEE,Volume:11,Issue:6, Dec,2004:6-28.
[3] 王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(5):857-869.
[4] Kushwaha,M. Molnar,K. Sallai,J. Volgyesi, P. Maroti, M. Ledeczi, A. Sensor Node Localization Using Mobile Acoustic Beacons[C], In proc. 2005. IEEE International Conference on Mobile Adhoc and Sensor Systems Conference, Nov,2005.
[5] 倪巍,王宗欣.基于接收信号强度测量的室内定位算法[J].复旦学报(自然科学版),2004.43(1):72-76.
[6] Mihail L. Sichitiu ,Vaidyanathan Ramadurai. Localization of Wireless Sensor Networks with a Mobile Beacon[C].//IEEE 2004:174-182.
[7] Koutsonilas D, Das S M, Hu Y Charlie. Path Planning of mobile landmarks for localization in wireless sensor networks[J].Computer Communication.2007,30(13): 2577-259.
[8] Rui Huang,Zaruba Gergely V. Static Pathplanning for mobile beaeons to localize sensor networks[C] / /Proc of IEEE PerComW. Piscataway,NJ:IEEE，2007:323-330.
[9] Hongjun Li,Jianwen Wang,Xun Li and Hongxu Ma. Real-time Path Planning of Mobile Anchor Node in Localization for Wireless Sensor Networks[C].//Proeeedings of the 2008 IEEE International Conference on Information and Automation,Zhangjiajie,China,June,20-23,2008.
[10] Srinath T V. Localization in Resource Constrained Sensor Networks Using a Mobile Beacon with In-Ranging[C]/ / IFIP International Conference on Wireless and Optical Communications Networks,India, 2006:301-305.
关键词： 人工智能 足球机器人 人工神经网络 智能控制
引言
足球机器人系统是一个典型的多智能体系统和分布式人工智能系统，涉及机器人学、计算机视觉[1]、模式识别、多智能体系统[2]、人工神经网络[3]等领域，而且它为人工智能理论研究及多种技术的集成应用提供了良好的实验平台。机器人球队与人类足球一样，它的胜负不但取决于机器人本身的性能，而且取决于比赛策略，只有将可靠的硬件与先进的策略结合才能取胜。人工智能技术在足球机器人的平台上有着重要的作用。从机器人的外观到机器人最重要的核心部分——控制、决策，都无不起着重要的作用。专家系统[4]、人工神经网络在机器人的路径规划[5]上得到充分的应用。
1.人工智能研究现状
人工智能[6-8]是一门研究人类智能机理，以及如何用计算机模拟人类智能活动的学科，该领域的研究包括机器人、语言识别[9]、图像识别、自然语言处理和专家系统等，涉及数理逻辑、语言学、医学和哲学等多门学科。人工智能学科研究的主要内容包括：知识表示[10][11]、自动推理和搜索方法、机器学习和知识获取、知识处理系统、自然语言理解、计算机视觉、智能机器人、自动程序设计等方面。
几乎所有的编程语言均可用于解决人工智能算法，但从编程的便捷性和运行效率考虑，最好选用“人工智能语言”[12]。常用的人工智能语言有传统的函数型语言Lisp、逻辑型语言Prolog及面向对象语言Smalltalk、VC++及VB等，Math-Works公司推出的高性能数值计算可视化软件Matlab中包含神经网络工具箱，提供了许多Matlab函数。另外，还有多种系统工具用于开发特定领域的专家系统，如INSIGHT、GURU、CLIPS、ART等。这些实用工具为开发人工智能应用程序提供了便利条件，使人工智能越来越方便地运用于各种领域。
智能机器人是信息技术和人工智能等学科的综合试验场，可以全面检验信息技术和人工智能等各领域的成果，以及它们之间的相互关系。人工智能技术中的视觉、传感融合、行为决策、知识处理等技术，需要使无线通讯、智能控制、机电仪一体化、计算机仿真等许多关键技术有机、高效地集成统一。人们在很多领域都成功地实现了人工智能：自主规划和调度、博弈、自主控制、诊断、后勤规划、机器人技术、语言理解和问题求解等。
2.人工智能主要研究领域
人工智能的研究领域非常广泛，而且涉及的学科非常多。目前，人工智能的主要研究领域包括：专家系统、机器学习、模式识别、自然语言理解、自动定理证明、自动程序设计、机器人学、智能决策支持系统及人工神经网络等。下面主要介绍在足球机器人设计、制造、控制等过程中常用的人工智能技术[13]。
2.1专家系统
专家系统是一个智能计算机程序系统，是一个具有大量专门知识与经验的程序系统，它应用人工智能技术和计算机技术，根据某领域一个或多个专家提供的知识和经验，进行推理和判断，模拟人类专家的决策过程，以便解决那些需要人类专家处理的复杂问题。专家系统一般具有如下基本特征：具有专家水平的专门知识；能进行有效的推理；具有获取知识的能力；具有灵活性；具有透明性；具有交互性；具有实用性；具有一定的复杂性及难度。
2.2人工神经网络
人工神经网络是由大量处理单元互联组成的非线性、自适应信息处理系统，采用了与传统人工智能和信息处理技术完全不同的机理，克服了传统的基于逻辑符号的人工智能在处理直觉、非结构化信息方面的缺陷，具有自适应、自组织和实时学习的特点。神经网络在很多领域已得到了很好的应用，但其需要研究的方面还很多。其中，具有分布存储、并行处理、自学习、自组织和非线性映射等优点的神经网络与其他技术的结合，以及由此而来的混合方法和混合系统，已经成为一大研究热点。由于其他方法也有优点，因此将神经网络与其他方法相结合，取长补短，可以达到更好的应用效果。目前这方面工作有神经网络与模糊逻辑、专家系统、遗传算法、小波分析、混沌、粗集理论、分形理论、证据理论和灰色系统等的融合。
2.3图像处理
图像处理是用计算机对图像进行分析，达到所需结果，又称影像处理。图像处理技术主要包括图像压缩，增强和复原，匹配、描述和识别三个部分。常见的处理有图像数字化、图像编码、图像增强、图像复原、图像分割和图像分析等。数字图像处理中的模式识别技术，可以对人眼无法识别的图像进行分类处理，可以快速准确地检索、匹配和识别出各种东西，在日常生活各方面和军事上用途较大。
3.人工智能在足球机器人中的应用
3.1基于专家系统的足球机器人规划
路径规划或避碰问题是足球机器人比赛中的一个重要环节。根据工作环境，路径规划模型可分为基于模型的全局路径规划和基于传感器的局部路径规划。全局路径规划的主要方法有：可视图法、自由空间法、最优控制法、栅格法、拓扑法、切线图法、神经网络法等。局部路径规划的主要方法有：人工势场法、模糊逻辑算法、神经网络法、遗传算法[14]等。机器人规划专家系统是用专家系统的结构和技术建立起来的机器人规划系统。大多数成功的专家系统都是以基于规则系统的结构来模仿人类的综合机理的。它由五部分组成：知识库、控制策略、推理机、知识获取、解释与说明。随着人工智能计算智能与进化算法研究的逐步发展，遗传算法、蚁群算法等的提出，机器人路径规划问题得到了相应发展。尤其是通过遗传算法在路径规划中的应用，机器人更加智能化，其运行路径更加逼近理想的优化要求。以动态、未知环境下的机器人路径规划为研究背景，利用遗传算法采用了基于路点坐标值的可变长染色体编码方式，构造了包含障碍物排斥子函数项的代价函数，使得路径规划中的地图信息被成功引入到了遗传操作的实现过程中。同时针对路径规划问题的具体应用，改进了交叉和变异两种遗传算子，获得了较为理想的路径搜索效率，达到了较好的移动机器人路径规划效果。
3.2人工神经网络在机器人定导航中的应用
人工神经网络是一种仿效生物神经系统的信息处理方法，其优点主要体现在它可以处理难以用模型或规则描述的过程和系统；对非线性系统具有统一的描述；有较强的信息融合能力。因此在移动机器人定位与导航方面，基于神经网络的多传感器信息融合正是利用了神经网络的这些特性，将机器人外部传感器的传感数据信息作为神经网络的输入处理对象，从而获得移动机器人自身位置与对障碍物比较精确的估计，实现移动机器人的避障与自定位。
结语
随着人工智能技术的进一步研究，足球机器人竞赛水平将不断提高。但就目前情况来看，在现有的基础上扩大应用的范围，增强应用的效果，还应主要在人工智能技术上做进一步的研究。专家系统在专家知识的总结、表述及不确定的情况下推理是目前专家系统的瓶颈所在。制造生产的多变复杂性及操作的人工经验性，使人工智能的应用受到限制。此外，一些工艺参数的定量化实现也不易。随着技术的飞速发展，人工智能技术也在进一步完善，如多种方法混合技术、多专家系统技术、机器学习方法、并行分布处理技术等。随着新型人工智能技术的出现，制造业将会更加光明，性能更加优越的足球机器人也不再遥远。
参考文献：
[1]郑南宁.计算机视觉与模式识别[M].北京-国防工业出版社，1998.3.
[2]Wang Hongbing Fan Zhihua She Chundong Formal Specification of Role Assignment for Open Multi Agent System Chinese of Journal Electronics[J].2007，16（2）：212-216.
[3]LIMING ZHANG AND FANJI GU NEURAL INFORMATION PROCESSING VOLUME 1[M]Fudan University Press， 2001.
[4]Cai Zixing，King-Sun Fu. Expert-System-Based Robot Planning ？Control Theory & Applications[J] .1988（2）： 35-42.
[5]张锐，吴成东.机器人智能控制研究进展[J].沈阳建筑工程学院学报（自然科学版），2003，19（1）：61-64.
[6]蔡自兴，徐光祐.人工智能机器应用（第三版）清华大学出版社，2004.
[7]艾辉.谢康宁，谢百治.谈人工智能技术[J]中国医学教育技术，2004，18（2）：78-80.
[8]Nilsson NJ.Artificial Intelligence：A New Synthesis[M].Beijing：China Machine Press，2006：72-95.
[9]Han Jiqing Gao Wen Robust Speech Recognition Method Based on Discriminative Environment Feature Extraction Journal of Computer Science and Technology[J]. 2001；16（5）：458-464.
[10]Tang Zhijie Yang Baoan Zhang Kejing Design of Multi-attribute Knowledge Base Based on Hybrid Knowledge Representation Journal of Donghua University 2006，23（6）：62-66.
[11]Hu Xiangpei Wang Xuyin Knowledge representation and rule——based solution system for dynamic programming model Journal of Harbin Institute of Technology 2003，10（2）：190-194.
[12]姚根.人工智能的概况及实现方法[J] .2009，28（3）：108.
关键词：IPv6；OSPFv3；RIPng；协议
中图分类号：TP393.05 文献标识码：A 文章编号：1007-9599 (2011) 18-0000-02
IPV6 Routing Protocols and Algorithms Exploration
Zhao Yikui
(Wuxi Technician College,Wuxi 214044,China)
Abstract:Ipv6 is the core of coming Internet technology.In contemporary network technology the Routing Protocol is important concept.In this article we introduce IPv6's RIPng Routing Protocol and OSPFv3 Routing Protocol based upon the next generation,at the same time introduce the fundamental algorithm of above two protocols.
Keywords:IPv6;OSPFv3;RIPng;Agreement
随着Internet的发展，使得网络规模急剧膨胀，目前使用的IPv4协议由于其缺陷，己经不能从根本上适应网络发展的需要。在这样的背景下，下一代网络标准――IPv6（Internet Protocol Version 6）协议应运而生。IETF设计了新一代的网络协议，也被称IPV6[3]。与IPV4（Internet Protocol Version 4）相比，在地址格式上发生了巨大的改变，地址长度由原来的32位变为128位。相应地在整个地址分配上也进行了一定的改进。IPV6协议仍然整个地址空间仍然是层次结构的，仍然支持类似于IPV4无类域间路由（classless inter-domain routing，简称CIDR）地址结构下的路由合并，因此IPV6协议采用不会改变路由查找的特点。但是地址空间的增大，大大增加了路由查找的复杂度。
目前IPv6网络的路由协议基本沿袭了IPV4相关路由协议，IPV6地址相对IPV4更加结构化和层次化，使得IPV6网络的路由架构的层次化和可扩展性更优，这不仅对路由协议本身提出了新的要求，也对在不同网络结构下如何利用不同路由协议特点建立路由体系提出了新的挑战。近年对IPV6标准的不断充实和完善，IPv6协议及相关协议发展已相当成熟。下面给各位探讨流行的2种路由协议：RIPng和OSPF。
一、RIPng协议（RIP next generation）和RIPng路由选择算法
在网络中最复杂，最重要的一个方面就是路由。路由选择算法是网络层软件的一部分。按照其能否随着网络的通信量或拓扑结构来适应和调整变化来划分，可以分为自适应路由选择算法和非自适应路由选择算法。自适应路由选择算法主要使用距离――向量路由和链路一状态路由两种自适应路由选择算法来收集和处理路由信息。
RIP作为一种成熟的路由标准，在因特网中有着广泛的应用，特别是在一些中小型网络中。正是基于这种现状，同时考虑到RIP与IPv6的兼容性问题，IETF对现有技术进行改造，制定了IPv6下的RIP标准，即RIPng（RIP next generation）。RIPng协议使用是距离――向量路由算法。以下介绍一下常用RIPng路由选择算法。
二、Floyd算法[4]
Floyd算法又称为弗洛伊德算法，是求解网络中所有两节点间最短路的比较有效的算法之一。是一种动态规划算法，它的核心思路通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
把图用邻接距阵G表示出来；如果从Vi到Vj有路可达，则G（i，j）=d，d表示该路长度，否则G（i，j）=inf，为了搜出最短路径我们还需要一个距阵用来记录所插入点的信息。这个距阵是D，D（i，j）表示从V（i）到V（j）需要经过的点，初始化D（i，j）=j，接着按顺序依次将端集中的端点作为中间的转接点，计算此点距其他各点的径长，每次计算后都以求得的与上次相比较小的径长去更新前一次较大的径长，若后求得的径长比前次径长大或者相等则不变。以此不断更新G和D。直至形中的数值收敛。
Floyd算法优点是比较容易理解，可以算出任意两个节点之间的最短距离，可以以较简单的代码来表示该算法。该算法的缺点是复杂性比较高，数据量大是效率较低。
三、OSPF（Open Shortest Path First）协议和OSPFv3路由选择算法[6]
OSPF即Open Shortest Path First（开放最短路径优先），与RIP协议是距离――向量路由不同，OSPF是典型的链路――状态协议，OSPFV2协议基于IPV4，用于支持IPV4服务；为了更好的支持IPV6，IETF推出OSPFv3。OSPF是一种基于区域实现的、建立在链路状态（Link State）算法和Dijkstra算法基础之上的内部网关动态路由协议。OSPFv3是该协议的第3版本，是IPV6网络中路由技术的主流协议。
OSPFv2是基于网络运行的，两个路由器要形成邻居关系必须在同一个网段。OSPFv3的实现是基于链路，一个链路可以划分为多个子网，节点即使不在同一个子网内，只要在同一链路上就可以直接通话。
四、Dijkstra算法[5]
OSPF中用到的Dijkstra算法和RIP中用到的距离向量算法一样，都是相当经典的最短路径算法。Dijkstra算法是由荷兰计算机科学家狄克斯特拉（Dijkstra）于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。
Dijkstra算法基本原理是：每次扩展一个距离最短的点，更新与其相邻点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质[6]。
假设每个点都有一对标号（mj，nj），其中mj是从起源点s到点j的最短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；nj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：（1）初始化。起源点设置为：①ms=0，ns为空；②所有其他点：mi=∞，ni=?；③标记起源点s，记k=s，其他所有点设为未标记的。（2）检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：mj=min［mj，mk+lkj］式中，lkj是从点k到j的直接连接距离。（3）选取下一个点。从所有未标记的结点中，选取mj中最小的一个i：mi=min［mj，所有未标记的点j］，点i就被选为最短路径中的一点，并设为已标记的。（4）找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点，设置：i=j*（5）标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2）再继续。
RIPng协议和OSPFv3协议作为IPv6网络使用较多的内部网关路由协议，具有出色的路由能力。这两种协议都是IPV4网络协议基础发展而来，但是网络协议还需考虑传输容量和服务质量，还要分析全网负荷，平衡各条通道的数据流量等诸多因素的，因此RIPng协议和OSPFv3协议还需进一步的研究和优化。
参考文献：
[1]Y.Rekhter,T.Li,An architecture for IP address allocation with CIDR,RFC 1518,1993,9
[2]M.Degermark,A.Brodnik,S.Carlsson,and S.Pink,Small forwarding tables for fast routing lookups,In:Proc.of the ACM SIGCOMM’97,Cannes France:ACM Press,1997,9:3-14
[3]伍海桑,陈茂科.IPv6原理与实践[M].北京:人民邮电出版社,2000
[4]来强,基于V-D算法的RIP协议及其设计[J].现代电子技术,2002,l:51-53
[5]李琨.RIP协议分析与仿真研究[J].计算机工程,2002,28(3):85-87
关键词:改进蚁群算法;网页分类;支持向量机;贡献函数
中图分类号:TP391文献标识码:A文章编号:1009-3044(2009)35-10069-03
Study of Categorization of Web-Page Based on Improved Ant Colony Algorithm and Support Vector Machine
SONG Jun-tao, DU Qing-ling
(Dept. of Information Science and Engineering, Henan University of Technology, Zhengzhou 450001, China)
Abstract: Web page categorization is an of web data mining, it is a typical application based on technology of natural language processing and machine learning. It is imperative to find a effective and efficient method for web page categorization. In this paper, a new method is proposed for web page categorization based on improved ant colony optimization algorithm (IACOA) and support vector machines (SVMs).The experimental results show that the method is effective and robust, only to make up for the use of support vector machines for large sample training set less than the slow convergence with better precision and recall.
Key words: improved ant colony algorithm (IACA); web page categorization; support vector machine (SVM); contribution function
随着计算机网络技术的快速发展和Web 2.0广泛深入的应用,同时互联网上的信息呈指数级增长,人们可利用的网络信息也越来越多,如何从这些海量的信息中高效的获得所需信息已成为当前必须解决的问题。bayes分类、关联规则、决策树分类、单纯的支持向量机算法[7]等在文本分类中得到广泛的应用并取得了很大的进步,与文本分类最大的不同在于网页属于半结构化数据且数量极大,先前的文本分类算法直接引用到网页分类中,其分类精度和效率受到一定的影响,特别是大规模样本适应性不强,收敛速度慢。支持向量机分类最大的优点在于构造一个最优超平面,且有强大的统计理论基础,分类精度高,因此在分类中得到广泛的应用,但对于大规模样本训练过程中,表现出适应性不强,收敛速度比较慢的不足,为此本文提出了基于蚁群算法和支持向量机的网页分类方法。
1 SVM基本原理和蚁群算法
1.1 SVM基本原理
支持矢量机(Support Vector Machine,SVM)[1]是Vapnik等人于20世纪90年代中期提出的一类新型机器学习方法, 其理论基础是统计学习理论。与基于经验风险最小化原理的传统的统计学习方法不同,SVM基于的是结构风险最小化原理。SVM不仅结构简单,而且各种技术性能尤其是推广能力比神经网络等方法有明显提高。标准的SVM的实现涉及求解线性约束的二次规划问题,该问题可以收敛到全局最优解。但当训练数据很多时――这是很多实际问题所碰到的情况,二次规划问题的求解受到存储器容量的限制,而且分类速度也得不到保证,从而限制了SVM在很多问题上的应用。常用的做法是将问题分解为若干个子问题,然后再对这些子问题进行逐一优化。这样做的缺陷是:结果可能只是一个次优解,并且分解的时候可能需要多次分解才能将问题的规模转化为能解决的程度。
1.2 蚁群算法简介
蚁群算法[2](Ant Algorithm)由意大利人M.Dorigo等人首先提出的,蚁群算法是一个新的启发算法,蚁群算法固有的并发性和可扩充性,使它非常适合用于带约束的二次优化求解问题。在同一时间内,所有影响资源状态的因素都能由一个事情,即信息素描述。进而能够非常简单、快速地获得预测结果。
该算法按照启发式思想,通过信息传媒Pheromone的诱导作用,逐步收敛到问题的全局最优解,是求解适应性计算问题的一种有效方法。由于带约束的二次规划求解问题是众所周知的NP问题,而大量的实验表明,蚁群算法是一种有效的求解NP类问题的新型算法,具有较强的鲁棒性和内在的分布并行性,且易于和其他方法相结合。蚁群算法还有一个很大的优点就是具有可扩展性。所谓可扩展性指的是在原有一个规模n的问题上求出最优解后,再增加m个节点,可在原有解的基础上快速找到该问题的n+m规模的最优解,本文将蚁群算法与支持向量机结合充分保证支持向量机分类精度同时弥补其针对大规模训练样本收敛慢的不足。
2 ACA及SVM在网页分类中的应用
2.1 网页文档预处理
网页中数据最大的特点是半结构化,数据呈现形式多样化,首先用向量空间模型(SVM)[4-5]表示Web页面数据信息,本文采用TFIDF[6]向量表示方法,并非所有特征对分类都有用,况且不同的特征所起的作用也不一样,预处理阶段最重要的是关键特征提取及降维,直接影响到后续分类的精度。
2.2 SVM训练及ACA优化求解流程
首先将样本集分为训练集(80%)和测试集(20%)两部分,训练集专门用于SVM训练,而测试集专门用于评价测试SVM分类性能,其中影响SVM分类性能的两个重要参数是折衷参数C和高斯核函数K(xi,xj)=Ф(xi)Ф(xj),训练过程中,不断地调整参数C,同时利用上述蚁群算法对高斯核函数进行优化,最终选取合适的参数值,整个过程利用上述蚁群算法对SVM分类器函数优化求解,输出分类结果,整个分类过程如图1。
2.3 SVM[8-10]训练算法描述
1) 假设待训练样本集为T={(x1,y1),(x2,y2),…,(xi,yi)} 其中xi∈Rn,yi∈{1,2,…M} i=1,2, …,n
2) SVM算法的出发点是利用核技巧在高维空间里进行有效的计算,找出支持向量及其系数构造最优分类面。而此最优分类面的构造问题实质上是在约束条件下求解一个二次优化问题,以得到一个最优的决策函数,最优分类超平面为:
决策分类目标函数为:
3) 最优分类超平面问题描述为:
b是一个阈值。
4) 其对偶最优化问题为:
αi为二次优化问题的最优解,其中,K(xi,xj)=Ф(xi)Ф(xj)称为高斯核函数,n为训练样本个数,C为惩罚因子,它控制的是训练错误率与模型复杂度间的折衷。容易证明,该优化问题的解中只有一部分(通常是很少的部分)αi不为零,这些不为零αi的对应的样本就是支持向量,只有支持向量影响最终的划分结果。
2.4 蚁群算法[3-9]求解步骤:
算法优化求解开始时,训练集中的每一个样本点对应一个蚂蚁智能体,从t=0时刻开始第一轮搜索,当t=l时所有蚂蚁遍历所有样本点,完成了第一轮搜索。此时更新路径上的信息素,并将禁忌表清空。然后开始下一轮搜索,在达到用户设定的最大搜索轮数NC时,算法终止,此时找到的最优解作为问题的最优解。
1) 初始化:设定t=0,循环轮次数NC=0,对每条路径设置ζi(0)=C和Δζij=0,将m只蚂蚁均匀放置n个训练集中。
2) 设置s=l(s是禁忌表的索引),对k=l,…,m,将第k只蚂蚁所在的样本点的编号放入禁忌表中。
3) 在禁忌表索引s≤n时,重复如下操作:
① s=s+i;
② 对k=1,…,m,做如下工作:依照公式
计算蚂蚁在样本点i选择第j个样本点作为下一站的概率,并按概率选择样本点,将蚂蚁移至该样本点,将其编号放入禁忌表中。
4) 对k=l,…,m,做如下工作:计算第k只蚂蚁走过的路
径长度,记录当前找到的最优解,按公式
计算每只蚂蚁的信息素增量。
5) 对所有的点(i,j)根据公式
更新路径上的信息素。
设置t=t+n;NC=NC+1;设置所有的Δζij=0,
6) 如果NC≤NCmax或者没有出现收敛现象,设置它们的禁忌表为空;转到第2)步;否则,输出最优解,算法结束。
2.5 改进蚁群算法
2.5.1 贡献函数的引入及优化信息素平滑机制
蚁群算法在蚂蚁对路径进行探索之前,会对每条路径上的信息素含量进行初始化,即每条边的信息素含量具有相同的赋值。蚂蚁在进行路径选择的时候,主要是凭借路径的长度和信息素的含量来计算选择该条路径的概率,而在算法的起始阶段,各条边上的信息素含量是没有差异或者差异很小。这样就导致了蚂蚁在最初阶段仅仅凭借路径的长短来对路径进行选择,然后再在选择的路径上留下信息素,从而吸引后续的蚂蚁继续对这些路径进行探索。这种机制会使蚂蚁尽可能的选择长度较短的边来构造整个路径,它使得蚂蚁在路径选择时只对局部的优化进行考虑,而忽略了全局,形成“近视”现象,在开始阶段,每条边上的信息素含量是相同的,蚂蚁仅根据路径的长度来进行概率性选择。一种被称作信息素平滑的机制首次被提出,它使得算法在接近收敛时能够减小各条边之间的信息素含量的差异,从而保证蚂蚁对解空间的探索行为不会集中在一个相对较窄的范围之内。为了更好的分析、改进这种机制,首先简单介绍一下蚁群算法的收敛条件。
从前面的分析可以看出,随着蚁群对路径探索的深入,也就是循环次数的增加,信息素的更新和挥发使得边之间的信息素含量的差异将会变得越来越大,最终导致以每个城市为起点的边集合中只有一条边上的信息素含量值保持在一个较高的水平上。由于信息素的挥发机制,其它的边几乎不对蚂蚁的选择过程产生影响。这种情况被称作算法收敛[11],具体的定义如下:
定义2.1 τ(i,j)以i为起点的所有边的集合上的信息素含量值,τmax(i,j)=argmax{τ(i,j)},τmin(i,j)=argmin{τ(i,j)},使信息素含量最大、最小值之间的差ζr=τmax(i,j)- τmin(i,j)。令τ=λζr+τmin(i,j),其中λ∈(0,1),那么点i的λ-branching就定义为集合{τ(i,j)τ(i,j)>τ
由定义2.1可以看出当信息素含量差异越大时,λ-branching的值越小。所有点的λ-branching的均值就表明了算法的收敛程度,均值越接近1,算法越接近收敛状态,即当meanλ-branching =l时,算法收敛,也就是说蚂蚁不再对新的解空间进行探索,最终结果将被获得。当算法非常接近收敛的时候,信息素平滑机制允许每条边上的信息素含量根据一定的比例进行增加,从而减小差异,保持蚂蚁对新的解空间的搜索行为。平滑公式如下:
其中,τij和τ*ij分别为平滑前后边(i,j)上的信息素含量,δ∈[0,1],τmax为最大的信息素含量。当δ∈(0,1)时,蚂蚁对路径的认识信息,即信息素含量,并没有完全丢失,而只是被弱化了:当δ=0时,平滑机制对于信息素含量没有任何影响;当δ=1时,每条边上的信息素含量都被设定为一个固定的值τmax。
但是,信息素平滑机制并没有考虑到边是否对于构造更好路径有帮助。这样那些有帮助的边没有得到足够的信息素增强,同时那些没有帮助,甚至可能对后续蚂蚁的选择过程产生负面影响的边上的信息素含量则得到了增强,从而使它们被选择的机会大大增加。这两个方面的影响都会在一定程度上降低算法的性能。因此,有必要引入贡献函数来对平滑机制进行改进,使得贡献函数大的边能够获得更多的信息素增量,而使那些没有贡献,甚至对构造更好的解产生负面作用的边获得较少的更新,以便蚂蚁在后续的探索过程中更多的探索贡献函数值比较大的边,从而构造出更好的路径。改进后的信息素平滑公式如下:
其中,(i,j)是边(i,j))的贡献函数。
2.5.2改进蚁群算法描述
网页分类的目的是从训练数据集中提取出IF-THEN规则,蚁群算法通过对每个属性域中的属性值集合的选取完成分类规则的构建,算法描述具体步骤如下:
1) 清空规则列表,构造训练集;
2) 初始化信息素和启发式函数;
3) 放置蚂蚁,开始对属性值集合进行选取,构造分类规则;
4) 对构造的规则进行处理,删除不相关的属性;
5) 根据构造的分类规则的好坏进行信息素更新,若满足终止条件,进行第6步,
否则进行第3步;
6) 将提取出的分类规则加入到规则列表中,若提取的分类规则可以涵盖足够的训练数据集中的数据,算法终止,否则,进行第2步。
3 实验结果与分析
3.1 试验结果
本文试验在MATLAB7.0 环境进行仿真,数据采用10000篇网页文档(根据网页主题内容共分10个大类别),通过预处理后从中随机抽取20%用于测试评价分类器的性能,剩余80%用于训练,如图2是在本文方法在训练过程中分别对不同的核函数(多层感知器核函数a、多项式核函数图b,高斯核函数图c)进行优化的分类效果图,结果表明本方法选用高斯核函数在网页分类(特别是高维空间训练集)中效率比较高,明显由于其它两种核函数。
本文提出的方法与其它SVM分类方法相比,在训练样本规模较小时分类精度没有明显的区别,但随着样本规模的增大,本文的方法在保证分类精度的同时适应性有明显提高,弥补了SVM本身针对大样本适应性方面的不足。
3.2 分析评价比较
表1是本文提出方法与其它两种方法在准确率、召唤率、宏平均和微平均方面的比较。
本文采用传统的评价方法:正确率(P),召唤率(R)和F1值来衡量分类的效果,其中
li,mi,ni分别表示第i(i=1,…,10)类分类结果中正确的网页数目,实际包含的网页数目和结果中出现的数目。微平均计算方法如下公式:
4 结束语
本文利用改进蚁群算法和支持向量机理论相结合,提出了基于改进蚁群算法和支持向量机的分类方法,对寻求构建高效的网页分类器进行了研究,并与传统的分类算法如bayes算法、蚁群算法和支持向量机算法等进行分析比较,结果表明该方法应用在网页分类中在有效性、准确性有明显的改善,尤其在大规模训练集中适应性更强。该方法在提高搜索引擎的速度和质量方面有很大的应用空间,是进一步学习研究的重点。
参考文献:
[1] VAPNIK V.Universal Learning Technology: Support Vector Machines[J].NEC Journal of Advanced Technology,2005(2):137-144.
[2] 段海滨.蚁群算法原理及应用[M].北京:科学出版社,2005.
[3] 朱刚,马良.TSP问题的蚁群算法求解[J].计算机工程与应用,2007,43(10):79-80.
[4] CHEN P H,LIN C J,SCHLKOPF B.A tutorial on v-support vector machines[J].Applied Stochastic Models in Business and Industry,2005,21(2):111-136.
[5] Chang Chin-chang.Lin Chi-hjen.LIBSVM: a Library for support vector machines[J/OL].csie.ntu.tw/~cjlin/libsvm.2005.
[6] Mlademic D, Grobelink M. Feature Selection on Hierarchy of Web Documents[J].Decision Support System,2006(35).
[7] 贾s,梁久祯.基于支持向量机的中文网页自动分类[J].计算机工程,2005(5):18-22.
[8] 彭涛.基于粒子群优化算法的网页分类技术[J].计算机研究与发展,2006(6)33-38.
[9] 许建潮,胡明.中文web文本的特征获取与分类[J].计算机工程,2005(4):24-26.
关键词：配送；路径优化；节约里程法
中图分类号：F252.24 文献识别码：A 文章编号：1001-828X（2017）012-0-02
一、顺丰速运现状分析
顺丰速运于1993年成立于广州顺德，目前已发展成为业务覆盖全国的包括港澳台地区的大型物流配送公司。为保障物流的时效性，顺丰一半实行通宵作业，所有晚上揽收的快件，将在当晚至凌晨完成全部的分拣，装运等工作，凌晨已准备或已经通过空运或陆运开始运输。在配送方面，顺丰搭建了自建的物流体系，在全国建立了华北、华南、华东三个分拨中心，保障全国不同区域的的快件能够在打到中心区之后快速送达辐射区域内：主要的一线城市之间每天均有两趟的包机专线运送，保障了空运的快件能够及时周转至下一环节；在城市内部，顺丰也建立了多个分拨中心，每天多个批次运送快件至各个快递网点，保障物流配送的“最后一公里”时效不受影响。
1.顺丰公司发展现状
从顺丰的配送来看，主要分为城市间运输、城市内配送、终端配送等多个环节。城市间运输依靠极为高效不间断的分拣装运流水线完成作业，快速将快件通过空运或陆运送出。城市内配送主要依靠往返于市内各分拨中心与营业网点之间的车辆保障运送，由于快件量多，每天需要运送的快件变动量大，实时的交通运输条件有较大差异，因此这一环节受到各类影响因素的作用最大。终端配送工作由快递员负责，主要通过高标准的员工培训及绩效奖励保证工作质量，因此有着极高的时效性保障。
2.顺丰配送的特点与需求
目前顺丰的配送特点有：
（1）有完善的货物追踪系统，高效便利的呼叫中心，使客户可以快捷方便的进行网上自助服务。
（2）有安全的运输服务保障，拥有自营的运输网络，为客户提供高效、高质、快速、安全的服务。
（3）有很大一部分责任心强，积极上进的员工。
（4）有良好的物流配送网络，配送覆盖面积大。
（5）有专业的o2o与DDP服务，网上、电话订单，迅速传达，快速灵活的门到门服务。
（6）有良好的客户资源和品牌口碑。
在配送方案的规划目标方面，保障速度最快、时间最低的条件下成本最优是其基本原则。顺丰相较于国内其他同行企业收费较高，费用的溢价主要用于保障整个配送过程以及设施的投入方面，保障快件的效率才是顺丰的第一服务原则。基于此，可以了解到顺分在配送方面的优化需求在配送环节中的成本降低，有效的规划其配送路线为基础，本文对这一条件下的配送路线优化进行了研究分析
3.顺丰配送路径中的问题分析
从顺丰配送的主要流程来看，城市内部的车辆配送受到的影响因素较多，由于受到道路拥堵等问题的影响，终端的配送由营业点快递员完成，其配送路线较为自由随机，以快递员对工作便利及效率的判断为主要标准。需要进行动态的方案规划。
以北京市为例，在北京市内的配送过程中，避免不了的是车辆拥堵问题，现代化的交通设施和出行方式使得交通运输压力很大。在配送专业人才欠缺的情况下，无法高效的利用配送优化方法来解决物流配送路线的压力是现在顺丰配送的问题所在。在既要满足配送时间合理的情况下，同时需要降低配送的成本是重中之重。
在配送方案的规划目标方面，保障速度最快条件下的成本最优是其基本原则。顺丰速运在国内收费较高，费用的溢价主要用于保障顺丰对基础服务设施的投入以及对员工的绩效保障上，保障快件运送效率是顺丰运作的第一原则，在此基础上才考虑成本经济。基于以上分析，可以了解到顺丰速运在配送方面存在优化需求的主要环节是城市内的车辆配送，其规划目标是速度最优条件下的成本最优，以此为基础，本文对这一条件下的顺丰配送路线优化方案进行了分析。
二、配送路线优化方法
1.路径规划的主要优化方案
路径规划问题（Vehicle Routing Problem，VRP）是在1959年有Dantzig以及Ramser提出的，VRP问题是一类典型的NP-C问题，该问题需要满足一定数量客户同一时间内的不同配送需求，配送的需求同时要满足时间最快、成本最低、客户满意度最高等多种约束条件。由于问题复杂，约束条件多，该问题一直以来吸引了较多理论研究的关注，并不断的改良算法，寻求最优的解决方案
在针对顺丰速运的物流配送优化方面，本文主要针对顺丰的配送中心与各营业网点之间的配送路线进行优化，在实际的问题中，需要针对动态因素的改变来调整算法
2.基于条件控制下的节约里程模型
运用最短路径算法确定货物始发点，并确定几个收货点，确保一下几种事项：（1）配送总里程最短；（2）单车货物不超载；（3）满足用户的需求；（4）每天每车的运输里程不超过最大规定里程。
图2-1 图2-2
如图2-1与图2-2所知，图2-1的行驶总里程为2a+2b+2c，图2-2的行驶总里程为a+d+e+c。计算图2-1总里程减去图2-2总里程即可得出最优方案：2a+2b+2c-（a+d+e+c）=a+2b+c-d-e。由三角形两边之和大于第三边得出：a+b>d；b+c>e，所以a+2b+c-d-e>0，即图2-1总里程大于图2-2总里程，图2-2为最优方案。
通过节约里程模型分析可知，利用节约里程法可以降低配送时间、配送成本，使原本多条配送路线闭合成回路缩短行驶路线。在企业将来的发展中可以获得更大的经济效益。在减少配送时间与配送距离的同时，也是为环保做出一份贡献，不仅仅推动了企业的发展，更是进一步的使国民生活质量得到了改善。
三、结语
由于顺丰速运将快件配送的速度保障作为工作的第一要素，因此在所有的配送过程中，城市内配送中心想各营业网点的配送速度成为了快件配送r效性的决定因素。本文以顺丰城市内配送方案为研究对象，结合节约里程法总结出该方案的可行性，配合方案能够对顺丰速运的配送路线进行合理优化，对于提升配送速度，节约配送成本有着较为显著的效果，同时有着较好的时间解决意义。
参考文献：
[1]张红霞，黄晓霞.物流企业配送车辆调度问题研究综述[J].电脑知识与技术，2009（13）.
[2]柳伍生，刘军.一种改进节约发在车辆配送路径优化中的应用[J].现代交通技术，2007（6）.
[3]魏宝红浅析我国电子商务中物流配送存在的问题及对策[J].现代交通技术，2007（6）.
[4]袁清平.物流企业配送系统系统优化研究[D].西华大学管理学院，2008.
关键词:群体动画;真实感行为;认知建模;行为建模;群体动画
中图分类号: TP391.41; TP391.9
文献标志码:A
Survey on realistic behavior in crowd animation
RAO Yun-bo, CHEN Lei-ting, ZHOU Jun, LI Yan-mei
英文地址(
School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan 611731, China
Abstract:In recent years, computer crowd animation has been widely used in various applications such as virtual reality, computer game, education, amusement, and simulation training. The critical two areas of crowd simulations include: the first one is focusing on the simulation model of large crowd motion that is how to simulate realism behavior in crowd animation; the second one is high-quality visualization that is how to regularly use virtual scene in large crowd motion by 3D model. Some wonderful results have been achieved in the two areas. The authors presented the definition of crowd animation and structure of crowd animation, gave a survey on realism behavior in crowd animation from crowd simulation timeline, crowd modeling and crowd simulation algorithms. At last, the authors also presented the conclusions and discussed the prospect
Key words:crowd animation; realism behavioral; cognize modeling; behavioral modeling; crowd motion
0 引言
近年来,计算机图形学得到了极大的发展,同时随着数字媒体处理技术的迅速发展及计算机硬件成本的进一步降低,计算机动画技术及其相关应用得到有力推动与普及,特别是计算机群体动画被广泛地应用于虚拟现实、计算机游戏、在线教育、娱乐、模拟训练等多个领域。第一个群体概念是Amkraut等人[1]提出的。所谓群体是指两人或两人以上的集合体,他们遵守共同行为规范、情感上互相依赖、思想上互相影响、有共同奋斗目标。而所谓群体运动[2]是指在场景中有大量的群体,这些群体做着大致相同的行为,即他们拥有同一个目标,但是仔细观察每个个体的动作和造型,又会发现他们存在细微差异。第一个可编程群体动画模拟(虚拟鸟群)是由Amkraut S等人在一部名为Eurhythmy的电影中实现的。
在真实世界中,组群是普遍存在的。在查阅文献[3-4]等后,把群体动画研究的应用及每个领域的研究者归纳如图1所示。根据图1可见群体动画的研究不只是在计算机图形学领域,而在其他学科诸如:社会学、心理学、工程学和计算机视觉等领域都有相应研究。从图1中可以看到群体动画应用到了群体管理(检阅系统、暴乱处理系统)、公共空间设计(建筑物和城市规划)、虚拟环境群(动画动漫、计算机游戏和电影等)、智能环境(组群行为学)和视觉监视等领域。
图片
图1 群体动画的应用领域和研究者
目前国内关于群体动画的研究工作较少。主要有:电子科技大学研究虚拟环境下群体动画实时模型与绘制技术,研究内容是构建一个群体动画通用引擎模块,包括群体行为模拟及群体渲染两个部分,并在此基础上实现群体行为验证演示系统;中国科学院虚拟实现技术实验室研究支持大型公共设施安全问题研究的虚拟现实系统,研究内容是场景快速建模、人群行为模拟、大规模虚拟群体绘制、火(烟雾)运动模拟与绘制等;浙江大学数字媒体计算与设计实验室研究虚拟人运动与表情建模,研究内容是运动捕获数据的分析、检索、合成,人脸表情跟踪、分析与再生、超分辨率生成、人脸重建人脸幻想;另外还有微软亚洲研究院的群体动画研究。国外关于群体动画研究相对较多。主要有:斯坦福大学基于群体行为在危急环境中的紧急撤离和个体的角色表现的研究;GEOIDE和加拿大图形网络中心基于警察和军队的组行为,开发模拟群体行为的研究;利物浦大学心理学院和荷兰警察研究院基于群体与群体之间的冲突及交互模拟的研究;英国EPSRC基于人群运动和密度对潜在的危险位置,以及正常人和犯罪人行为的研究;欧盟PRISMATICA和ADVISOR基于人群在公共场所的运输流动研究;欧洲ICT财团ISCAPS基于区域类人群的自动安全监视系统的研究;以及欧盟支持的SERKET基于模拟群体恐怖防护的应急系统的研究。
虽然关于群体动画的研究者多且存在于不同的领域,而且在计算机方面群体动画国内外的研究工作也很多,但是关于计算机群体动画真实感行为综述的文章在国内外发表较少,部分综述存在于文献[5-11]中,但是不够完善。本文的贡献在于:1)明确了群体运动的概念;2)提出了群体动画的引擎框架,并对计算机群体动画研究进行分类;3)根据群体动画的发展历程对群体动画的研究工作进行归纳;4)对群体动画的典型建模进行分析与总结;5)归纳了群体动画在真实感行为方面的主要研究算法;6)利用给出的群体动画框架在理论上探索新的计算机群体动画真实感行为研究方向。
1 群体动画的引擎框架
在综合研究文献[3-4,12]后,归纳了如下的群体动画研究方向。
1.1 群体动画研究领域(方向)
目前群体运动技术中三个关键的研究方向是:1)研究并建立大规模群体运动的仿真模型,即如何实现对群体运动的真实感行为模拟;2)研究群体动画中高质量的可视化效果,即如何将大规模群体运动以三维的方式逼真地展现到虚拟场景中,这些都要依靠计算机的硬件绘制能力;3)真实感行为与可视化效果的混合研究。真实感行为模拟研究通常可以通过简单的2D可视化来对群体运动进行模拟,比如撤退模拟、社会群体模拟。在该领域中模拟的行为通常从一个有限的、可控制的效果到特定情况下的真实世界群体运动。在理想情况下,模拟的结果和真实人群运动相一致。研究质量的可视化效果的目的是使得群组中个体的行为和外貌产生多样性,同时提高场景的渲染速度。比如在电影作品创作和计算机游戏中的群体运动模拟,在这种情况下,真实感行为模型的真实性就不是太重要,而令人信服的视觉效果才是所关心的重点。真实感行为与可视化效果的混合研究领域中,面向可视化效果的群体系统尝试融合更好的行为模型,从而简化令人信服的动画创作,而面向行为的群体模型则尝试达到更好的可视化效果,尤其是在撤退模拟领域的研究。总之,群体运动要求群体真实感行为的有效性和高质量的可视化效果。
1.2 群体动画引擎框架
通过对群体动画研究文献分析。图2给出了一种群体动画的引擎框架,用于描述群体动画的研究方向、技术和综述的模块。该引擎主要考虑了群体动画的真实感行为模拟与高效的可视化效果两个方面。框架包含三个模块:群体动画管理器模块、真实感行为模拟模块和群体动画高效的可视化效果模块。群体动画管理器用于对群体的真实感行为模拟模块和群体动画高效的可视化效果模块进行管理,需要考虑群体所在的虚拟环境的复杂性、群体角色可视化方法和真实感行为模型等方面。真实感行为模拟模块包括5个基本建模:基于行为的建模、基于认知的建模、基于虚拟环境的建模、基于人群建模、基于角色的群体建模(将在第3章介绍)和两种算法:基于路径规划算法、基于碰撞避免算法(将在第4章介绍)。群体动画的高效的可视化效果模块,主要用于加速复杂虚拟场景绘制速率,提高计算机实时渲染能力的主要技术有[5,9]:可见性剔除技术、基于几何的图形绘制和加速技术、基于图像的绘制加速技术和基于可编程图像硬件(GPU)的加速渲染技术。
2 基于发展历程的群体动画真实感行为模拟分析
群体动画真实感行为的研究开始于19世纪,但是尝试用计算机建模来模拟群体行为则是最近才开始的。近几年来,群体真实感行为方面的研究者涉及的领域非常广泛,比如建筑学领域、计算机图形学领域、物理学领域以及社会学领域都一直在进行关于群体真实感行为的研究。
引言从社会学的角度给出了群体和群体运动的概念。在参考文献[13-14]后,从计算机图形学的角度对这个两个概念进行定义。
Фㄒ1 设F是群体函数,I为群体的集合。pi为个体,则群体集合P′可以表示为:
F(p1,p2,…,pn)=p′; p′∈I(1)
其中P′为值域,表示一个群体。要求P′燎sum(P′)=p1+p2+…+pi≥2,pi={r,e,j,g},r表示群体遵循的规则,e表示群体感情和精神上依托,j表示群体交互,g表示群体共同的奋斗目标。
通过对群体的定义和理解,给出群体运动的定义。
定义2 设F是群体运动评估函数,pi为个体,G(pi)为第i个个体运动评估函数,则群体运动可以定义为:
F(p1+p2+…+pn)=G(p1)+G(p2)+…+G(pn)(2)
其中F(p1+p2+…+pn)表示群体运动的评估值总值。现在根据个体运动情况和约束来对G(pi)进行分解。假设每个个体从原点到目标地点的时间为t∈[0,T],距离为s,则:
G(pi)=∏t∈[0,T]f(α∫so1ds+β∫To1dt+γ∫ToGdt)(3)
其中:α∫so1ds为个体从原点到目标地点的距离;β∫To1dt为个体从原点到目标地点的时间;γ∫ToGdt为个体从原点到目标地点时产生的运动舒适度(主要指运动个体的约束,如:碰撞、外形、个体质量、个体速度和运动方向等);α,β,γ为权重系数。
通过对群体及群体运动的定义,图3给出了一个群体动画发展历程的主要研究成果及群体动画的主要研究者。
Amkraut等人[1]在1985年SIGGRAPH的The Electronic Theater中提出群体动画概念。他们的工作是采用鸟群运动的全局向量力场来完成,并且使用这个技术在Eurhythmy的电影中第一次实现了可编程虚拟鸟群的群体动画模拟。人类群体的真实感行为模拟或者说具有人特点的群体模拟都是以那些更为简单的实体群体模拟为基础的,特别是鸟群的模拟[15]和鱼群的模拟[16]。
在1987年SIGGRAPH的The Electronic Theater中Reynolds[15]提出boids系统,首次完整给出了一个群体行为控制的模型,其目的是为自治主体群给出一种类似鸟群、鱼群或蜂群等群体行为的逼真形式。Reynolds提出了基于规则(中心吸引力、速度跟随、相互排斥力)来模拟简单个体组成的群落与环境以及个体之间的互动行为,其所实现的群体行为动画可以获得突现行为效果。后来,Reynolds扩展了他的工作,引入了指导行为的目标寻找、躲避障碍、路径跟进和分散等策略对群体动画进行处理。
Tu等人[16]提出基于自然生命模型的动画生成方法,把鱼作为自主智能体,创作了包括生物力学模型、几何显示模型、感知模型、动机模型和行为选择机制在内的人工鱼模拟动画系统。通过固定的、具有优先级的规则在一系列基本行为中进行选择。这些规则包括:避开障碍物、进食、求偶、逃跑、游戈和离开等。实现了鱼的捕食、求偶、集群和逃逸等生物活动,是基于Agent的群体动画的典型代表之一。Funge等人[17]对Tu的工作进行了扩展。对行为动力学中的诸如“刺激―响应”等进行模拟,同时也模拟了感知系统中的知识和学习过程。对于感知系统,Shao等人[18]又进一步扩展到了步行者的视觉范围和寻道方面。
Brogan等人[19-20]基于规则组合的模型通过对各种场的构建以及个体间、个体与环境间各种力的按规则生成和组合来实现个体的避障。算法分为两个步骤:第1步,感知模型决定个体和障碍物是否都可视;第2步,安置算法决定为每个运动个体获取位置和个体与障碍物的速度。由于连续的设定、计算复杂性、系统平衡性的制约以及穿透矫正行为的缺失,它们都没有彻底解决个体间可能出现的穿透问题。其中Lakoba等人[21]和Treuille等人[13]分别提出了一种用来矫正穿透的方法,但存在算法上的局限,依然无法彻底避免穿透。
Bouvier等人[22-23]使用了一种与鸟群模拟相似的方法来模拟人群。他们将粒子系统与转换网格相结合,用来模拟虚拟城市中的人群。在低层行为,类似于物理电子学中的吸引力和排斥力使得人群在所处的环境中移动。群体目标的一致性产生群体个体之间的相互吸引力,而障碍物则产生群体个体之间的排斥力场。高层行为则通过转换网格进行模拟,在该转换网格中转换依赖于时间、对某些点的访问、局部人群密度的改变以及全局事件等。
Musse等人[24-25]针对虚拟人群的实时模拟提出了一种层次模型。该模型是基于组的,而不是基于个体的。组是一种更加智能的结构,每一个组都由不同的自治水平来控制:可指导的群体可在运行时遵循由用户指定的顺序;可编程的群体则遵循预定制好的行为;而自治性的群体则使用事件和反作用力来产生更加复杂的行为。群体所处的环境则是由一些标识目标与路径的信息点集合一些动作点集组成,如在到达目标以后需要做的动作点集合。
Ulicny和Thalmann等人[26-27]提出了一种基于层次的群体动画规则。在他们的系统中,行为捕获通过层次来决定其行为规则,而行为的执行通过层次的有限状态机处理。
Niederberger等人[28]对群体模拟的应用提出了一种分层次的体系结构。在该体系结构中,群体行为是通过对现有行为类型的特殊化和对新类型的继承来定义的。每一组的结构是通过递归和基于模式,而行为引擎为了保证最小的帧率,则需要考虑每次运行时所需要的最大时间量。
Treuille等人[13]使用一个全局的动态势能场处理变化的环境,同时考虑了人群的密度、人群的速度、地势高低以及舒适度的问题,将局部的碰撞避免和全局的路径控制结合在一起,但要求以组为单位进行模拟,组内的个体拥有相同的运动特性,有效地解决了在没有明确碰撞规避机制的情况下,大量虚拟人群的运动,但只能是在二维的环境中进行,如图4所示。
图片
图4 城市各种模拟方案[13]da Silva等人[29]提出了运动风格克隆。在动态环境中创作自然人体运动因为其复杂的几何和物理作用而变得困难,提出了在交互状态下通过规则的控制计算来克隆运动风格。只要给出运动的参数和期望的目标,控制系统就能模拟和克隆出新环境,且产生的高质量运动可以与几何和物理的环境模拟保持一致。关于运动克隆的文章,在2008年McDonnell等人[30]也提出了外形的克隆,在大规模人群中通过模板风格进行克隆。
Kwon等人[31]提出了一个依靠个体运动的轨迹及维持相邻个体整体的组运动编辑。用户可以通过拖拉个体来改变组的运动轨迹。多个组的运动能够被整合成一个长的或者大的运动,采用了一种地图的结构,顶点表示指定针的个置,边表示邻接个体的排列和移动的轨迹。Kim等人[32]扩展了Kwon的工作,提出了同步的多个体运动编辑方式,针对多个体交互时候存在的线形约束,采用了拉普拉斯方法。
3 群体动画建模
动画的建模在计算机图形学上按照层次等级方式进行归纳。最早的动画模型是几何模型,然后是前向和逆向的运动学建模,接着是基于物理的模型,最近在创作动画方面提出行为建模,即个体对环境刺激和感知产生反映。最高层次的建模:认知模型,即独立的个体能对给定的目标和自由的动作产生反映。具体结构如图5所示。
图片
图5 动画建模层次归类[41]
对于群体运动的建模也遵循图5所示的动画建模分类,但是在群体运动中考虑如下因素:1)基于人群的群体运动模拟较多,且人是自然界最复杂的智能体,日常生活中的每一件小动作,如饮水、购物,其背后都隐含着复杂的感知和决策过程,在这些方面人类对于自身认识还相当不够;2)环境对群体运动模拟的影响比较大;3)不同的角色在不同虚拟环境中对群体运动个体的影响比较大。
基于以上分析和群体动画引擎框架,在这里把群体动画的建模分为五类:基于行为的建模、基于认知的建模、基于虚拟环境的建模、基于人群建模和基于角色的群体建模。下面将介绍每类中比较成熟且有代表意义工作的文献。
3.1 基于行为的建模
行为建模技术主要考虑模拟个体的数目、个体的智商水平、控制机制和碰撞处理等。解决这些问题的方法可以是粒子系统、群体系统、行为系统和等级层次系统等[25]。
粒子系统最早由Reeves于1983年引进到计算机图形学领域,用来进行一些自然模糊现象的建模和可视化,比如云、水、气体以及火焰等。法国的Bouvier等人[23]以粒子系统为原型建立了人群运动模型。在Bouvier建立的模型中,每个人都是一个模拟对象――“粒子”,整个人群则看作是一个粒子系统,系统内的粒子间可以进行互动。一个粒子集合对应于一群具有相同行为模式的人,通过在粒子系统内设置各种力场,采用牛顿力学机制并辅以被赋予概率的事件,通过仿真计算求得每个粒子的位置、速度、加速度等属性,以实现人群运动的模拟。对于一些复杂的、需要较多决策知识的人群行为,还需要提供人群行为模式的学习方法、建立决策知识库等。Tu等人[16]的研究工作是这一模型的代表。
3.2 基于认知的建模
认知建模的研究主要在行为控制,目前在计算机图形学中认知建模的研究有文献[17,33-39]。其中Funge等人[17]提出了认知建模在行为建模方面的作用,并通过对角色动作、角色先前条件和影响、角色行为的设置等定义了认知建模语言(Cognitive Modelling Language, CML)。认知建模分为两个子模块:知识域描述和角色范围。知识域描述是描述角色在环境中的基本信息,而角色范围是角色行为按照一定规则获得指定目标。CML为获取的目标提供了高维接口:一方面CML是传统语言,可以描述指定的动画角色;另一个方面,CML提供了简单而有力的认知建模语言,通过CML语法描述关键的精确映射及计算。
Pelechano等人[34-36]提出了HiDAC(高密度的自治群体)模型,集中模拟个体在动态变化环境中的局部运动行为。结合心理学和几何学的规则,采用了个体认知和基于物理的力模型。系统模拟了个体在不同环境下的不同运动行为(如:抖动行为、双向行走行为、推行为和恐慌的蔓延行为)。并概括了基于个体模拟研究群体的基本方法:社会力模型、基于规则模型和基于CA(Cellular Automata)模型。
Shao等人[18]提出的人工生命方法整合了运动、感知、行为和认知等。方法支持自由行走的个体感知虚拟环境和反映个体行为,解决了行走者在复杂的城市环境下模拟不真实的一些行为(如:群体运动的碰撞避免、群体的运动轨迹等)。
以班晓娟等人[37]提出的“晓媛鱼”为基础的相关研究有:人工鱼的自繁衍、自学习和“情+智”协调研究等,这些研究大多集中在人工鱼的个体上,旨在提高人工鱼个体的智能水平和认知能力。
赵光俊等人[38]针对群体动画中角色的行为选择(策略、目标和计划)过程和认知建模方法,提出了一种建立自主角色认知模型的新方法。通过在行为动画中引入“动物行为逻辑”的概念,给出了高层非确定性目标导向行为与低层确定性预定义行为相结合的协调控制方案,并以鱼群动画为例进行了仿真实验。此方法不仅使行为动画中的角色具备行为选择智能,且能较好地反映群体行为的真实性。
Silverman等人[39]利用影响人群行为的心理元素提出了PMFServ系统。PMFServ系统是具有高融合的软件系统,能模拟不同的群体领域,而且提供了认知结构的接口,能模拟基于情感的人群。
3.3 基于群体环境的建模
环境建模与行为建模非常相关,模拟环境的目的是为了让群体的模拟与它们所处的环境相符。如果虚拟群体的行为与它们所处的环境相符,则虚拟群体模拟的可信性则会大大地增加。相反,如果虚拟群体的行为与现实世界不一致或者不被允许,比如穿墙或者人在水上行走,则会破坏掉虚拟群体模拟的可信性。
Thomas等人[40]提出了一种针对人群行为的虚拟城市模型。在该模型中,环境数据库被划分为两部分:一部分是一种包含区域树的层次结构,这点与信息化环境数据库相似;一部分是一种具有公路交通网络的拓扑结构,每一块区域包含了关于流通方向的信息,包括在交叉路口的通道变化。每一个个体使用该数据库作为整个城市的导航。
Sung等人[41]提出了一种控制群体行为的新方法,该方法通过使用一种名为“Situation”的结构来将行为信息存放到所处的环境中。同先前的方法相比,环境结构Situation中的信息是可以交叉的,而与这些交叉的环境结构Situation相对应的行为则是通过概率分布计算得到。根据当前所处环境状态或的过去状态,行为函数决定了行为状态转换的可能性,即触发行为的变化。
王洁等人[42]针对模拟低密度下个人安全距离的保持和高密度下人群拥挤的情况,采用基于原位置的穿透矫正法克服现有模拟中由于避免穿透而引入的限制和失真,有效地杜绝穿透现象的出现。
3.4 基于人群的建模
目前通用的人群运动建模方法均处于初步研究阶段,实际应用有一定难度。而针对特定应用系统,在限定模拟场景或情节并给定人群目标的情况下,研究人群的行为特征、建立人群运动模型则较为容易。目前已经有不少针对特定应用的人群运动仿真系统,如:模拟在轮船失事情况下乘客逃生过程的maritime EXODUS系统;模拟在地铁、港口等典型建筑物危急情况下人群逃生的Vegas系统等。下面介绍一些有代表工作的文献。
3.4.1 恐慌状态下人群撤离运动建模
Helbing等人[43]系统地研究了恐慌状态下的人群撤离行为,建立了恐慌状态下人群撤离的运动仿真模型。该模型仅针对恐慌状态下的人群撤离行为,以粒子系统为基础,着重研究和分析个体的受力情况,根据个体的受力情况计算个体的移动速度,模拟恐慌状态下人群撤离的典型行为特征,计算人群通过狭隘通道和出口撤离的速度,并计算可能的受伤人数。个体受力情况和运动速度的关系可用式(4)表示:
midvidt=miv0i(t)e0i(t)-vi(t)τi+∑j≠ifij+∑wfiw (4)
其中:mi是个体质量;v0i(t)是个体速率i的初始速度;e0i(t)是个体初始运动方向;vi(t)是个体期望的经过ti时刻后的运动速度;∑j≠ifij是周围人群施加给个体i的力。∑wfiw是周围建筑如墙壁、障碍物等施加给个体i的力。图6显示了恐慌状态下人群撤离的模拟。
3.4.2 Vi Crowd 人群运动建模
ViCrowd模型由瑞士联邦技术研究所计算机图形实验室的Soraia等人[25]提出。ViCrowd模型定义了虚拟人三个不同层次的集合:人群、团队和个体。而后定义了人群的三个大方面的属性:知识、信念和意图。知识主要涉及虚拟环境中的各种信息,包括:障碍物、基于环境的人群动作和行为、人群知识等。信念主要包括人群即将执行的动作和行为,它可以分为三个方面:1)人群和群的行为,比如聚集、跟随、更换目标、吸引、排斥、分裂、空间占用和安全检测等;2)情感状态,比如喜怒哀乐等;3)个人信念,比如个体是否要脱离或加入一个群、个体在人群中的地位等。意图则表示人群目标。
图片
图6 人群通过一个狭隘出口撤离的模拟结果[43]
ViCrowd模型同时还定义了虚拟人行为的三个自由度层次,即被引导的(又称外部控制)、规划的(也称脚本控制)和自治的(内在行为)。在人群运动模拟中,外部控制行为的优先级最高,其次是脚本控制行为,最后是自治行为。图7是采用ViCrowd模型进行仿真的结果。
图片
图7 基于ViCrowd 模型的人群运动仿真结果[25]
3.4.3 Brogan and Hodgins建模
Brogan and Hodgins模型,主要针对具有显著物理特征的人群[20],在建模过程中更多地使用动力学原理,对人群的速度、位置、加速度变化进行了更多的考虑和限制,同时也从物理角度应用动力学原理建立个体运动仿真模型。它是粒子系统针对具有显著物理特征的人群行为的一种扩展,适用于马拉松、自行车赛、游泳等体育项目的模拟仿真。模拟结果如图8所示。
图片
图8 Brogan and Hodgins人群运动仿真[20]
3.5 基于角色的群体建模
通常在特定的生存环境中,不同的智能角色有不同的感觉能力。为了生动逼真地刻画出智能角色的感知能力,必须对智能角色的感知系统进行合理、正确的建模。为智能角色建立感知模型涉及两个内容:1)模仿智能角色的感知能力以及感知局限性;2)通过模仿角色大脑对感知信息的处理结果来解释感知的信息。
Reynolds等人[15]提出了一个集群行为计算模型,其中每个角色是在各自的环境中独立的行为者,通过感知局部环境来决定在给定的时间采取何种行为;Tu[7]的工作中提出了基于自然生命模型的动画自动生成方法,把鱼作为自激励的自主智能体,创作了生动逼真的人工鱼群,其工作是智能角色动画的典型代表;Isla等人[44]提出了智能角色建模领域中的最新挑战。这些基于角色的建模较复杂,产生的运动有限,需要进一步对真实感行为进行研究。
3.6 小结
如表1所示,我们对近年来有关计算机群体动画研究的文献按照群体动画的建模方式进行分类。从表1中可以看出,在收集到的50篇论文中,对于群体动画的研究大多从个体行为研究开始,主要方法是采用基于社会力模型、基于规则模型、CA模型和人工生命方法等。通过对群体动画建模分类,能更好地理解群体动画研究的方法和方向。
表格(有表名)
表1 计算机群体动画的建模分类
群体动画的建模类型主要研究内容研究方法研究文献
基于行为的建模考虑模拟个体的数目、个体的智商水平、控制机制和碰撞处理等粒子系统、群体系统、行为系统、等级层次系统等[1,15-16,23,25]基于认识的建模行为控制社会力模型、基于规则模型、基于CA模型[17-20,23,[34-39]基于群体环境的建模复杂环境对模拟、对群体运动的影响,阻止穿透现象的产生环境数据库、环境结构[41-43]基于人群的建模人群的行为特征、建立人群运动模型ViCrowd模型、社会力模型、基于规则模型、物理学模型[20,25,43]基于角色的建模智能角色的研究人工生命方法、基于规则的模型[7,15,29-30,44]
4 群体运动算法
群体真实感行为的控制方式主要分为两类:自底向上的方式,即基于局部控制的方式;自顶向下的方式,即基于全局控制的方式。对于运动的群体,无论是局部控制方式还是全局控制方式都要设计解决两个问题:路径规划和碰撞避免。对于这两个问题,先前的研究者提出一些算法和方法,下面进行归纳分析。
4.1 碰撞避免算法
碰撞检测按照是否考虑时间参数,可分为连续碰撞检测和离散碰撞检测。其碰撞检测的典型算法包括:空间分解法和包围盒层次法。常见的空间分解法有八叉树法和二叉空间剖分法。常见的包围盒有包围球、沿坐标轴的轴向包围盒(AABB)、方向包围盒(OBB)和离散方向多面体(k-DOP)等。
Kim等人[45]采用了分割区域的方法,并为每个人设置一个触角圆柱体用于探测其所在方形内其他个体。缺点:触角圆实际上是个体的感知范围,范围太大计算量会增加,太小就不能模拟人的视觉。Chenney等人[46]采用流片元方式使用可自由分支的流模拟人群体的方法,有效地模拟拥塞避免的人群特性。
在1983年Reeves提出粒子系统后,Bouvier等人[22-23]使用粒子系统和有限自动机模拟了城市环境中的虚拟人群,使用类似电子力的吸引力和排斥力作为底层力来实现碰撞避免。
刘莉等人[47]提出一种新的穿透深度计算方法,无须对凹多面体进行凸分解,就能精确地计算任意多面体间的方向穿透深度。在此基础上,提出一种基于个体分解的包围体层次,极大地提高了算法的效率。
其他碰撞的算法有:基于网格的规则、基于密度的技术、行为系统和粒子交互力。
4.2 路径规划算法
所谓路径规划就是依据某个或某些优化准则(如工作代价最小、行走路线最短和行走时间最短等),在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的路径。主要的方法有:基于网格的算法、基于人工势能场算法、CMM算法、IRM算法和DB算法等。
基于网格的方法是把虚拟环境划分成单元格,然后使用A*搜索算法。A*搜索算法缺乏适应性,同一条路径只有固定的路径查询格式,计算代价比较大。D*算法[48]也使用网格方法,采用全局搜索算法且克服A*算法的缺点。优点是:当重新计算新优化路径时,不需要计算整个路径。Tang等人[49]使用了一种改进的A*算法在由高度图生成的地形网格上进行路径规划。Willns等人[50]提出了改进的DB算法,该算法是基于网格的动态距离繁衍系统。Reynolds[15]提出了领队跟随和路径跟随模式。对于被指定的组,领队跟随运动模式的组内成员分为领队者和跟随者,当指定领队的运动速度、方向和目标位置以后,跟随者的运动就完全由领队者控制,初始状态时的领队者和跟随者的相对位置关系和目标状态时的领队者和跟随者的相对位置关系相同。
Pettre等人[51]使用静态场景的导航图实时地规划个体的路线,但是没有考虑碰撞和拥塞的避免。通常来说,静态势能场不能处理变化的环境。Treuille等人[13]使用一个全局的动态势能场解决了这个问题,算法同时考虑了人群的密度、人群的速度、地势高低以及舒适度的问题,但只能是在二维的环境中进行。
Geraerts等人[52]提出CMM(走廊地图方法)。CMM克服了传统路径寻径的缺点,在复杂环境中容易计算出光滑路径。但是对同一路径搜索方式固定,无灵活性。Karamouzas等人[53]使用运动个体在走廊中的路径选择扩展了CMM方法。Geraerts等人[54]采用提取离散的路径信息来改进CMM。
Karamouzas等人[55]提出了IRM算法,该方法被广泛地应用于计算机游戏和虚拟环境。IRM算法被分为三个阶段:1)计算个体指示的路线;2)对路线创建一个走廊,使得个体在虚拟环境中无碰撞;3)使用势能场方法从创建的走廊中提取个体运动信息。该算法能准确地规划路径并且防止个体碰撞。
Lamarche等人[56]为快速层次路径规划提出了一种几何环境的拓扑结构,为虚拟群体提出了一种可反应的导航算法。但是采用了一个独立的碰撞避免过程,在拥塞的处理上容易产生堵塞现象。
4.3 小结
表2对碰撞避免算法和路径规划算法的16篇文献进行分类。并对每一类算法进行归类,其实在很多文献中,碰撞避免算法和路径规划算法往往是放在一起研究,如文献[52,55]等。
表格(有表名)
5 结语
群体动画属于计算机图形学的研究范畴,但是群体动画的真实感行为研究涉及到计算机图形学、人工智能、机器学习和认知科学等领域,已经成为一个多学科技术交叉的研究领域。
本文首先给出了群体动画引擎框架,对群体动画进行分类和归纳;根据群体动画近年来的发展情况进行了分析,给出了群体和群体运动的概念;根据群体动画引擎框架对现有的计算机群体动画真实感行为的建模研究进行了综述(主要包括:基于认知的建模、基于行为的建模、基于群体环境的建模、基于人群的建模和基于角色的群体建模);同时对群体运动的个体从碰撞避免算法和路径规划算法等两个方面对群体动画的算法进行分析。
通过查阅相关文献[2-4,13,16,18],群体动画未来几年可能取得突破的研究方向有:1)基于心理学和认知科学的研究,发掘出更具一般性的群体行为、表情甚至感情等机制的真实感行为;2)全局控制与局部控制的人工智能问题在大规模场景中的研究;3)多种群体分组策略研究,并通过按照地理及目标点进行分组控制,优化计算性能;4)个体的高层决策模型研究,采用有限状态机及模糊状态机来描述个体的意图转换,从而做出意图决策;5)群体模型中个体避免碰撞和智能路径规划技术的算法研究,可以考虑基于“局部侧滑力避障路径算法”、“基于自学习的避障路径算法”及“基于特定目标点的最优化路径算法”等算法的改进。
致谢 本文的工作得到了国家863计划项目(2007AA01Z322)和总装基金项目(9140A06060208DZ0207) 资助。同时感谢本文所参考文献的作者和研究团体,感谢他们卓绝的工作;感谢电子科技大学计算机学院数字媒体研究所的各位成员,感谢他们的建议和良好的协作精神。
参考文献:
[1]AMKRAUT S, GIRARD M, KARL G. Motion studies for a work in progress entitled "Eurnythmy" [EB/OL]. [2009-04-20]. /Paper/1280362.aspx
[2]PELECHANO N, OBRIEN K, SILVERMAN B, et al. Crowd simulation incorporating Agent psychological models, roles and communication [C]// Proceedings of the 1st International Workshop on Crowd Simulation. St. Philadelphia, PA: [s.n.], 2008: 21-30
[3]ADI BIN MOHAMED AZAHAR M, SUNAR M S, DAMAN D, et al. A survey on real-time crowds simulation [C]// Proceedings of the 3rd International Conference on Technologies for E-learning and Digital Entertainment, LNCS 5093. Berlin: Springer-Verlag, 2008: 573-580
[4]ZHAN BEI-BEI, MONEKOSSO D N, REMAGNINO P, et al. Crowd analysis: A survey [J]. Machine Vision and Applications, 2008, 19(5/6): 345-357
[5]陈雷霆.三维复杂场景实时绘制技术[D].成都:电子科技大学,2007
[6]肖俊.智能人体动画若干关键技术研究[D].杭州:浙江大学,2007
[7]TU XIAO-YUAN. Artificial animals for computer animation: Biomechanics, locomotion, perception, and behavior [D]. Toronto: University of Toronto, 1996
[8]MCDONNELL R. Realistic crowd animation: A perceptual approach [D]. Dublin: University of Dublin, Trinity College, 2006
[9]陈健.群体动画实时渲染技术的研究[D].成都:电子科技大学,2007
[10]徐文彬.大规模虚拟人实时绘制技术研究及其实现[D].北京:中国科学院计算技术研究所,2006
[11]PALMQVIST B, DIMBERG N. Boids for real-time management of armies [D]. Umea: Umea University, 2006
[12]THALMANN D, MUSSE S R. Crowd simulation [M]. London: Springer-Verlag, 2007
[13]TREUILLE A, COOPER S, POPOVIC Z. Continuum crowds [C]// SIGGRAPH06: Proceedings of the 33rd International Conference and Exhibition. Boston, Massachusetts: ACM Press, 2006: 1160-1168
[14]HUANG LING, WONG S C, ZHANG MENG-PING, et al. Revisiting Hughes dynamic continuum model for pedestrian flow and the development of an efficient solution algorithm [J]. IEEE Transportation Research, 2009, 43(1): 127-141
[15]REYNOLDS C W. Flocks, herds, and schools: A distributed behavioral model [C]// SIGGRAPH87: Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 1987: 25-34
[16]TU X, TERZOPOULOS D. Artificial fishes: Physics, locomotion, perception, behavior [C]// SIGGRAPH94: Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 1994: 43-50
[17]FUNGE J, TU X, TERZOPOULOS D. Cognitive modeling: Knowledge, reasoning and planning for intelligent characters [C]// SIGGRAPH99: Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 1999, 29-38
[18]SHAO W, TERZOPOULOS D. Autonomous pedestrians [C]// SCA05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. New York: ACM Press, 2005: 19-28
[19]HODGINS J, BROGAN D. Robot herds: Group behaviors for systems with significant dynamics [C]// Proceedings of the 1995 IEEE/RSJ International Conference on Intelligent Robots and Systems. Washington, DC: IEEE Computer Society, 1995: 528-534
[20]BROGAN D, HODGINS J. Group behaviors for systems with significant dynamics [J]. Autonomous Robots, 1997, 4(1): 137-153
[21]LAKOBA T I, KAUP D J, FINKELSTEIN N M. Modifications of the Helbing-Molnár-Farkas-Vicsek social force model for pedestrian evolution [J]. Simulation, 2005, 8l(5): 339-352
[22]BOUVIER E, GUILLOTEAU P. Crowd simulation in immersive space management [C]// Proceedings of the 1996 Eurographics Workshop on Virtual Environments and Scientific Visualization. Berlin: Springer-Verlag, 1996: 104-110
[23]BOUVIER E, COHEN E, BAJMAN L. From crow simulation to airbag deployment: Particle systems, a new paradigm of simulation [J]. Journal of Electrical Imaging, 1997, 6(1): 94-107
[24]MUSSE S R. Human crowd modeling with various levels of behavior control [D]. Lausanne: EPFL, 2000
[25]MUSSE S R, THALMANN D. A hierarchical model for real time simulation of virtual human crowds [J]. IEEE Transactions on Visualization and Computer Graphics, 2001, 7(2): 152-164
[26]ULICNY B, THALMANN D. Towards interactive real-time crowd behavior simulation [J]. Computer Graphics Forum, 2002, 21(4): 767-775
[27]ULICNY B, THALMANN D. Crowd brush: Interactive authoring of real-time crowd scenes [C]// Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. New York: ACM Press, 2004: 243-252
[28]NIEDERBERGER C, GROSS M. Hierarchical and heterogeneous reactive Agents for real-time applications [J]. Computer Graphics Forum, 2003, 22(3): 323-331
[29]da Silva M, ABE Y, POPOVIC J. Interactive simulation of stylized human locomotion [J]. ACM Transactions on Graphics, 2008, 27(3): 63:1-63:12
[30]McDONNELL R, LARKIN M, DOBBYN S, et al. Clone attack! perception of crowd variety [J]. ACM Computer Graphics, 2008, 27(3): 1-8
[31]KWON T, LEE K H, LEE J, et al. Group motion editing [J]. ACM Computer Graphics, 2008, 27(3): 80:1-80:8
[32]KIM M, HYUN K, KIM J, et al. Synchronized multi-character motion editing [C]// SIGGRAPH 2009: Proceedings of the 2009 International Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 2009: 79-79
[33]CONDE T, THALMANN D. Learnable behavioral model for autonomous virtual Agents: Low-level learning [C]// Proceedings of the 5th International Joint Conference on Autonomous Agents and Multiagent Systems. New York: ACM Press, 2006: 89-96
[34]PELECHANO N, ALLBECK J M, BADLER N I. Controlling individual Agents in high-density crowd simulation [C]// Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. New York: ACM Press, 2007: 99-108
[35]PELECHANO N, STOCKER C, ALLBECK J, et al. Being a part of the crowd: Towards validating VR crowds using presence [C]// AAMAS08: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, 2008: 136-142
[36]DURUPINAR F, ALLBECK J, PELECHANO N, et al. Creating crowd variation with the OCEAN personality model [C]// AAMAS 2008: Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, 2008: 12-16
[37]宁淑荣,班晓娟,涂序彦.人工鱼“情+智”协调的“意图产生”和“行为控制”[J].自动化学报,2007,33(8):835-839
[38]赵光俊,张文俊,陈伟平.群体行为动画中认知角色的建模方法[J].系统仿真学报,2007,19(14):3253-3257
[39]SILVERMAN B G, BHARATHY G, OBRIEN K, et al. Human behavior models for Agents in simulators and games: Part I-Enabling science with PMFserv [J]. Presence: Teleoperators, and Virtual Environments, 2006, 15(2): 139-162
[40]THOMAS G, DONIKIAN S. Modeling virtual cities dedicated to behavioral animation [J]. Computer Graphics Forum, 2000, 19(3): C71-C80
[41]SUNG M, GLEICHER M, CHENNEY S. Scalable behaviors for crowd simulation [J]. Computer Graphics Forum, 2004, 23(3): 519-528
[42]王洁,王兆其,李淳芄,等.一种用于群体模拟的分层次避障法[J].计算机研究与发展,2007,44(12):2058-2065
[43]HELBING D, FARKAS I, VICSEK T. Simulating dynamical features of escape panic [J]. Nature, 2000, 407(6803): 487-490
[44]ISLA D, BLUMBERG B. New challenges for character-based AI for games [C]// Proceedings of AAAI Spring Symposium on AI and Interactive Entertainment. Cambridge, MA: AAA Press, 2002: 141-146
[45]KIM H K, OH J K, CHOI M G. An event-driven approach for crowd simulation with example motions, CS-TR-2001-170[R]. Taejon, Korea: Korea Advanced Institute of Science and Technology, 2002
[46]CHENNEY S. Flow tiles [C]// Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Aire-la-Ville, Switzerland: Eurographics Association, 2004: 233-242
[47]刘莉, 王兆其, 夏时洪, 等.碰撞响应中方向穿透深度算法的研究[J].计算机研究与发展,2008,45(3):519-526
[48]KOENIG S, LIKHACHEV M. Fast replanning for navigation in unknown terrain [J]. IEEE Transactions on Robot, 2005, 21(3): 354-363
[49]TANG W, WAN T R, PATEL S. Real-time crowd movement on large scale terrains [C]// Proceedings of the 2003 Theory and Practice of Computer Graphics. Washington, DC: IEEE Computer Society, 2003: 146-146
[50]WILLNS A R, YANG S X. Real-time robot path planning via a distance propagating dynamic system with obstacle clearance [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, 2008, 38(3): 884-893
[51]PETTRE J, LAUMOUND J P, THALMANN D. A navigation graph for real-time crowd animation on multilayered and uneven terrain [C]// V-CROWDS05: Proceedings of the 1st International Workshop on Crowd Simulation. Lausanne, Switzerland: [s.n.], 2005: 81-89
[52]GERAERTS R, OVERMARS M H. The corridor map method: A gen-eral framework for real-time high-quality path planning [J]. Computer Animation and Virtual Worlds, 2007, 18(2):107-119
[53]KARAMOUZAS I, OVERMARS M H. Adding variation to path planning [J]. Computer Animation and Virtual Worlds, 2008, 19(3/4): 283-293
[54]GERAERTS R, OVERMARS M H. Enhancing corridor maps for real-time path planning in virtual environments [C]// CASA 2008: Proceedings of the 2008 International Conference on Computer Animation and Social Agents. Seoul, Korea: [s.n.], 2008: 64-71
关键词：unity 3D 探险游戏 C# 藏族特色
中图分类号：TP311 文献标识码：A 文章编号：1003-9082（2015）06-0019-01
引言
在人类的社会生活当中，游戏占有很大的比重，并且随着社会的发展而不断发展。在现有的游戏市场中，具有藏族特色游戏更是寥寥无几，恢弘传统民族文化，游戏也是一种途径。在本游戏设计之初，对一些具有藏族特色的游戏，进行了试玩和调查，比如藏式麻将[1]对本游戏具有很大的引导作用。藏式探险小游戏的设计与开发，在一定的程度上，开创了藏式探险游戏的先河。藏式探险小游戏的设计与开发，旨在训练玩家的思维应变能力，以及在玩的过程中了解的文化元素，游戏场景设计中具有大量的藏族元素，如场景中的雪山冰川，给人以身临其境的感受。
一、运用unity3D游戏引擎中遇到的问题
1.unity3D游戏引擎中图形用户界面藏文字符实现
Unity3D游戏引擎在目前的游戏市场占据着半壁江山，因此在游戏设计之初，就决定使用该款游戏引擎作为设计开发平台。但是，unity3D本身仍然存在着一些弊端，现在市场上的unity3D软件还不支持中文输入，因此藏文的输入也是无法完成，用户图形界面如果需要做得具有藏族特色，即插入藏文字符菜单栏，实现起来有困难。unity3D中可以将任意字体作为材质文件赋予“GUI Text”，其中就包括藏文字体。具体做法如下：
第一步：将需要的藏文字体拷入到项目文件中“Assets”（资源）文件夹内。
第二步：在菜单栏选中Game Object创建一个G.U.I文件，将字体导入，在属性面板中找到“Text”后面的输入框输入需要的文字即可；
2.游戏引擎后台程序设计语言的选择
在网络日益盛行的当今社会，各种程序设计语言如雨后春笋，Unity3D游戏引擎作为一款主流的游戏制作软件，对程序设计语言也有较高的要求。Unity3D后台支持的主要程序设计语言有C#、java script和bootstrap等程序语言[1]。本次游戏设计选择了C#语言作为游戏设计开发语言，由于使用C#可以减少许多语言上的麻烦，而且C#作为一种简单、通用、现代的语言，对于新手是比较合适的程序设计语言。同时，C#语言也是unity3D后台程序开发运用最广泛的语言，而且C#的算法在unity3D游戏引擎中容易实现[2]。相比其他几种程序语言，如果使用java script程序设计语言，程序代码将会很繁琐，而且java script的运算速度相对较慢。Bootstrap是目前最受欢迎前端框架，更多用于做网站，不适合做游戏开发。
二、游戏设计中算法的实现
1.探险人物路径的设计
人物在探险的过程中会有栅栏的阻碍和怪兽的追击，人物路径的设计具有一定的难度，解决人物移动的算法运用了C#程序设计语言中常用的遍历算法。以下代码完成了人物路径的设计：
//人物所在的行列数编号=格子的行列数编号+1
for （int i = 0； i < 8； i++）//遍历编号为0-7总共8行的格子
{for （int j = 0； j < 6； j++）//遍历每一行编号为0-5总共有6列的格子
if （row == j + 1）{ //当前遍历的格子与人物所在的行数相同
if （col == i）{//当前遍历的格子列数=人物所在的列数+1
if （！row barrier.Contains（new Vector2（row - 1， col - 1）））//若此格子右边没有竖栅栏阻挡 }
//则当前遍历的格子列数=人物所在的列数-1
if （col == i + 2）{
if （！Row barrier.Contains（new Vector2（row - 1， col - 2））） //若此格子左边没有竖栅栏阻挡；人物向左移动，并记录移动前的行列数
dir = 3； old Row = row； old Col = col； move = true； }} }
//当前遍历的格子与人物所在的列数相同
if （col == i + 1）
//当前遍历的格子行数=人物所在的列数+1
2.游戏中怪兽移动算法
算法在程序设计中具有核心作用，因此算法的设计对程序的设计具有决定性的作用，常见算法设计方法主要有：递推法、递归法、回溯法、迭代法、动态规划法等[3]。而此次探险游戏设计使用了类深度优先遍历的计算方法，用程序实现搜寻答案的计算方法，即根据探险人物路径遍历搜寻怪兽的移动算法。由以下代码实现了怪兽的移动：
void AI（）
{
if （！move && m Move==0）
{ //怪兽移动前，人物不移动时进行AI
//生成可行走路径数组
Now Path.Add（new Vector2（m Row， m Col））；//将当前搜寻的格 子位置打入到当前要遍历的路径链表
m Path.Add（new List（now Path））；//将当前要遍历的 路径链表插入到可移动路径数组
//开始遍历
for （int i = 0； i < m Path.Count； i++）
{//若速度（2+1，因包括自身所在格）范围内的所有格子都已遍历， 则退出遍历}
三、结语
在信息化高速发展的今天，游戏市场还处在不断发展的阶段，而开发具有藏族特色的游戏，前景更是广阔。基于unity3D藏式探险游戏设计完成了具有特色的传统游戏开发，实现了在unity3D游戏引擎上对具有藏式特色游戏的设计开发。不可避免该设计还存在一些缺点，在以后的时间里，不断完善使其做到极致。同时了解更多关于的传奇故事，将其演绎成游戏的形式奉献给大家，将元素及文化传向中国、传向世界。
参考文献
[1]曲珍.朱世清.藏式麻将游戏设计与实现[M]：大学出版社，2013.
[2]吴亚峰.Unity 3D游戏开发技术详解与典型案例[M]：人民邮电出版社，2012.
[4]雷军环、刘震.数据结构C#版教程[M]：清华大学出版社，2009.
关键词：遗传算法；时间窗；车辆路径问题；基因库
中图分类号：TP202+.7文献标识码：A文章编号：1009-3044(2011)10-2411-03
Research on VRPTW Problem Based on Improved Genetic Algorithm
FAN Yue-lin, ZHOU Su-ping
(Economy Management College, Nanjing University of Information Science & Technology, Nanjing 210044, China)
Abstract: The Vehicle Routing Problem with Time Windows (VRPTW) is NP-hard, this paper explored the optimal solution by improved Genetic Algorithm, and firstly analyzed the general mathematical model of the Vehicle Routing Problem with Time Window, and dealt with Time Window through penalty function. Then designed a fitness function with weight in-built, then adopted the elite selection operator based on gene pool ,PMX crossover operator and local_climbing mutation operator. Finally compared the algorithm with simple genetic algorithm and adaptive genetic algorithm by simulation. The results indicate that the improved genetic algorithm has higher convergent speed and global searching capability.
Key words: genetic algorithm; time window; VRP; gene pool
车辆路径问题（Vehicle Routing Problem-VRP）是物流配送中的关键问题之一，最早由Dantzing和Ramser于1959年提出[1]，是典型的NP-hard问题。而有时间窗约束的车辆路径问题（Vehicle Routing Problem with Time Window-VRPTW ）则是VRP的一个特例，它考虑了需求在时间上的约束，即要求车辆尽可能在时间窗以内到达客户点，现实意义更强。众所周知，对于NP-hard问题，采用精确式算法得出确定的最优解往往是不可行或不经济的，而更为有效的方法则是通过某种启发式算法找到问题的近优解。其中遗传算法以其独特的算法形式和运行机理在复杂问题的求解中有着比较明显的优势。为此，本文采用改进的遗传算法对有时间窗约束的车辆路径问题进行了探讨研究，以寻找最优解为目标，在构造出VRPTW的一般模型后，着重阐述了改进遗传算法的设计，最后通过仿真计算取得了良好的效果。
1 VRPTW模型
给定一个配送中心，拥有若干载重相同的配送车辆。在配送中心周围分布有若干客户，每个客户有不同的货物需求。配送车辆装载一定数量的货物，按照预先分配好的线路行驶，在各个客户要求的服务时间窗内将货物送达。通过合理安排配送线路和次序，使得配送过程的总成本最小（见图1）。
为方便表示，建立如下符号体系：Z表示配送总成本；m为所需的配送车辆数；n代表需要服务的客户数量；Di,j表示从客户i到客户j的距离（i,j的取值从0到n）；c表示单位距离运输成本；gi表示客户i的需求量；q表示配送车辆的最大载重；[eti,lti]是客户i要求的服务时间窗；ti是配送车辆到达客户i的时间（t0是车辆从配送中心的出发时间），time是对每个客户的服务停留时间，speed是配送车辆的平均行驶速度。另外定义变量如：
本文采用罚函数的方法来处理时间窗约束，并设a、b分别为配送车辆提前和滞后到达客户的时间窗惩罚因子，则客户i处的时间窗成本为：
有了以上的符号体系，可以得到如下成本表示[3]：
距离运输成本：
(1)
超重成本：
(2)
时间窗成本：
(3)
其中DistanceCost计算的是各条线路的距离成本；CapacityCost计算的是各配送车辆由于超载所产生的成本，在现实生活中如果严防超载，可以将M系数设置成非常大（一般为1000000）即可；TWCost反应了配送车辆违背时间窗的惩罚成本。三种成本按照用户设定的权重值(W1,W2,W3)加权计算，就得到了配送总成本的表达形式：
(4)
2 改进的遗传算法
2.1 算法原理
遗传算法最初是由J.H.Holland等在70年代提出[2]，以自然选择和遗传理论为基础，模仿自然界优胜劣汰的进化机制，通过不断迭代最终得出最优解。本文对传统遗传算法的选择和变异操作进行改进，算法流程图见图2。
2.2 算法设计
2.2.1 编码
本文将按照配送车辆到达客户的先后顺序进行编码。假设有九个客户需要配送货物，分别命名为1,2，…9，配送中心为0，随机产生一个序列作为一条染色体如3 5 6 9 2 1 4 8 7 ，表示配送车辆到达的次序是客户3,客户5，…，最后到达客户7。现实应用中往往需同时派出多辆配送车运送货物，每辆配送车负责一条线路，对以上的染色体进行可行化处理――线路划分，这样每辆配送车能在不超载的情况下完成各自的配送任务，这样就很好的解决了车辆载重约束。线路划分算法如图3。
假设经过线路划分的染色体编码形式变为：
解码后：
2.2.2 适应度函数
适应度函数是衡量染色体接近最优解的程度，能有效地反映每一条染色体与问题最优解染色体的差距。由于我们在编码阶段已经通过线路划分完全消除了车辆超载的可能，因此我们在适应度的计算中只需考虑距离运输成本和时间窗成本。我们采用如下设计：
第w条染色体的适应度函数为fw
(5)
其中w1,w3分别为距离运输成本和时间窗成本的权重值，且0≤w1,w3≤1 , w1+w3=1.
2.2.3 遗传操作的改进
遗传操作包括选择、交叉和变异三个过程。在选择算子中本文在roulette wheel选择法的基础上进行改进，建立了世代基因库，用于存储进化过程中适应度很高的精英染色体。基因库中染色体按适应度大小排序且库大小设置为20，每次更新基因库时将新染色体按适应度大小插入，将适应度最小者剔除以保证基因库中的平均适应度不断提高（见图4） 。在选择染色体时将基因库中的染色体混入一般染色体中用于进一步进化。
交叉算子模拟的是自然界中的基因重组过程，本文采用部分匹配交叉（partially matched crossover , PMX）,在交叉过程中将隔离基因预先剔除，交叉完成后重新进行线路划分，以杜绝不可行解的出现。
变异过程是对染色体上一个或几个基因位进行随机替换。本文将传统多点变异改进成局部爬山变异，即变异有若干个候选变异方向，算子将按照其中最好的方向实施变异，以达到局部最优。设计如下：在染色体编码序列中随机产生三个位置（非隔离基因0）pos1, pos2, pos3作为变异点如：
pos1, pos2, pos3三个位置的编码值任意交换位置产生A33=6种组合，分别计算这六种组合所对应的编码序列的适应度函数，将适应度最高的染色体保留下来作为变异的结果。如此使得变异算子具有局部爬山能力，可使染色体只向有利的方向变异，提高收敛速度。
3 仿真实验及分析
3.1 仿真条件及参数设置
本文在Java Eclipse Galileo环境下进行了仿真，主机配置为Intel 双核处理器，CPU主频1.8GHZ，内存2.0GB，采用Java和SQL Sever2000编程实现。仿真数据如下：O是配送中心，坐标为[200,200]，配送车辆出发时间是8:00，A～J分别代表十个有配送需求的客户，客户信息见表1。算法参数为：种群大小=50，交叉概率=0.80，变异概率=0.01，终止代数=500，车辆最大载重=8.0，早于时间窗惩罚因子=10.0，晚于时间窗惩罚因子=10.0。
表1 客户信息表
3.2 仿真结果及分析
采用以上参数设置时经过687ms的计算取得了较为满意的计算结果见图6。结果显示，当种群进化到113代以后，配送车辆的规划路径已经不在发生变化（---OGFO---OAJHIO----OEDCBO----），并且总成本也趋于稳定直至254代以后完全固定在2244.098为止。图5则给出了最佳配送方案的直观展示，十个客户按照配送顺序被划分到①②③三个区域，分别由三辆配送车进行配送。
为验证本文改进遗传算法的可行性和有效性，分别采用传统遗传算法（SGA）、自适应遗传算法（ASA）和本文改进的遗传算法（IGA）对带时间窗VRP问题在相同实验环境和仿真数据下进行了100次对比仿真实验，结果如表2。
表2表明：对于本文的带时间窗VRP问题，改进遗传算法的选择和变异操作中要比另外两种算法复杂，但局部的复杂却提高了算法全局的进化效率，收敛时间大为缩短。而且当问题规模较小时，三种方法虽都能得出最优解，但改进算法的最优解收敛次数却提高了13.64%以上。可见改进的遗传算法运算效率得到了提升而且全局搜索能力大大增强。
4 结束语
采用遗传算法处理带时间窗约束的车辆路径问题，其实质就是将约束条件转化到遗传算子的设计中，在成功处理了约束条件后，问题就简化为简单的TSP问题[6]，目前，具有较强实际意义的约束条件有载重约束、时间窗约束、路径长度约束、取货送货约束、回程约束和司机工作时间约束等等。随着约束条件的增加，遗传算法的设计难度也越大。因此，如何恰当的将各种约束条件进行转化成为解决车辆路径问题的关键，也是当前的研究热点。笔者希望通过本文的探讨研究能为VRP问题的研究者提供参考。
参考文献：
[1] CORDEAU J F,LAPORTE G.A unified tabu search heuristic for vehicle routing problems with time window[J].Journal of the Operational Research Society,2001,52(8):928-936.
[2] Holland J H.Adaptation in Natural and Artificial System[M].Mit Press,Cambridge,Mass,1975.
[3] 陈湘州,杨勇,王俊年.一种改进的自然数编码遗传算法在非满载时间窗车辆优化调度问题中的应用[J].长沙电力学院学报:自然科学版,2004,19(2):56-59.
[4] 孙曦,蔡临宁.带时间窗的车辆路由问题的改进遗传算法[J].工业工程与管理,2007(3):16-20.
[5] 孙辉.遗传算法在物流企业配送业务中的应用[D].吉林大学数学所,2005.
[6] 李大卫,王莉,王梦光.遗传算法在有时间窗车辆路径问题上的应用[J].系统工程理论与实践,1999,19(8):65-69.
关键词：无人机；航路规划；动态规划算法；启发式算法；遗传算法
1 无人机航路规划问题的描述
无人机航路规划是依据地形信息和执行任务环境条件信息，综合考虑无人机的性能、到达时间、耗能、威胁以及飞行区域等约束条件，为无人机规划出一条或多条自出发点到目标点的最优或可行的飞行航路，保证无人机高效、圆满地完成飞行任务，并安全返回基地[1]。其本质是多约束条件下最优或可行解的求解问题。无人机航路规划一般分两步：首先是飞行前预规划，即根据既定任务，结合环境限制与飞行约束条件，从整体上制定最优参考路径并装订特殊任务；其次是飞行过程中的重规划，即根据飞行过程中遇到的突发状况，如地形、气象变化、未知限飞禁飞因素等，局部动态的调整飞行路径或改变动作任务（如图1所示）。
从框图中可知，按照任务环境模型是否实时变化，即无人机飞行环境是否确定，航路规划可分为已知威胁信息环境下航路规划和未知威胁信息环境下航路规划。已知威胁信息环境下航路规划根据无人机飞行环境的确定信息，在无人机执行任务之前就可以进行规划设计，这一过程一般在无人机起飞前完成，实时性要求不高；未知威胁信息环境下航路规划通过无人机对环境变化更新后，在飞行中对航路进行重规划，实时性要求较高。
2 无人机航路规划约束条件
2.1 飞行环境限制
无人机在执行任务时，会受到如禁飞区、障碍物、险恶地形等复杂地理环境的限制，因此在航路规划时，应尽量避开这些区域，可将这些区域在地图上标识为禁飞区域，以提升无人机工作效率。此外，飞行区域内的气象因素也将影响任务效率，应充分考虑大风、雨雪等复杂气象下的气象预测与应对机制。
2.2 无人机物理限制
⑴最小转弯半径：由于无人机飞行转弯形成的弧度将受到自身飞行性能限制，它限制无人机只能在特定的转弯半径范围内转弯。⑵最大俯仰角：限制了航迹在垂直平面内上升和下滑的最大角度。⑶最小航路段长度：无人机飞行航路由若干个航点与相邻航点之间的航路段组成，在航路段飞行途中沿直线飞行，而到达某些航点时有可能根据任务的要求而改变飞行姿态，最小航路段长度是指限制无人机在开始改变飞行姿态前必须直飞的最短距离。⑷最低安全飞行高度：限制通过任务区域最低飞行高度，防止飞行高度过低而撞击地面而坠毁。
2.3 飞行任务要求
无人机具体执行的飞行任务主要包括到达时间和进入目标方向等，需满足如下要求：⑴航路距离约束：限制航路长度不大于一个预先设定的最大距离。⑵固定的目标进入方向：确保无人机从特定角度接近目标。
2.4 实时性要求
当预先具备完整精确的环境信息时，可一次性规划自起点到终点的最优航路。而实际情况是难以保证获得的环境信息不发生变换；另一方面，由于任务的不确定性，无人机常常需要临时改变飞行任务。在环境信息变化区域不大的情况下，可通过局部更新的方法进行航路的在线重规划；而当环境变化区域较大时，无人机航路规划系统则必须具备在线重规划功能。
3 无人机航路规划算法
由于无人机所处的战场环境异常复杂辽阔，规划约束条件众多，各因素之间又存在强耦合，再加上无人机自身独特的控制方式，航路规划在处理这些因素时面临极大挑战。Canny在1988年就已经证明航路规划是一个NP问题，对其直接求解往往导致组合爆炸。为了加速规划进程，近年来国内外学者已提出了许多不同的规划方法。下面对已有的规划方法加以概述。
3.1 动态规划算法
动态规划是分阶段决策过程的最优化方法。动态规划法是对于存在多个空中封锁和地面障碍等多约束的情况下，采用航路图分类法进行航路规划。无人机根据约束，在有限的探测和处理范围内，根据不同的滚转角度，得到下一时刻无人机可能到达的位置，并在新的飞行点上，计算再下一时刻的位置。以此类推，得到一棵航路树，比较树枝终点的性能指标并找到代价最小的节点，反向搜索其父节点，得到最优航路。
动态规划法模型简单，对地形要求不高，算法不依赖于威胁场的连续性，容易实现。但由于动态规划算法具有维数爆炸特性，如果在大范围内进行动态搜索，计算机无法处理大量信息，因此动态规划算法适于小范围内航路规划，对于范围较大的区域会出现组合爆炸。
3.2 启发式算法
启发式算法是指通过寻求一种能产生可行解的启发式规划，找到问题的一个最优解或近似最优解。启发式算法比较典型的是启发式A*搜索法，是利用问题拥有的启发信息来引导搜索，以达到减少搜索范围，降低问题复杂度的目的。启发式搜索首先定义以下代价函数：f（M）=g（M）+h（M）
式中：g（M）为启发式因子，表示从初始节点到当前节点M的真实代价；h（M）表示从当前节点M到目标节点的最小代价估计值；f（M）则表示从初始节点经M到目标节点的最小代价路径的估计值。搜索的原则是优先扩展f（M）小的节点，最终搜索得到最优航路（如图2所示）。
启发式算法由于提供了智能搜索，因此大幅度提高了搜索效率。用启发式A*搜索法进行航路搜索时，由于需要综合考虑各种因素，获得一条最优航路需要很长的收敛时间和极大的内存空间，因此不适于实时求解。为此，Robert J.Szczerba等人提出了一种用于二维规划的稀疏A*搜索算法。该算法结合航路约束有效地消减搜索空间，大大缩短了搜索时间，节省了内存空间，较好地满足了实时性要求。
3.3 遗传算法
遗传算法提供了一种求解复杂问题的通用框架，它仿效生物的遗传和进化机制，借助复制、杂交、变异等操作，使所要解决的问题从初始解一步步逼近最优解。其5个要素包括染色体编码、初始群体、适应度函数、遗传操作和控制参数。很多学者都将遗传算法用行器的航路规划求解。
在角频率组固定的情况下，使用幅值组构造一条染色体，其基因位置表示对应的角频率，数值代表相应的幅值。应用该型染色体构造方法进行遗传搜索得到的优化航路（如图3所示）。
遗传算法计算速度快，得到的航路满足无人机机动性能，无须再进行平滑处理，所得航路能够严格经过起始点和目标点，但是容易产生早熟现象，不能得到最优解。Juris Vagners等人通过采用多种群并发计算，通过竞争机制优选的思想来解决遗传算法的早熟现象。Ioannis K.Nikolos等人采用更能符合实际的B样条曲线来表示航路，对无人机全局和局部航路进行规划，得到了较好的结果。
综上，无人机航路规划有多种算法，既有适于小范围的规划算法，可在无人机上进行动态修改；又有适于大范围的规划算法，可在已知信息下求得全局最优解；既能进行人为的智能规划，又能在一定范围内进行模型的自动求解。应在具体问题具体分析基础上，发展高效的无人机航路规划方法。
随着无人机所要执行的任务越来越复杂，加上环境的不确定性，对航路规划的要求也将越来越高。未知威胁信息环境下的实时航路规划将是未来研究的重点，高效的全局搜索方法和局部搜索方法，二者混合使用将是无人机航路规划的一种趋势。
[参考文献]
[1]J.F.Gilmore.Autonomous vehicle planning analysis methodology[J].In：The Proceeding of American Control Conference，Kluwer.Boston，MA，1991.
