Mixed deterministic and probabilistic networks

The paper introduces mixed networks, a new graphical model framework for expressing and reasoning with probabilistic and deterministic information. The motivation to develop mixed networks stems from the desire to fully exploit the deterministic information (constraints) that is often present in graphical models. Several concepts and algorithms specific to belief networks and constraint networks are combined, achieving computational efficiency, semantic coherence and user-interface convenience. We define the semantics and graphical representation of mixed networks, and discuss the two main types of algorithms for processing them: inference-based and search-based. A preliminary experimental evaluation shows the benefits of the new model.     

Integrating integer programming and probabilistic deduction graphs for probabilistic reasoning

Optimal solutions of several variants of the probabilistic reasoning problem were found by a new technique that integrates integer programming and probabilistic deduction graphs (PDG). PDGs are extended from deduction graphs of the and-type via normal deduction graphs. The foregoing variants to be solved can involve multiple hypotheses and multiple evidences where the former is given and the latter is unknown and being found or vice versa. The relationship among these hypotheses and evidences with possible intermediaries is represented by a causal graph. The proposed method can handle a large causal graph of any type and find an optimal solution by invoking a linear integer programming package. In addition, formulating the reasoning problem to fit integer programming takes a polynomial time. H.-L. Li was visiting the Department of Computer Sciences, University of North Texas in 1988–1989. He is with the Institute of Information Management, National Chiao Tung University, Hsinchu, Taiwan, R.O.C.     

Comparison of probabilistic and deterministic optimizations using genetic algorithms

This paper describes an application of genetic algorithms to deterministic and probabilistic (reliability-based) optimization of damping augmentation for a truss structure. The probabilistic formulation minimizes the probability of exceeding upper limits on the magnitude of the dynamic response of the structure due to uncertainties in the properties of the damping devices. The corresponding deterministic formulation maximizes a safety margin with respect to these limits. Because this work was done in the context of an experimental comparison of the reliabilities of the resulting designs, antioptimization was used to maximize the contrast between the probabilities of failure of the two designs. This contrast maximization was also performed with a genetic algorithm. The paper describes the genetic algorithm used for the optimization and antioptimization, and a number of modifications to the antioptimization formulation intended to reduce the computational expense to an acceptable level. Optimal designs are obtained for both formulations. The probabilistic design shows a very significant improvement in reliability.     

A comparison of deterministic and probabilistic methods for indoor localization

Received signal strength indication fingerprinting (RSSIF) is an indoor localization technique that exploits the prevalence of wireless local area networks (WLANs). Past research into RSSIF systems has seen the development of a number of algorithmic methods that provide effective indoor positioning. A key limitation, however, is that the performance of these methods is heavily dependent on practical implementation parameters and the nature of the test-bed environment. As a result, past research has tend to only compare algorithms of the same paradigm using a specific test-bed, and thus making it difficult to judge and compare their performance objectively. There is, therefore, a critical need for a study that addresses this gap in the literature. To this end, this paper compares a range of RSSIF methods, drawn from both probabilistic and deterministic paradigms, on a common test-bed. We evaluate their localization efficiency and accuracy, and also propose a number of improvements and modifications. In particular, we report on the impact of dense and transient access points (APs) - two problems that stem from the popularity of WLANs. Our results show methods that average the distance to the k nearest neighbors in signal space perform well with reduced dimensions. Moreover, we show the benefits of using the standard deviation of RSSI values to exclude transient APs. Other than that, we outline a shortcoming of the Bayesian algorithm in uncontrolled environments with highly variable APs and RSSI values, and propose an extension that uses a mode filter to restore its accuracy with increasing samples.     

概率规划的研究与发展

概率规划是智能规划研究的一个重要方面, 首先给出概率规划领域定义语言, 并介绍其语法及语义, 随后重点介绍了求解概率规划的各种方法, 如动态规划、启发式动态规划和基于规划图的方法等, 并分析了各种方法的特点. 最后对国际概率规划比赛进行了介绍.     

Causal graphs and structurally restricted planning

The causal graph is a directed graph that describes the variable dependencies present in a planning instance. A number of papers have studied the causal graph in both practical and theoretical settings. In this work, we systematically study the complexity of planning restricted by the causal graph. In particular, any set of causal graphs gives rise to a subcase of the planning problem. We give a complete classification theorem on causal graphs, showing that a set of graphs is either polynomial-time tractable, or is not polynomial-time tractable unless an established complexity-theoretic assumption fails; our theorem describes which graph sets correspond to each of the two cases. We also give a classification theorem for the case of reversible planning, and discuss the general direction of structurally restricted planning.     

Systematic and deterministic graph minor embedding for Cartesian products of graphs

The limited connectivity of current and next-generation quantum annealers motivates the need for efficient graph minor embedding methods. These methods allow non-native problems to be adapted to the target annealer’s architecture. The overhead of the widely used heuristic techniques is quickly proving to be a significant bottleneck for solving real-world applications. To alleviate this difficulty, we propose a systematic and deterministic embedding method, exploiting the structures of both the specific problem and the quantum annealer. We focus on the specific case of the Cartesian product of two complete graphs, a regular structure that occurs in many problems. We decompose the embedding problem by first embedding one of the factors of the Cartesian product in a repeatable pattern. The resulting simplified problem comprises the placement and connecting together of these copies to reach a valid solution. Aside from the obvious advantage of a systematic and deterministic approach with respect to speed and efficiency, the embeddings produced are easily scaled for larger processors and show desirable properties for the number of qubits used and the chain length distribution. We conclude by briefly addressing the problem of circumventing inoperable qubits by presenting possible extensions of our method.     

Superposition: composition vs refinement of non-deterministic,action-based systems

The traditional notion of superposition has been used for supporting two distinct aspects of parallel program design: composition and refinement. This is because, when trace-based semantics of concurrency are considered, which is typical of most formal methods, these two relationships are modelled as inclusion between sets of behaviours. However, when forms of non-deterministic behaviour have to be considered, which is the case for component and service-based development, these two aspects do not coincide. In this paper, we show how the two roles of superposition can be separated and supported at the language and semantic levels. For this purpose, we use a categorical formalisation of program design in the language CommUnity that we are also using for addressing architectural concerns, another area in which the distinction between composition and refinement is particularly important.Correspondence and offprint request to: Antónia Lopes, orgdivisionDepartment of Informatics, Faculty of Sciences, University of Lisbon, Campo Grande, 1749-016 Lisbon, Portugal.Received November 2002 Accepted in revised form June 2003 by B.T. Denvir and E. Boiten     

Ensemble-based clustering of large probabilistic graphs using neighborhood and distance metric learning

Graphs are commonly used to express the communication of various data. Faced with uncertain data, we have probabilistic graphs. As a fundamental problem of such graphs, clustering has many applications in analyzing uncertain data. In this paper, we propose a novel method based on ensemble clustering for large probabilistic graphs. To generate ensemble clusters, we develop a set of probable possible worlds of the initial probabilistic graph. Then, we present a probabilistic co-association matrix as a consensus function to integrate base clustering results. It relies on co-occurrences of node pairs based on the probability of the corresponding common cluster graphs. Also, we apply two improvements in the steps before and after of ensembles generation. In the before step, we append neighborhood information based on node features to the initial graph to achieve a more accurate estimation of the probability between the nodes. In the after step, we use supervised metric learning-based Mahalanobis distance to automatically learn a metric from ensemble clusters. It aims to gain crucial features of the base clustering results. We evaluate our work using five real-world datasets and three clustering evaluation metrics, namely the Dunn index, Davies–Bouldin index, and Silhouette coefficient. The results show the impressive performance of clustering large probabilistic graphs.

     

基于改进的随机路径图及和声算法的舰船航线规划

针对海上航行中障碍物躲避问题,提出改进的随机路径图及和声算法为舰船进行航线规划.该算法首先利用改进的随机路径图,在障碍物边缘、起点与终点连线等关键区域进行节点设置及扩充,根据舰船及障碍物运动特征,分阶段在海图上设置节点并连接,利用较少的节点生成完备的路径网络图,基于此选择节点生成初始全局航线;其次利用改进的和声算法对航线进行优化,障碍物的运动特性导致解空间为复杂的多峰形态,为避免节点位置变动导致新生成航线不可行,设置限定条件,仅对满足要求的航线利用航线交叉、消除节点、微调等策略进行优化.实验结果表明,相较对比算法,所提算法能够有效生成更高质量的全局航线,且在优化过程中生成的不可行航线数量远低于其余几种算法,具有更高的可靠性及稳定性.     

State estimation and detectability of probabilistic discrete event systems

A probabilistic discrete event system (PDES) is a nondeterministic discrete event system where the probabilities of nondeterministic transitions are specified. State estimation problems of PDES are more difficult than those of non-probabilistic discrete event systems. In our previous papers, we investigated state estimation problems for non-probabilistic discrete event systems. We defined four types of detectabilities and derived necessary and sufficient conditions for checking these detectabilities. In this paper, we extend our study to state estimation problems for PDES by considering the probabilities. The first step in our approach is to convert a given PDES into a nondeterministic discrete event system and find sufficient conditions for checking probabilistic detectabilities. Next, to find necessary and sufficient conditions for checking probabilistic detectabilities, we investigate the “convergence” of event sequences in PDES. An event sequence is convergent if along this sequence, it is more and more certain that the system is in a particular state. We derive conditions for convergence and hence for detectabilities. We focus on systems with complete event observation and no state observation. For better presentation, the theoretical development is illustrated by a simplified example of nephritis diagnosis.     

Rapidly exploring random graphs: motion planning of multiple mobile robots

Rapidly exploring random trees (RRT) and probabilistic roadmaps (PRM) are sampling-based techniques being extensively used for robot path planning. In this paper, the tree structure of the RRT is generalized to a graph structure which enables a greater exploration. Exploration takes place simultaneously from multiple points in the map, all explorations fusing at multiple points producing well-connected graph architecture. Initially, in a typical RRT manner, the search algorithm attempts to reach the goal by expansions, and thereafter furtherer areas are explored. With some additional computation cost, as compared to RRT with a single robot, the results can be significantly improved. The so-formed graph is similar to roadmap produced by PRM. However as compared to PRM, the proposed algorithm has a more judicious search strategy and is adaptable to the number of nodes as a parameter. Experimental results are shown with multiple robots planned using prioritization scheme. Results show the betterment of the proposed algorithm as compared to RRT and PRM techniques.     

Multi-objective probabilistic optimum monitoring planning considering fatigue damage detection,maintenance, reliability,service life and cost

Effective and efficient service life management is essential for a deteriorating structure to ensure its structural safety and extend its service life. The difficulties encountered in the service life management are due to the uncertainties associated with detecting and identifying structural damages, and assessing and predicting the structural performance. To reduce these uncertainties, continuous long-term structural health monitoring (SHM) can be employed. However, a rational and practical SHM planning is required to simultaneously maximize the accuracy, efficiency, and cost-effectiveness in service life management. This paper proposes a probabilistic optimum SHM planning based on five objectives to be simultaneously optimized: minimizing the expected damage detection delay, minimizing the expected maintenance delay, maximizing the damage detection time-based reliability index, maximizing the expected service life extension, and minimizing the expected life-cycle cost. The formulations of the five objectives are based on the probabilistic fatigue damage assessment. The monitoring plannings associated with both a single- and a multi-objective probabilistic optimization process (MOPOP) are investigated. For efficient decision making in identifying the essential objectives and selecting a well-balanced solution among the Pareto optimal solutions, the degree of conflict among objectives and objective weights are estimated. The novel approach proposed in this paper accounts for the interdependencies among the five objectives considered and demonstrates the role of the optimum SHM planning in service life management of deteriorating structures. The proposed MOPOP SHM planning is applied to the hull structure of a ship subjected to fatigue.     

A secondary decomposition based hybrid structure with meteorological analysis for deterministic and probabilistic wind speed forecasting

Accurate wind speed forecasting could ensure the reliability and controllability for the wind power system. In this paper, a new hybrid structure based on meteorological analysis is proposed for the wind speed vector (wind speed and direction) deterministic and probabilistic forecasting. Twelve kinds of secondary decomposition methods are employed to decrease the interference existing in the data. To improve the training efficiency and accelerate the sample selection process, active learning is employed. Four different wind speed datasets collected from Ontario Province, Canada, are utilized as case studies to evaluate the forecasting performance of the proposed structure. Experimental results show that the proposed structure based on meteorological analysis is suitable for wind speed vector forecasting and could obtain better forecasting performance. Furthermore, except accurate deterministic forecasts, the proposed structure also provides more probabilistic forecasting information.     

A study on the preliminary ship design method using deterministic approach and probabilistic approach including hull form

This paper describes a preliminary ship design method using deterministic approach and probabilistic approach in the process of hull form design. In the deterministic approach, an interdisciplinary ship design method integrates principal dimension decisions and hull form variations in the preliminary ship design stage. Integrated ship design, as presented in this paper, has the distinctive feature that these parameters are evaluated simultaneously. Conversely, in sequential design, which is based on the traditional preliminary ship design process, hull form designs and principal dimension decisions are determined separately and sequentially. The current study adopts the first method to enhance the design quality in the early design stage. Furthermore, a probabilistic approach is applied to ship design to resolve uncertainties in design information more efficiently than a deterministic approach would.     

Biological systems: Stochastic,deterministic or both

Many systems in nature, including biological systems, have very complex dynamics which generate random-looking time series. To better understand a particular dynamical system, it is often of interest to determine whether the system is caused by deterministic subsystems (e.g. chaotic systems), stochastic subsystems, or both. Although there are now several different approaches to determine this from time series data (e.g. correlation dimension and Lyapunov exponent calculations), these methods often require large amounts of stationary data (biological data is frequently nonstationary for long time scales), can often mis-identify certain systems, and can be subject to other technical problems. Alternatively, one can use methods that measure the complexity in a particular system which seldom make assumptions about a particular system, such as assuming the presence of stationarity. Additionally, mathematical and computational modeling techniques can be used to test different hypothesis about the dynamics of biological systems.     

Envelopes and waves: safe multivehicle collision avoidance for horizontal non-deterministic turns

International Journal on Software Tools for Technology Transfer - We present an approach to analyze the safety of asynchronous, independent, non-deterministic, turn-to-bearing horizontal maneuvers...     

基于障碍预估与概率方向权值的移动机器人动态路径规划

主要研究了移动机器人在未知动态环境中的路径规划问题.提出一种将障碍预估与概率方向权值相结合的动态路径规划新方法.该方法将卡尔曼滤波引入到规划算法中,使得对障碍物运动状态的实时有效预估成为可能.同时,为实现移动机器人的实时路径规划,提出一种新的概率方向权值方法,基于周期规划将障碍物与目标信息进行融合,能够有效处理室内环境下对于障碍物的速度和运动轨迹均未知的动态路径规划问题.仿真结果以及基于SmartROB2移动机器人平台所进行的实验结果验证了该方法的有效性和实用性.