基于优先级时间Petri网的实时嵌入式多核系统分析

已有的基于点区间优先级时间Petri网分析实时嵌入式多核系统的工作,存在以下不足:(1)点区间优先级时间Petri网只考虑每个任务的执行时间是一个固定值的情况,而更多的实际应用中每个任务的执行时间是在一个区间范围内,因此不能模拟这些应用;(2)没有实现从任务依赖图到点区间优先级时间Petri网的自动转化,不便于工程设计人员使用;(3)没有考虑任务间互斥访问共享变量的情况.为此,定义了优先级时间Petri网(Pri-TPN)以弥补第1个不足;定义带有资源分配与优先级的任务依赖图(TDG-RAP)以弥补第3个不足;给出从TDG-RAP到Pri-TPN的转化规则与算法以弥补第2个不足,以及基于Pri-TPN分析任务最坏执行时间与系统死锁的算法;开发工具软件,方便工程设计人员使用.

基于蚁群算法的多机器人协作策略

蚁群算法是一种通过对蚂蚁社会长期观察得来的优化算法 .它建立在蚁群的一种叫“外激励”的联系方式上 ,对解决一些分布式控制问题和复杂的优化问题十分有效 .将“外激励”这一概念引入多机器人系统中 ,设计了一种基于蚁群算法的多机器人协作策略 .这一策略可以解决多机器人系统在未知环境工作时所面临的一项艰巨的任务 :自主协作规划 .定义了多机器人系统在未知环境中可能存在的一个问题 :任务死锁 ;将衰减因子引入协作算法 ,以防止任务死锁的发生 ;通过仿真验证了算法的性能 .

未知环境中多Agent自主协作规划策略

针对多智能体(Agent)系统在未知环境中自主协作规划存在任务死锁及协作效率不高的问题,提出一种基于改进蚁群算法的多Agent协作策略,并用于多Agent协作搬运中。该方法将Agent所处位置和目标任务之间的距离以及信息素控制因子引入蚁群算法。实验结果表明,该方法相比没有引入距离因子的协作方法,协作效率更高;相比没有引入控制因子的协作方法,可有效防止任务死锁发生。

一种基于动态决策路径的网格任务调度算法

网格下的任务调度是一个NP问题.一些迭代算法例如遗传算法可以较有效地解决,但是迭代次数过多时间复杂度高.传统的启发式策略则往往会造成资源空闲时刻过多,反而延误整个程序的完成时间.采用一种"先调度、后优化"的思想,首先采用普通的启发式算法得到调度方案,然后根据得到的甘特图重新生成DAG图,生成决策任务和决策路径,采用启发式算法将决策任务尽可能提前调度到资源的空闲时段提前运行,达到缩短整个任务收敛时间的目的,同时给出任务之间的死锁判定方法.实验证明,新算法优于其他启发式算法.

静态检测Ada任务死锁的Petri网方法

文中提出了一种利用Ｐｅｔｒｉ网对Ａｄａ任务静态检测其死锁的方法．在检测时，首先建立Ａｄａ程序各单元的Ａｄａ网，再根据程序中各单元的关系将Ａｄａ网组装成完整的Ａｄａ网，然后对其作可达性分析来检测死锁．本文介绍了Ａｄａ网的建立和组装方法，对Ａｄａ网的特点作了理论上的分析。

日常养老情境的异构多机器人动态多任务分配

针对异构多机器人系统动态任务分配问题,基于多智能体技术,利用符合养老情境特点的多智能体组织结构,提出处理养老情境下任务类型相对固定的异构多机器人多任务动态分配机制.建立基于被服务对象满意度函数的投标值计算模型,兼顾多任务的动态分配与被服务对象的满意度.根据拓扑排序算法,提出多智能体系统死锁的检测及处理方法,解决执行智能体自锁、各执行智能体间互锁的问题.对不同任务情况在不同分配机制下的被服务对象满意度进行仿真.仿真结果表明,在避免死锁的情况下,所提机制能够兼顾养老情景下的动态任务分配和被服务对象的满意度.

AGVS循环死锁搜索算法的改进设计及其实现

为了解决国内AGVS在循环死锁搜索算法研究中存在的搜索循环死锁类型不全的问题,利用任务-资源图(task-resource graph,T-R图)提出一个改进算法.改进算法如下:首先,根据AGV的相对位置变化和执行任务的情况,利用T-R图对AGVS进行建模,然后根据循环死锁的T-R图特征,在每一个状态时刻下,使用图的强连通分支理论搜索循环死锁.当访问完所有状态时刻下的T-R图,也就找到了AGVS中的所有循环死锁.算例验证与理论分析均说明改进算法可以搜索到全部类型的循环死锁,解决了原算法存在的不足.根据改进算法开发的控制规则,可以有效避免新循环死锁的产生.同时指出,对改进算法稍加修改,可以找到AGVS中所有的循环死锁和非循环死锁.

浅议SQL Server中死锁的产生和解决对策

针对SQL Server事务处理中出现的死锁现象进行了分析,并用一个实例构造出了死锁的情形,观察了SQL Server对死锁现象的处理。文中还提出了若干避免出现死锁现象的对策。

自适应紧急控制系统中的多任务处理

自适应紧急控制系统中的在线预决策子系统是一个实时的多任务系统。针对它的特点,文中采用了一些多任务处理的关键技术,主要包括FIFO 算法和优先级调度算法相结合的多线程调度,基于管程的多线程同步与互斥的处理和基于软件狗检测、分级重新启动的死锁处理。试验结果表明这些技术的采用。

非死锁合同网协议驱动的多机分布式时序任务分配

针对多无人机协同任务分配的时序约束问题,提出了基于非死锁合同网协议(DF-CNP)的分布式时序任务分配方法,从理论上避免任务死锁,提升分配结果最优性。定义了局部信息条件下时序任务死锁判据,通过检测时序任务图环路状态与顶点可达性,判定分配方案的全局死锁状态,保证分配结果的可行性。定制了最近邻-深度优先混合搜索算法,在合同网排序过程中优先选择最近邻任务,并结合死锁判据递归回溯,在分布式架构下并行生成满足死锁约束的任务排序方案,提升分配结果的最优性。仿真对比结果表明:相比于非死锁遗传算法(TB-GA),DF-CNP在求解效率方面具有显著优势;与耦合约束一致性束算法(CBBA-TCC)相比,DF-CNP结果最优性明显提升。

动态仓储环境下的多机器人路径规划方法

针对动态仓储环境下多机器人运动过程中出现的拥塞死锁问题,利用路径长度、转弯数、路径惩罚函数建立小车单任务耗时模型。模型引入阻塞惩罚函数,移除可能发生阻塞的路径增加罚值。同时针对传统遗传算法路径规划操作过程中路径交叉变异导致路径中断不可用的情况,设计重复点交叉算子,在变异操作后检查路径合法性,使算法都是在可行的解空间上进行搜索。仿真实验表明,算法能指导机器人获得动态环境下的最优路径,同时算法收敛速度大大提高。

用于多机器人路径规划的一种改进蚁群算法

基于MATLAB平台,将改进的蚁群算法应用于多移动机器人的路径规划。为了避免多机器人协作时容易引起的"任务死锁",每当机器人选择到系统中所有机器人一起合作也无法完成的任务时,降低该任务的信息素浓度,使得机器人能够跳出该任务,从而得以顺利完成其他可完成的任务。仿真研究表明:该算法能明显改善多机器人路径规划性能,并且算法简单有效。

一种多任务系统的描述工具

ETP(Extelqded Timed Petri Net)是 Petri 同的一种扩充形式.ETP 中的位置有两种类型:(1)支配型位置;(2)非支配型位置.它的转移被赋予定时功能.在描述多任务系统时,支配型位置用来表示控制流,非支配型位置用来表示任务间通信、任务间相互作用.本文以 IRMX86为例介绍了 ETP 表示多任务系统的方法.并提出了一种实时系统死锁的分析方法.

优先级置顶算法在FlexRay线控转向系统中的应用研究

为解决FlexRay线控转向系统中常见的死锁问题,采用优先级置顶算法进行多任务动态调度。首先,分析FlexRay线控转向系统多任务动态调度过程中的死锁问题;然后深入研究优先级置顶算法防止死锁问题的原理;最后搭建双通道多冗余的FlexRay线控转向系统,进行重要系统参数配置。运行结果表明,未使用优先级置顶算法的FlexRay线控转向系统出现了死锁现象,使用优先级置顶算法进行动态任务调度之后,系统可正常运行,证明了算法有效性。

基于顺序扩展一致性包算法的多无人机分布式任务分配

以异构多无人机协同执行复杂的耦合多任务为背景,提出一种求解分布式任务分配问题非死锁的顺序扩展一致性包算法.首先,建立考虑任务载荷资源、任务时序、威胁区等约束条件的时序多任务分配模型;其次,对一致性包算法的任务包构建过程和冲突消解规则进行扩展,并设计一种基于有向图深度优先搜索的方法进行任务方案的死锁检测和修正,以实现无冲突和无死锁的任务分配;然后,将关联任务之间的时序约束转化为软时间窗约束,利用顺序分层的策略进行求解;最后,为了提高任务分配结果的可靠性,采用Dubins曲线路径将航路规划耦合到任务分配中.仿真实验表明,所提出的算法能够快速有效地求解异构多无人机分布式耦合多任务分配问题,具备良好的最优性和时效性.