Using Assumptions to Distribute CTL Model Checking

In this work we discuss the problem of performing distributed CTL model checking by splitting the given state space into several “partial state spaces” . The partial state space is modelled as a Kripke structure with border states. Each computer involved in the distributed computation owns a partial state space and performs a model checking algorithm on this incomplete structure. To be able to proceed, the border states are augmented by assumptions about the truth of formulas and the computers exchange assumptions about relevant states as they compute more precise information. In the paper we give the basic definitions and present the distributed algorithm.     

Assumption-based distribution of CTL model checking

In this paper we discuss the problem of performing distributed CTL model checking by splitting the given state space into several partial state spaces. The partial state space is modelled as a Kripke structure with border states. Each computer involved in the distributed computation owns a partial state space and performs a model-checking algorithm on this incomplete structure. To be able to proceed, the border states are augmented by assumptions about truth values of formulas and the computers exchange assumptions about relevant states to compute more precise information.     

SVM参数优化的AFMC算法

支持向量机的参数选择仍未有系统的理论指导,其优化选择一直是支持向量机的一个重要研究方向。考虑到人工鱼群算法优化支持向量机参数往往易陷入最优参数组合微小邻域的问题,构造了用于支持向量机参数优化的AFMC算法。该算法前期利用鱼群算法较好的并行寻优性能,能快速寻得问题的近似最优解,而后利用MonteCarlo法进行局部寻优,以实现快速、有效地获取强近优解。数值实验结果表明,该算法具有较好的分类性能和较快的寻优速度,验证了在支持向量机参数寻优中的有效性和可行性。     

满足匹配律的策略参数搜索决策模型

匹配律是决策理论的基本定律之一,它建立了对备选目标的偏好与所获奖励之间的对应关系.通过构建获得匹配律的策略模型,研究了该定律成立的可能机制.基于再励学习理论,提出了通过调整策略参数以满足决策目标的策略搜索模型.在该策略模型的基础上,通过设定简单的假设条件推导出满足匹配律的策略算法.理论分析和数值仿真结果均验证了算法的正确性.另一方面利用该算法模拟了经典的心理学与神经生理学的匹配行为实验.研究结果不仅对匹配行为给出了合理的解释,也为建立基于奖励的决策模型提供了一种有效的理论建模方法.     

Robust probabilistic planning with ilao

In probabilistic planning problems which are usually modeled as Markov Decision Processes (MDPs), it is often difficult, or impossible, to obtain an accurate estimate of the state transition probabilities. This limitation can be overcome by modeling these problems as Markov Decision Processes with imprecise probabilities (MDP-IPs). Robust LAO* and Robust LRTDP are efficient algorithms for solving a special class of MDP-IPs where the probabilities lie in a given interval, known as Bounded-Parameter Stochastic-Shortest Path MDP (BSSP-MDP). However, they do not make clear what assumptions must be made to find a robust solution (the best policy under the worst model). In this paper, we propose a new efficient algorithm for BSSP-MDPs, called Robust ILAO* which has a better performance than Robust LAO* and Robust LRTDP, considered the-state-of-the art of robust probabilistic planning. We also define the assumptions required to ensure a robust solution and prove that Robust ILAO* algorithm converges to optimal values if the initial value of all states is admissible.     

Snap-stabilization and PIF in tree networks

The contribution of this paper is threefold. First, we present the paradigm of snap-stabilization. A snap- stabilizing protocol guarantees that, starting from an arbitrary system configuration, the protocol always behaves according to its specification. So, a snap-stabilizing protocol is a time optimal self-stabilizing protocol (because it stabilizes in 0 rounds). Second, we propose a new Propagation of Information with Feedback (PIF) cycle, called Propagation of Information with Feedback and Cleaning (). We show three different implementations of this new PIF. The first one is a basic cycle which is inherently snap-stabilizing. However, the first PIF cycle can be delayed O(h ²) rounds (where h is the height of the tree) due to some undesirable local states. The second algorithm improves the worst delay of the basic algorithm from O(h ²) to 1 round. The state requirement for the above two algorithms is 3 states per processor, except for the root and leaf processors that use only 2 states. Also, they work on oriented trees. We then propose a third snap-stabilizing PIF algorithm on un-oriented tree networks. The state requirement of the third algorithm depends on the degree of the processors, and the delay is at most h rounds. Next, we analyze the maximum waiting time before a PIF cycle can be initiated whether the PIF cycle is infinitely and sequentially repeated or launch as an isolated PIF cycle. The analysis is made for both oriented and un-oriented trees. We show or conjecture that the two best of the above algorithms produce optimal waiting time. Finally, we compute the minimal number of states the processors require to implement a single PIF cycle, and show that both algorithms for oriented trees are also (in addition to being time optimal) optimal in terms of the number of states. WARNING: The concept of snap-stabilization was first introduced in [12]. The concept evolved over the last eight years. We take this evolution in consideration in this paper, which includes the early results published in [10] and [12]. In particular, infinite repetition of computation cycles is a requirement of self-stabilizing systems. This is not required in snap-stabilization because snap-stabilization ensures that the first completed computation cycle is executed according to the specification of the problem. The correctness proofs conform to this basic property.     

Explicit synchronisation of heterogeneous dynamics networks via three-layer communication framework

This paper addresses the explicit synchronisation of heterogeneous dynamics networks via three-layer communication framework. The main contribution is to propose an explicit synchronisation algorithm, in which the synchronisation errors of all the agents are decoupled. By constructing a three-layer node model, the proposed algorithm removes the assumptions that the topology is fixed and the synchronisation process is coupled. By introducing appropriate assumptions, the algorithm leads to a class of explicit synchronisation protocols based on the states of agents in different layers. It is proved in the sense of Lyapunov that, if the dwell time is larger than a threshold, the explicit synchronisation can be achieved for closed-loop heterogeneous dynamics networks under switching topologies. The results are further extended to the cases in which the switching topologies are only frequently but not always connected. Simulation results are presented with four single-link manipulators to verify the theoretical analysis.     

Self-configurable border landmark selection in wireless networks: Algorithms and applications

The nodes at the border of the self-configurable wireless network are commonly employed as landmarks for many applications, including infrastructureless localization, border detection, and routing. However, how to identify the best set of nodes as such landmarks is still an open problem. In this paper, we propose three algorithms for border landmark selection, namely: the Convex Hull-Based (CHB) algorithm, the Center Node Elimination (CNE) algorithm, and the Hierarchy-Structured (HS) algorithm. CHB works perfectly in theory and provides a deep insight into the landmark selection problem. At the same time, it is noticed that CHB is centralized and sensitive to errors in distance estimation. The CNE algorithm is a distributed approach, devised to gradually exclude the nodes in the “center” of the network until the desired number of nodes are left, which are employed as landmarks. While CNE works effectively in a small network, its high order computation complexity and communication overhead may eventually lead to scalability problem when it is applied in very large networks. To address this problem, we propose the HS algorithm for striking the balance between accuracy and complexity/overhead. In HS, we establish a hierarchical structure with multiple layers, and apply the CNE algorithm in an appropriate layer to identify an initial set of candidate nodes. The outcomes are then rectified through a recursive process, yielding the final landmarks. Three applications, including coordinates establishment, border detection, and landmark-based routing in general networks without location information, are introduced based on the selected landmarks. We carry out extensive simulations to compare the performance of our landmark selection algorithms and demonstrate their effectiveness in all of the applications.     

Affect expression in ECAs: Application to politeness displays

In this paper we present our embodied conversational agent (ECA) capable of displaying a vast set of facial expressions to communicate its emotional states as well as its social relations. Our agent is able to superpose and mask its emotional states as well as fake or inhibit them. We defined complex facial expressions as expressions arising from these displays. In the following, we describe a model based on fuzzy methods that enables to generate complex facial expressions of emotions. It uses fuzzy similarity to compute the degree of resemblance between facial expressions of the ECA. We also present an algorithm that adapts the facial behaviour of the agent depending on its social relationship with the interactants. This last algorithm is based on the theory of politeness by Brown and Levinson (1987). It outputs complex facial expressions that are socially adequate.     

A performance study of multiprocessor task scheduling algorithms

Multiprocessor task scheduling is an important and computationally difficult problem. A large number of algorithms were proposed which represent various tradeoffs between the quality of the solution and the computational complexity and scalability of the algorithm. Previous comparison studies have frequently operated with simplifying assumptions, such as independent tasks, artificially generated problems or the assumption of zero communication delay. In this paper, we propose a comparison study with realistic assumptions. Our target problems are two well known problems of linear algebra: LU decomposition and Gauss–Jordan elimination. Both algorithms are naturally parallelizable but have heavy data dependencies. The communication delay will be explicitly considered in the comparisons. In our study, we consider nine scheduling algorithms which are frequently used to the best of our knowledge: min–min, chaining, A^*, genetic algorithms, simulated annealing, tabu search, HLFET, ISH, and DSH with task duplication. Based on experimental results, we present a detailed analysis of the scalability, advantages and disadvantages of each algorithm.

FSM状态间逻辑条件检验的算法研究

有限状态机(FSM)是VLSI控制结构的一种映射,它的自动综合成为设计自动化的一个十分重要的环节和途径。本文讨论在FSM自动综合中输入阶段的状态间逻辑条件检验的问题,研究分析状态间逻辑条件检验的相互关系及影响,并提出了FSM状态间逻辑条件检验的优化算法,从而使时间复杂度降低,实现更加简便。最后,本文给出了优化算法的流程和一些实验结果,结果令人满意。     

Web cache management based on the expected cost of web objects

With the recent explosion in usage of the World Wide Web, Web caching has become increasingly important. However, due to the non-uniform cost/size property of data objects in this environment, design of an efficient caching algorithm becomes an even more difficult problem compared to the traditional caching problems. In this paper, we propose the Least Expected Cost (LEC) replacement algorithm for Web caches that provides a simple and robust framework for the estimation of reference probability and fair evaluation of non-uniform Web objects. LEC evaluates a Web object based on its cost per unit size multiplied by the estimated reference probability of the object. This results in a normalized assessment of the contribution to the cost-savings ratio, leading to a fair replacement algorithm. We show that this normalization method finds optimal solution under some assumptions. Trace-driven simulations with actual Web cache logs show that LEC offers the performance of caches more than twice its size compared with other algorithms we considered. Nevertheless, it is simple, having no parameters to tune. We also show how the algorithm can be effectively implemented as a Web cache replacement module.     

Nominally Robust Model Predictive Control With State Constraints

In this paper, we present robust stability results for constrained discrete-time nonlinear systems using a finite-horizon model predictive control (MPC) algorithm for which we do not require the terminal cost to have any particular properties. We introduce a definition that attempts to characterize the robustness properties of the MPC optimization problem. We assume the systems under consideration satisfy this definition (for which we give sufficient conditions) and make two further assumptions. These are that the value function is bounded by a K_infin function of a state measure (related to the distance from the state to some target set) and that this measure is detectable from the stage cost used in the MPC algorithm. We show that these assumptions lead to stability that is robust to sufficiently small disturbances. While in general the results are semiglobal and practical, when the detectability and upper bound assumptions are satisfied with linear K_infin functions, the stability and robustness are either semiglobal or global (with respect to the feasible set). We discuss algorithms employing terminal inequality constraints and also provide a specific example of an algorithm that employs a terminal equality constraint.     

A fast expected time algorithm for the 2-D point pattern matching problem

Point set pattern matching is an integral part of many pattern recognition problems. We study a randomized algorithm for the alignment approach to model-based recognition.Under certain mild assumptions we show that if our scene is a set of n points and our model is a set of m<n points our algorithm has expected running time for finding an occurrence of the model in the scene. This is significantly faster than any existing algorithms in the literature. We then describe some experimental results on randomly generated data using a practical version of our algorithm. These results agree well with the theoretical analysis.     

A trust region SQP-filter method for nonlinear second-order cone programming

In this paper, we consider the nonlinear second-order cone programming problem. By combining an SQP method and filter technique, we present a trust region SQP-filter method for solving this problem. The proposed algorithm avoids using the classical merit function with penalty term. Furthermore, under standard assumptions, we prove that the iterative sequence generated by the presented algorithm converges globally. Preliminary numerical results indicate that the algorithm is promising.     

基于越界重置和高斯变异的蝙蝠优化算法

针对蝙蝠算法个体越界、易早熟收敛的问题，提出一种基于越界重置和高斯变异的蝙蝠优化算法。新算法将飞越解空间边界的个体拉回解空间内，利用越界重置策略重新分配位置。通过高斯变异策略控制个体的搜索范围，使种群以最优解为中心向四周呈放射状搜索，增强了算法的局部搜索和全局寻优能力。蝙蝠算法在靠近目标解时响度和脉冲发射频率更新不协调，影响了算法的持续进化能力,通过线性渐变策略保证响度和脉冲发射频率的变化与算法持续进化相适应。研究了在解空间不同位置关系的情况下新算法和对比算法的优化能力，并结合实验数据对算法收敛稳定性进行分析。实验结果表明，提出的新算法具有较好的收敛速度和精度，其全局寻优能力和高维问题优化能力体现了很好的鲁棒性。     

Self-stabilizing strong fairness under weak fairness

Fairness assumptions have a great impact on distributed algorithms. They play a major role in determining the time complexity and the correctness of algorithms, since progress or freedom from various types of starvation may not be guaranteed without fairness assumptions. In this paper, we present a stabilizing deterministic algorithm allowing simultaneous execution of actions for strong fairness under weak fairness assumption, in addition, we show that the proposed algorithm yields a high degree of concurrency. We conclude the paper with some remarks on issues such as time optimal implementation of strong fairness and open problems related to fairness     

Tracking the best level set in a level-crossing analog-to-digital converter

In this paper, we investigate level-crossing (LC) analog-to-digital converters (ADC)s in a competitive algorithm framework. In particular, we study how the level sets of an LC ADC should be selected in order to track the dynamical changes in the analog signal for effective sampling. We introduce a sequential LC sampling algorithm asymptotically achieving the performance of the best LC sampling method which can choose both its LC sampling levels (from a large class of possible level sets) and the intervals (from the continuum of all possible intervals) that these levels are used based on observing the whole analog signal in hindsight. The results we introduce are guaranteed to hold in an individual signal manner without any stochastic assumptions on the underlying signal.