多智能体中央式协同路径规划算法综述

协同路径规划是实现多智能体协同作业的一项关键技术,需要保证行进至目标点前智能体间无碰撞,同时满足规划轨迹平滑性、规划时间有效性等要求。在明确多智能体协同规划问题的基础上,根据算法原理,将中央式协同路径规划算法分为基于A~*搜索、基于冲突搜索、基于安全间隔路径、基于代价增长树、基于规约算法以及其他算法,简单阐述各算法原理。研究发现,基于冲突搜索的协同路径规划算法因其计算质量及速度优势成为当前的主流算法,以此为基础进行改进成为当前研究热点。单一类型的算法对不同智能体规模及场景下的适应能力有限,多类型算法融合及智能化方法的介入将成为未来多智能体协同规划的发展趋势。

时态图顶点介数中心度计算方法

在社会网络分析中,介数中心度用于衡量顶点对网络结构的贡献大小,是一种广泛使用的顶点重要度衡量指标.该指标主要通过计算经过顶点的最短路径数来表明顶点的重要性.目前研究的介数中心度算法主要聚焦在普通图上,针对时态图的研究工作较少.普通图介数中心度计算方法主要依据Brandes算法设计,Brandes算法有效的关键理论是最短路径的子路径依然是最短路径,即最优子结构特性.然而时态图包含时态信息,时态路径类型多样,并且时态最短路径并不满足此特性,因此普通图介数中心度计算理论与方法不再适用于时态图.鉴于此,定义了严格(时态递增)和非严格(时态非递减)2种时态路径类型,并研究了时态图介数中心度计算理论与方法.提出了一种高效的基于消息传播的2阶段迭代计算框架.第1阶段采用自顶向下的广度优先遍历方式计算时态最短路径;第2阶段采用自底向上的方式计算顶点的后继节点和孩子节点对其介数中心度的贡献值,并设计了基于消息传播机制的迭代累积计算方法.为了提高效率和可扩展性,实现了基于OpenMP(open multiprocessing)框架的多线程并行算法FTBC(fast temporal betweenness centrality).基于8个真实的时态图数据集实验结果表明,与现有方法相比,提出的介数中心度计算方法具有更优的计算性能.

复杂社会网络的介数性质近似计算方法研究

随着计算机和互联网的迅猛发展,面向互联网的社会网络挖掘和分析成为一个新的课题。从互联网挖掘的社会网络往往规模巨大,这对网络分析算法的性能提出了更高的要求。介数值作为图的重要结构性质,广泛应用于基于图的聚类、分类算法,如何降低其计算的复杂性是急需解决的问题。目前,常用的方法是利用对最短路径长度的近似来降低网络分析算法的复杂性,但已有的近似方法没有考虑现实大规模网络的复杂网络特性,对最短路径长度的近似方法也不能直接用于介数值的近似。本文提出了一种新的介数近似计算方法,其基本思想是结合复杂网络的结构特性,利用通过网络中枢节点的路径来近似最短路径,以近似的最短路径求得介数的近似值。这为图的结构性质的近似估算提供了一种新颖的思路。通过与传统的介数计算方法和近似方法进行实验比较,验证了本文的算法能够大幅降低计算复杂性,并保持较高的近似有效性,并通过对实验数据的分析得到了若干有益的结论,为进一步的研究工作奠定了基础。

二次半定规划一个原始对偶路径跟踪算法

本文提出求解二次半定规划的一个基于H..K..M方向的原始对偶路径跟踪算法.文中首先导出确定H..K..M方向的线性方程组,并证明该搜索方向的存在唯一性;然后给出算法的具体步骤,并证明算法产生的迭代点列落在中心路径的某个邻域内.最后采用Matlab(R2011b)数学软件编程对算法进行数值试验.数值结果表明算法是有效的.

结合集中式与分布式特征的多路径QoS组播路由协议

提出了一个结合集中式算法与分布式算法优点的多路径启发式QoS组播路由算法和协议,它以单播路由协议OSPF传播链路的代价信息为基础,运用最小代价Dijkstra算法计算端节点到当前在树节点的最小代价路径,然后启动一个分布式计算过程得到一个可选路径集,加入节点通过一个综合性启发式选择其中的最佳路径连接到组播树.算法能够有效地支持延时和带宽受限的代价优化组播树构造,具有无环选路、呼叫接收成功率高、呼叫建立时间短、伸缩性好等特点.

线性权互补问题的改进全牛顿步不可行内点算法

权互补问题是指在一个流形与一个锥的交集上找到一向量对,使得这对向量的某代数积等于一个给定的权向量。当权向量为零时,权互补问题退化为互补问题。作为互补问题的非平凡推广,权互补问题可用于求解科学、经济和工程中的诸多均衡问题,且在某些情况下可以产生更高效的算法。考虑非负象限上的一类线性权互补问题,提出了一种改进的全牛顿步不可行内点算法来求其数值解。通过推广线性优化的全牛顿步不可行内点算法,给出了线性权互补问题的扰动问题、中心路径及其诱导的牛顿方向。算法构造了线性权互补问题的一系列扰动问题的严格可行点;每一步主迭代由一个可行步和若干个中心步组成,且都采用全牛顿步,因而无需计算步长;在每一步迭代,算法的可行性残差和权向量残差都以相同比率减少;运用中心步的二次收敛结果,为可行步提供了一个稍宽的邻域。通过分析算法的可行步,中心步和收敛性,得到了算法的全局收敛性和多项式时间复杂度。最后,数值算例验证了算法求解线性权互补问题的有效性。

线性规划的非可行的内点算法

首先简要介绍非可行的内点算法,然后提出一种新的中心路径的取法,并由此给出一个对Kojima-Megiddo-Mizuno算法的改进的方法,这一新的算法是具有O(n2L)次收敛性的算法,并对这一算法的收敛性加以证明,这一新的算法与其它算法最明显的差异是不必假设LP解的存在性,就可以证明原始—对偶问题的多项式时间收敛性。文章的最后通过数值实验将该算法与Ye的解决线性规划的中心路径算法进行了比较。比较的结果显示新的算法从各个方面都要优于Ye的算法。

Floyd算法在中心小学选址上的应用

中心小学选址是一个非常重要的问题。是将地理信息作为选址的主要依据,将几个相邻的村子的地理信息抽象成数学当中的图,然后用图论中求中心点和中位点的方法来确定中心小学的位置。在求中心点、中位点时要用到图论中最短路径算法,对经典的最短路径算法Floyd算法作了介绍。最后,用实例来分析中心点与中位点选址模型,并对中位点模型作了进一步分析。

单调加权互补问题的路径跟踪算法

加权互补问题是线性互补问题的推广模型,具有重要的应用背景.分析了加权互补问题的中心路径及其邻域,基于新定义的邻域,提出了求解单调加权互补问题的一个路径跟踪算法.取邻域中一点为初始点,证明了算法的O(nL)迭代复杂性.当加权互补问题中的权向量w为零向量时,该中心路径及其邻域和线性互补问题中的定义相同,该算法即为求解线性互补问题的宽邻域路径跟踪算法.

基于改进蚁群算法的室内移动机器人路径规划

近年来,路径规划作为移动机器人研究领域中的一个核心课题而备受关注。使用传统蚁群算法为移动机器人规划路径时,搜索容易陷入局部最优,并且收敛速度比较慢,针对这一缺陷,借鉴狼群分配原则对蚁群信息素的更新方式加以改进,避免了蚁群算法陷入局部最优,同时加快了算法收敛速度。然后,综合考虑室内移动机器人路径的长度和平滑度等性能指标,提出一种中心节点替换的平滑方法,使蚁群算法所规划出的路径长度缩短,同时去除了路径中的尖锐转角,提高了路径的平滑性。栅格环境下的仿真结果显示,改进后算法可以规划出更加平滑的路径曲线,且路径长度和算法迭代次数有明显减少,证明改进蚁群算法能有效地应用于室内移动机器人路径规划。

线性权互补问题的一种改进全牛顿步可行内点算法

通过构造中心路径的新等价变换,提出求解线性权互补问题的一种改进全牛顿步可行内点算法。基于全牛顿步搜索方向,分析该算法的可行性和多项式时间复杂度,最后通过数值算例验证了算法的有效性。

多目标半定规划的加权中心路径法

对于线性型多目标半定规划问题,引进加权中心路径的概念,并利用单目标半定规划的中心路径法,提出了求解多目标半定规划问题的加权中心路径法．先得到对应一个权向量的有效解,然后在此基础上,提出了通过一次迭代得到对应一定范围内其他任意权向量的有效解的一步修正方法．

水平线性互补问题的广义中心路径跟踪算法(英文)

对水平线性互补问题提出了一种广义中心路径跟踪算法.任意的原始-对偶可行内点均可作为算法的初始点.每步迭代选择"仿射步"与"中心步"的凸组合为新的迭代方向,采用使对偶间隙尽可能减小的最大步长.算法的迭代复杂性为O(nL).

基于多功能网的最短路径查询算法

在单一网络功能下节点间最短路径的研究基础上,提出基于多功能网的最短路径查询问题,给出一种基于贪心策略的查询算法来查询节点间在不同网络功能下的最短路径。利用多功能网对山东半岛城市群进行建模,分别查询城市群网络实现经济和信息两种不同功能时城市间的最短路径,并计算分析。研究结果表明,查询节点间在不同网络功能下的最短路径对于挖掘复杂系统不同功能间的潜在联系具有一定的现实意义。

凸二次半定规划一个新的路径跟踪算法

给出了求解凸二次半定规划一个原始-对偶路径跟踪算法。引进了中心路径函数,在每次迭代中,基于牛顿法和对称化技术计算NT方向作为搜索方向,证明了满NT步的可行性以及中心函数在新迭代点的性质。在一定条件下算法经0 (n1/2log[(n+1/4)η^0/ε])次迭代后得到一个ε-最优解。

线性权互补问题的全牛顿步可行内点算法

基于全牛顿步和中心路径,给出了线性权互补问题的全牛顿步内点算法,并证明了该算法的可行性和多项式时间复杂度。数值实验验证了算法的有效性。

中心式诱导路径优化计算方法

基于并行计算技术和网络数据存储方法,考虑了出行者的偏好,分析了多级网络分解方法和双端队列最短路径计算方法,提出了一种新的中心式诱导路径优化计算方法。以长沙市和长春市城市路网的实际数据为基础,在普通PC机群、联想服务器机群及惠普工作站机群3种不同计算性能的并行计算平台上进行试验测试。测试结果表明:使用网络数据存储方法,能够直接确定邻接节点与相应弧的存储位置,节点信息的查询时间明显减小;使用多级网络分解方法,主要路段作为被切割弧的概率降低,最短路径计算过程中处理器的通信量减小;使用双端队列最短路径计算方法,最短路径计算速度明显提升;使用新的计算方法,长沙市路网中400万条最短路径计算时间为46s,长春市路网中1 170万条最短路径计算时间为72s,完全能够满足中心式诱导路径优化时间小于5min的要求。

LMI优化的一种原对偶中心路径算法

系统和控制理论中许多重要的问题,都可转化为具有线性目标函数、线性矩阵不等式约束的LMI优化问题,从而使其在数值上易于求解.本文给出一种求解LMI优化问题的原对偶中心路径算法,该算法利用牛顿方法求解中心路径方程得到牛顿系统,并将该牛顿系统对称化以避免得到非对称化的搜索方向.文章详细分析了算法的计算复杂性.

凸二次半定规划一个长步原始对偶路径跟踪算法

本文基于Nesterov-Todd方向,并引进中心路径测量函数以及原始对偶对数障碍函数,建立了一个求解凸二次半定规划的长步路径跟踪法.算法保证当迭代点落在中心路径附近时步长1被接受.算法至多迭代O(n|lnε|)次可得到一个ε最优解.论文最后报告了初步的数值试验结果.

Fisher市场均衡问题的新全牛顿步可行内点算法

【目的】基于光滑中心路径的等价变换,提出一种新的求解Fisher市场均衡问题的线性权互补(Weighted linear complementarity problem, WLCP)模型的全牛顿步可行内点算法。【方法】扰动WLCP,构造光滑中心路径的新代数等价形式,运用牛顿法得到新搜索方向,从而提出求解Fisher市场均衡问题的全牛顿步可行内点算法。【结果】算法采用全牛顿步避免线搜索,提高计算效率,且具有可行性和多项式复杂度。【结论】初步数值结果表明算法有效。