对不确定规划中观测约简的进一步研究

从3个方面改进了不确定规划(non-deterministic planning,简称NDP)中的观测约简:一是如何找最小观测集合(minimal observation set,简称MOS),二是如何在观测代价不均等时找最优观测集合(optimal observation set,简称OOS),三是如何找到容错的OOS.通过MOS问题和图论中的最小覆盖集问题(minimal set cover,简称MSC)的类似性,可证MOS是NP难的问题,还可参考MSC算法得出时间复杂性不超过O(2^mm²)且不低于Ω(2^m?1)的算法,其中m是观测的个数.通过使用整数规划(integer programming,简称IP)技术,可找到OOS以及容错的OOS.可以证明,上述算法能够保证找到解,并且能够保证解的最优性.     

强循环规划的观察信息约简

在现实的规划领域中,观察信息的获得需要花费一定的代价,然而对于一个规划解来说,一些观察信息在执行规划解的过程中是不会被用到的,所以如何把这些不必要的观察信息去除从而节省实际过程中的成本是非常有必要的。针对强循环规划的观察信息展开研究,提出了一个对强循环规划观察信息进行约简的算法,该算法能够找出在完全可观察条件下强循环规划的最小观察变量集合,通过使用最小观察变量集合,可以进一步提高执行强循环规划解的效率。     

分层法求最小权值强规划解

在不确定规划领域中,以往对强规划解的研究侧重于解本身,很少考虑不确定转移系统执行动作所需的代价;而已有的研究最小权值强规划解的算法效率不高。针对这一问题,引入模型检测的强规划分层方法,设计了一种快速求解最小权值强规划解的算法。该算法首先将不确定规划问题中的状态进行强规划分层,然后利用分层信息反向搜索最小权值强规划解;且在搜索的过程中,根据算法策略,实时更新所需搜索层数的上界和下界,从而避免了大量的无用搜索,提高了搜索效率。实验表明:所设计的算法能快速求解出最小权值强规划解,求解效率比已有的直接求解最小权值强规划解的算法高;且分层数和动作数越大,优势越明显。     

不确定规划中的多Agent带权值强规化算法

在智能规划领域中,以往对不确定规划问题的研究主要集中于单个Agent,而对多Agent规划的研究则侧重于确定规划。针对该问题,提出基于多Agent的带权值不确定规划问题,对所求解的强规划解,设计使其所需动作权值总和近似最小的算法。根据基于模型检测的强规划分层方法,对每个Agent进行强规划分层,合并所有Agent的分层信息,并在合并的过程中得到同层状态之间的冲突表。在保证冲突最小的情况下,以最小动作权值优先的贪心方法,求出强规划解。实验结果表明,该算法能较快地求解出使所选择的动作权值总和近似最小的强规划解。     

不确定规划中一种观察信息高效约简算法

在不确定规划中,可通过观察周围的信息来区分多个状态,但周围的观察信息较多,因此如何从大量的观察信息中筛选必须的信息非常重要。以往算法是在直接搜索过程中增加一些剪枝条件来达到优化的目的,存在一定的局限性。在对观察信息约简研究中,为提高搜索效率,设计一种高效的不确定规划中观察信息约筒算法。该算法将规划问题转化为求解O—l矩阵的覆盖问题,使用数据结构十字链表来表示O-1矩阵,通过维护十字链表并采用启发式函数来加速求解一个最小观察变量集。实验结果表明,该算法不仅能够找最小观察变量集,而且运行速度超过同类算法。     

一种求解最小权值强规划的方法

以规划领域中的不确定状态转移系统作为研究对象,给出最小权值强规划解的概念,提出一种求最小权值强规划解的方法.该方法可以求解与动作代价相关的数值规划问题,在不确定状态转移系统的执行动作上增加权值来表示动作的代价,在此基础上设计求解最小权值强规划解的算法.实验结果表明,该算法能有效求解最小权值强规划解,且比用反向搜索方法求...     

空间机器人随机故障容错规划的蜜蜂算法

本文为解决复杂的随机规划问题设计了一种基于随机模拟的混沌量子蜜蜂算法,证明了该算法的收敛 性,并分析了算法的收敛速度．分析6 自由度空间机器人系统的不确定性,采用基于微分变换法进行误差分析,建 立了随机数学规划模型．为涉及故障前后运动学与动力学约束限制的容错轨迹规划,以加权最小驱动力矩为优化性 能指标,采用混沌量子蜜蜂算法求解全部工作时间中机械臂故障前后的最优轨迹．通过降低异常关节的运动速度来 降低故障关节力矩,保证机械臂在发生故障后具有较高的操作能力．案例研究验证了该算法的有效性、稳定性及准 确性．     

确定树求强规划解

定义了确定树,设计了求确定树的方法。基于该方法设计了求强规划解的算法,找到每个初始状态对应的确定树,在找到确定树之后,求强规划解不需要从目标状态一直搜索到初始状态,只需要从目标状态反向找到确定树的任意一个节点,再通过这个节点在确定树中反向搜索到初始状态从而得到一个强规划解。实验结果表明：所设计的算法比用反向搜索方法求强规划解的算法的效率高。     

部分可观察强规划中约减观察变量的研究

给出了一种约减观察变量方法——假设所有的状态变量都不是观察变量,在此基础上逐步增加必要的观察变量,从而最终得到一个必要的观察变量集合.在添加必要的观察变量过程中,该方法不要求得到所有变量的相关信息,从而具有更好的通用性.根据是否存在单个观察变量能够区分域中任意两个状态的问题,分别给出了两种约减观察变量方法:当存在一个观察变量可以区分规划域中任意两个状态时,算法可以得到一个最小的观察变量集合;当不存在这样一个观察变量时,算法可以得到一个尽可能小的观察变量集合,但不能保证该集合最小.     

基于蚁群算法的最小代价航迹规划仿真

在大比例尺地图的路径规划中,由于飞行器全局航迹规划需要计算机存储的栅格点数量巨大,存在维数爆炸问题,使得航迹解算计算量激增,因此提出1种改进的蚁群算法,将栅格由大及小进行划分,利用大栅格为飞行器选择相对平滑和离散度低的飞行地形,利用小栅格为飞行器提供相对精确的全局飞行航迹,将栅格带所有栅格的代价之和作为航迹代价,从而选出1条航迹代价最小的路径．该算法将蚁群算法的信息素更新机制更加合理地应用到航迹规划中．仿真结果表明,该方法能解决航迹维数解算问题,可以将一系列栅格点组成的路径点集合为最优解,为飞行器提供最优航迹规划路径．     

Supervisory control of switching control systems

In this paper, the problem of designing a switching policy for an adaptive switching control system is formulated as a problem of supervisory control of a discrete-event system (DES). Two important problems in switching control are then addressed using the DES formulation and the theory of supervisory control under partial observation. First, it is verified whether for a given set of controllers, a switching policy satisfying a given set of constraints on the transitions among controllers exists. If so, then a minimally restrictive switching policy is designed. Next, an iterative algorithm is introduced for finding a minimal set of controllers for which a switching policy satisfying the switching constraints exists. It is shown that in the supervisory control problem considered in this paper, limitations on event observation are the factors that essentially restrict supervisory control. In other words, once observation limitations are respected, limitations on control will be automatically satisfied. This result is used to simplify the proposed iterative algorithm for finding minimal controller sets.     

Aggregate keyword search on large relational databases

Keyword search has been recently extended to relational databases to retrieve information from text-rich attributes. However, all the existing methods focus on finding individual tuples matching a set of query keywords from one table or the join of multiple tables. In this paper, we motivate a novel problem of aggregate keyword search: finding minimal group-bys covering a set of query keywords well, which is useful in many applications. We develop two interesting approaches to tackle the problem. We further extend our methods to allow partial matches and matches using a keyword ontology. An extensive empirical evaluation using both real data sets and synthetic data sets is reported to verify the effectiveness of aggregate keyword search and the efficiency of our methods.     

Multisensor fusion for linear control systems with asynchronous, Out-Of-Sequence and erroneous data

This paper presents a set of new centralized algorithms for estimating the state of linear dynamic Multiple-Input Multiple-Output (MIMO) control systems with asynchronous, non-systematically delayed and corrupted measurements provided by a set of sensors. The delays, which make the data available Out-Of-Sequence (OOS), appear when using physically distributed sensors, communication networks and pre-processing algorithms. The potentially corrupted measurements can be generated by malfunctioning sensors or communication errors. Our algorithms, designed to work with real-time control systems, handle these problems with a streamlined memory and computational efficient reorganization of the basic operations of the Kalman and Information Filters (KF & IF). The two versions designed to deal only with valid measurements are optimal solutions of the OOS problem, while the other two remaining are suboptimal algorithms able to handle corrupted data.     

基于粗糙集和SAT算法的属性约简

粗糙集理论是80年代初由波兰数学家Z.Pawlak首先提出的一个分析数据的数学理论。该理论近几年来日益受到各领域的广泛关注,并已在机器学习、模式识别、决策分析、过程控制、数据库知识发现等广泛领域得到成功应用。论文提出了一种求最小约简的基于命题可满足性(简称SAT)算法的算法,提出一个解决SAT问题的分割和结合的算法。实验结果表明,论文所提算法在高度准确分类的基础上,所得约简中大大减少了规则的数目。     

Magnitude ordering of degree complements of certain node pairs in an undirected graph and an algorithm to find a class of maximal subgraphs

An undirected or a symmetric graph consists of a set of nodes and a set of nonoriented edges connecting between pairs of nodes. In widely differing disciplines of science and engineering, symmetric graphs find important uses. In many of these application areas, an often encountered problem is that of finding all the maximal complete subgraphs of a symmetric graph. In this paper, borrowing the concept of strong connectedness in a nonsymmetric graph, the idea of minimally strongly connected (MSC) and maximal minimally strongly connected (MMSC) subgraphs in a symmetric graph is introduced. The MMSC subgraphs play a kind of role identical to that played by maximal complete subgraphs in symmetric graphs. Many important properties of MMSC subgraphs are discussed in the paper, and an explicit, computer-oriented algorithm is developed for finding all the MMSC subgraphs, given an undirected graph.     

An analysis of self-diagnosis model by conditional fault set

Diagnosability and syndrome decoding of a self-diagnosis model is studied with a conditional fault set. The conditional fault set is a fault set which is induced under such a condition that some subset of units are faulty (or fault-free).The diagnosability defined on the model is generalized to include such information as (1) the maximum number of units to be identified as faulty; (2) the maximum number of units to be identified as fault-free; and (3) the maximum number of units whose states are definitely identified, when the upper bound on the number of faulty units is assumed.Furthermore, we discuss the problem of finding minimal fault set. This problem is formulated in mathematical programming with the conditional fault set. A syndrome decoding algorithm is also presented which uses the conditional fault set in a similar manner to Hamming distance used in syndrome decoding of error-correcting codes.     

Search methods for tile sets in patterned DNA self-assembly

The Pattern self-Assembly Tile set Synthesis (PATS) problem, which arises in the theory of structured DNA self-assembly, is to determine a set of coloured tiles that, starting from a bordering seed structure, self-assembles to a given rectangular colour pattern. The task of finding minimum-size tile sets is known to be NP-hard. We explore several complete and incomplete search techniques for finding minimal, or at least small, tile sets and also assess the reliability of the solutions obtained according to the kinetic Tile Assembly Model.     

Polynomial Time Algorithms for 2-Edge-Connectivity Augmentation Problems

Given a 2-edge-connected, real weighted graph G with n vertices and m edges, the 2-edge-connectivity augmentation problem is that of finding a minimum weight set of edges of G to be added to a spanning subgraph H of G to make it 2-edge-connected. While the general problem is NP-hard and 2 -approximable, in this paper we prove that it becomes polynomial time solvable if H is a depth-first search tree of G . More precisely, we provide an efficient algorithm for solving this special case which runs in O(M · α(M,n)) time, where α is the classic inverse of Ackermann's function and M=m · α(m,n) . This algorithm has two main consequences: first, it provides a faster 2 -approximation algorithm for the general 2 -edge-connectivity augmentation problem; second, it solves in O(m · α(m,n)) time the problem of restoring, by means of a minimum weight set of replacement edges, the 2 -edge-connectivity of a 2-edge-connected communication network undergoing a link failure.