A preliminary specification methodology for model-based diagnosis

This paper sets out to provide a basis for a specification methodology for modelbased diagnostic systems (MBDS). The purpose of the methodology is to provide a mapping from the problem space of possible diagnostic applications to the solution space provided by the various approaches to MBDS. Therefore, given the major characteristics of a diagnostic problem, the methodology should provide guide-lines by which the specification of a suitable MBDS may be determined. As a first stage in the development of this methodology we provide taxonomies of the problem and solution spaces. The former is characterised via a set ofProblem requirements, divided intoTask, Fault andModel requirements, while the latter is classified as a set ofSystem specifications, with reference to the major functional blocks of MBDS: namely theDiagnostic Strategist, thePredictor and theCandidate Proposer. The last part of this paper proposes a mapping between these two multi-dimensional spaces. This mapping is preliminary, and therefore neither exhaustive nor exclusive, but together with the taxonomies of the problem requirements and system specification will provide a catalyst for the development of a more extensive methodology.     

基于模型诊断中结合问题特征的新方法

基于模型诊断一直是人工智能领域中热门的研究问题.近些年来,随着SAT求解器效率的逐渐提高,基于模型的诊断也被转换成SAT问题进行求解.在对基于模型诊断求解方法CSSE-tree深入研究基础上,结合诊断问题和SAT求解过程的特征,给出先对包含组件个数较多的候选诊断进行求解的方法,进而减小SAT求解问题的规模;在对极小诊断解和非极小诊断解剪枝方法的基础上,首次提出非诊断解定理及非诊断解空间的剪枝方法,有效地实现了对诊断的无解空间进行剪枝.根据组件个数较多的候选诊断先求解及有解无解剪枝方法特征,构建基于反向搜索的LLBRS-tree方法.实验结果表明:与CSSE-tree算法相比,LLBRS-tree算法减少了SAT求解次数、减小了求解问题规模,效率较好,尤其是求解多诊断时效率提高更为显著.     

Flexible diagnosis of discrete-event systems by similarity-based reasoning techniques

Diagnosis of discrete-event systems (DESs) may be improved by knowledge-compilation techniques, where a large amount of model-based reasoning is anticipated off-line, by simulating the behavior of the system and generating suitable data structures (compiled knowledge) embedding diagnostic information. This knowledge is exploited on-line, based on the observation of the system behavior, so as to generate the set of candidate diagnoses (problem solution). This paper makes a step forward: the solution of a diagnostic problem is supported by the solution of another problem, provided the two problems are somewhat similar. Reuse of model-based reasoning is thus achieved by exploiting the diagnostic knowledge yielded for solving previous problems. The technique still works when the available knowledge does not fit the extent of the system, but only a partition of it, that is, when solutions are available for subsystems only. In this case, the fragmented knowledge is exploited in a modular way, where redundant computation is avoided. Similarity-based diagnosis is meant for large-scale DESs, where the degree of similarity among subsystems is high and stringent time constraints on the diagnosis response is a first-class requirement.     

Composing semantic Web services under constraints

Web service composition is an inevitable aspect of Web services technology, which solves complex problems by combining available basic services and ordering them to best suit the problem requirements. Automatic composition gives us flexibility of selecting best candidate services at composition time satisfying QoS requirements; this would require the user to define constraints for selecting and composing candidate Web services. In this work, a Web service composition approach is presented in which a rich set of constraints can be defined on the composite service. The output of the framework is the schedule of Web service composition in which how and when services are executed is defined. The basic properties of the proposed approach is converting Web service composition problem into a constraint satisfaction problem in order to find the best solution that meets all criteria defined by user and providing semantic compatibility and composability during composition.     

区间多目标优化中决策空间约束、支配及同序解筛选策略

针对优化函数未知的昂贵区间多目标优化, 根据决策空间数据挖掘, 提出了一种基于最近邻法和主成分分析法(Principal component analysis, PCA)的NSGA-II算法. 该算法首先通过约束条件将待测解集分为可行解和非可行解, 利用最近邻法对待测解和样本解进行相似性计算, 判断待测解是否满足约束. 然后对于两个解的Pareto支配性同样利用最近邻法来区分解之间的被支配和非被支配关系. 由于目标空间拥挤距离无法求出, 为此在决策空间利用主成分分析法将K-均值聚类后的解集降维, 找出待测解的前、后近距离解, 通过决策空间拥挤距离对同序值解进行筛选. 实现NSGA-II算法的改进.     

Evolutionary Optimization of File Assignment for a Large-Scale Video-on-Demand System

We present a genetic algorithm for tackling a file assignment problem for a large-scale video-on-demand system. The file assignment problem is to find the optimal replication and allocation of movie files to disks so that the request blocking probability is minimized subject to capacity constraints. We adopt a divide-and-conquer strategy, where the entire solution space of file assignments is divided into subspaces. Each subspace is an exclusive set of solutions sharing a common file replication instance. This allows us to utilize a greedy file allocation method for finding a good-quality heuristic solution within each subspace. We further design two performance indices to measure the quality of the heuristic solution on 1.) its assignment of multicopy movies and 2.) its assignment of single-copy movies. We demonstrate that these techniques, together with ad hoc population handling methods, enable genetic algorithms to operate in a significantly reduced search space and achieve good-quality file assignments in a computationally efficient way.     

Minimum-time control of robotic manipulators with geometric path constraints

Conventionally, robot control algorithms are divided into two stages, namely, path or trajectory planning and path tracking (or path control). This division has been adopted mainly as a means of alleviating difficulties in dealing with complex, coupled manipulator dynamics. Trajectory planning usually determines the timing of manipulator position and velocity without considering its dynamics. Consequently, the simplicity obtained from the division comes at the expense of efficiency in utilizing robot's capabilities. To remove at least partially this inefficiency, this paper considers a solution to the problem of moving a manipulator in minimum time along a specified geometric path subject to input torque/force constraints. We first describe the manipulator dynamics using parametric functions which represent geometric path constraints to be honored for collision avoidance as well as task requirements. Second, constraints on input torques/ forces are converted to those on the parameters. Third, the minimum-time solution is deduced in an algorithm form using phase-plane techniques. Finally, numerical examples are presented to demonstrate utility of the trajectory planning method developed.     

Making constraint solvers more usable: overconstraint problem

The richness and expressive power of geometric constraints causes unintended ambiguities and inconsistencies during their solution or realization. For example, geometric constraint problems may turn out to be overconstrained requiring the user to delete one or more of the input constraints, and the solutions must then be dynamically updated. Without proper guidance by the constraint solver, the user must have profound insight into the mathematical nature of constraint systems and understand the internals of the solver algorithm. But a general user is most likely unfamiliar with those problems, so that the required interaction with the constraint solver may well be beyond the user's ability. In this paper, we present strategies and techniques to empower the user to deal effectively with the overconstraint problem while not requiring him or her to become an expert in the mathematics of constraint solving.We formulate this problem as a series of formal requirements that gel with other essentials of constraint solvers. We then give algorithmic solutions that are both general and efficient (running time typically linear in the number of relevant constraints).     

A distance-limited continuous location-allocation problem for spatial planning of decentralized systems

We introduce a new continuous location-allocation problem where the facilities have both a fixed opening cost and a coverage distance limitation. The problem has wide applications especially in the spatial planning of water and/or energy access networks where the coverage distance might be associated with the physical loss constraints. We formulate a mixed integer quadratically constrained problem (MIQCP) under the Euclidean distance setting and present a three-stage heuristic algorithm for its solution: In the first stage, we solve a planar set covering problem (PSCP) under the distance limitation. In the second stage, we solve a discrete version of the proposed problem where the set of candidate locations for the facilities is formed by the union of the set of demand points and the set of locations in the PSCP solution. Finally, in the third stage, we apply a modified Weiszfeld’s algorithm with projections that we propose to incorporate the coverage distance component of our problem for fine-tuning the discrete space solutions in the continuous space. We perform numerical experiments on three example data sets from the literature to demonstrate the performance of the suggested heuristic method.     

基于微粒群和满足质量约束的组炉方案优化方法

分析了面向订单生产的钢铁企业面临的市场需求与生产组织特点, 将炼钢组炉方案的优化设计归结为一个满足化学成份等质量因素约束的聚类分析问题. 在此基础上提出了基于微粒群优化的求解方法, 该方法利用主成分分析技术缩小了问题域的维度, 在传统的工艺约束、交货期约束和炉容量等约束的基础上, 引入质量相近产品成份取值范围约束来限定微粒的活动范围, 采用炼钢组炉计划与质量设计的集成模式, 在多约束下对成份相近的不同品种的候选组炉合同进行聚类分析, 实现了面向钢铁产品多品种小批量需求的满足质量约束的组炉方案的优化.     

Constructing Bayesian networks for medical diagnosis fromincomplete and partially correct statistics

The paper discusses several knowledge engineering techniques for the construction of Bayesian networks for medical diagnostics when the available numerical probabilistic information is incomplete or partially correct. This situation occurs often when epidemiological studies publish only indirect statistics and when significant unmodeled conditional dependence exists in the problem domain. While nothing can replace precise and complete probabilistic information, still a useful diagnostic system can be built with imperfect data by introducing domain-dependent constraints. We propose a solution to the problem of determining the combined influences of several diseases on a single test result from specificity and sensitivity data for individual diseases. We also demonstrate two techniques for dealing with unmodeled conditional dependencies in a diagnostic network. These techniques are discussed in the context of an effort to design a portable device for cardiac diagnosis and monitoring from multimodal signals     

DiSC: Benchmarking Secure Chip DBMS

Secure chips, e.g. present in smart cards, USB dongles, i-buttons, are now ubiquitous in applications with strong security requirements. And they require embedded data management techniques. However, secure chips have severe hardware constraints which make traditional database techniques irrelevant. The main problem faced by secure chip DBMS designers is to be able to assess various design choices and trade-offs for different applications. Our solution is to use a benchmark for secure chip DBMS in order to (1) compare different database techniques, (2) predict the limits of on-chip applications, and (3) provide co-design hints. In this paper, we propose DiSC (Data management in Secure Chip), a benchmark which matches these three objectives. This work benefits from our long experience in developing and tuning data management techniques for the smart card. To validate DiSC, we compare the behavior of candidate data management techniques thanks to a cycle-accurate smart card simulator. Finally, we show the applicability of DiSC to future designs involving new hardware platforms and new database techniques.     

A Bayesian exploration-exploitation approach for optimal online sensing and planning with a visually guided mobile robot

We address the problem of online path planning for optimal sensing with a mobile robot. The objective of the robot is to learn the most about its pose and the environment given time constraints. We use a POMDP with a utility function that depends on the belief state to model the finite horizon planning problem. We replan as the robot progresses throughout the environment. The POMDP is high-dimensional, continuous, non-differentiable, nonlinear, non-Gaussian and must be solved in real-time. Most existing techniques for stochastic planning and reinforcement learning are therefore inapplicable. To solve this extremely complex problem, we propose a Bayesian optimization method that dynamically trades off exploration (minimizing uncertainty in unknown parts of the policy space) and exploitation (capitalizing on the current best solution). We demonstrate our approach with a visually-guide mobile robot. The solution proposed here is also applicable to other closely-related domains, including active vision, sequential experimental design, dynamic sensing and calibration with mobile sensors.     

Collision detection for moving polyhedra

We consider the collision-detection problem for a three-dimensional solid object moving among polyhedral obstacles. The configuration space for this problem is six-dimensional, and the traditional representation of the space uses three translational parameters and three angles (typically Euler angles). The constraints between the object and obstacles then involve trigonometric functions. We show that a quaternion representation of rotation yields constraints which are purely algebraic in a seven-dimensional space. By simple manipulation, the constraints may be projected down into a six-dimensional space with no increase in complexity. The algebraic form of the constraints greatly simplifies computation of collision points, and allows us to derive an efficient exact intersection test for an object which is translating and rotating among obstacles.     

A modified bidirectional decoding strategy based on the BAMstructure

Based on the B. Kosko's bidirectional associative memories (BAM) strategy, a modified bidirectional decoding strategy (MBDS) is introduced. The MBDS structure provides sufficient recalling capabilities by adding some association fascicles to the BAM structure. These association fascicles are established with a relating parameter that controls the recalling performances. Pattern recognition examples are presented to shown that the MBDS requires considerably fewer weighting connections than the dummy augmentation method does. Moreover, in the problem of pattern recognition, if there are large number of trained pairs, the MBDS is still applicable, but the dummy augmentation method seems to be obstructed.     

Enforcing Service-Level Constraints in Supply Chains With Assembly Operations

We study a feedforward supply network that involves assembly operations. We compute optimal stock levels which minimize inventory costs and maintain stockout probabilities below given desirable levels (service-level constraints). To that end, we develop large deviations approximations for inventory costs and service level constraints and formulate the stock level selection problem as a nonlinear programming problem which can be solved using standard techniques. This results in significant computational savings when compared to exhaustive search using simulation. Our distributional assumptions are general enough to include temporal dependencies in the demand and production processes. We leverage the solution of the inventory control problem in the design of supply contracts under explicit service-level constraints     

Linear programming approach to constrained feedback control

This paper deals with the problem of stabilizing linear discrete-time systems under state and control linear constraints using linear programming techniques. Linear state constraints describe a polyhedron in the state space so that the problem considered is to make such a polyhedron positively invariant while the control does not violate its constraints. For this, necessary and sufficient conditions are given for the existence of a solution of the problem in terms of polyhedron's vertices and directions. These conditions are described by a set of linear constraints and, following the approach introduced by Vassilaki et al. , they can be solved using linear programming techniques. The objective function proposed here turns out to be a natural one when describing the constraints in terms of polyhedron's vertices and directions.     

Dinkelbach NCUT: An Efficient Framework for Solving Normalized Cuts Problems with Priors and Convex Constraints

In this paper, we propose a novel framework, called Dinkelbach NCUT (DNCUT), which efficiently solves the normalized graph cut (NCUT) problem under general, convex constraints, as well as, under given priors on the nodes of the graph. Current NCUT methods use generalized eigen-decomposition, which poses computational issues especially for large graphs, and can only handle linear equality constraints. By using an augmented graph and the iterative Dinkelbach method for fractional programming (FP), we formulate the DNCUT framework to efficiently solve the NCUT problem under general convex constraints and given data priors. In this framework, the initial problem is converted into a sequence of simpler sub-problems (i.e. convex, quadratic programs (QP’s) subject to convex constraints). The complexity of finding a global solution for each sub-problem depends on the complexity of the constraints, the convexity of the cost function, and the chosen initialization. However, we derive an initialization, which guarantees that each sub-problem is a convex QP that can be solved by available convex programming techniques. We apply this framework to the special case of linear constraints, where the solution is obtained by solving a sequence of sparse linear systems using the conjugate gradient method. We validate DNCUT by performing binary segmentation on real images both with and without linear/nonlinear constraints, as well as, multi-class segmentation. When possible, we compare DNCUT to other NCUT methods, in terms of segmentation performance and computational efficiency. Even though the new formulation is applied to the problem of spectral graph-based, low-level image segmentation, it can be directly applied to other applications (e.g. clustering).     

A Comparison of Traditional and Constraint-based Heuristic Methods on Vehicle Routing Problems with Side Constraints

The vehicle routing problem (VRP) is a variantof the familiar travelling salesperson problem (TSP). In theVRP we are to perform a number of visits, using a number of vehiclesof limited capacity, while typically minimizing the distancetravelled. VRPs can be complicated by imposing time windows ordeadlines on visits, sequencing constraints between visits, andso on. In this paper, we use a constraint-based toolkit for solvingvehicle routing problems to study the effect of different heuristictechniques. We investigate the performance of a number of constructionand improvement techniques, and show that as the size of thesolution space is decreased through addition of side constraints,certain conventional techniques fail while constraint directedtechniques continue to perform acceptably. This suggests thatconstraint programming techniques are particularly suited toVRPs with side constraints.     

Solving Hierarchical Constraints over Finite Domains with Local Search

Many real world problems have requirements and constraints which conflict with each other. One approach for dealing with such over-constrained problems is with constraint hierarchies. In the constraint hierarchy framework, constraints are classified into ranks, and appropriate solutions are selected using a comparator which takes into account the constraints and their ranks. In this paper, we present a local search solution to solving hierarchical constraint problems over finite domains (HCPs). This is an extension of local search for over-constrained integer programs WSAT(OIP) to constraint hierarchies and general finite domain constraints. The motivation for this work arose from solving large airport gate allocation problems. We show how gate allocation problems can be formulated as HCPs using typical gate allocation constraints. Using the gate allocation benchmarks, we investigate how constraint heirarchy selection strategies and the problem formulation using two models: a 0–1 linear constraint hierarchy model and a nonlinear finite domain constraint hierarchy model.