An evidential approach to SLAM,path planning,and active exploration

Probability theory has become the standard framework in the field of mobile robotics because of the inherent uncertainty associated with sensing and acting. In this paper, we show that the theory of belief functions with its ability to distinguish between different types of uncertainty is able to provide significant advantages over probabilistic approaches in the context of robotics. We do so by presenting solutions to the essential problems of simultaneous localization and mapping (SLAM) and planning based on belief functions. For SLAM, we show how the joint belief function over the map and the robot's poses can be factored and efficiently approximated using a Rao-Blackwellized particle filter, resulting in a generalization of the popular probabilistic FastSLAM algorithm. Our SLAM algorithm produces occupancy grid maps where belief functions explicitly represent additional information about missing and conflicting measurements compared to probabilistic grid maps. The basis for this SLAM algorithm are forward and inverse sensor models, and we present general evidential models for range sensors like sonar and laser scanners. Using the generated evidential grid maps, we show how optimal decisions can be made for path planning and active exploration. To demonstrate the effectiveness of our evidential approach, we apply it to two real-world datasets where a mobile robot has to explore unknown environments and solve different planning problems. Finally, we provide a quantitative evaluation and show that the evidential approach outperforms a probabilistic one both in terms of map quality and navigation performance.     

Parametric regression analysis of imprecise and uncertain data in the fuzzy belief function framework

In this paper, parametric regression analyses including both linear and nonlinear regressions are investigated in the case of imprecise and uncertain data, represented by a fuzzy belief function. The parameters in both the linear and nonlinear regression models are estimated using the fuzzy evidential EM algorithm, a straightforward fuzzy version of the evidential EM algorithm. The nonlinear regression model is derived by introducing a kernel function into the proposed linear regression model. An unreliable sensor experiment is designed to evaluate the performance of the proposed linear and nonlinear parametric regression methods, called parametric evidential regression (PEVREG) models. The experimental results demonstrate the high prediction accuracy of the PEVREG models in regressions with crisp inputs and a fuzzy belief function as output.     

Inference in directed evidential networks based on the transferable belief model

Inference algorithms in directed evidential networks (DEVN) obtain their efficiency by making use of the represented independencies between variables in the model. This can be done using the disjunctive rule of combination (DRC) and the generalized Bayesian theorem (GBT), both proposed by Smets [Ph. Smets, Belief functions: the disjunctive rule of combination and the generalized Bayesian theorem, International Journal of Approximate Reasoning 9 (1993) 1–35]. These rules make possible the use of conditional belief functions for reasoning in directed evidential networks, avoiding the computations of joint belief function on the product space. In this paper, new algorithms based on these two rules are proposed for the propagation of belief functions in singly and multiply directed evidential networks.     

A new fuzzy based algorithm for solving stereo vagueness in detecting and tracking people

This paper describes a system capable of detecting and tracking various people using a new approach based on colour, stereo vision and fuzzy logic. Initially, in the people detection phase, two fuzzy systems are used to filter out false positives of a face detector. Then, in the tracking phase, a new fuzzy logic based particle filter (FLPF) is proposed to fuse stereo and colour information assigning different confidence levels to each of these information sources. Information regarding depth and occlusion is used to create these confidence levels. This way, the system is able to keep track of people, in the reference camera image, even when either stereo information or colour information is confusing or not reliable. To carry out the tracking, the new FLPF is used, so that several particles are generated while several fuzzy systems compute the possibility that some of the generated particles correspond to the new position of people. Our technique outperforms two well known tracking approaches, one based on the method from Nummiaro et al. [1] and other based on the Kalman/meanshift tracker method in Comaniciu and Ramesh [2]. All these approaches were tested using several colour-with-distance sequences simulating real life scenarios. The results show that our system is able to keep track of people in most of the situations where other trackers fail, as well as to determine the size of their projections in the camera image. In addition, the method is fast enough for real time applications.     

Evidential calibration of binary SVM classifiers

In machine learning problems, the availability of several classifiers trained on different data or features makes the combination of pattern classifiers of great interest. To combine distinct sources of information, it is necessary to represent the outputs of classifiers in a common space via a transformation called calibration. The most classical way is to use class membership probabilities. However, using a single probability measure may be insufficient to model the uncertainty induced by the calibration step, especially in the case of few training data. In this paper, we extend classical probabilistic calibration methods to the evidential framework. Experimental results from the calibration of SVM classifiers show the interest of using belief functions in classification problems.     

Self-tuning of fuzzy belief rule bases for engineering system safety analysis

A framework for modelling the safety of an engineering system using a fuzzy rule-based evidential reasoning (FURBER) approach has been recently proposed, where a fuzzy rule-base designed on the basis of a belief structure (called a belief rule base) forms a basis in the inference mechanism of FURBER. However, it is difficult to accurately determine the parameters of a fuzzy belief rule base (FBRB) entirely subjectively, in particular for complex systems. As such, there is a need to develop a supporting mechanism that can be used to train in a locally optimal way a FBRB initially built using expert knowledge. In this paper, the methods for self-tuning a FBRB for engineering system safety analysis are investigated on the basis of a previous study. The method consists of a number of single and multiple objective nonlinear optimization models. The above framework is applied to model the system safety of a marine engineering system and the case study is used to demonstrate how the methods can be implemented.     

A note on article “The evidential reasoning approach for multiple attribute decision analysis using interval belief degrees”

Wang et al. use an evidential reasoning approach for solving multiple attribute decision analysis (MADA) problems under interval belief degrees [Y.M. Wang, J.B. Yang, D.L. Xu, K.S. Chin, The evidential reasoning approach for multiple attribute decision analysis using interval belief degrees, European Journal of Operational Research 175 (2006) 35–66]. In this note it is shown some nonlinear optimization models in that paper are incorrect. The necessary corrections are proposed.     

Active classification using belief functions and information gain maximization

Obtaining reliable estimates of the parameters of a probabilistic classification model is often a challenging problem because the amount of available training data is limited. In this paper, we present a classification approach based on belief functions that makes the uncertainty resulting from limited amounts of training data explicit and thereby improves classification performance. In addition, we model classification as an active information acquisition problem where features are sequentially selected by maximizing the expected information gain with respect to the current belief distribution, thus reducing uncertainty as quickly as possible. For this, we consider different measures of uncertainty for belief functions and provide efficient algorithms for computing them. As a result, only a small subset of features need to be extracted without negatively impacting the recognition rate. We evaluate our approach on an object recognition task where we compare different evidential and Bayesian methods for obtaining likelihoods from training data and we investigate the influence of different uncertainty measures on the feature selection process.     

Evidential reasoning based preference programming for multiple attribute decision analysis under uncertainty

Multiple attribute decision analysis (MADA) problems having both quantitative and qualitative attributes under uncertainty can be modelled and analysed using the evidential reasoning (ER) approach. Several types of uncertainty such as ignorance and fuzziness can be consistently modelled in the ER framework. In this paper, both interval weight assignments and interval belief degrees are considered, which could be incurred in many decision situations such as group decision making. Based on the existing ER algorithm, several pairs of preference programming models are constructed to support global sensitivity analysis based on the interval values and to generate the upper and lower bounds of the combined belief degrees for distributed assessment and also the expected values for ranking of alternatives. A post-optimisation procedure is developed to identify non-dominated solutions, examine the robustness of the partial ranking orders generated, and provide guidance for the elicitation of additional information for generating more desirable assessment results. A car evaluation problem is examined to show the implementation process of the proposed approach.     

OPAST子空间跟踪数据压缩半盲多用户检测

基于子空间方法的最小均方误差半盲多用户检测的计算核心是对信号子空间的特征值与特征向量的同时跟踪.仅跟踪计算信号子空间特征向量的子空间跟踪算法不能直接应用于这种检测方法.利用数据压缩技术,提出一种只需跟踪计算信号子空间正交规范基的自适应数据压缩半盲多用户检测.将著名的正交投影逼近子空间跟踪(OPAST)算法应用于这种数据压缩半盲多用户检测,发现OPAST算法具有自然的数据压缩结构,在几乎不增加运算量的情况下即可实现数据压缩半盲多用户检测.仿真实验表明:基于OPAST算法的数据压缩半盲多用户检测具有良好的检测性能.     

A framework for managing uncertain inputs: An axiomization of rewarding

The success postulate in belief revision ensures that new evidence (input) is always trusted. However, admitting uncertain input has been questioned by many researchers. Darwiche and Pearl argued that strengths of evidence should be introduced to determine the outcome of belief change, and provided a preliminary definition towards this thought. In this paper, we start with Darwiche and Pearl’s idea aiming to develop a framework that can capture the influence of the strengths of inputs with some rational assumptions. To achieve this, we first define epistemic states to represent beliefs attached with strength, and then present a set of postulates to describe the change process on epistemic states that is determined by the strengths of input and establish representation theorems to characterize these postulates. As a result, we obtain a unique rewarding operator which is proved to be a merging operator that is in line with many other works. We also investigate existing postulates on belief merging and compare them with our postulates. In addition, we show that from an epistemic state, a corresponding ordinal conditional function by Spohn can be derived and the result of combining two epistemic states is thus reduced to the result of combining two corresponding ordinal conditional functions proposed by Laverny and Lang. Furthermore, when reduced to the belief revision situation, we prove that our results induce all the Darwiche and Pearl’s postulates as well as the Recalcitrance postulate and the Independence postulate.     

The evidential reasoning approach for MADA under both probabilistic and fuzzy uncertainties

Many multiple attribute decision analysis (MADA) problems are characterised by both quantitative and qualitative attributes with various types of uncertainties. Incompleteness (or ignorance) and vagueness (or fuzziness) are among the most common uncertainties in decision analysis. The evidential reasoning (ER) approach has been developed in the 1990s and in the recent years to support the solution of MADA problems with ignorance, a kind of probabilistic uncertainty. In this paper, the ER approach is further developed to deal with MADA problems with both probabilistic and fuzzy uncertainties.In this newly developed ER approach, precise data, ignorance and fuzziness are all modelled under the unified framework of a distributed fuzzy belief structure, leading to a fuzzy belief decision matrix. A utility-based grade match method is proposed to transform both numerical data and qualitative (fuzzy) assessment information of various formats into the fuzzy belief structure. A new fuzzy ER algorithm is developed to aggregate multiple attributes using the information contained in the fuzzy belief matrix, resulting in an aggregated fuzzy distributed assessment for each alternative. Different from the existing ER algorithm that is of a recursive nature, the new fuzzy ER algorithm provides an analytical means for combining all attributes without iteration, thus providing scope and flexibility for sensitivity analysis and optimisation. A numerical example is provided to illustrate the detailed implementation process of the new ER approach and its validity and wide applicability.     

Sum-based weighted belief base merging: From commensurable to incommensurable framework

Different methods have been proposed for merging multiple and potentially conflicting information. The merging process based on the so-called “Sum” operation offers a natural method for merging commensurable prioritized belief bases. Their popularity is due to the fact that they satisfy the majority property and they adopt a non-cautious attitude in deriving plausible conclusions.This paper analyzes the sum-based merging operator when sources to merge are incommensurable, namely when they do not share the same meaning of uncertainty scales. We first show that the obtained merging operator can be equivalently characterized either in terms of an infinite set of compatible scales, or by a well-known Pareto ordering on a set of propositional logic interpretations. We also study some restrictions on compatible scales based on different commensurability hypothesis.Moreover, this paper provides a postulate-based analysis of our merging operators. We show that when prioritized bases to merge are not commensurable, the majority property is no longer satisfied. We provide conditions to recovering it. We also analyze the fairness postulate, which represents the unique postulate unsatisfied when belief bases to merge are commensurable and we propose a new postulate of consensuality. This postulate states that the result of the merging process must be consensual. It obtains the consent of all parties by integrating a piece of belief of each base.Finally, in the incommensurable case, we show that the fairness and consensuality postulates are satisfied when all compatible scales are considered. However, we provide an impossibility theorem stating that there is no way to satisfy fairness and consensuality postulates if only one canonical compatible scale is considered.     

Early detection of vessel delays using combined historical and real-time information

In ocean transportation, detecting vessel delays in advance or in real time is important for fourth-party logistics (4PL) in order to fulfill the expectations of customers and to help customers reduce delay costs. However, the early detection of vessel delays faces the challenges of numerous uncertainties, including weather conditions, port congestion, booking issues, and route selection. Recently, 4PLs have adopted advanced tracking technologies such as satellite-based automatic identification systems (S-AISs) that produce a vast amount of real-time vessel tracking information, thus providing new opportunities to enhance the early detection of vessel delays. This paper proposes a data-driven method for the early detection of vessel delays: in our new framework of refined case-based reasoning (CBR), real-time S-AIS vessel tracking data are utilized in combination with historical shipping data. The proposed method also provides a process of analyzing the causes of delays by matching the tracking patterns of real-time shipments with those of historical shipping data. Real data examples from a logistics company demonstrate the effectiveness of the proposed method.     

Likelihood-based belief function: Justification and some extensions to low-quality data

Given a parametric statistical model, evidential methods of statistical inference aim at constructing a belief function on the parameter space from observations. The two main approaches are Dempster's method, which regards the observed variable as a function of the parameter and an auxiliary variable with known probability distribution, and the likelihood-based approach, which considers the relative likelihood as the contour function of a consonant belief function. In this paper, we revisit the latter approach and prove that it can be derived from three basic principles: the likelihood principle, compatibility with Bayes' rule and the minimal commitment principle. We then show how this method can be extended to handle low-quality data. Two cases are considered: observations that are only partially relevant to the population of interest, and data acquired through an imperfect observation process.     

Change rules for hierarchical beliefs

The paper builds a belief hierarchy as a framework common to all uncertainty measures expressing that an actor is ambiguous about his uncertain beliefs. The belief hierarchy is further interpreted by distinguishing physical and psychical worlds, associated to objective and subjective probabilities. Various rules of transformation of a belief hierarchy are introduced, especially changing subjective beliefs into objective ones. These principles are applied in order to relate different contexts of belief change, revising, updating and even focusing. The numerous belief change rules already proposed in the literature receive epistemic justifications by associating them to specific belief hierarchies and change contexts. As a result, it is shown that the resiliency of probability judgments may have some limits and be reconciled with the possibility of learning from factual messages.     

Least committed basic belief density induced by a multivariate Gaussian: Formulation with applications

We consider here the case where our knowledge is partial and based on a betting density function which is n-dimensional Gaussian. The explicit formulation of the least committed basic belief density (bbd) of the multivariate Gaussian pdf is provided in the transferable belief model (TBM) framework. Beliefs are then assigned to hyperspheres and the bbd follows a χ² distribution. Two applications are also presented. The first one deals with model based classification in the joint speed–acceleration feature space. The second is devoted to joint target tracking and classification: the tracking part is performed using a Rao–Blackwellized particle filter, while the classification is carried out within the developed TBM scheme.     

Reasoning with imprecise belief structures

This paper extends the theory of belief functions by introducing new concepts and techniques, allowing to model the situation in which the beliefs held by a rational agent may only be expressed (or are only known) with some imprecision. Central to our approach is the concept of interval-valued belief structure (IBS), defined as a set of belief structures verifying certain constraints. Starting from this definition, many other concepts of Evidence Theory (including belief and plausibility functions, pignistic probabilities, combination rules and uncertainty measures) are generalized to cope with imprecision in the belief numbers attached to each hypothesis. An application of this new framework to the classification of patterns with partially known feature values is demonstrated.     

Reply to the note on article “The evidential reasoning approach for multiple attribute decision analysis using interval belief degrees”

In a very recent note by Gao and Ni [B. Gao, M.F. Ni, A note on article “The evidential reasoning approach for multiple attribute decision analysis using interval belief degrees”, European Journal of Operational Research, in press, doi:10.1016/j.ejor.2007.10.0381], they argued that Yen’s combination rule [J. Yen, Generalizing the Dempster–Shafer theory to fuzzy sets, IEEE Transactions on Systems, Man and Cybernetics 20 (1990) 559–570], which normalizes the combination of multiple pieces of evidence at the end of the combination process, was incorrect. If this were the case, the nonlinear programming models we proposed in [Y.M. Wang, J.B. Yang, D.L. Xu, K.S. Chin, The evidential reasoning approach for multiple attribute decision analysis using interval belief degrees, European Journal of Operational Research 175 (2006) 35–66] would also be incorrect. In this reply to Gao and Ni, we re-examine their numerical illustrations and reconsider their analysis of Yen’s combination rule. We conclude that Yen’s combination rule is correct and our nonlinear programming models are valid.