一种分布式多主体规划算法

提出一种分布式多主体规划算法.在此算法中,主体规划之间的冲突检测与协调通过多主体协商来解决,即主体规划之间约束一致性的分布式判断.在确定环境中该算法是可靠的.由于算法中主体之间交换的只是与冲突有关的动作、因果链和约束,因此具有通信量小、安全性高的优点.     

具有并行约束目标的多主体系统动态角色分配

多主体系统已成为建模和开发大型复杂分布式信息系统的一种理想范型.很多基于主体技术的系统要求支持动态角色分配,而已有动态角色分配算法忽略了目标之间的约束对角色分配的影响.首先,提出一个具有并行约束目标的多主体系统动态角色分配模型,引入多个角色分配管理者主体共同承担角色分配的计算任务,避免因单个主体可能造成的计算瓶颈.然后,基于并行约束目标结构图,给出目标集划分算法.并设计实现了角色分配算法,分析了该算法的时间复杂度.最后,实验研究了角色分配算法的执行时间,表明理论分析与实验结果一致.基于目标集合划分对角色分配的计算任务进行分割,使得各个角色分配管理者主体的计算结果无需进行合并再进行并行约束检查.     

以多人博弈效用函数为演化指导函数的演化算法

研究一种基于多人纯策略非合作博弈的演化优化算法,可用于一类组合优化问题的求解.该算法的演化过程可建模为一个马尔科夫链模型.它将组合优化问题映射为多人非合作博弈,通过博弈主体的理性行为对问题的解进行优化.给出定义良好并可供扩展的算法框架,明确算法的要素所必须满足的3个约束:有限性约束、弱一致性约束和收敛性约束,并应用于若干典型NP-Hard的组合优化问题的求解.理论和实验结果表明,与一些传统优化算法相比,本算法在实际应用中具有良好的问题求解能力.     

维修仿真中的混合碰撞检测算法

针对维修仿真中物体之间存在的穿越问题,提出一种混合碰撞检测处理算法。该算法结合轴向包围盒的快速性及几何约束的精确性,采用轴向包围盒改善虚拟人与虚拟物体之间的碰撞效果,运用几何约束算法解决虚拟人所携带零件与其他零件之间的穿越问题。实验结果表明,该算法的实时碰撞检测效果较优。     

基于多目标函数的电网拓扑关系约束规则的优化算法

用现有约束规则优化算法得到的电网拓扑结构无法获取其中环和根节点之间的连通路径，在寻找路径过程中功率损耗较大。为了解决这一问题，设计一种基于多目标函数电网拓扑关系约束规则的优化算法。应用小世界网络构建电网拓扑结构模型，求得幂律分布曲线，建立变电站来减少功率损耗；将有功网损最小、节点电压偏移最小作为目标函数，获得功率平衡方程，建立约束规则；采用粒子群算法求解最优参数，完成基于多目标函数的电网拓扑关系约束规则优化算法的设计。测试结果表明设计的优化算法能够获取电网结构的所有环和所有根节点之间的连通路径，功率损耗为11.31 kW,减小了功率损耗。     

多传感器系统含状态约束的分布式并行卡尔曼滤波算法

基于群智能建筑系统,提出一种含有状态约束的并行式卡尔曼滤波算法。算法通过物理约束建立方程,利用相邻节点间的约束关系和投影法计算出含有状态约束的卡尔曼滤波估计值,从而达到故障诊断与数据校核的目的。算法基于的分布式结构采用传感器网络节点的形式,每个节点有自身处理系统而不需要任何中心节点或中心通信设施。因此,本文提出的算法具有完全分布性,允许在多个测量节点之间独立计算。本文详细论述算法推导过程,并通过软件仿真与硬件测试,验证了算法的并行性、准确性和稳定性。     

一种工作流中的服务选择算法

与其他服务发现相比，工作流中的服务选择有着自身的特点。在目前情况下，大多数的服务选择只是从对服务本身需求的角度来考虑，并未涉及到多个服务之间的关联约束和协调性问题。而在工作流中，这些问题同样是影响服务选择的主要因素。本文提出一种服务选择算法，在该算法中，利用规则从多个方面来反映服务之间的约束关系并指导服务选择的方式，进一步对每个候选服务与相关联服务之间的兼容性进行了比较，最后得到一个同时满足自身和流程需求的服务。     

快速启发式多约束优化路径算法研究

针对QoS路由算法中多约束算法的不足,提出了一种新的多约束算法:快速启发式多约束优化路径算法(FH_MCOP)。与现有的路由算法相比,它有两个显著的不同:增加了一个λ快速计算机制,可以降低计算复杂度和加快计算速度,缩短算法响应时间;对MCOP算法进行了有效的改进,使计算结果达到优化。计算结果表明,FH_MCOP能针对多约束优化路径问题的特点降低计算量和提高计算速度。     

改进的半监督模糊聚类算法

针对Ｇｒｉｒａ等近期提出的利用点对约束的半监督模糊聚类算法,其约束项与竞争聚类算法（ＣＡ）的目标函数之间数量级不一致,造成隶属度调整过度的问题,在重新定义目标函数的基础上提出一种改进算法,约束惩罚函数采用约束点对中两个样本新的联合表达式,使数量级与经典模糊聚类算法一致．实验结果显示,新算法的约束项与ＣＡ目标函数之间能很好地协调合作,并能通过对模糊隶属度的适度调整,实现更准确的聚类．     

几何因果定性推理的基本原理和算法

因果定性推理是一种通过分析描述物理系统行为和关系的约束找出系统内部各个成分之间的因果结构的推理方法．本文提出一种基于约束和变量分析的因果定性分析模型和算法．该方法在产品设计中有广泛的应用，利用这个模型和算法可较好地解决参数化设计中的几何推理问题，还可用作概念设计的工具，用于完成复杂系统设计任务的划分及定序、设计变量之间相互依赖关系分析等工作．算法具有应用性强、效率和稳定性好、支持欠约束和多解问题等优点.     

Distributed constraint satisfaction with partially known constraints

Distributed constraint satisfaction problems (DisCSPs) are composed of agents connected by constraints. The standard model for DisCSP search algorithms uses messages containing assignments of agents. It assumes that constraints are checked by one of the two agents involved in a binary constraint, hence the constraint is fully known to both agents. This paper presents a new DisCSP model in which constraints are kept private and are only partially known to agents. In addition, value assignments can also be kept private to agents and not be circulated in messages. Two versions of a new asynchronous backtracking algorithm that work with partially known constraints (PKC) are presented. One is a two-phase asynchronous backtracking algorithm and the other uses only a single phase. Another new algorithm preserves the privacy of assignments by performing distributed forward-checking (DisFC). We propose to use entropy as quantitative measure for privacy. An extensive experimental evaluation demonstrates a trade-off between preserving privacy and the efficiency of search, among the different algorithms. Partially supported by the Spanish project TIN2006-15387-C03-01. Partially supported by the Lynn and William Frankel center for Computer Sciences and the Paul Ivanier Center for Robotics and Production Management.     

移动自组织网络中基于移动Agent 的多约束QoS 多播路由算法

提出了一种移动自组织网络中基于移动Agent 的多约束QoS 多播路由算法．算法采用移动Agent 采集 网络信息,每个源节点构造一棵具有带宽和能量约束的多播树,选择节点剩余能量多的作为中间转发节点,以延长 网络的生存时间．当数据传输过程中链路发生断裂时,算法修复局部路径,而不是重新发送数据包,有效地降低了 路由重构和数据重传的可能性．利用网络仿真工具NS2 系统进行了仿真实验,实验结果证明新算法具有很高的效率 和鲁棒性．     

Limited range spatial load balancing in non-convex environments using sampling-based motion planners

This paper analyzes the limited range, spatial load balancing problem for agents deployed in non-convex environments and subject to differential constraints which restricts how the agents can move. First, the (unlimited range) spatial load balancing problem is introduced and the minimization problem with area constraints is defined. Then, to extend the problem for limited ranges, two cost functions and a sub-partition are defined. The problems are then analyzed and the results prove the existence of a partition that satisfies the area constraints. The non-convex environment makes the problem difficult to solve in continuous-space. Therefore, a probabilistic roadmap is used to approximate agents’ cells via a graph. A distributed algorithm is proven to converge to an approximate solution. Finally, the convergence of the algorithm is shown in simulation.     

On decentralized negotiation of optimal consensus

A consensus problem consists of finding a distributed control strategy that brings the state or output of a group of agents to a common value, a consensus point. In this paper, we propose a negotiation algorithm that computes an optimal consensus point for agents modeled as linear control systems subject to convex input constraints and linear state constraints. By primal decomposition and incremental subgradient methods, it is shown that the algorithm can be implemented such that each agent exchanges only a small amount of information per iteration with its neighbors.     

Target tracking and obstacle avoidance for multi-agent networks with input constraints

In this paper, the problems of target tracking and obstacle avoidance for multi-agent networks with input constraints are investigated. When there is a moving obstacle, the control objectives are to make the agents track a moving target and to avoid collisions among agents. First, without considering the input constraints, a novel distributed controller can be obtained based on the potential function. Second, at each sampling time, the control algorithm is optimized. Furthermore, to solve the problem that agents cannot effectively avoid the obstacles in dynamic environment where the obstacles are moving, a new velocity repulsive potential is designed. One advantage of the designed control algorithm is that each agent only requires local knowledge of its neighboring agents. Finally, simulation results are provided to verify the effectiveness of the proposed approach.     

Distributed robust MPC for nonholonomic robots with obstacle and collision avoidance

Considering that the inevitable disturbances and coupled constraints pose an ongoing challenge to distributed control algorithms, this paper proposes a distributed robust model predictive control (MPC) algorithm for a multi-agent system with additive external disturbances and obstacle and collision avoidance constraints. In particular, all the agents are allowed to solve optimization problems simultaneously at each time step to obtain their control inputs, and the obstacle and collision avoidance are accomplished in the context of full-dimensional controlled objects and obstacles. To achieve the collision avoidance between agents in the distributed framework, an assumed state trajectory is introduced for each agent which is transmitted to its neighbors to construct the polyhedral over-approximations of it. Then the polyhedral over-approximations of the agent and the obstacles are used to smoothly reformulate the original nonconvex obstacle and collision avoidance constraints. And a compatibility constraint is designed to restrict the deviation between the predicted and assumed trajectories. Moreover, recursive feasibility of each local MPC optimization problem with all these constraints derived and input-to-state stability of the closed-loop system can be ensured through a sufficient condition on controller parameters. Finally, simulations with four agents and two obstacles demonstrate the efficiency of the proposed algorithm.     

基于模糊约束规划的自动协商

给出了一个基于模糊约束规划模型的自动协商系统。建立了模糊约束规划模型并利用模糊模拟、神经网络和遗传算法给出了求解Pareto最优解的混合智能算法;协商过程中卖方智能体根据神经网络拟合的效用函数并运行混合智能体算法得到当前协商步的Pareto最优解,避免了对大型商品数据库的反复搜索,为系统推向实际应用奠定了基础;协商模型仿真实验表明了协商系统返回的解与实际调查得到的用户偏好相一致。