IEEE CONTROL SYSTEMS SOCIETY TECHNICAL COMMITTEE

ON DISCRETE EVENT SYSTEMS

Editor: (Samuel) Qing-Shan Jia

Chair, IEEE CSS Technical Committee on DES

Center for Intelligent and Networked Systems

Department of Automation

Tsinghua University

Beijing 100084

China

Phone: (+86) 10-6277-3006

Fax: (+86) 10-6279-6115

e-mail: jiaqs@tsinghua.edu.cn

WWW: http://cfins.au.tsinghua.edu.cn/personalhg/jiaqingshan/

It is the responsibility of the contributor to ensure that they have

the necessary permissions/clearance required for the transmittal of

their news item.

_.___________________________________________________________________._

Contents:

1. Editorial

2. Announcement

2.1 DESpot 1.4.0 released with support for Multi-Level HISC and

Distributed Computation

3. Journals

3.1 Selections from the IEEE Transactions on Automation Science and Engineering

Special Section on Advances in Discrete-Event Systems for Automation

Volume: 11, Issue: 11, January 2014

3.2 Selections from the IEEE Transactions on Control Systems Technology

Volume: 22, Issue: 1, January 2014

_.___________________________________________________________________._

Editorial

_.___________________________________________________________________._

Welcome to the newsletter of the IEEE Control Systems Technical

Committee on Discrete Event Systems!

Personal note from the editor:

Welcome to the january 2014 newsletter.

Samuel

_.___________________________________________________________________._

Announcements

_.___________________________________________________________________._

Contributed by: Ryan Leduc < leduc@mcmaster.ca >

DESpot 1.4.0 released with support for Multi-Level HISC and

Distributed Computation

DESpot is a new discrete-event system (DES) software research tool. It

supports both flat projects (collection of plant and supervisor DES), and

Hierarchical Interface-Based Supervisory Control (HISC) projects.

New to DESpot 1.4.0 is the addition of support for multi-level HISC projects

including experimental support for multi-level HISC with low data events for

the non-BDD algorithms. Multi-level synthesis is not yet supported. This

release also adds distributed algorithms for the Linux version of DESpot.

Message passing interfaces (MPI) libraries are used as the underlying

technology.

DESpot Features:

*  Supports flat DES projects and HISC projects, including low data events.

*  DESpot comes with a detailed help browser. A web version, including many

screen shots, can be found here:

http://www.cas.mcmaster.ca/~leduc/despotHF/resources/helpfiles/HelpBrowser.h

tml

*  DESpot has a graphical DES editor, including export to postscript and PNG

graphic formats.

*  DESpot can verify the three main HISC properties individually, or as a

group using the "Check Project" menu item. Check project runs each property

check in a separate thread, so if you have a quad-core CPU, you could see

around a 3x speedup.

*  DESpot now includes the bddHISC algorithms. bddHISC can verify an HISC

project, or do HISC synthesis using binary-decision diagram (BDD) based

algorithms capable of handling individual components at least as large as

10^15 states.

*  DESpot allows the entry of timed DES (TDES) projects for use with

sampled-data supervisory control.

*  DESpot has a built in DES simulator that includes graphical simulation of

the DES. DESpot can also use the HISC structure to accelerate the

simulation.

*  DESpot is open source software, released under the GNU General Public

DESpot is written in C++ and uses the QT GUI libraries.  At the moment,

DESpot is available as source code and as a Windows' installer.  It runs

under Linux, Windows, and Mac OS X.

http://www.cas.mcmaster.ca/~leduc/DESpot.html

_.___________________________________________________________________._

Journals

_.___________________________________________________________________._

Contributed by: Yulin Lei < leiyl11@mails.tsinghua.edu.cn >

Selections from the IEEE Transactions on Automation Science and Engineering

Special Section on Advances in Discrete-Event Systems for Automation

Volume: 11 Issue: 11

January 2014

1. Symbolic Representation and Computation of Timed Discrete-Event Systems

Miremadi, S. ;  Fei, Z. ;  Akesson, K. ;  Lennartson, B.

Abstract:

In this paper, we symbolically represent timed discrete-event systems (TDES), which can be used to efficiently compute the supervisor in the supervisory control theory context. We model a TDES based on timed extended finite automata (TEFAs): an augmentation of extended finite automata (EFAs) by incorporating discrete time into the model. EFAs are ordinary automata extended with discrete variables, where conditional expressions and update functions can be attached to the transitions. The symbolic computations are based on binary decision diagrams (BDDs). We show how TEFAs can be represented by BDDs. The main feature of this approach is that the BDD-based fixed point computations are not based on tick models that have been commonly used in this area, leading to better performance in many cases. The approach has been implemented and applied to a simple case study and several large-scale benchmarks.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6644325

1. Application of Supervisory Control Synthesis to a Patient Support Table

of a Magnetic Resonance Imaging

Theunissen, R.J.M.; Petreczky, M.; Schiffelers, R.R.H.; van Beek, D.A.; Rooda, J.E.

Abstract:

In this paper, we present a case-study on application of Ramadge-Wonham supervisory control theory (abbreviated by SCT in the sequel) to a patient support system of a magnetic resonance imaging (MRI) scanner. We discuss the whole developmental cycle, starting from the mathematical models of the uncontrolled system and of the control requirements, and ending with the implementation of the obtained controller on the actual hardware. The obtained controller was tested on the physical system. In this case study, we attempted to build the models in a modular way, in order to decrease the computational complexity of the controller synthesis and to improve the adaptability of the models. An important advantage of SCT is that it allows automatic generation of the controller, and that it can thus improve adaptability of the control software. We also briefly discuss our experience on the adaptability of the control software, obtained in the course of this case study.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6603361

1. Supervisory Control for State-Vector Transition Models—A Unified Approach

Lennartson, B. ; Basile, F. ;  Miremadi, S. ;  Fei, Z. ;  Hosseini, M.N. ;  Fabian, M. ;  Akesson, K.

Abstract:

A generic state-vector transition (SVT) model is suggested, including a flexible synchronous composition involving both shared variables and events. This model is analyzed, focusing on properties that are important for supervisor synthesis. A synthesis procedure is then developed for the SVT model, where supervisor guards are generated that guarantee a controllable, nonblocking and maximally permissive supervisor. Novel conditions are introduced, such that more flexible specifications can be applied than earlier suggested for related models. Since the SVT model includes automata and (colored) Petri nets, optionally extended with variables, guards and actions, as special cases, the suggested synthesis approach unifies supervisor synthesis for the main discrete event model classes. Finally, the SVT model is naturally represented and efficiently computed based on binary decision diagrams, and the resulting supervisor guards are easily implemented in industrial control systems.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6683086

1. Bridging the Gap Between Design and Implementation of Discrete-Event Controllers

Moreira, M.V. ;   Basilio, J.C.

Abstract:

Extended labeled Petri nets (ELPNs), i.e., labeled Petri nets with inhibitor arcs, are usually used to model the desired closed-loop behavior of a controlled discrete-event system, and, as such, their states are formed with both the controller and the plant states. However, the control logic is based on the controller states only and the interaction between controller and plant is carried out through sensor readings from the plant and control actions (forced events) from the controller. This makes ELPN not suitable for modeling the controller. Control interpreted Petri nets (CIPNs), on the other hand, include control actions in the places and sensor readings in the transitions as part of their formal structure, and so provide a better formalism for controller modeling. In this paper, we propose a two-step approach to discrete-event controller implementation, as follows: (i) we first propose a set of transformation rules to convert the initial ELPN to an equivalent CIPN, therefore extracting the control logic from the desired closed-loop behavior and (ii) we present a straightforward systematic way to translate the CIPN into a ladder diagram. We apply the results presented here to the implementation of the automation system of a plastic molding machine.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6621049

1. Supervisor Simplification for AMS Based on Petri Nets and Inequality Analysis

Hu, H. ;   Liu, Y.

Abstract:

In the framework of automated manufacturing systems (AMS), Petri nets are widely used to model, analyze, and control them. Resolving deadlocks is of paramount significance because their emergence may likely zero a systems throughput, if not necessarily. Supervisory control technique is the most widely adopted method to resolve them. A control policy can be converted into satisfying a set of inequalities, each of which corresponds to a siphon in a Petri net structure. The number of siphons can be exponential in the worst case, so does the number of inequalities. Taking into account the independent and dependent inequalities, this paper proposes a method to remove all the dependent inequalities, while preserving only the independent ones. This method can significantly reduce the size of a supervisory controller. Examples are presented to illustrate the effectiveness and efficiency of this method.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6663702

1. Fault-Tolerant Control for Safety of Discrete-Event Systems

Shu, S. ;   Lin, F.

Abstract:

This paper considers fault-tolerant control that ensures the safety of a discrete-event system. We consider multiple faulty modes. Each faulty mode is modeled by an automaton. These automata, together with the automaton modeling normal mode, describe a discrete-event system with faults. Each faulty mode has some illegal states that must be avoided by control so that the fault can be tolerated. We assume that fault-tolerant control takes actions (disablements) only when the occurrence of a fault is certain. We consider cases of both full event observation and partial event observation. We derive necessary and sufficient conditions for the existence of fault-tolerant control. We also provide formulas and algorithms to calculate control actions if the necessary and sufficient conditions are satisfied. Both offline control synthesis (for full event observation) and online control synthesis (for partial event observation) are investigated. We allow multiple faults as well as single faults.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6555971

1. Freeway Traffic Modeling and Control in a First-Order Hybrid Petri Net Framework

FANTI, M.P. ;   Iacobellis, G. ;   Mangini, A.M. ;   Ukovich, W.

The paper presents a model for freeway traffic performance evaluation and control in a First-Order Hybrid Petri Net (FOHPN) framework. Such a hybrid Petri net formalism includes continuous places holding fluid, discrete places containing a non-negative integer number of tokens and transitions, which are either discrete or continuous. In order to suitably describe the dynamics of the freeway traffic flow, we allow updating the transition firing speed as a function of the markings modeling the freeway traffic, as described by the stationary flow-density relationship. Moreover, we propose an online optimal control coordination of speed limits with the objective of maximizing the flow density. The use of FOHPNs offers several significant advantages with respect to the model existing in the related literature: the graphical feature enables an easy modular modeling approach and the mathematical aspects efficiently allow simulating and optimizing the system. The effectiveness of the FOHPN formalism is shown by applying the proposed modeling and control technique to a stretch of a freeway in the North-East of Italy, where a solution of an accident situation is considered.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6510519

1. State Estimation of Timed Labeled Petri Nets With Unobservable Transitions

Declerck, P. ; Bonhomme, P.

Abstract:

The aim of this paper is to reconstruct the least/greatest sequence of unobservable transitions in timed Petri nets based on the online observation of firing occurrences of some transitions on a sliding horizon. The Petri net, which can be unbounded and can contain self-loops and circuits, is described under an algebraic form composed of $A.xleq b$ which expresses the possible time sequence $x$ and the fundamental marking relation. Under the assumption of Backward/Forward Conflict Freeness of the unobservable-induced subnet, we show the existence of a finite least/greatest sequence with respect to the data known on a given horizon. A technique of computation using linear programming is given.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6674072

1. Efficient Enumeration of Minimal Unsafe States in Complex Resource Allocation Systems

Nazeem, A. ; REVELIOTIS, S.

Abstract:

An earlier work of ours has proposed a novel approach for the deployment of the maximally permissive deadlock avoidance policy for complex resource allocation systems (RAS), that is based on the identification and the efficient storage of a critical subset of states of the underlying RAS state space; the availability of this information enables an expedient one-step-lookahead scheme for the identification and blockage of transitions that will take the system behavior outside its safe region. This paper complements the aforementioned results by introducing a novel algorithm that provides those critical states while avoiding the complete enumeration of the RAS state space.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6555954

1.  Testing Experiments on Synchronized Petri Nets

Pocci, M. ; Demongodin, I. ;   Giambiasi, N. ;   Giua, A.

Abstract:

Synchronizing sequences have been proposed in the late 1960s to solve testing problems on systems modeled by finite-state machines. Such sequences lead a system, seen as a black box, from an unknown current state to a known final one.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6678639

1. A Study on Sinus-Lifting Motion of a Snake Robot With Sequential Optimization

of a Hybrid System

Toyoshima, S. ;   Tanaka, M. ;   Matsuno, F.

Abstract:

In this paper, we consider “sinus-lifting motion” of a living snake, in which a snake lifts up some parts of its body from the ground, and switches the lifted parts dynamically. It is not clear whether imitating the sinus-lifting motion is the best locomotion or not for a snake like robot. The aim of this paper is to propose an appropriate motion pattern to a snake like robot considering the optimality of the sinus-lifting motion. We introduce two physical parameters, constraint forces and energy efficiency, as cost functions to optimize and propose switching strategies for generating optimal motion patterns of a snake like robot.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6576914

1. Diagnosability of Discrete-Event Systems Using Labeled Petri Nets

Cabasino, M.P. ; Giua, A. ;   SEATZU, C.

Abstract:

In this paper, we focus on labeled Petri nets with silent transitions that may either correspond to fault events or to regular unobservable events. We address the problem of deriving a procedure to determine if a given net system is diagnosable, i.e., the occurrence of a fault event may be detected for sure after a finite observation. The proposed procedure is based on our previous results on the diagnosis of discrete-event systems modeled with labeled Petri nets, whose key notions are those of basis markings and minimal explanations, and is inspired by the diagnosability approach for finite state automata proposed by Sampath  in 1995. In particular, we first give necessary and sufficient conditions for diagnosability. Then, we present a method to test diagnosability that is based on the analysis of two graphs that depend on the structure of the net, including the faults model, and the initial marking.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6663699

1. A Propagative Model of Simultaneous Impact: Existence, Uniqueness,

and Design Consequences

Seghete, V. ;   Murphey, T.D.

Abstract:

This paper presents existence and uniqueness results for a propagative model of simultaneous impacts that is guaranteed to conserve energy and momentum in the case of elastic impacts with extensions to perfectly plastic and inelastic impacts. A corresponding time-stepping algorithm that guarantees conservation of continuous energy and discrete momentum is developed, also with extensions to plastic and inelastic impacts. The model is illustrated in simulation using billiard balls and a two-dimensional legged robot as examples; the latter is optimized over geometry and gait parameters to achieve unique simultaneous impacts.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6572900

1. Planar Compliances of Symmetric Notch Flexure Hinges: The Right Circularly

Corner-Filleted Parabolic Design

Lobontiu, N. ;   Cullin, M. ;   Petersen, T. ;   Alcazar, J.A. ;   Noveanu, S.

Abstract:

This study proposes a general analytical compliance model for symmetric notch flexure hinges composed of segments with constant width and analytically defined variable thicknesses. Applying serial combination and longitudinal/transverse mirroring of base segments, the in-plane compliances of the full flexure are obtained as functions of one quarter-flexure compliances. The new right circularly corner-filleted parabolic flexure hinge is introduced as an illustration of the general analytical modeling algorithm. Experimental testing and finite element simulation confirm the analytical model predictions for an aluminum flexure prototype. The planar compliances sensitivity to the relevant geometric parameters is also studied.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6418064

1. An Optimal Sample Allocation Strategy for Partition-Based Random Search

Chen, W. ;   Gao, S. ;   Chen, C.-H. ;   Shi, L.

Abstract:

Partition-based random search (PRS) provides a class of effective algorithms for global optimization. In each iteration of a PRS algorithm, the solution space is partitioned into subsets which are randomly sampled and evaluated. One subset is then determined to be the promising subset for further partitioning. In this paper, we propose the problem of allocating samples to each subset so that the samples are utilized most efficiently. Two types of sample allocation problems are discussed, with objectives of maximizing the probability of correctly selecting the promising subset $(P{CSPS})$  given a sample budget and minimizing the required sample size to achieve a satisfied level of $P{CSPS}$ , respectively. An extreme value-based prospectiveness criterion is introduced and an asymptotically optimal solution to the two types of sample allocation problems is developed. The resulting optimal sample allocation strategy (OSAS) is an effective procedure for the existing PRS algorithms by intelligently utilizing the limited computing resources. Numerical tests confirm that OSAS is capable of increasing the $P{CSPS}$ in each iteration and subsequently improving the performance of PRS algorithms.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6497538

1. Path Generation Using {mbi \eta}^4 -Splines for a Truck and Trailer Vehicle

Ghilardelli, F. ;   Lini, G. ;   Piazzi, A.

Abstract:

Generation of high-quality drive paths is a significant issue for automated wheeled vehicles. To achieve this aim for a truck and trailer vehicle, the paper proposes the use of a parameterized curve primitive, the ${mbi eta}^4$-spline. Using this spline, generation and shaping of smooth feasible paths is made possible as well as the transfer between arbitrary dynamic configurations of the articulated vehicle. The ${mbi eta}^4$ -spline is a ninth-order polynomial curve that can interpolate given Cartesian points with associated arbitrary unit tangent vector, curvature, and first and second derivatives of curvature. It depends on a set of eight (eta) parameters that can be freely chosen to modify the path shape without changing the interpolations conditions at the path endpoints. Completeness, minimality, and symmetry of the ${mbi eta}^4$-spline are established. An example on a parking maneuver of the articulated vehicle is presented and the pertinent optimal path planning is also discussed.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6565390

1. A Multiagent Q-Learning-Based Optimal Allocation Approach for Urban

Water Resource Management System

Ni, J. ;   Liu, M. ;   Ren, L. ;   Yang, S.X.

Abstract:

Water environment system is a complex system, and an agent-based model presents an effective approach that has been implemented in water resource management research. Urban water resource optimal allocation is a challenging and critical issue in water environment systems, which belongs to the resource optimal allocation problem. In this paper, a novel approach based on multiagent Q-learning is proposed to deal with this problem. In the proposed approach, water users of different regions in the city are abstracted into the agent-based model. To realize the cooperation among these stakeholder agents, a maximum mapping value function-based Q-learning algorithm is proposed in this study, which allows the agents to self-learn. In the proposed algorithm, an adaptive reward value function is used to improve the performance of the multiagent Q-learning algorithm, where the influence of multiple factors on the optimal allocation can be fully considered. The proposed approach can deal with various situations in urban water resource allocation. The experimental results show that the proposed approach is capable of allocating water resource efficiently and the objectives of all the stakeholder agents can be successfully achieved.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6410370

1. Building Energy Doctors: An SPC and Kalman Filter-Based Method for

System-Level Fault Detection in HVAC Systems

Sun, B. ;   Luh, P.B. ;   Jia, Q.-S. ;   O'Neill, Z. ;   Song, F.

Abstract;

Buildings worldwide account for nearly 40% of global energy consumption. The biggest energy consumer in buildings is the Heating, Ventilation and Air Conditioning (HVAC) systems. HVAC also ranks top in terms of number of complaints by tenants. Maintaining HVAC systems in good conditions through early fault detection is thus a critical problem. The problem, however, is difficult since HVAC systems are large in scale, consisting of many coupling subsystems, building and equipment dependent, and working under time-varying conditions. In this paper, a model-based and data-driven method is presented for robust system-level fault detection with potential for large-scale implementation. It is a synergistic integration of: ) Statistical Process Control (SPC) for measuring and analyzing variations; 2) Kalman filtering based on gray-box models to provide predictions and to determine SPC control limits; and (3) system analysis for analyzing propagation of faults' effects across subsystems. In the method, two new SPC rules are developed for detecting sudden and gradual faults. The method has been tested against a simulation model of the HVAC system for a 420-meter-high building. It detects both sudden faults and gradual degradation, and both device and sensor faults. Furthermore, the method is simple and generic, and has potential replicability and scalability.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6410372

1. A Quality Flow Model in Battery Manufacturing Systems for Electric Vehicles

Ju, F. ; Li, J. ;   Xiao, G. ;   Huang, N. ;   Biller, S.

Abstract:

Improving quality in large volume battery manufacturing systems for hybrid and electric vehicles is of significant importance. In this paper, we present a flow model to analyze and improve product quality in electrical vehicle battery assembly lines with 100% inspections and repairs for defective parts. Specifically, a battery assembly line consisting of multiple inspection stations is considered. After each inspection, defective parts will be repaired and sent back to the line. A quality flow model is introduced to analyze quality propagations along the battery production line. Analytical expressions of final product quality are derived and structural properties, such as monotonicity and sensitivities, are investigated. A bottleneck identification and mitigation method is introduced to improve quality performance. Finally, a case study is presented to illustrate the applicability of the method.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6425437

1. Robotic Explosive Charging in Mining and Construction Applications

Bonchis, A. ;   Duff, E. ;   Roberts, J. ;   Bosse, M.

Abstract:

This paper describes the development and testing of a robotic system for charging blast holes in underground mining. The automation system supports four main tactical functions: detection of blast holes; teleoperated arm pose control; automatic arm pose control; and human-in-the-loop visual servoing. We present the system architecture, and analyze the major components, Hole detection is crucial for automating the process, and we discuss theoretical and practical aspects in detail. The sensors used are laser range finders and cameras installed in the end effector. For automatic insertion, we consider image processing techniques to support visual servoing the tool to the hole. We also discuss issues surrounding the control of heavy-duty mining manipulators, in particular, friction, stiction, and actuator saturation.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6464528

1. Cigarette Production Scheduling by Combining Workflow Model and Immune Algorithm

Zuo, X. ; Tan, W. ;   Lin, H.

Abstract:

Cigarette production scheduling is vital in improving production efficiency and reducing supply delay. In

this paper, a workflow model combined with an immune algorithm is proposed to solve this problem for

improving production efficiency. First, the problem is formulated as a mixed-integer quadratically

constrained programming model. Afterwards, the problem is transformed into a workflow resource allocation

one. Based on this model, an immune algorithm is presented to find a set of activity priorities that are

combined with dispatching rules to allocate resources. Activity priorities are represented by antibodies

and evaluated by simulation runs on the workflow model. The proposed approach is applied to several

production scheduling instances, and results are compared with other approaches. Experiments show that the

result from the proposed approach is substantially better than those obtained from other approaches. It is

demonstrated that our approach can effectively reduce production tardiness and improve efficiency.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6414611

1. An Intelligent Decision Support System for the Operating Theater: A Case Study

Sperandio, F. ;   Gomes, C. ;   Borges, J. ;   Brito, A.C. ;   Almada-Lobo, B.

Abstract:

From long to short term planning, decision processes inherent to operating theater organization are often

subject of empiricism, leading to far from optimal results. Waiting lists for surgery have always been a

societal problem, which governments have been fighting with different management and operational stimulus

plans. The current hospital information systems available in Portuguese public hospitals, lack a decision

support system component that could help achieve better planning solutions. Thus, an intelligent decision

support system has been developed, allowing the centralization and standardization of planning processes,

improving the efficiency of the operating theater and tackling the waiting lists for surgery fragile

situation. The intelligence of the system derives from data mining and optimization techniques, which

enhance surgery duration predictions and operating rooms surgery schedules. Experimental results show

significant gains, reducing overtime, undertime, and better resource utilization.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6410367

1. Degree of Redundancy of Linear Systems Using Implicit Set Covering

Arellano, J.D. ;   Hicks, I.V.

Abstract:

In this paper, we present a set covering problem (SCP) formulation to compute the degree of redundancy of linear systems. Computing the degree of redundancy of a linear system allows for the evaluation of the quality of the sensor network. The formulation is equivalent to solving the linear matroid cogirth problem, finding the cardinality of the smallest cocircuit of a matroid. We also discuss existing methods developed to solve the matroid cogirth problem and the SCP. Computational results are provided to validate a branch-and-cut algorithm that addresses the SCP formulation.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6558498

1. Extended Interference Matrices for Exploded View of Assembly Planning

Yu, J. ;   Xu, L.D. ;   Bi, Z. ;   Wang, C.

Abstract:

One of the tasks in assembly planning is to create the exploded views for the visualization purpose and the verification of assembly plans. In this paper, we introduce how to generate exploded views automatically from an assembly model. To increase the level of automation, a new relational matrix called extended interference matrix (EIM) is used to represent the assembly relations among constitutive parts. Information in an EIM is used to create the exploded views. An innovative method is developed to generate the exploded views based on the assembly sequences and EIMs. The corresponding Application Programming Interface (API) to the Unigraphics software has been developed as an integration of the algorithm with the CAD software tool. The assembly model of a gear reducer is used as a case study.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6416096

1. Algorithms for Routing an Unmanned Aerial Vehicle in the Presence of Refueling Depots

Sundar, K. ; Rathinam, S.

Abstract:

We consider a single Unmanned Aerial Vehicle (UAV) routing problem where there are multiple depots and the vehicle is allowed to refuel at any depot. The objective of the problem is to find a path for the UAV such that each target is visited at least once by the vehicle, the fuel constraint is never violated along the path for the UAV, and the total fuel required by the UAV is a minimum. We develop an approximation algorithm for the problem, and propose fast construction and improvement heuristics to solve the same. Computational results show that solutions whose costs are on an average within 1.4% of the optimum can be obtained relatively fast for the problem involving five depots and 25 targets.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6619438

1. Parallel Machine Selection and Job Scheduling to Minimize Sum of Machine Holding

Cost, Total Machine Time Costs, and Total Tardiness Costs

Bahram Alidaee; Haitao Li

Abstract:

This paper is concerned with scheduling of a set of single-operation tasks on a set of parallel machines

where subcontracting is allowed. The objective is to choose a subset of machines/subcontractors from a set

of available machines/subcontractors to perform all jobs to minimize sum of several costs. Processing time

of jobs is assumed to be equal. Lower and upper bound for number of jobs assigned to a

machine/subcontractor is considered. We first present a comprehensive survey of applications and models. We

show special case of the problem when lower bound for number of jobs assigned to each machine/subcontractor

is equal to zero is equivalent to single-sink fixed-charge transportation problem (SSFCT). This proves NP-

hardness of the problem. Efficient dynamic programming algorithm for this special case is presented.

Complicating issues regarding the general case with nonzero lower bounds for number of jobs assigned to

machines/subcontractors is discussed. We transfer the general problem to multiple choice knapsack problem

(MCKP) that can be solved efficiently using available algorithms. Several new problems are introduced.

Complexity of each problem is resolved. Transformation to MCKP is provided that allows available algorithms

to solve the problems. The main contribution of this paper is to establish theoretical results regarding

the solution of these difficult problems.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6478848

1. An Improved Mixed Integer Programming Approach for Multi-Hoist Cyclic Scheduling Problem

Che, A. ;   Lei, W. ;   Feng, J. ;   Chu, C.

Abstract:

This paper addresses the single-track multi-hoist cyclic scheduling problem. In most existing studies,

loaded hoist moves are implicitly or explicitly assumed to start and end within the same cycle. We give a

counterexample to demonstrate that the optimal solution obtained with such an assumption is not necessarily

the best one among all feasible solutions, called globally optimal solution. To obtain a globally optimal

solution, we propose an improved mixed integer programming (MIP) approach for the multi-hoist cyclic

scheduling problem with relaxation of the above assumption. Computational results on benchmark and randomly

generated instances are reported and analyzed.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6522200

1. Robust Electromagnetic Control of Microrobots Under Force and Localization Uncertainties

Marino, H. ;   Bergeles, C. ;   Nelson, B.J.

Abstract:

Microrobots are promising tools for micromanipulation and minimally invasive interventions. Robust

electromagnetic control of microrobots can be achieved through precisely modeled magnetic steering systems

and accurate localization. Error-free modeling and position information, however, are not realistic

assumptions, and microrobots need to be controlled under force and localization uncertainties. In this

paper, methods to account for these types of uncertainties are presented. Initially, the uncertainties in

electromagnetic force generation of a new class of manipulation systems are quantified. Subsequently, a

drag-force uncertainty model for linear dynamics is proposed. This model can be employed for microrobots

whose fluid dynamics are not well understood. A set of performance measures is introduced in the design of

controllers, and a PID and a robust ${cal H}_infty$ controller are synthesized and evaluated through

simulations. To demonstrate the capabilities of the synthesized controllers under localization and force

uncertainties, low update rates are considered. The ${cal H}_infty$  controller can provably respect the

performance measures under higher uncertainties than the PID controller, and its performance is further

quantified through experiments in a prototype electromagnetic control system.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6552206

1. Emulating Nuclear Emissions With a Pulsed Laser

Hockman, B.J. ;   Sun, J. ;   Tanner, H.G.

Abstract:

This paper presents an approach to emulate the Poisson process observed by a sensor when subject to low

levels of radiation, motivated by the problem of detecting a weak source in the presence of background

radiation. We construct a physical emulation of this process to serve as a means of experimentation for

various detection models involving mobile sensor networks. A pulsing laser emulates the nuclear emission,

and a rotating mirror deflects the pulses in a random direction. The degree to which the proposed emulation

process matches actual radiation measurement results is assessed experimentally, and the utility of the

device is demonstrated and compared against conventional methods in a simple detection scenario.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6508871

_.___________________________________________________________________._

Contributed by: Yulin Lei < leiyl11@mails.tsinghua.edu.cn >

Selections from the IEEE Transactions on Control Systems Technology

Volume: 22 Issue: 1

January 2014

1. Organizational Control of Discrete-Event Systems: A Hierarchical Multiworld

Supervisor Design

Seow, K.T.

Abstract:

An organizational control architecture for supervising a class of multilevel hierarchical discrete-event

systems is proposed in this paper. The architecture can be built on the basis of a standard scalable

hierarchical design method, formalizing a common design practice of structuring the control of a discrete-

event organization bottom-up into a consistent multiworld control hierarchy. It is shown that, under some

mild condition of fairness, a multilevel recursive control law exists that is optimal and nonblocking. This

law governs the hierarchy top-down as a dynamic programming recursion, over which an organizational control

algorithm is obtained that computes the control decisions partially online and in linear time. It is

explained and illustrated how the approach reduces the complexity of off-line control synthesis and

increases the online transparency of control operations.

Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6471770

_.___________________________________________________________________._

The End

_.___________________________________________________________________._