The Multi-Objective Shortest Path (MOS) problem finds a set of unique Pareto-optimal paths from a source to a destination in a multi-attribute graph. This NP-hard problem exhibits exponential complexity growth with increasing objectives, rendering exact solutions computationally intractable. This paper presents MPMOS, the first GPU-accelerated architecture for exact MOS computation, addressing three key challenges: irregular label processing, unpredictable memory requirements that exceed static limits, and maintaining correctness under massive parallelism. Our contributions include: (1) concurrent extraction and processing of lexicographically ordered labels, (2) work-aware label distribution, (3) label-level vectorization with objective-aware dominance and pruning checks, (4) smart compaction to eliminate fragmentation in data structures, and (5) dynamic memory allocation enabling scalability to an increasing number of objectives. Experimental evaluation on NVIDIA GH200 across real-world maritime vessel routing and road network graphs shows MPMOS achieves an order of magnitude geometric mean speedup over a CPU parallel MOS, and two orders of magnitude over a state-of-the-art sequential MOS algorithm with exact Pareto-optimality maintained. The dynamic memory allocator enables GPU acceleration for exact multi-objective optimization at unprecedented computational scales.

The Multi-Objective Shortest-Path (MOS) problem finds a set of Pareto-optimal solutions from a start node to a destination node in a multi-attribute graph.The literature explores multi-objective A*-style algorithmic approaches to solving the NP-hard MOS problem.These approaches use consistent heuristics to compute an exact set of solutions for the goal node.A generalized MOS algorithm maintains a "frontier" of partial paths at each node and performs ordered processing to ensure that Pareto-optimal paths are generated to reach the goal node.The algorithm becomes computationally intractable at a higher number of objectives due to a rapid increase in the search space for non-dominated paths and the significant increase in Pareto-optimal solutions.While prior works have focused on algorithmic methods to reduce the complexity, we tackle this challenge by exploiting parallelism to accelerate the MOS problem.The key insight is that MOS algorithms rely on the ordered execution of partial paths to maintain high work efficiency.The proposed parallel algorithm (OPMOS) unlocks ordered parallelism and efficiently exploits the concurrent execution of multiple paths in MOS.Experimental evaluation using the NVIDIA GH200 Superchip's 72-core Arm-based CPU shows the performance scaling potential of OPMOS on work efficiency and parallelism using a real-world application to ship routing.

In numerous applications, the challenge of path planning in continuous spaces is a critical issue, commonly tackled using heuristic algorithms. However, humans follow paths that diverge significantly from those produced by these approaches, underscoring the salience of semantic preferences of humans. To address this gap, we present an algorithm that selects the optimal path by evaluating relative rewards within a probabilistic framework. The challenges posed by the complexity of continuous space, concerning the distribution shapes influenced by obstacles, are effectively managed through a particle-based approach, demonstrating the remarkable flexibility and adaptability of the probabilistic framework.

Power electronic (PE) reliability is critical to electric vehicle performance and safety. Thus, it is vital to predict the remaining useful life (RUL) of components that are subject to predictable degradation. Here, we propose a RUL estimation framework for PE components. The framework has two consecutive phases: Generation of distance-based health indicators through an unsupervised learning procedure, such as self-organizing map (SOM) or K-means clustering, and subsequent deployment of interacting multiple model (IMM) that integrate linear and extended Kalman filters with varied degradation profiles to forecast future values of the indicator and RUL. Specifically, a nominal SOM or K-means model is learned, using theon-state median signal data from the PE component. The indicator is then calculated by measuring the distance between the test vector and the cluster center. To adaptively track the health indicator and its rate of change, accounting for the noise intrinsic to degradation processes, various degradation profiles, and the measurement system, the IMMs are applied. The RUL is evaluated as the difference between a predefined threshold and the health indicator estimate, divided by the present degradation rate. Validation of the framework involved accelerated aging experimental datasets, encompassing both low-frequency and high-frequency switching scenarios. The results reveal the framework's versatility and potential for implementation across diverse applications.

Hybrid models are increasingly employed to simulate intricate physical processes by combining domain expertise embedded in physics-based models with process measurements-based data. The combination of domain knowledge and measurement data results in hybrid models that lead to high-accuracy decisions, extrapolation capabilities, and compliance with basic physical laws. Surrogate modeling, one aspect of hybrid modeling, involves a simplified model to capture the physics in a process, emphasizing an adaptable mathematical expression. This study applies hybrid modeling to address the intricate tool wear process in precision machining by developing a recursive model using symbolic regression.

This paper presents a mechanism for evaluating the Root Mean Square Error (RMSE) of a Minimum Variance Unbiased Estimator (MVUE) of a target state in 3D space using acoustic measurements. The target state is represented by $(\theta, \phi, r)$ and it is estimated using Time Difference of Arrival measurements at the sensors and we assume that the sound-speed c is unknown. We then examine the interaction between azimuth angle $\theta$ on range RMSE, and the impacts of measurement noise variance on RMSE of $(\theta, \phi, r, c)$ estimates. These results and analytical formulations can be used as a baseline to evaluate proper 3D array geometry design, as well as inform the potential RMSE improvements when using a biased minimum mean square error (MMSE) estimator over an unbiased (MVUE) one for the same set of measurements.

In precision machining, predicting the tool health can improve productivity, job quality, and reduce machine downtime and energy consumption. While deep learning (DL) algorithms have garnered recent interest, they lack the physics understanding associated with machining processes. To address this limitation, we present a symbolic regression framework for tool wear diagnostics. The method explores analytical symbolic expressions using health indicators and cutting settings. Tool health indicators are computed from wavelet subspaces of vibration signals by applying a distance metric to the wavelet coefficients. These indicators are strongly correlated with tool wear measurements, making them suitable for tool wear diagnostics. We applied the developed framework to the IEEE PHM 2010 data, which comprises three sets of run-to-failure machining tests conducted with three tools. The framework predicted tool wear with an$R^{2}$of 0.947 and a mean absolute error (MAE) of 0.006 mm across test sets. The results demonstrate the effectiveness of the symbolic regression approach for tool wear diagnostics, showcasing the richness of information in the indicators and the quality of the developed model$\mathbf{for}$tool wear estimation.

This paper develops computationally efficient algorithms for the analysis of acoustic data to localize a target through improved angle of arrival estimation. The passive target localization problem has a wide range of applications in wireless communication, navigation, acoustic sensor networks, indoor localization, to name a few. We have focused on novel formulations and solution methods for target localization using Time Differences of Arrival (TDOA) among distinct pairs of passive sensor nodes in an acoustic sensor network with known sensor positions.

Planning ship routes that take into account meteorological and oceanographic conditions is a salient problem for both commercial and Naval applications. The A* algorithm is a very common method for finding the minimum cost path in a graph. Finding appropriate heuristics for a cost function is critical to the computational efficiency and memory requirements of the A* algorithm. We propose heuristic evaluation functions (HEFs) based on the minimum, mean, median, and mode of the cost function values over the reachable nodes given time constraints. Only the HEF based on the minimum is admissible, but we show that the other heuristics are able to find near-optimal solutions in substantially shorter times than the Dijkstra's algorithm, which does not use a heuristic. We evaluate these heuristics over many scenarios and show that overall the HEF based on the mean value performs the best. This HEF can be used in time-critical applications where an occasional loss of optimality is sacrificed for faster run time, such as real-time planning and control, or as part of a multi-objective shortest path algorithm for planning and execution.

This paper proposes an integrated software-hardware approach for automated bathymetry mapping using low-cost unmanned surface vehicles (USVs). The solution takes inspiration from adaptive sampling, aiming to minimize the time, hardware, and training costs compared to traditional coverage path planning (CPP) methods. The proposed approach implements a scalable Markov Decision Process (MDP)-based model and a planning method based on multi-agent approximate dynamic programming (ADP), which prescribes USVs to seek the most informative samples in bandwidth-limited environments with uncertain and incomplete prior map information. The control structure offloads surrogate model updates and path planning to the control station and ensures mission completion even with communication dropouts. Computer simulation results on both real-world and computer-generated bathymetry data demonstrate the effectiveness of the proposed approach in terms of predictive accuracy and efficiency. The proposed solution has the potential to significantly aid coastal development by streamlining access to accurate models of near-shore bathymetry.

This work formalizes the Route Planning Problem (RPP), wherein a set of distributed assets (e.g., ships, submarines, unmanned systems) simultaneously plan routes to optimize a team goal (e.g., find the location of an unknown threat or object in minimum time and/or fuel consumption) while ensuring that the planned routes satisfy certain constraints (e.g., avoiding collisions and obstacles). This problem becomes overwhelmingly complex for multiple distributed assets as the search space grows exponentially to design such plans. The RPP is formalized as a Team Discrete Markov Decision Process (TDMDP) and we propose a Multi-agent Multi-objective Reinforcement Learning (MaMoRL) framework for solving it. We investigate challenges in deploying the solution in real-world settings and study approximation opportunities. We experimentally demonstrate MaMoRL's effectiveness on multiple real-world and synthetic grids, as well as for transfer learning. MaMoRL is deployed for use by the Naval Research Laboratory - Marine Meteorology Division (NRL-MMD), Monterey, CA.

Performance of a Li-ion battery is affected by temperature; low temperature causes reduced power output and high temperature affects state of health and compromises safety. To overcome these challenges and for reliable performance of batteries, thermal management is needed in electric vehicles. This paper presents a thermal-electrical equivalent circuit model to predict the surface temperature of a battery. Three algorithms are presented for the estimation of thermal-electrical equivalent model parameters. These algorithms are based on least square, constrained least squares, and weighted least squares respectively. It is shown that the performance of a battery thermal model parameter estimation approach can suffer from measurement noise. The performance of the algorithms are compared using computer simulations at various signal-to-noise levels. It is found that the weighted least squares based approach outperforms the other two approaches in parameter estimation accuracy.

This paper develops an easily-implementable version of Page's CUSUM quickest-detection test, designed to work in certain composite hypothesis scenarios with time-varying data statistics. The decision statistic can be cast in a recursive form and is particularly suited for on-line analysis. By back-testing our approach on publicly-available COVID-19 data we find reliable early warning of infection flare-ups, in fact sufficiently early that the tool may be of use to decision-makers on the timing of restrictive measures that may in the future need to be taken.

Fault prognosis of the air-handling systems, which are the key subsystems of heating, ventilation, and air conditioning systems, allows system operators to know the remaining useful life (RUL), thus preventing unexpected breakdowns and reducing the operational and maintenance costs. In this article, a new hidden semi-Markov model-based method is developed. In the method, only relevant state-transition points are selected and estimated, leading to computational efficiency. Physics-based models are used in a novel way to provide “mapping matrices” relating component capacities to fault severities, capturing impacts of multiple failure modes. Experimental results show that our method can effectively estimate the RUL of the components and the systems.

Adaptive bitrate streaming (ABR) has become the de facto technique for video streaming over the Internet. Despite a flurry of techniques, achieving high quality ABR streaming over cellular networks remains a tremendous challenge. ABR streaming can be naturally modeled as a control problem. There has been some initial work on using PID, a widely used feedback control technique, for ABR streaming. Existing studies, however, either use PID control directly without fully considering the special requirements of ABR streaming, leading to suboptimal results, or conclude that PID is not a suitable approach. In this paper, we take a fresh look at PID-based control for ABR streaming. We design a framework called PIA (PID-control based ABR streaming) that strategically leverages PID control concepts and incorporates several novel strategies to account for the various requirements of ABR streaming. We evaluate PIA using simulation based on real LTE network traces, as well as using real DASH implementation. The results demonstrate that PIA outperforms state-of-the-art schemes in providing high average bitrate with significantly lower bitrate changes (reduction up to 40 percent) and stalls (reduction up to 85 percent), while incurring very small runtime overhead. We further design PIA-E (PIA Enhanced), which improves the performance of PIA in the important initial playback phase.

This paper presents a predictive data analytics process for examining the relationship between team communication and performance in planning tasks. Team performance is measured in terms of the time each team spends in completing the planning task and the cost of the concomitant work schedule. The predictive data analytics process encompasses three data abstraction techniques for data preparation, three probabilistic models that represent the temporal features of data abstracted from team communication interactions, and a validation process that selects the best pair of data abstraction and model for subsequent insight analysis. Experimental data obtained from 32 teams of three members each, tasked to solve a personnel scheduling problem, is used for validating the proposed methodology.

Anti-submarine warfare (ASW) missions are the linchpin of maritime operations involving effective allocation and path planning of scarce assets to search for, detect, classify, track, and prosecute hostile submarines within a dynamic and uncertain mission environment. Motivated by the need to assist ASW commanders to make better decisions within an evolving mission context, we investigate a moving target search problem with multiple searchers and develop a context-driven decision support tool for the ASW mission planning problem. Given the spatial probability distribution of a target submarine, sensor detection probability surfaces from meteorological and oceanographic products, and the risk to the fleet as a function of distance of the target from the fleet, we model and formulate the ASW asset allocation and search path planning problem using a hidden Markov modeling framework. We propose a two phase approach to solve this NP-hard problem. In phase I, we partition the geographic area, satisfying contiguity constraints, into search regions using an evolutionary algorithm (EA) coupled with a Voronoi tessellation approach, and allocate the assets to partitioned search areas using the auction algorithm. In phase II, we construct a dynamic search plan for each asset over the search interval using EA. We evaluate our approach via a hypothetical ASW scenario to monitor an enemy submarine in a geographic region via multiple assets. We compare our results to various search path planning strategies that, using the context-driven decision support tool developed here, revise the search regions at periodic intervals given a fixed total search time.

This paper validates two approximate dynamic programming approaches on a maritime interdiction problem involving the allocation of multiple heterogeneous assets over a large area of responsibility to interdict multiple drug smugglers using heterogeneous types of transportation on the sea with varying contraband weights. The asset allocation is based on a probability of activity surface, which represents spatio-temporal target activity obtained by integrating intelligence data on drug smuggler whereabouts/waypoints for contraband transportation, behavior models, and meteorological and oceanographic information. We validate the proposed architectural and algorithmic concepts via several realistic mission scenarios. We conduct sensitivity analyses to quantify the robustness and proactivity of our approach, as well as to measure the value of information used in the allocation process. The contributions of this paper have been transitioned to and are currently being tested by Joint Interagency Task Force-South, an organization tasked with providing the initial line of defense against drug trafficking in the East Pacific and Caribbean Oceans.

Streaming videos over cellular networks is highly challenging. Since cellular data is a relatively scarce resource, many video and network providers offer options for users to exercise control over the amount of data consumed by video streaming. Our study shows that existing data saving practices for Adaptive Bitrate (ABR) videos are suboptimal: they often lead to highly variable video quality and do not make the most effective use of the network bandwidth. We identify underlying causes for this and propose two novel approaches to achieve better tradeoffs between video quality and data usage. The first approach is Chunk-Based Filtering (CBF), which can be retrofitted to any existing ABR scheme. The second approach is QUality-Aware Data-efficient streaming (QUAD), a holistic rate adaptation algorithm that is designed ground up. We implement and integrate our solutions into two video player platforms (dash.js and ExoPlayer), and conduct thorough evaluations over emulated/commercial cellular networks using real videos. Our evaluations demonstrate that compared to the state of the art, the two proposed schemes achieve consistent video quality that is much closer to the user-specified target, lead to far more efficient data usage, and incur lower stalls.

Adaptive Bitrate (ABR) video streaming is widely used for over-the-top (OTT) video delivery. Recently, streaming providers have been moving towards using Variable Bitrate (VBR) encodings for the video content, spurred by the potential of improving user QoE (Quality of Experience) and reducing network bandwidth requirements compared to Constant Bitrate (CBR) encodings. However VBR introduces new challenges for ABR streaming, whose nature and implications are little understood. We explore these challenges across diverse video genres, encoding technologies, and platforms. We identify distinguishing characteristics of VBR encodings that impact user QoE and should be factored in any ABR adaptation decision. Traditional ABR adaptation strategies designed for the CBR case are not adequate for VBR. We develop novel best practice design principles to guide ABR rate adaptation for VBR encodings. As a proof of concept, we design a novel and practical control-theoretic rate adaptation scheme, CAVA (Control-theoretic Adaption for VBR-based ABR streaming), incorporating these concepts. Extensive evaluations show that CAVA substantially outperforms existing state-of-the-art adaptation techniques, validating the importance of these design principles.

Routing in uncertain environments is challenging as it involves a number of contextual elements, such as different environmental conditions (forecast realizations with varying spatial and temporal uncertainty), changes in mission goals while en route, and asset status. In this paper, we use an approximate dynamic programming method with Q-factors to determine a cost-to-go approximation by treating the weather forecast realization information as a stochastic state. These types of algorithms take a large amount of offline computation time to determine the cost-to-go approximation, but once obtained, the online route recommendation is nearly instantaneous and several orders of magnitude faster than previously proposed ship routing algorithms. The proposed algorithm is robust to the uncertainty present in the weather forecasts. We compare this algorithm to a well-known shortest path algorithm and apply the approach to a real-world shipping tragedy using weather forecast realizations available prior to the event.

We consider the problem of point target detection on images and focal plane arrays (FPA). Imaging sensors are becoming ubiquitous tools in several applications, such as biomedical systems, autonomous surveillance systems, target tracking systems, and robotics. In these applications, matched filter and template matching are commonly used detection strategies, however, these approaches are unable to provide sub-pixel accuracy and avenues for adaptive pixel-width selection for computationally efficient image processing. In this paper, we derive the maximum likelihood estimator (MLE) of target location on images. The proposed MLE is optimal under the assumption that the FPA contains a point target that has its signal intensity spread in multiple image pixels in the form of a Gaussian point spread function (PSF) with known standard deviation. Further, we derive the Cramér-Rao lower bound (CRLB) of the estimate and present the hypothesis test for target acceptance, resulting in a novel maximum likelihood detector (MLD) for images. Simulation results are provided to validate the performance of the proposed MLE and MLD; it is shown that the MLE is efficient in very low SNR values, starting at -15 dB, and the MLD achieves probability of detection of near unity with zero false alarms starting at 0 dB.

Adaptive bitrate streaming (ABR) has become the de facto technique for video streaming over the Internet. Despite a flurry of techniques, achieving high quality ABR streaming over cellular networks remains a tremendous challenge. ABR streaming can be naturally modeled as a feedback control problem. There has been some initial work on using PID, a widely used feedback control technique, for ABR streaming. Existing studies, however, either use PID control directly without fully considering the special requirements of ABR streaming, leading to suboptimal results, or conclude that PID is not a suitable approach. In this paper, we take a fresh look at PID-based control for ABR streaming. We design a framework called PIA that strategically leverages PID control concepts and incorporates several novel strategies to account for the various requirements of ABR streaming. We evaluate PIA using simulation based on real LTE network traces, as well as using real DASH implementation. The results demonstrate that PIA outperforms state-of-the-art schemes in providing high average bitrate with significantly lower bitrate changes (reduction up to 40%) and stalls (reduction up to 85%), while incurring very small runtime overhead.

In a heating, ventilation, and air conditioning system, an air-handling system is a key module. Its components (e.g., air handling unit, air-mixing box, and fans), linked through airflows, condition air to a desired temperature and/or humidity based on comfort or controlled environment requirements. Identifying failure modes and estimating their severities allow maintenance crews to know which faults have occurred, how critical they are, and be guided in the repair process to improve the system availability. The problem of fault detection and diagnosis in air-handling systems is complex because of fault propagation across components, and high false alarm rates caused by uncertainties in system and measurement dynamics. In this paper, to capture fault propagation impacts in an efficient manner, dynamic hidden Markov models are developed to identify failure modes, since they contain state transition matrices depending on other components and do not generate joint states. To filter out false alarms, “coupled statistical process control” techniques are developed by using state transitions matrices representing coupling among components. Experimental results show that the method can effectively diagnose faults with high-diagnosis accuracy. Note to Practitioners-Faults in heating, ventilation, and air conditioning air handling units (AHU) may cause high energy consumption and discomfort to occupants. Fault diagnosis in AHU is challenging since: 1) effects of faults propagate across components connected by airflows and 2) measurement noises may cause high false alarm rates. In this paper, a novel fault diagnosis method is established to identify failure modes and fault severities. This method explicitly considers the fault coupling among components. To reduce false alarm rates, new statistical process control techniques are developed to filter out false alarms. Experimental results show that our method can effectively diagnose faults with high diagnosis accuracy.

This paper presents a mixed-initiative tool for multiobjective planning and asset routing (TMPLAR) in dynamic and uncertain environments. TMPLAR is built upon multiobjective dynamic programming algorithms to route assets in a timely fashion, while considering fuel efficiency, voyage time, distance, and adherence to real world constraints (asset vehicle limits, navigator-specified deadlines, etc.). TMPLAR has the potential to be applied in a variety of contexts, including ship, helicopter, or unmanned aerial vehicle routing. The tool provides recommended schedules, consisting of waypoints, associated arrival and departure times, asset speed and bearing, that are optimized with respect to several objectives. The ship navigation is exacerbated by the need to address multiple conflicting objectives, spatial and temporal uncertainty associated with the weather, multiple constraints on asset operation, and the added capability of waiting at a waypoint with the intent to avoid bad weather, conduct opportunistic training drills, or both. The key algorithmic contribution is a multiobjective shortest path algorithm for networks with stochastic nonconvex edge costs and the following problem features: 1) time windows on nodes; 2) ability to choose vessel speed to next node subject to (minimum and/or maximum) speed constraints; 3) ability to select the power plant configuration at each node; and 4) ability to wait at a node. The algorithm is demonstrated on six real world routing scenarios by comparing its performance against an existing operational routing algorithm.

In this paper, we propose a Markov chain-based testability growth model (TGM) for the just in-time fix program. This model can help the system designers to manage the testability growth process during system maturation. We also derive a cost-benefit model for allocating test resources to optimize a specified testability metric subject to a constraint on cumulative test cost. Bayesian inference, coupled with a hybrid genetic and particle swarm optimization method, is used to estimate the parameters of the TGM from evolving data, and the resulting model is utilized to track and project the testability metric. A near-optimal Lagrangian relaxation-based algorithm is applied to solve the test resource allocation problem. The testability growth and resource allocation models are validated via simulation examples. Results show that the model and algorithms presented in this paper have the potential to efficiently manage the testability growth problem.

Counter-smuggling operations constitute a high priority national security mission since drug-trafficking not only involves many criminals, but can also be a source of financing for many illicit activities such as narco-terrorism and arms trafficking. The counter-smuggling mission involves surveillance operations (to search, detect, track and identify potential threats) and interdiction operations (to intercept, investigate and potentially apprehend suspects). Potential smuggling activity is represented in the form of color-coded heat maps built using intelligence and meteorological and oceanographic information, which are interpreted in the form of probability of activity (PoA) surfaces. The PoA surfaces constitute the “sufficient statistics” for the asset allocation and scheduling processes. However, in the case of disconnected, intermittent, and low-bandwidth environments, the problem of allocating resources becomes very challenging as PoA information is unavailable or is not up to date. In this paper, we propose to utilize flow (historic PoA)-based surfaces, which provide cues on where the smugglers may have traversed in the past. Using the flow surfaces, we allocate the surveillance and interdiction assets to best thwart potential smuggling activities. We further evaluate the quality of our solution in terms of the number of targets interdicted and the amount of contraband seized.

In this paper, we introduce a collaborative learning problem that is applicable in multi-agent data mining using heterogeneous computing resources in environments with limited control, resource failures, and communication bottlenecks. Specifically, we consider the scenario in which multiple agents collect noisy and overlapping information regarding an entity, such as a network attribute, which might correspond to multiple models. The agents are unable to share the entire information due to communication bottlenecks and other strategic issues; instead, the agents share their “local estimate” about the entity. The objective is to obtain the best estimate of the true value of the entity based on the local estimates shared by the agents. First, we derive a centralized solution where the locally processed information from each agent is assumed available at a central node. Then, we develop a distributed solution to the problem that is suitable to environments with limited control, resource failures, and communication bottlenecks.

Anti-Submarine Warfare (ASW) involves effective allocation and path planning of ASW platforms to search for, detect, classify, track and prosecute hostile submarines within an evolving environment. As the environmental context evolves rapidly, continuously collected Meteorological and Oceanographic (METOC) data is used for assessing the impact of the current and forecasted environment on individual sensors and weapon platforms, as well as on tactics in the form of performance surfaces, which is presented to the commanders in making go/no-go decisions. However, due to the overwhelming amount of METOC information, it is very challenging for the commanders to interpret and analyze the data for generating plans or evaluating courses of action in a timely manner. In this paper, motivated by the need to assist ASW commanders in making proactive decisions in an evolving environmental context, we present a decision support tool for modeling and incorporating the appropriate METOC information from multiple sources and further utilizing it to determine the search regions and optimal trajectories to search for and track the enemy submarines in a timely manner.

Even self-deployment is one of the best strategies to deploy mobile sensors when the region of interest is unknown and manual deployment is infeasible. A widely used distributed algorithm, Lloyd`s method, can achieve even self-deployment. It however suffers from two critical issues when being used in mobile sensor networks. First, it does not consider limited sensor communication range. Second, it does not optimize sensor movement distances, and hence can lead to excessive energy consumption, a primary concern in sensor networks. This paper first formulates a locational optimization problem that achieves even deployment while it takes account of energy consumption due to sensor movement, and then proposes two iterative algorithms. The first algorithm, named Lloyd- α, reduces the movement step sizes in Lloyd`s method. It saves traveling distance while maintaining the convergence property. However, it leads to a larger number of deployment steps. The second algorithm, named Distributed Energy-Efficient self-Deployment (DEED), reduces sensor traveling distances and requires a comparable number of deployment steps as that in Lloyd`s method. This paper further proposes an intuitive method to deal with limited sensor communication range that is applicable to all three methods. Extensive simulation using NS-2 demonstrates that DEED leads to up to 54 percent less traveling distance and 46 percent less energy consumption than Lloyd`s method.

Motivated by the Navy's interest in decision support tools that augment planning activities within a maritime operations center (MOC), we have developed a multilevel resource allocation model that is capable of interacting with human planners to dynamically allocate hierarchically-organized assets to process interdependent tasks in order to accomplish mission objectives. The planning problem is formulated as a mixed-integer nonlinear programming (MINLP) problem of minimizing the overall difference between the human-specified desired task accuracy performance criteria and the expected performance outcomes, the latter being based on how well the assigned resources match the required resources, subject to a number of real-world planning constraints. To solve the resulting large-scale MINLP problem, we propose two methods: 1) a Lagrangian relaxation method that solves the multilevel asset allocation problem with a measure of sub-optimality in terms of an approximate duality gap and 2) a dynamic list planning heuristic algorithm that provides high-quality sub-optimal solutions rapidly (less than 10 s for the scenarios considered here). Finally, we verify our methods using realistic MOC planning scenarios, provide a comparative evaluation of the performance measures of the two proposed methods, and investigate the value of information via human-in-the-loop experiments.

Motivated by the need for multiple agents to collaborate in order to solve a distributed resource allocation planning problem, this paper develops a distributed framework that combines each agent's information, expertise, responsibility, and asset ownership with the goal of optimizing a given mission objective. A mission is a collection of interdependent tasks to be executed in a directed/sequential sequence. Each task is modeled by a vector of resource requirements, a processing time, and a start time (release time). Each agent has a subset of tasks for which it is responsible, and owns a set of heterogeneous assets, where each asset is modeled by a vector of resource capabilities that it provides. Multiple agents must collaboratively allocate assets to tasks to maximize an expected mission performance, defined by how well all of the tasks' requirements are satisfied by the allocated asset capabilities. Our agent-based distributed planning framework uses a blackboard communication paradigm to exchange information among agents. The framework contains an intra-agent and an interagent module that support individual and cooperative planning, respectively. The intra-agent module employs an optimization-based m-best asset allocation algorithm to match an agent's own tasks with its locally owned assets. The interagent module coordinates the exchange of information and asset allocations among agents to improve the local plans using an asset pricing mechanism, and includes a means for characterizing an agent's cooperative behavior.

This paper presents two domain-independent optimization-based planning algorithms for efficiently allocating assets that are needed to execute a set of interdependent tasks. The first algorithm is an asset package selection module that combines mixed integer programming and an extended Murty's decision space partitioning algorithm that can be used to provide human planners with a set of alternative asset packages that meet individual task requirements, while maximizing task execution accuracy. This asset package selection module was embedded in a decision aid that supported a mixed-initiative team-in-the-loop planning experiment (MOC-1) conducted at the Naval Postgraduate School in March 2009. The experiment examined the effectiveness and efficiency of two different Maritime Operations Center (MOC) organizational structures for conducting a mission planning activity that required the use of scarce resources. The second algorithm is a planning module that integrates weighted length algorithm, asset package selection module, rollout strategy, and a pairwise exchange method to assist experiment designers to set the parametric conditions for the mission planning activity (e.g., asset types and numbers, task requirements, and asset capabilities) and to assure that the tasks as presented to the human planners would, in fact, be achievable to a specified level of accuracy.

In this paper, we formulate a coupled factorial hidden Markov model-based (CFHMM) framework to diagnose dependent faults occurring over time (dynamic case). In our previous research, the problem of diagnosing multiple faults over time (dynamic multiple fault diagnosis (DMFD)) is solved based on a sequence of test outcomes by assuming that the faults and their time evolution are independent. This problem is NP-hard, and, consequently, we developed a polynomial approximation algorithm using Lagrangian relaxation within a FHMM framework. Here, we extend this formulation to a mixed memory Markov coupling model, termed dynamic coupled fault diagnosis (DCFD) problem, to determine the most likely sequence of (dependent) fault states, the one that best explains the observed test outcomes over time. An iterative Gauss-Seidel coordinate ascent optimization method is proposed for solving the DCFD problem. A soft Viterbi algorithm is also implemented within the framework for decoding-dependent fault states over time. We demonstrate the algorithm on simulated systems with coupled faults and the results show that this approach improves the correct isolation rate (CI) as compared to the formulation where independent fault states (DMFD) are assumed. As a by-product, we show empirically that, while diagnosing for independent faults, the DMFD algorithm based on block coordinate ascent method, although it does not provide a measure of suboptimality, provides better primal cost and higher CI than the Lagrangian relaxation method for independent fault case. Two real-world examples (a hybrid electric vehicle, and a mobile autonomous robot) with coupled faults are also used to evaluate the proposed framework.

The set-covering problem is widely used to model many real-world applications. In this paper, we formulate a generalization of set-covering, termed dynamic set-covering (DSC), which involves a series of coupled set-covering problems over time. We motivate the DSC problem from the viewpoint of a dynamic multiple fault diagnosis problem, wherein faults, possibly intermittent, evolve over time; the fault-test dependencies are deterministic (components associated with passed tests cannot be suspected to be faulty and at least one of the components associated with failed tests is faulty), and the test outcomes may be observed with delay. The objective of the DSC problem is to infer the most probable time sequence of a parsimonious set of failure sources that explains the observed test outcomes over time. The DSC problem is NP-hard and intractable due to the fault-test dependency matrix that couples the failed tests and faults via the constraint matrix, and the temporal dependence of failure sources over time. By relaxing the coupling constraints using Lagrange multipliers, the DSC problem can be decoupled into independent subproblems, one for each fault. Each subproblem is solved using the Viterbi decoding algorithm, and a primal feasible solution is constructed by modifying the Viterbi solutions via a heuristic. The Lagrange multipliers are updated using a subgradient method. The proposed Viterbi-Lagrangian relaxation algorithm provides a measure of suboptimality via an approximate duality gap. As a major practical extension of the above problem, we also consider the problem of diagnosing faults with delayed test outcomes, termed delay DSC. A detailed experimental evaluation of the algorithms is provided using real-world problems that exhibit masking faults.

In this paper, we propose new formulations for the problem of test selection in the presence of imperfect tests in order to minimize the total costs of tests subject to lower bound constraints on fault detection and fault isolation. Our formulation allows tests to have multiple outcomes and delays caused by fault propagation, reporting, and transmission. Since the test selection problem is NP-hard even in the presence of perfect binary tests with no delays, we propose genetic algorithm (GA) and Lagrangian relaxation algorithm (LRA) to solve this problem. GA is a general approach for solving the problem with imperfect tests, including the scenarios with delayed and multiple test outcomes. The LRA is suitable for problems with perfect tests, including multiple outcomes. A key advantage of the LRA approach is that it provides an approximate duality gap, which is an upper bound measure of suboptimality of the solution. Our formulations and algorithms are tested on various real-world and simulated systems, and comparisons are made with previous test selection methods developed for perfect tests with no delays. The results show that our methods can efficiently solve the imperfect test selection problem. In addition, they have better performance (measured in terms of the number of tests used) than the methods in the literature for the perfect test selection cases. Finally, the GA has better computational efficiency than the LRA for all of the scenarios with perfect tests.

In this paper, we propose a delay dynamic coupled fault diagnosis (DDCFD) model to deal with the problem of coupled fault diagnosis with fault propagation/transmission delays and observation delays with imperfect test outcomes. The problem is to determine the most likely set of faults and their time evolution that best explains the observed test outcomes over time. It is formulated as a combinatorial optimization problem, which is known to be NP-hard. Since the faults are coupled, the problem does not have a decomposable structure as, for example, in dynamic multiple fault diagnosis, where the coupled faults and delays are not taken into account. Consequently, we propose a partial-sampling method based on annealed maximum a posteriori (MAP) algorithm, a method that combines Markov chain Monte Carlo and simulated annealing, to deal with the coupled-state problem. By reducing the number of samples and by avoiding redundant computations, the computation time of our method is substantially smaller than the regular annealed MAP method with no noticeable impact on diagnostic accuracy. Besides the partial-sampling method, we also propose an algorithm based on block coordinate ascent and the Viterbi algorithm (BCV) to solve the DDCFD problem. It can be considered as an extension of the method used to solve the dynamic coupled fault diagnosis (DCFD) problem. The model and algorithms presented in this paper are tested on a number of simulated systems. The results show that the BCV algorithm has better accuracy but results in large computation time. It is only feasible for problems with small delays. The partial-sampling algorithm has a smaller computation time with an acceptable diagnostic accuracy. It can be used on systems with large delays and complex topological structure.

This paper presents a multi-level operational command and control (C2) architecture that is applicable to the Navy's maritime operations centers (MOCs) for assessing, planning and executing multiple missions and tasks across a range of military operations. The control architecture consists of three levels: strategic level control (SLC), operational level control (OLC) and tactical level control (TLC). In addition to coordination within each level, two specific coordination layers are identified at the strategic-operational level control (SLC-OLC) and at the operational-tactical level control (OLC-TLC) interfaces. We employ a semi-Markov decision process (SMDP) approach at the SLC-OLC interface layer to optimize DIME (diplomatic, information, military and economic) actions based on national resource priorities. A distributed SMDP approach is applied to action-goal attainment (AGA) graphs at the OLC-TLC interface layer to address the mission monitoring/planning issues and to optimize the courses of action based on the outcomes of asset-task allocation at the TLC. The optimization of a hierarchy of SMDPs is accomplished by exchanging performance and mission priority information through the interface layers. Specifically, the times between decision epochs at the SLC-OLC layer are determined by the mission completion times at the OLC-TLC layer, while the mission priorities (weights) to be used in mission planning at the OLC-TLC layer are determined by DIME actions at the SLC-OLC layer. In short, we model the hierarchical decision making process by exchanging the outcomes of SMDPs between the SLC-OLC and the OLC-TLC layers to find the best courses of actions for a range of military operations.

Faulty components in a network need to be localized and repaired to sustain the health of the network. In this paper, we propose a novel approach that carefully combines active and passive measurements to localize faults in wireless sensor networks. More specifically, we formulate a problem of optimal sequential testing guided by end-to-end data. This problem determines an optimal testing sequence of network components based on end-to-end data in sensor networks to minimize expected testing cost. We prove that this problem is NP-hard, and propose a recursive approach to solve it. This approach leads to a polynomial-time optimal algorithm for line topologies while requiring exponential running time for general topologies. We further develop two polynomial-time heuristic schemes that are applicable to general topologies. Extensive simulation shows that our heuristic schemes only require testing a very small set of network components to localize and repair all faults in the network. Our approach is superior to using active and passive measurements in isolation. It also outperforms the state-of-the-art approaches that localize and repair all faults in a network.

This paper presents how information and organizational structures with point-to-point communication structure impact team coordination in a distributed task-asset allocation problem. A key distinguishing characteristic of this problem is that each decision maker knows only a part of the weight matrix and/or controls a subset of the assets. Here, we extend the distributed algorithm developed for blackboard communication structure in another part of this work to the point-to-point communication structure. Our results indicate that edge organizations with horizontal and vertical information structures exhibit shorter delays than those with block diagonal and checkerboard information structures. We also showed how our findings can be applied effectively to mission planning of the Navy's maritime operations center.

In this paper, multistage auction-based intelligence, surveillance, and reconnaissance (ISR) sensor coordination mechanisms are investigated in the context of dynamic and uncertain mission environments such as those faced by expeditionary strike groups. Each attribute of the mission task is modeled using a hidden Markov model (HMM) with controllable emission matrices, corresponding to each ISR asset package (subset of sensors). For each HMM-asset package pair, we evaluate a matrix of information gains (uncertainty reduction measures). The elements of this matrix depend on the asset coordination structure and the concomitant delays accrued. We consider three coordination structures (distributed ISR coordination, ISR officer serving as a coordinator, and ISR officer serving as a commander) here. We evaluate these structures on a hypothetical mission scenario that requires the monitoring of ISR activities in multiple geographic regions. The three structures are evaluated by comparing the task state estimation error cost, as well as travel, waiting, and assignment delays. The results of the analysis were used as a guide in the design of a mission scenario and asset composition for a team-in-the-loop experimentation. Our solution has the potential to be a mixed initiative decision support tool to an ISR coordinator/commander, where the human provides possible ISR asset package-task pairings and the tool evaluates the efficacy of the assignment in terms of task accuracy and delays. We also apply our approach to a hypothetical disaster management scenario involving chemical contamination and discuss the computational complexity of our approach.

The battery management system (BMS) is an integral part of an automobile. It protects the battery from damage, predicts battery life, and maintains the battery in an operational condition. The BMS performs these tasks by integrating one or more of the functions, such as protecting the cell, thermal management, controlling the charge-discharge, determining the state of charge (SOC), state of health (SOH), and remaining useful life (RUL) of the battery, cell balancing, data acquisition, communication with on-board and off-board modules, as well as monitoring and storing historical data. In this paper, we propose a BMS that estimates the critical characteristics of the battery (such as SOC, SOH, and RUL) using a data-driven approach. Our estimation procedure is based on a modified Randles circuit model consisting of resistors, a capacitor, the Warburg impedance for electrochemical impedance spectroscopy test data, and a lumped parameter model for hybrid pulse power characterization test data. The resistors in a Randles circuit model usually characterize the self-discharge and internal resistance of the battery, the capacitor generally represents the charge stored in the battery, and the Warburg impedance represents the diffusion phenomenon. The Randles circuit parameters are estimated using a frequency-selective nonlinear least squares estimation technique, while the lumped parameter model parameters are estimated by the prediction error minimization method. We investigate the use of support vector machines (SVMs) to predict the capacity fade and power fade, which characterize the SOH of a battery, as well as estimate the SOC of the battery. An alternate procedure for estimating the power fade and energy fade from low-current Hybrid Pulse Power characterization (L-HPPC) test data using the lumped parameter battery model has been proposed. Predictions of RUL of the battery are obtained by support vector regression of the power fade and capacity fade estimates. Survival function estimates for reliability analysis of the battery are obtained using a hidden Markov model (HMM) trained using time-dependent estimates of capacity fade and power fade as observations. The proposed framework provides a systematic way for estimating relevant battery characteristics with a high-degree of accuracy.

Task-asset assignment is a fundamental problem paradigm in a wide variety of applications. A typical problem scenario involves a single decision maker (DM) who has complete knowledge of the weight (or reward/benefit/accuracy) matrix and who can control any of the assets to execute the tasks. Motivate by planning problems arising in distributed organizations, this paper introduces a novel variation of the assignment problem, wherein there are multiple DMs and each DM know only a part of the weight matrix and/or controls a subset of the assets. We extend the auction algorithm to such realistic settings with various partial information structures and communication structures. We show that by communicating the bid, the best and the second best profits among DMs and with a coordinator, the DMs can reconstruct the centralized assignment solution. The auction setup provides a nice analytical framework for formalizing how team members build internal models of other DMs and achieve team cohesiveness over time.

Model-based fault diagnosis, using statistical hypothesis testing, residual generation (by analytical redundancy), and parameter estimation, has been an active area of research for the past four decades. However, these techniques are developed in isolation, and generally, a single technique cannot address the diagnostic problems in complex systems. In this paper, we investigate a hybrid approach, which combines model-based and data-driven techniques to obtain better diagnostic performance than the use of a single technique alone, and demonstrate it on an antilock braking system. In this approach, we first combine the parity equations and a nonlinear observer to generate the residuals. Statistical tests, particularly the generalized likelihood ratio tests, are used to detect and isolate a subset of faults that are easier to detect. Support vector machines are used for fault isolation of less-sensitive parametric faults. Finally, subset selection (via fault detection and isolation) is used to accurately estimate fault severity.

Faulty components in a network need to be localized and repaired to sustain the health of the network. In this paper, we propose a novel approach that carefully combines active and passive measurements to localize faults in wireless sensor networks. More specifically, we formulate a problem of optimal sequential testing guided by end-to-end data. This problem determines an optimal testing sequence of network components based on end-to-end data in sensor networks to minimize testing cost. We prove that this problem is NP-hard and propose a greedy algorithm to solve it. Extensive simulation shows that in most settings our algorithm only requires testing a very small set of network components to localize and repair all faults in the network. Our approach is superior to using active and passive measurements in isolation. It also outperforms the state-of-the-art approaches that localize and repair all faults in a network.

Asset assignment and scheduling algorithms were developed and implemented to support a team-in-the-loop planning experiment conducted at the Naval Postgraduate School (NPS) in March 2009. The experiment examined planning and information flows among three cells in an abstracted and simplified Maritime Operations Center (MOC). This paper describes two optimization-based modules that focused on the Future Operations (FOPS) cell's planning activities. Module 1, a FOPS Planning Module, was a decision aid that presented the planners with N-best asset packages that would meet individual task requirements, while maximizing task execution accuracy. Module 2, a Scheduling Module, was an optimization-based scheduling algorithm that was used by experiment designers to set the conditions for the mission planning activity (e.g., asset types and numbers, task requirements and asset capabilities), and to assure that the tasks presented to the human planners would be achievable to a specified level of accuracy. A third module, termed Current Operations (COPS) Risk Analysis module, not discussed in detail here, was also implemented to assist COPS players on the consequences of redirecting assets from an ongoing task.

Testing complex systems, such as the ASML TWINSCAN lithographic machine, is expensive and time consuming. In a previous work, a test sequencing method to calculate time-optimal test sequences has been developed. Because complex systems are composed of several subsystems, which are again composed of several modules, there exists a need to hierarchically model test sequencing problems. Such a hierarchical test sequencing problem consists of a high-level model that describes a test sequencing problem at the system level, and one or more low-level models that describe the test sequencing problems at the subsystem or module level. The tests at the system level correspond to the solutions of low-level problems. This paper describes a hierarchical test sequencing model and proposes two algorithms to compute an optimal test sequence. The benefits of hierarchically modeling a problem are less computational effort and less modeling effort, because not all relations are needed. This is illustrated by a small example. The industrial relevance of this method is illustrated on a case study related to a manufacturing testing phase of a lithographic machine.

In this paper, we consider a model for the dynamic multiple-fault diagnosis (DMFD) problem arising in online monitoring of complex systems and present a solution. This problem involves real-time inference of the most likely set of faults and their time-evolution based on blocks of unreliable test outcomes over time. In the DMFD problem, there is a finite set of mutually independent fault states, and a finite set of sensors (tests) is used to monitor their status. We model the dependence of test outcomes on the fault states via the traditional D-matrix (fault dictionary). The tests are imperfect in the sense that they can have missed detections, false alarms, or may be available asynchronously. Based on the imperfect observations over time, the problem is to identify the most likely evolution of fault states over time. The DMFD problem is an intractable NP-hard combinatorial optimization problem. Consequently, we decompose the DMFD problem into a series of decoupled subproblems, one for each sample epoch. For a single-epoch MFD, we develop a fast and high-quality deterministic simulated annealing method. Based on the sequential inferences, a local search-and-update scheme is applied to further improve the solution. Finally, we discuss how the method can be extended to dependent faults.

Imperfect test outcomes, due to factors such as unreliable sensors, electromagnetic interference, and environmental conditions, manifest themselves as missed detections and false alarms. This paper develops near-optimal algorithms for dynamic multiple fault diagnosis (DMFD) problems in the presence of imperfect test outcomes. The DMFD problem is to determine the most likely evolution of component states, the one that best explains the observed test outcomes. Here, we discuss four formulations of the DMFD problem. These include the deterministic situation corresponding to perfectly observed coupled Markov decision processes to several partially observed factorial hidden Markov models ranging from the case where the imperfect test outcomes are functions of tests only to the case where the test outcomes are functions of faults and tests, as well as the case where the false alarms are associated with the nominal (fault free) case only. All these formulations are intractable NP-hard combinatorial optimization problems. Our solution scheme can be viewed as a two-level coordinated solution framework for the DMFD problem. At the top (coordination) level, we update the Lagrange multipliers (coordination variables, dual variables) using the subgradient method. At the bottom level, we use a dynamic programming technique (specifically, the Viterbi decoding or Max-sum algorithm) to solve each of the subproblems, one for each component state sequence. The key advantage of our approach is that it provides an approximate duality gap, which is a measure of the suboptimality of the DMFD solution. Computational results on real-world problems are presented. A detailed performance analysis of the proposed algorithm is also discussed.

The problem of detecting an anomaly (or abnormal event) is such that the distribution of observations is different before and after an unknown onset time, and the objective is to detect the change by statistically matching the observed pattern with that predicted by a model. In the context of asymmetric threats, the detection of an abnormal situation refers to the discovery of suspicious activities of a hostile nation or group out of noisy, scattered, and partial intelligence data. The problem becomes complex in a low signal-to-noise ratio environment, such as asymmetric threats, because the ldquosignalrdquo observations are far fewer than ldquonoiserdquo observations. Furthermore, the signal observations are ldquohiddenrdquo in the noise. In this paper, we illustrate the capabilities of hidden Markov models (HMMs), combined with feature-aided tracking, for the detection of asymmetric threats. A transaction-based probabilistic model is proposed to combine HMMs and feature-aided tracking. A procedure analogous to Page's test is used for the quickest detection of abnormal events. The simulation results show that our method is able to detect the modeled pattern of an asymmetric threat with a high performance as compared to a maximum likelihood-based data mining technique. Performance analysis shows that the detection of HMMs improves with increase in the complexity of HMMs (i.e., the number of states in an HMM).

Recently, significant attention in compressed sensing has been focused on basis pursuit, exchanging the cardinality operator with the l1-norm, which leads to a linear formulation. Here, we want to look beyond using the l1-norm in two ways: investigating non-linear solutions of higher complexity, but closer to the original problem for one, and improving known low complexity solutions based on matching pursuit using rollout concepts. Our simulation results concur with previous findings that once x is "sparse enough", many algorithms find the correct solution, but for averagely sparse problems we find that the l1-norm often does not converge to the correct solution - in fact being outperformed by matching pursuit based algorithms at lower complexity. The non-linear algorithm we suggest has increased complexity, but shows superior performance in this setting.

Is it possible to identify and even forecast well in advance (6-12 months) the relative stability of a state to enable policy makers to successfully intervene? How does one acquire that understanding? One technique is to model and understand the social factors, which summarize the background conditions, attributes and performance factors of the country over time. The purpose of this paper is to: (1) present a generalized data-driven framework for conflict analysis and forecasting, (2) show that state-of-the-art pattern classification techniques provide significant improvements to forecasting accuracy, and (3) introduce classification problems arising in social sciences to the engineering community for further enhancement of analysis techniques. We evaluate the efficacy of our data-driven framework on macro-structural factors as relevant contributors to country instability, delineating the independent and dependent variables. The results demonstrate significant improvement over previous approaches in classification metrics of accuracy, precision, and recall.

In this paper, we employ a Hidden Markov Random Field (HMRF) model and a novel algorithm for the Quadratic Assignment Problem (QAP) to discover the attributes of and relationships among organizational members, assets, mission areas, and mission tasks. The problem is one of identifying the mapping between the hypothesized nodes of a command and control (C2) organization and tracked individuals and resources. The HMRF formulation allows the computation of the posteriori energy function quantifying the belief that the observed data graph has been generated by a particular organizational graph (model graph). The experimental results demonstrate that the HMRF probabilistic model and the m-best assignment-based search algorithm can accurately identify the different organizational structures and achieve correct node mappings among various organizational members. The algorithm itself can be employed for solving general QAPs as well.

Conventional maintenance strategies, such as corrective and preventive maintenance, are not adequate to fulfill the needs of expensive and high availability transportation and industrial systems. A new strategy based on forecasting system degradation through a prognostic process is required. The recent advances in model-based design technology have realized significant time savings in product development cycle. These advances facilitate the integration of model-based diagnosis and prognosis of systems, leading to condition-based maintenance and increased availability of systems. With an accurate simulation model of a system, diagnostics and prognostics can be synthesized concurrently with system design. In this paper, we develop an integrated prognostic process based on data collected from model-based simulations under nominal and degraded conditions. Prognostic models are constructed based on different random load conditions (modes). An interacting multiple model (IMM) is used to track the hidden damage. Remaining-life prediction is performed by mixing mode-based life predictions via time-averaged mode probabilities. The solution has the potential to be applicable to a variety of systems, ranging from automobiles to aerospace systems.

A new Markov decision problem (MDP)-based method for managing goal attainment (GA), which is the process of planning and controlling actions that are related to the achievement of a set of defined goals in the presence of resource and time constraints, is proposed. Specifically, we address the problem as one of optimally selecting a sequence of actions to transform the system and/or its environment from an initial state to a desired state. We begin with a method of explicitly mapping an action-GA graph to an MDP graph and developing a dynamic programming (DP) recursion to solve the MDP problem. For larger problems having exponential complexity with respect to the number of goals, we propose guided search algorithms such as AO*, AOepsiv*, and greedy search techniques, whose search power rests on the efficiency of their heuristic evaluation functions (HEFs). Our contribution in this part stems from the introduction of a new problem-specific HEF to aid the search process. We demonstrate reductions in the computational costs of the proposed techniques through performance comparison with standard DP techniques. We conclude this paper with a method to address situations in which alternative strategies (e.g., second best) are required. The new extended AO* algorithm identifies alternative control sequences for attaining the organizational goals.

Based on the concept of autonomous cooperating holons, this paper presents a holonic command and control (C2) organizational control architecture (OCA) that models aC2organization as an integration of holonic multilevel decentralized decision-making networks. The OCA consists of two levels: operational- and tactical-level controls. Authority and control are highly distributed among agents belonging to different levels of the holarchy to empower the edges, whereas the integration of decisions is ensured to achieve overall mission objectives. In order to complete a mission in real time in dynamic environments, the decision makers (DMs) at different control levels need to coordinate their actions extensively and be prepared to adapt their schedules. Based on the proposed OCA, we present a holonic multiobjective evolutionary algorithm that produces flexible distributed schedules that account for the unexpected changes in the mission environment, such as asset breakdown, appearance of new events, DM failure, etc. This approach generates multilevel Pareto optimal solutions and, as a consequence, produces a set of ranked neighboring schedules. The actual schedule is a combination of different phases from alternative neighboring schedules that adapt to environmental disturbances. Moreover, the cost of adaptability is reduced while maintaining the stability of the organization. Numerical experiment shows the advantages of the proposed OCA, viz., simplicity, efficiency, and flexibility, which enable an organization to achieve high performance under dynamic and uncertain environments.

To achieve reliable packet transmission over a wireless link without feedback, we propose a layered coding approach that uses error-correction coding within each packet and erasure-correction coding across the packets. This layered approach is also applicable to an end-to-end data transport over a network where a wireless link is the performance bottleneck. We investigate how to optimally combine the strengths of error- and erasure-correction coding to optimize the system performance with a given resource constraint, or to maximize the resource utilization efficiency subject to a prescribed performance. Our results determine the optimum tradeoff in splitting redundancy between error-correction coding and erasure-correction codes, which depends on the fading statistics and the average signal to noise ratio (SNR) of the wireless channel. For severe fading channels, such as Rayleigh fading channels, the tradeoff leans towards more redundancy on erasure-correction coding across packets, and less so on error-correction coding within each packet. For channels with better fading conditions, more redundancy can be spent on error-correction coding. The analysis has been extended to a limiting case with a large number of packets, and a scenario where only discrete rates are available via a finite number of transmission modes.

Lossy links used in a sensor network affect network performance, and hence need to be detected and repaired [1, 2]. One approach to detect lossy links is that each node monitors the loss rates on its neighboring links and reports them to the sink. This approach, although straightforward, causes large amount of traffic. Another approach to detect lossy links is through end-to-end data that are transmitted periodically from sources to the sink(s) [3, 1, 2]. This end-to-end approach has the advantage of not generating any additional monitoring traffic. The challenge is, however, to develop accurate inference algorithms for lossy link detection based on end-to-end measurements.

The knowledge of the principles and goals under which an adversary organization operates is required to predict its future activities. To implement successful counter-actions, additional knowledge of the specifics of the organizational structures, such as command, communication, control, and information access networks, as well as responsibility distribution among members of the organization, is required. In this paper, we employ a Hidden Markov Random Field (HMRF) model and a graph matching algorithm to discover the attributes of and relationships among organizational members, assets, environment areas, and mission tasks. We focus on identifying the mapping between hypothesized nodes of enemy command organization and tracked individuals and resources. This also allows us to compute the posterior energy function quantifying the belief that the observed data has been generated by a particular organization. The experiment results show that our probabilistic model and the Simulated Annealing search algorithm can accurately identify the different organizational structures and achieve correct node mappings among organizational members.

In this paper, a hidden Markov model (HMM)-based dynamic sensor scheduling problem is formulated, and solved using rollout concepts to overcome the computational intractability of the dynamic programming (DP) recursion. The problem considered here involves dynamically sequencing a set of sensors to minimize the sum of sensor cost and the HMM state estimation error cost. The surveillance task is modeled as a single HMM with multiple emission matrices corresponding to each of the sensors. The rollout information gain (RIG) algorithm proposed herein employs the information gain (IG) heuristic as the base algorithm. The RIG algorithm is illustrated on an intelligence, surveillance, and reconnaissance (ISR) scenario of a village for the presence of weapons and terrorists/refugees. Extension of the RIG strategy to monitor multiple HMMs involves combining the information gain heuristic with the auction algorithm that computes the κ-best assignments at each decision epoch of rollout.

This paper considers the problem of temporally fusing classifier outputs to improve the overall diagnostic classification accuracy in safety-critical systems. Here, we discuss dynamic fusion of classifiers which is a special case of the dynamic multiple fault diagnosis (DMFD) problem [1]–[3]. The DMFD problem is formulated as a maximum a posteriori (MAP) configuration problem in tri-partite graphical models, which is NP-hard. A primal-dual optimization framework is applied to solve the MAP problem. Our process for dynamic fusion consists of four key steps: (1) data preprocessing such as noise suppression, data reduction and feature selection using data-driven techniques, (2) error correcting codes to transform the multiclass data into binary classification, (3) fault detection using pattern recognition techniques (support vector machines in this paper), and (4) dynamic fusion of classifiers output labels over time using the DMFD algorithm. An automobile engine data set, simulated under various fault conditions [4], was used to illustrate the fusion process. The results demonstrate that an ensemble of classifiers, when fused over time, reduces the classification error as compared to a single classifier and static fusion of classifiers trained over the entire batch of data. The results for sliding window dynamic fusion are also provided.

Chillers constitute a significant portion of energy consumption equipment in heating, ventilating and air-conditioning (HVAC) systems. The growing complexity of building systems has become a major challenge for field technicians to troubleshoot the problems manually; this calls for automated ldquosmart-service systemsrdquo for performing fault detection and diagnosis (FDD). The focus of this paper is to develop a generic FDD scheme for centrifugal chillers and also to develop a nominal data-driven (ldquoblack-boxrdquo) model of the chiller that can predict the system response under new loading conditions. In this vein, support vector machines, principal component analysis, and partial least squares are the candidate fault classification techniques in our approach. We present a genetic algorithm-based approach to select a sensor suite for maximum diagnosabilty and also evaluated the performance of selected classification procedures with the optimized sensor suite. The responses of these selected sensors are predicted under new loading conditions using the nominal model developed via the black-box modeling approach. We used the benchmark data on a 90-t real centrifugal chiller test equipment, provided by the American Society of Heating, Refrigerating and Air-Conditioning Engineers, to demonstrate and validate our proposed diagnostic procedure. The database consists of data from sixty four monitored variables of the chiller under 27 different modes of operation during nominal and eight faulty conditions with different severities.

Theory and applications of model-based fault diagnosis have progressed significantly in the last four decades. In addition, there has been increased use of model-based design and testing in the automotive industry to reduce design errors, perform rapid prototyping, and hardware-in-the-loop simulation (HILS). This paper presents a new model-based diagnostic development process for automotive engine control systems. This process seamlessly employs a graph-based dependency model and mathematical models for online/offline diagnosis. The hybrid method improves the diagnostic system's accuracy and consistency, utilizes existing validated knowledge on empirical models, enables remote diagnosis, and responds to the challenges of increased system complexity. The development platform consists of an engine electronic control unit (ECU) rapid prototyping system and HILS equipment—the air intake subsystem (AIS). The diagnostic strategy is tested and validated using the HILS platform.

The quick medical reference decision-theoretic (QMR-DT) network is a large two-layer Bayesian network (BN) [consisting of 571 diseases (ldquofailure sourcesrdquo) and 4075 findings (ldquotest outcomesrdquo)] based on expert and statistical knowledge in internal medicine. The maximum a posteriori (MAP) diagnosis (configuration) based on QMR-DT constitutes an intractable inference problem for all, but a small set of, cases. Consequently, we consider near-optimal algorithms for finding the most likely set of diseases given a set of findings. A computationally efficient algorithm that can handle cases with hundreds of positive findings, i.e., the Lagrangian relaxation algorithm (LRA), is presented. By relaxing the original problem via a set of Lagrange multipliers, the LRA generates an upper bound for the objective function. The near-optimal diagnosis (configuration) is found by minimizing the duality gap via a subgradient method. Numerical experiments show that the LRA is promising in achieving highly accurate diagnosis, and that it is computationally very efficient in solving MAP configuration problems in large and dense two-layer BNs with noisy-OR (BN2O) nodes and containing undirected loops (cycles), such as the QMR-DT network.

Networked embedded systems, such as modern automobiles, consist of a large number of physically distributed nodes (subsystems). Each node communicates with other nodes via a network. With the rapid growth in the number of control units, a global diagnosis method, which collects the diagnostic information from all the subsystem controllers, is not practical because of high communication requirements and time delays induced by centralized diagnosis. This paper presents a distributed diagnosis algorithm based on a digraph model and a local fault-test dependency matrix (D-matrix) at each node. Each local diagnoser first performs local diagnosis, taking into account local sensed information only. Then, the local diagnoses are transparently updated to a global diagnosis through communication among nodes, constrained by the topology of interconnected digraph models. The distributed diagnosis algorithm is evaluated on several real-world examples.

The modern era of sophisticated automobiles is necessitating the development of generic and automated embedded fault diagnosis tools. Future vehicles are expected to contain more than one hundred complex electronic control units (ECUs) and data acquisition systems to control and monitor large number of system variables in real-time. There exists an abundant amount of literature on fault detection and diagnosis (FDD). However, these techniques are developed in isolation. In order to solve the problem of FDD in complex systems, such as modern vehicles, a hybrid methodology combining different techniques is needed. Here, we apply an approach based on signal analysis that combines various signal processing and statistical learning techniques for real-time FDD in automotive engines. The data under several scenarios is collected from an engine model running in a real-time simulator and controlled by an ECU.

In this paper, we introduce an advanced software tool for modeling asymmetric threats, the Adaptive Safety Analysis and Monitoring (ASAM) system. The ASAM system is a hybrid model-based system for assisting intelligence analysts to identify asymmetric threats, to predict possible evolution of the suspicious activities, and to suggest strategies for countering threats. It employs a novel combination of hidden Markov models (HMMs) and Bayesian networks (BNs) to compute the likelihood that a certain threat exists. It provides a distributed processing structure for gathering, sharing, understanding, and using information to assess and predict adversary network states. We illustrate the capabilities of the ASAM system by way of application to a hypothetical model of development of nuclear weapons program by an unknown hostile country. The simulation results show that the ASAM system is able to detect the modeled pattern with a high performance (greater than 95% clutter suppression capability).

A collaboration scheme for information integration among multiple agencies (and/or various divisions within a single agency) is designed using hierarchical and hybrid Bayesian networks (HHBNs). In this scheme, raw information is represented by transactions (e.g., communication, travel, and financing) and information entities to be integrated are modeled as random variables (e.g., an event occurs, an effect exists, or an action is undertaken). Each random variable has certain states with probabilities assigned to them. Hierarchical is in terms of the model structure and hybrid stems from our usage of both general Bayesian networks (BNs) and hidden Markov models (HMMs, a special form of dynamic BNs). The general BNs are adopted in the top (decision) layer to address global assessment for a specific question (e.g., "Is target A under terrorist threat?" in the context of counterterrorism). HMMs function in the bottom (observation) layer to report processed evidence to the upper layer BN based on the local information available to a particular agency or a division. A software tool, termed the adaptive safety analysis and monitoring (ASAM) system, is developed to implement HHBNs for information integration either in a centralized or in a distributed fashion. As an example, a terrorist attack scenario gleaned from open sources is modeled and analyzed to illustrate the functionality of the proposed framework.

A key concept in congruent organizational design is the so-called strategic grouping, which involves the aggregation of task functions, positions, and assets into units. Group technology (GT) has emerged as a manufacturing philosophy for improving productivity in batch production systems, while retaining the flexibility of a job shop production. In this paper, a methodology [nested genetic algorithm (NGA)] to group tasks and assets into several clusters [decision makers (DMs), command cells] is proposed; this methodology employs concepts from GT and genetic algorithms (GAs) to minimize the weighted total workload, measured in terms of intra-DM and inter-DM coordination workloads. The numerical results show that the proposed NGA approach obtains a near-optimal layout of the organization, i.e., the assignment of platforms to tasks and the patterns of coordination achieve a nice tradeoff between inter-DM and intra-DM coordination workload.

The paper presents a new diagnostic development platform for automotive systems. The development platform consists of a target ECU rapid prototyping system and a hardware-in-the-loop simulation (HILS) equipment. An integrated diagnostic process that seamlessly employs a graph-based dependency model and quantitative models for intelligent diagnosis is introduced, along with a practical example of model-based engine diagnosis. The diagnostic strategy is tested and validated using the HILS platform.

The probabilistic data association (PDA) method for multiuser detection (MUD) over synchronous CDMA channels is extended to the signal detection problem in V-BLAST systems. Computer simulations show that the algorithm has an error probability that is significantly lower than that of the V-BLAST optimal order detector and has a computational complexity that is cubic in the number of transmit antennas.

A complex sphere decoding algorithm is presented for signal detection in V-BLAST systems, which has a computational cost that is significantly lower than that of the original complex sphere decoder (SD) for a wide range of SNRs. Simulation results on a 64-QAM system with 23 transmit and 23 receive antennas at an SNR per bit of 24 dB show that the new sphere decoding algorithm obtains the ML solution with an average cost that is at least 6 times lower than that of the original complex SD. Further, the new algorithm also shows robustness with respect to the initial choice of sphere radius.

In this letter, we compare the complexity and efficiency of several methods used for multiuser detection in a synchronous code-division multiple-access system. Various methods are discussed, including decision-feedback (DF) detection, group decision-feedback (GDF) detection, coordinate descent, quadratic programming with constraints, space-alternating generalized EM (SAGE) detection, Tabu search, a Boltzmann machine detector, semidefinite relaxation, probabilistic data association (PDA), branch and bound (BBD), and the sphere decoding (SD) method. The efficiencies of the algorithms, defined as the probability of group detection error divided by the number of floating point computations, are compared under various situations. Of particular interest is the appearance of an "efficient frontier" of algorithms, primarily composed of DF detector, GDF detector, PDA detector, the BBD optimal algorithm, and the SD method. The efficient frontier is the convex hull of algorithms as plotted on probability of error versus computational demands axes: algorithms not on this efficient frontier can be considered dominated by those that are.

A fast optimal algorithm based on the branch-and-bound (BBD) method is proposed for the joint detection of binary symbols of K users in a synchronous code-division multiple-access channel with Gaussian noise. Relationships between the proposed algorithms (depth-first BBD and fast BBD) and both the decorrelating decision-feedback (DF) detector and sphere-decoding algorithm are clearly drawn. It turns out that decorrelating DF detector corresponds to a "one-pass" depth-first BBD; sphere decoding is, in fact, a type of depth-first BBD, but one that can be improved considerably via tight upper bounds and user ordering, as in the fast BBD. A fast "any-time" suboptimal algorithm is also available by simply picking the "current-best" solution in the BBD method. Theoretical results are given on the computational complexity and the performance of the "current-best" suboptimal solution.

In Parts I and II of this paper, we presented a three-phase iterative optimization process to design normative organizations. Such organizations are mission-based in that they are organized to perform a given task and then are dissolved. The objectives of the present paper are to 1) define and classify the processes of strategy and structural adaptation in organizations in response to mission and environmental changes, 2) extend our three-phase design methodology to construct robust and adaptive organizations, and 3) analyze the effects of mission parameters on their performance. We investigate the performance of organizations through internal workload and external coordination measures for individual DMs, as well as workload distribution as the overall organizational measure.

Test sequencing is a binary identification problem wherein one needs to develop a minimal expected cost test procedure to determine which one of a finite number of possible failure states, if any, is present. In this paper, we consider a multimode test sequencing (MMTS) problem, in which tests are distributed among multiple modes and additional transition costs will be incurred if a test sequence involves mode changes. The multimode test sequencing problem can be solved optimally via dynamic programming or AND/OR graph search methods. However, for large systems, the associated computation with dynamic programming or AND/OR graph search methods is substantial due to the rapidly increasing number of OR nodes (denoting ambiguity states and current modes) and AND nodes (denoting next modes and tests) in the search graph. In order to overcome the computational explosion, we propose to apply three heuristic algorithms based on information gain: information gain heuristic (IG), mode capability evaluation (MC), and mode capability evaluation with limited exploration of depth and degree of mode Isolation (MCLEI). We also propose to apply rollout strategies, which are guaranteed to improve the performance of heuristics, as long as the heuristics are sequentially improving. We show computational results, which suggest that the information-heuristic based rollout policies are significantly better than traditional information gain heuristic. We also show that among the three information heuristics proposed, MCLEI achieves the best tradeoff between optimality and computational complexity.

A new methodology is given in this paper to obtain a near-optimal strategy (i.e., specification of courses of action over time), which is also robust to environmental perturbations (unexpected events and/or parameter uncertainties), to achieve the desired effects. A dynamic Bayesian network (DBN)-based stochastic mission model is employed to represent the dynamic and uncertain nature of the environment. A genetic algorithm is applied to search for a near-optimal strategy with DBN serving as a fitness evaluator. The joint probability of achieving the desired effects (namely, the probability of success) at specified times is a random variable due to uncertainties in the environment. Consequently, we focus on signal-to-noise ratio (SNR), a measure of the mean and variance of the probability of success, to gauge the goodness of a strategy. The resulting strategy will not only have a high likelihood of inducing the desired effects, but will also be robust to environmental uncertainties.

A fast optimal algorithm based on the branch and bound (BBD) method is proposed for the joint detection of binary symbols of K users in a synchronous code-division multiple access (CDMA) channel with Gaussian noise. Relationships between the proposed algorithms (depth-first BBD and fast BBD) and both the decorrelating decision feedback (DF) detector and sphere decoding (SD) algorithm are clearly drawn. It turns out that decorrelating DF detector corresponds to a "one-pass" depth-first BBD; sphere decoding is in fact a type of depth-first BBD, but one that can be improved considerably via tight upper bounds and user ordering as in our fast BBD.

A system wide prognostic process is required to fulfill the needs of expensive and high availability industrial systems. The recent advances in model-based design technology have facilitated the integration of model-based diagnosis and prognosis of systems, leading to condition-based maintenance. In this paper an integrated prognostic process based on data collected from model-based simulations under nominal and degraded conditions is described. Interacting Multiple Model (IMM) is used to track the hidden damage. Remaining life prediction is performed by mixing mode-based life predictions via time-averaged mode probabilities. The prognostic process is demonstrated on a suspension system.

In this paper, we present three classes of computationally efficient algorithms that can handle cases with hundreds of positive findings in QMR-DT(Quick Medical Reference, Decision-Theoretic) Network. These include Lagrangian Relaxation Algorithm (LRA), Primal Heuristic Algorithm (PHA), and Approximate Belief Revision Algorithm (ABR). These algorithms solve the QMR-DT problem by finding the most likely set of diseases given the findings. Extensive computational experiments have shown that LRA obtains the best solutions among the three algorithms proposed within a relatively small processing time. We also show that the Variational Probabilistic Inference method is a special case of our LRA. The solutions are generic and have application to multiple fault diagnosis in complex industrial systems.

The probabilistic data association (PDA) method is extended to multiuser detection over symbol-asynchronous code-division multiple access (CDMA) communication channels. A direct extension as well as a sliding window processing method are introduced. While achieving near-optimal performance with O(K/sup 3/) computational complexity in synchronous CDMA, K being the number of users, it is shown that, in asynchronous CDMA, the probability of group detection error of the proposed PDA method is very close to the performance lower bound provided by an ideal clairvoyant optimal detector, and the computational complexity is only marginally increased to O([h/s]K/sup 3/) per symbol, where h and s are the width and the sliding rate of the processing window, respectively. Due to the outstanding performance of the PDA detector in heavily overloaded asynchronous systems, it is observed that an optimally designed synchronous system can be easily outperformed by an arbitrarily designed asynchronous system. Hence, it is proposed to use asynchronous transmission deliberately, even when synchronous transmission is possible - asynchronous is better than synchronous!.

A strategy of user ordering and time labeling for a decision feedback (DF) detector in asynchronous code-division multiple-access communications is proposed and is proved to be optimal for the ideal DF detector. The proposed algorithm requires O(K/sup 4/) offline operations, where K is the number of users. Although error propagation complicates the analysis of the actual DF detector, computer simulations show that, with the proposed user ordering and time labeling, the performance of an actual DF detector overlays the theoretical bound in most cases.

The group decision feedback (GDF) detector is studied in this letter. Given the maximum group size, a grouping algorithm is proposed. It is shown that the proposed grouping algorithm maximizes the symmetric energy of the multiuser detection system. Furthermore, based on a set of lower bounds on asymptotic group effective energy (AGEE) of the GDF detector, it is shown that the proposed grouping algorithm, in fact, maximizes the AGEE lower bound for every group of users. The theoretical analysis of the grouping algorithm enables the offline estimation of the computational cost and the performance of a GDF detector. The computational complexity of a GDF detector is exponential in the largest size of the groups. Simulation results are presented to verify the theoretical conclusions. The results from this letter can be applied to the decision feedback detector by setting the maximum group size to one.

Test sequencing is a binary identification problem wherein one needs to develop a minimal expected cost testing procedure to determine which one of a finite number of possible failure sources, if any, is present. The problem can be solved optimally using dynamic programming or AND/OR graph search methods (AO/sup */, CF, and HS). However, for large systems, the associated computation with dynamic programming or AND/OR graph search methods is substantial, due to the rapidly increasing number of OR nodes (denoting ambiguity states) and AND nodes (denoting tests) in the search graph. In order to overcome the computational explosion, the one-step or multistep lookahead heuristic algorithms have been developed to solve the test sequencing problem. In this paper, we propose to apply rollout strategies, which can be combined with the one-step or multistep lookahead heuristic algorithms, in a computationally more efficient manner than the optimal strategies, to obtain solutions superior to those using the one-step or multistep lookahead heuristic algorithms. The rollout strategies are illustrated and tested using a range of real-world systems. We show computational results, which suggest that the information-heuristic based rollout policies are significantly better than other rollout policies based on Huffman coding and entropy.

Graph-based systems are models wherein the nodes represent the components and the edges represent the fault propagation between the components. For critical systems, some components are equipped with smart sensors for on-board system health management. When an abnormal situation occurs, alarms will be triggered from these sensors. This paper considers the problem of identifying the set of potential failure sources from the set of ringing alarms in graph-based systems. However, the computational complexity of solving the optimal multiple fault diagnosis (MFD) problem is exponential. Based on Lagrangian relaxation and subgradient optimization, we present a heuristic algorithm to find approximately the most likely candidate fault set. A computationally cheaper heuristic algorithm - primal heuristic - has also been applied to the problem so that real-time MFD in systems with several thousand failure sources becomes feasible in a fraction of a second. This paper also considers systems with asymmetric and multivalued alarms (tests).

A strategy for user ordering and time labeling for a decision feedback (DF) detector in asynchronous Code-Division Multiple Access (CDMA) communications is discussed. Ordering and labeling would at first appear to be of a complexity exponential in K, the number of users. Surprisingly, optimal sequencing requires only O(K4) operations, and is needed only once per packet: it is thus a cheap way to obtain an often marked improvement in performance, compared to power-ordering and chronological labeling.

This paper presents a design methodology for synthesizing organizations to execute complex missions efficiently. It focuses on devising mission planning strategies to optimally achieve mission goals while optimally utilizing organization's resources. Effective planning is often the key to successful completion of the mission, and conversely, mission failure can often be traced back to poor planning. Details on subsequent phases of the design process to construct the mission-driven human organizations are discussed in a companion paper.

For pt.I. see ibid., p. 346-59. This paper presents a multiobjective structural optimization process of designing an organization to execute a specific mission. We provide mathematical formulations for optimization problems arising in Phases II and III of our organizational design process and polynomial algorithms to solve the corresponding problems. Our organizational design methodology applies specific optimization techniques at different phases of the design, efficiently matching the structure of a mission (in particular, the one defined by the courses of action obtained from mission planning) to that of an organization. It allows an analyst to obtain an acceptable tradeoff among multiple mission and design objectives, as well as between computational complexity and solution efficiency (desired degree of suboptimality).

This paper presents a generalization to classical scheduling theory by removing the restriction that only one processor can work on a given task at a particular time. Instead, it is assumed that each task can be allocated any number of identical processors from one to the maximum number available, with each task's completion time being a function of the number of processors allocated. Tasks may be started any time, but once started, a task must not have its processor allocation altered or be preempted. Two objective functions are considered: minimizing the overall completion time for the tasks (make-span) and minimizing a weighted sum of the task completion times (weighted response). Both are considered subject to a constraint on the total number of processors available. Suboptimal algorithms are developed for both of these NP-hard problems using Lagrangian relaxation, and their performances are analyzed through extensive simulations. Duality gaps for all problems tested ranged from under 1% to 92%, depending more on the problem size than the specific problem.

A probabilistic data association (PDA) method is proposed in this paper for multiuser detection over synchronous code division multiple access (CDMA) communication channels. PDA models the undecided user signals as binary random variables. By approximating the interuser interference (IUI) as Gaussian noise with an appropriately elevated covariance matrix, the probability associated with each user signal is iteratively updated. Computer simulations show that the system usually converges within 3-4 iterations, and the resulting probability of error is very close to that of the optimal maximum likelihood (ML) detector. Further modifications are also presented to significantly reduce the computational cost.

The sequential group detection technique is a generalization of the decision feedback detector: in the latter, users are successively demodulated and cancelled one-by-one, while in the former this basic operation is performed simultaneously on groups of users. The computational complexity of a group decision feedback detector (GDFD) is exponential in the largest size of the groups; thus instead of using the partition of users as design parameters, choosing the "maximum group size" is more reasonable in practice. Given the maximum group size, a grouping algorithm is proposed. It is shown that the proposed grouping algorithm maximizes the asymptotic symmetric energy (ASE) of the multiuser detection system. Furthermore, based on a set of lower bounds on the asymptotic group symmetric energy (AGSE) of the GDFD, it is shown that the proposed grouping algorithm, in fact, maximizes the AGSE lower bound for every group of users. Together with a fast computational method based on branch-and-bound, the theoretical analysis of the grouping algorithm enables the offline estimation of the computational cost and the performance of GDFD. Simulation results are presented to verify the theoretical results.

We (2001) previously showed that for solutions of the binary quadratic programming problem there exists an "efficient frontier" in the performance/speed domain among the algorithms which characterizes the relative performance of each algorithm. Here, in addition to the algorithms implemented previously, the Boltzmann machine, genetic algorithm and space alternating generalized EM (SAGE) receiver are implemented and results are given for much larger scale problems. Simulation results show that these and several other of the proposed methods can significantly outperform the decision feedback detector or its group counterpart.

We (2001) previously showed that for solutions of the binary quadratic programming problem there exists an "efficient frontier" in the performance/speed domain among the algorithms which characterizes the relative performance of each algorithm. Here, in addition to the algorithms implemented previously, the Boltzmann machine, genetic algorithm and space alternating generalized EM (SAGE) receiver are implemented and results are given for much larger scale problems. Simulation results show that these and several other of the proposed methods can significantly outperform the decision feedback detector or its group counterpart.

The objectives of this paper are to (i) define and classify the processes of strategy and structural adaptation in organizations in response to mission and environmental changes, (ii) apply our modified design methodology to construct robust, adaptive, and flexible (both robust and adaptive) organizations; and (iii) analyze the effects of mission parameters on their performance. We investigate the performance of organizations through dynamic metrics, which include a performance based congruence measure, as well as DM activity and task workload measures as functions of time.

Binary quadratic programming (BQP) problems arise frequently in digital communication systems where online solutions are required. The multiuser detection (MUD) problem in code division multiple access (CDMA) communications, studied in the paper, is one such example. Due to the NP-hard nature of the BQP problem arising in MUD, only sub-optimal methods with polynomial complexities can be realistically considered. In the paper, a suboptimal algorithm based on the idea of probabilistic data association (PDA) is proposed. By treating the detection parameters as binary random variables, and by approximating the multi-modal Gaussian mixture by a single Gaussian noise, the PDA method provides near-optimal solution with a computational complexity of O(N/sup 3/), where N is the problem size. Several other algorithms for the MUD problem are also considered and compared in terms of computational efficiency and the degree of suboptimality.

This paper generalizes classical scheduling theory by removing the restriction that only a single processor can work on a given task at a particular time. Instead, it is assumed that each task can be allocated any number of identical processors from one to the maximum number available, and that a task's completion time is a nonincreasing function of the number of processors allocated. Once started, a task must run to completion without altering the number of processors given to it. Furthermore, a task can start only when no task is currently executing. The objective considered is minimization of overall completion time (make-span) for the tasks subject to the constraint of a limited number of available processors. To approximately solve this problem, an algorithm based on Lagrangian relaxation is developed, and its performance is analyzed through extensive simulations. Approximate duality gaps range from 0 to about 60% on average and are strongly a function of problem type and size.

A class of coordinate descent methods is proposed for the joint detection of binary symbols of K users in a synchronous correlated waveform multiple-access (CWMA) channel with Gaussian noise. We consider the detection problem as one of optimizing a quadratic objective function with binary constraints on decision variables. The proposed coordinate descent methods, while still maintaining a low computational complexity, are shown to provide as much as two orders of magnitude improvement in the probability of error, especially in situations where the existing methods do not perform well. The paper concludes with a discussion of how the proposed methods can be further improved.

Presents a classification of the optimization problems arising in the normative design of organizations to execute specific missions. The use of specific optimization algorithms for different phases of the design process leads to an efficient matching between the mission structure and that of an organization and its resources/constraints. It allows an analyst to obtain an acceptable trade-off among multiple objectives and constraints, as well as between computational complexity and solution efficiency (desired degree of sub-optimality).

We consider the discrete-time version of performability modeling of automated manufacturing systems (AMSs) capable of producing multiple part types, when the Markov rewards are random. The discrete-time approach is well suited for the performance studies of AMSs in the presence of failures, repairs, and reconfigurations, AMSs exist in various configuration states and this transitional behavior is modeled using discrete-time Markov chains. In addition, the performance in each configuration state is modeled by a Markov reward structure. The random reward structure models the behavior of real systems more accurately than the deterministic models used in the earlier literature. We derive recursive expressions for the conditional densities and moments of the cumulative performance function and study their asymptotic properties, when the underlying Markov chain describing the evolution of the configuration states is homogenous. Recursions are also derived for the computation of the cross correlation of the productivity of different part types. Examples are provided to illustrate the methods obtained in the paper.

We consider the problem of constructing optimal and near-optimal test sequences for multiple fault diagnosis. The computational complexity of solving the optimal multiple-fault isolation problem is super exponential, that is, it is much more difficult than the single-fault isolation problem, which, by itself, is NP-hard. By employing concepts from information theory and AND/OR graph search and by exploiting the single fault testing strategies of Pattipati et al. (1990), we present several test sequencing algorithms for the multiple fault isolation problem. These algorithms provide a trade-off between the degree of suboptimality and computational complexity. Furthermore, we present novel diagnostic strategies that generate a diagnostic directed graph, instead of a traditional diagnostic tree, for multiple fault diagnosis. Using this approach, the storage complexity of the overall diagnostic strategy reduces substantially. The algorithms developed herein have been successfully applied to several real-world systems.

We present a hidden Markov model (HMM) based algorithm for fault diagnosis in systems with partial and imperfect tests. The HMM-based algorithm finds the most likely state evolution, given a sequence of uncertain test outcomes over time. We also present a method to estimate online the HMM parameters, namely, the state transition probabilities, the instantaneous probabilities of test outcomes given the system state and the initial state distribution, that are fundamental to HMM-based adaptive fault diagnosis. The efficacy of the parameter estimation method is demonstrated by comparing the diagnostic accuracies of an algorithm with complete knowledge of HMM parameters with those of an adaptive one. In addition, the advantages of using the HMM approach over a Hamming-distance based fault diagnosis technique are quantified. Tradeoffs in computational complexity versus performance of the diagnostic algorithm are also discussed.

In this paper, we first present the formulation and solution of the basic test sequencing problem. We then consider generalized test sequencing problems that incorporate various practical features such as precedence constraints and setup operations for tests, multi-outcome tests, modular diagnosis, and rectification. We develop various AO/sup */ and information heuristic-based algorithms to solve these practical test sequencing problems. We also discuss the issues involved in implementation of the test sequencing algorithms for solving large problems efficiently, and show that our preprocessing techniques result in considerable speed-ups.

We consider four test sequencing problems that frequently arise in test planning and design for testability (DFT) processes. Specifically, we consider the following problems: (1) how to determine a test sequence that does not depend on the failure probability distribution; (2) how to determine a test sequence that minimizes expected testing cost while not exceeding a given testing time; (3) how to determine a test sequence that does not utilize more than a given number of tests, while minimizing the average ambiguity group size; and (4) how to determine a test sequence that minimizes the storage cost of tests in the diagnostic strategy. We present various solution approaches to solve the above problems and illustrate the usefulness of the proposed algorithms.

In this paper, we consider imperfect test sequencing problems under a single fault assumption. This is a partially observed Markov decision problem (POMDP), a sequential multistage decision problem wherein a failure source must be identified using the results of imperfect tests at each stage. The optimal solution for this problem can be obtained by applying a continuous-state dynamic programming (DP) recursion. However, the DP recursion is computationally very expensive owing to the continuous nature of the state vector comprising the probabilities of faults. In order to alleviate this computational explosion, we present an efficient implementation of the DP recursion. We also consider various problems with special structure (parallel systems) and derive closed form solutions/index-rules without having to resort to DP. Finally, we present various top-down graph search algorithms for problems with no special structure, including multistep DP, multistep information heuristics, and certainty equivalence algorithms.

This paper presents a heuristic approach to scheduling the execution of interdependent tasks in a complex environment. In this context, tasks require the assignment of a set of assets within a specified opportunity window. The tasks are geographically distributed and require the movement of assets prior to processing. Each asset has multiple resources and is generally combined to meet the requirements of a given task. In this paper, a graphical task model is introduced that facilitates hierarchical, sequential, and parallel task relationships. The schedule is determined by sequentially assigning assets to tasks using a greedy heuristic. Each assignment corresponds to a subproblem, where a set of assets is selected to process a single task. The performance of this heuristic is improved via a rollout algorithm.

Multisignal modeling methodology is a simple and efficient knowledge representation scheme that captures the basic attributes of a system (structure, specifications, etc.) that are obtainable from design data and product specifications. QSI's TEAMS toolset employs multisignal modeling for testability analysis, test program set development, onboard monitoring and ground support systems. We outline the modeling methodology, its use in related areas of reliability analysis and failure modes, effects and criticality analysis (FMECA), and our efforts in building a reusable test and model library.

Real time monitoring of complex systems requires a smart and efficient inference engine. TEAMS-RT is capable of monitoring up to 1000 tests in real-time. Even so, for larger systems, a centralized solution will be computationally infeasible. Here, we present a lattice architecture of multiple collaborative TEAMS-RTs that can be embedded in the different subsystems of an interconnected system. A signal processing toolkit has been developed to facilitate data acquisition, filtering, feature extraction and test decisions.

This paper introduces a comprehensive methodology for synthesizing adaptive decision-making organizations to complete a complex joint-operations mission. We present a multiobjective organizational design algorithm with the embedded strategy adaptation and structural reconfiguration schemes to produce an adaptive organizational structure. The synthesis of adaptive organizations is illustrated via an example under multiple scenarios of anomalies. The results of this paper form a foundation for current research on organizational adaptation.

Presents a comprehensive methodology for validating automatically generated software. The process consists of developing a fault-effect dependency model for the software, designing input stimuli to make the bugs manifest, designing tests to detect the incompatibilities from the intended behavior, and identifying the faulty code segment. A key feature of the methodology is the application of functional dependency modeling concepts, that have been proven to be robust in the testability analysis and fault diagnosis of large, complex hardware systems, to software verification and validation.

In this paper, we investigate and systematically evaluate two machine learning algorithms for analog fault detection and isolation: (1) restricted Coloumb energy (RCE) neural network, and (2) learning vector quantization (LVQ). The RCE and LVQ models excel at recognition and classification types of problems. In order to evaluate the efficacy of the two learning algorithms, we have developed a software tool, termed Virtual Test-Bench (VTB), which generates diagnostic information for analog circuits represented by SPICE descriptions. The RCE and LVQ models render themselves more naturally to online monitoring, where measurement data from various sensors is continuously available. The effectiveness of RCE and LVQ is demonstrated on illustrative example circuits.

The paper summarizes recent results on both binary and M-ary distributed hypothesis testing problems with decision makers (DMs) organized in structured decision networks. The general problem of finding an optimal organizational structure and decision strategy for such networks is formulated as a functional optimization problem. A normative model to study the effect of interactions between task structure and organizational design on the performance of hierarchical organizations is presented. A binary signal detection model is considered to illustrate the joint impact of organizational design and of task environment on the organizational decision performance. The concept of a congruent organizational structure (i.e., a structure that achieves centralized performance with minimal communication) is introduced, and a graph decomposition algorithm to synthesize congruent structures is discussed.

We consider the problem of constructing optimal and near-optimal multiple fault diagnosis (MFD) in bipartite systems with unreliable (imperfect) tests. It is known that exact computation of conditional probabilities for MFD is NP hard. The novel feature of our diagnostic algorithms is the use of Lagrangian relaxation and subgradient optimization methods to provide: 1) near optimal solutions for the MFD problem and 2) upper bounds for an optimal branch and bound algorithm. The proposed method is illustrated using several examples. Computational results indicate the following: 1) our algorithm has superior computational performance to the existing algorithms (approximately three orders of magnitude improvement over the algorithm by Z. Binglin et al. (1993)); 2) near optimal algorithm generates the most likely candidates with a very high accuracy; 3) our algorithm can find the most likely candidates in systems with as many as 1000 faults.

This paper deals with the design and implementation of an algorithm for track formation and maintenance in a multisensor Air Traffic Surveillance scenario. The major contribution of the present work is the development of the combined likelihood function that enables the replacement of the Kalman filter (KF) with the much more versatile interacting multiple model (IMM) estimator which, as a self adjusting variable-bandwidth state estimator accounts for the various motion modes of the aircraft. This likelihood function defines the objective function used in the measurement to track assignment algorithm. Also, this algorithm incorporates both skill and beacon returns i.e., it fuses the primary and secondary radar data. Data from two FAA radars are used to evaluate the performance of this algorithm. The use of the IMM estimator yields considerable noise reduction during uniform motion, while maintaining the accuracy of the state estimates during maneuver. Overall, the mean square prediction error (to the next observation time) is reduced by 30% and the rms errors in the altitude rate estimates are reduced by a factor of three over the KF. The usefulness of the tracker presented here is also demonstrated on a noncooperative target.

The focus of this paper is to present the results of our investigation and evaluation of various shared-memory parallelizations of the data association problem in multitarget tracking. The multitarget tracking algorithm developed was for a sparse air traffic surveillance problem, and is based on an Interacting Multiple Model (IMM) state estimator embedded into the (2D) assignment framework. The IMM estimator imposes a computational burden in terms of both space and time complexity, since more than one filter model is used to calculate state estimates, covariances, and likelihood functions. In fact, contrary to conventional wisdom, for sparse multitarget tracking problems, we show that the assignment (or data association) problem is not the major computational bottleneck. Instead, the interface to the assignment problem, namely, computing the rather numerous gating tests and IMM state estimates, covariance calculations, and likelihood function evaluations (used as cost coefficients in the assignment problem), is the major source of the workload. Using a measurement database based on two FAA air traffic control radars, we show that a "coarse-grained" (dynamic) parallelization across the numerous tracks found in a multitarget tracking problem is robust, scalable, and demonstrates superior computational performance to previously proposed "fine-grained" (static) parallelizations within the IMM.

We present a robust scalable parallelization of a multitarget tracking algorithm developed for air traffic surveillance. We couple the state estimation and data association problems by embedding an interacting multiple model (IMM) state estimator into an optimization-based assignment framework. A SPMD distributed-memory parallelization is described wherein the interface to the optimization problem, namely computing the rather numerous gating and IMM state estimates, covariance calculations, and likelihood function evaluations (used as cost coefficients in the assignment problem), is parallelized. We describe several heuristic algorithms developed for the inherent task allocation problem wherein the problem is one of assigning track tasks, having uncertain processing costs and negligible communication costs, across a set of homogeneous processors to minimize workload imbalances. Using a measurement database based on two FAA air traffic central radars, courtesy of Rome Laboratory, we show that near linear speedups are obtainable on a 32-node Intel Paragon supercomputer using simple task allocation algorithms.

This paper considers the problem of determining the optimal distributed decision strategy for a team of decision-makers (DMs) arranged in an arbitrary acyclic organizational structure and controlling a complex structured process. Each DM has access to uncertain and partial information about the task environment and can control only a portion of it. We present an influence diagram model of the joint task-organization system and formulate the optimal team strategy in terms of a set of coupled hypothesis testing tasks at DMs. Specifically, we show that the scope of a local decision task is determined by the interaction of the task structure (what can be measured) and of the information access structure of the organization (who can measure what); while the control structure (who can influence what event) has an impact on the locally perceived costs associated with the decision options available. Theoretical results are illustrated via a numerical example, and connections to existing decision models are discussed.

We consider the transient performance analysis of failure-prone manufacturing systems producing multiple part types. We decompose the exact monolithic model into: 1) a slower time scale structure state process modeling the failure and repair, and 2) a faster time scale performance model describing the part processing and the material movement. We combine the solution of these two models to show that the accumulated reward over a given time interval is a solution of a set of forward or adjoint multidimensional linear hyperbolic partial differential equations. This result generalizes the existing results on composite performance-dependability analysis of manufacturing systems. We also present efficient numerical methods for computing the distribution of the cumulative operational time, and the mean and variance of the cumulative production over a given time interval. Further, we bring out the significance of these results in the manufacturing systems context through several examples.>

This paper presents a methodology for the design of products/processes that makes use of the concepts of robust design and the techniques of multiple criteria optimization for simultaneously optimizing many quality characteristics. First, a systematic approach to the selection of an efficient matrix experiment for a design problem is presented. Appropriate performance measures are obtained so that their joint optimization results in the minimum variation of product characteristics. The use of transformations is highlighted as a useful technique to statistically validate the design process. A discrete multiple criteria optimization algorithm that incorporates the methods of dominated approximations and reference points is developed to obtain nondominated solutions for the design problem. The methodology is illustrated using a case study gleaned from the literature.>

Performance evaluation of failure-prone manufacturing systems is of significant practical interest. In this paper, the authors consider the parametric sensitivity analysis of manufacturing systems producing multiple part types. This involves transient analysis of the Markov model of the system and computation of the derivative of the cumulative throughput with respect to the varying parameters. Such an analysis would be useful in studying the effects of various not exactly known parameters on the system performance, identifying the bottlenecks and hot spots and in system optimization studies. In this paper, the authors derive expressions for the sensitivity of the first two moments of the throughput-related performability with respect to failure and repair rates of various subsystems such as machines, guided vehicles, robots, etc. The authors also present two examples to illustrate the theoretical results of this paper.>

Uses discrete-time Markov reward models to obtain moment recursions of the cumulative performance of an automated manufacturing system (AMS). AMS exists in various structure states due to failures, repairs and reconfigurations of its components. This multi-state behavior is modeled using a Markov reward structure that is similar to the continuous-time versions. This methodology may also be used to compute other performance measures, such as the expected in-process inventory and the expected production per unit time. A three-stage transfer line with finite buffers is used to illustrate the methods obtained in the paper.>

The problem of evaluating the performability density and distribution of degradable computer systems is considered. A generalized model of performability is considered, wherein the dynamics of configuration modes are modeled as a nonhomogeneous Markov process, and the performance rate in each configuration mode can be time dependent. The key to the development of a unifying mathematical framework is the introduction of two related performability processes: the forward performability process over the interval (0,t), and the performability-to-go process over the interval (t,T), where T is the mission time. Stochastic differential equations techniques show that the joint density of the forward performability and configuration states satisfies a linear, hyperbolic partial differential equation (PDE) with time-dependent coefficients that runs forward in time, while the performability-to-go process satisfies an adjoint PDE running reverse in time. A numerical method for solving the PDEs is presented and is illustrated with examples.>

The use of Lagrangian relaxation to schedule job shops, which include multiple machine types, generic precedence constraints, and simple routing considerations, is explored. Using an augmented Lagrangian formulation, the scheduling problem is decomposed into operation-level subproblems for the selection of operation beginning times and machine types, with given multipliers and penalty coefficients. The multipliers and penalty coefficients are then updated at the higher level. The solution forms the basis of a list-scheduling algorithm that generates a feasible schedule. A procedure is also developed to evaluate the quality of this feasible schedule by generating a lower bound on the optimal cost. Numerical examples are taken from a representative industrial job shop. High-quality schedules are efficiently generated every other day over a three-week period, with costs generally within 4% of their respective lower bounds. The methodology compares favorably with knowledge-based scheduling.>

A hierarchical team faced with a binary detection problem, wherein decision makers (DMs) have access to different subsets of noise-corrupted information about the true state of the environment, is considered. A normative model is developed that aggregates the individual expertise of DMs at different levels of the hierarchy. The resulting team expertise is characterized in the form of a team receiver operating characteristic (ROC) curve, thereby replacing the team by an equivalent single decision-making node. The normative model is tested against human teams in a laboratory experiment. The team objective is to minimize the cost of errors in the final decision at the primary DM, where the cost structure and the information structure are treated as independent variables. Discrepancies between normative predictions and experimental results are attributed to inherent limitations and cognitive biases of humans.>

A distributed binary detection problem with multimessage (>or=1 bit) communications is considered, wherein the nodes (sensors, decision-makers (DMs)) of the system are organized in the form of a tree with multiple root nodes. A numerical algorithm is developed for determining the optimal decision rule at each node assuming monotone cost functions imposed only on the root nodes. It is assumed that the observations of each node are conditionally independent of those of the other nodes. It is shown that the problem is equivalent to solving a nonlinear optimal control problem, and the necessary conditions of optimality using Bayes' risk as the optimization criterion are derived. The optimal control approach provides an interpretation of certain functions of the co-state variables in terms of thresholds, and leads to a computationally efficient min-H algorithm to solve for the optimal decision rule at each node. The numerical algorithm provides a tool to investigate the organizational issues of adaptation, structure, and robustness.>

In this paper we formulate the following natural multiprocessor scheduling problem: Consider a parallel system with P processors. Suppose that there are Ntasks to be scheduled on this system, and that the execution time of each task j ε {1,…,N} is a nonincreasing function tj(βj) of the number of processors βj ε {1,…,P} allotted to it. The goal is to find, for each task j, an allotment of processors βj, and, overall, a schedule assigning the tasks to the processors which minimizes the makespan, or latest task completion time. The so-called shelf strategy is commonly used for orthogonal rectangle packing, a related and classic optimization problem. The prime difference between the orthogonal rectangle problem and our own is that in our case the rectangles are, in some sense, malleable: The height of each rectangle is a nonincreasing function of its width. In this paper, we solve our multiprocessor scheduling problem exactly in the context of a shelf-based paradigm. The algorithm we give uses techniques from resource allocation theory and employs a variety of other combinatorial optimization techniques.

The primary focus of diagnosis in field maintenance of systems is to identify the faulty modules rather than the individual faults within the modules. In addition, diagnosis is often integrated with two types of repair: type 1 repair wherein a module is repaired after complete diagnosis, and a type 2 repair wherein a module suspected to be faulty is replaced after partial diagnosis. The problem of constructing optimal and suboptimal test sequences to diagnose faults in modular systems with type 1 and type 2 repair options is considered. Dynamic programming recursion for this generalized test sequencing problem is derived, and lower bounds on the optimal cost-to-go based on information theory are derived. These bounds ensure that an optimal test algorithm is found by AND/OR graph heuristic search procedures. It is illustrated how type 2 repair can be profitably combined with diagnosis to reduce the expected test time.>

An efficient, exact algorithm is developed for optimizing the performance of nested block joins. The method uses both dynamic programming and branch-and-bound. In the process of deriving the algorithm, the class of resource allocation problems for which the greedy algorithm applies has been extended. Experiments with this algorithm on extremely large problems show that it is superior to all other known algorithms by a wide margin.>

A methodology is presented for mapping the processes comprising a mission onto the capable resources within the organization such that the completion time of the terminal process in the mission is minimized. The authors then build a Petri net simulation directly from the output of the mapping algorithm to perform sensitivity analyses on the solution. This capability enables the analyst to study in an interactive way variations in the performance of the organization as a function of its workload capacity, the expertise distribution of its members, the task requirements, and the communication network linking the different resources in the organization.>

Distributed information processing by a three-person hierarchical team, consisting of a primary decision maker (DM) and two expert subordinates, is considered. The problem context is binary hypotheses testing, wherein the team is asked to decide whether a contact is a threat or a neutral based on distributed, noisy, and at times ambiguous, measurements. A normative Bayesian model, which prescribes the behavior of an optimal team, is developed. The normative predictions are compared with the experimental data, and the cognitive biases of conservatism and of undervaluing of subordinates' reports by the primary DM are identified. A normative-descriptive model incorporating these human biases is developed using Kalman filtering (least squares) theory. The output of the resulting normative-descriptive model is shown to provide an excellent match with the experimental data.>

An optimization-based decision support system (DSS) for designing cost-efficient automatic test equipment (ATE) facilities is presented. The DSS combines efficient algorithms from cluster analysis, mixed-integer nonlinear programming, and closed queuing network theory in an iterative fashion to solve this problem. The DSS uses a hierarchical clustering algorithm to define test station configurations and to decompose a large, complex optimization problem into several moderately sized mixed-integer nonlinear programming problems. These problems are solved using a Lagrangian relaxation technique to determine the optimal distribution of the service workload among the test stations and to determine the number of test resources to be installed in each station; these solutions define the test facility design. The steady-state performance of these designs is evaluated using an approximate mean value analysis algorithm. The DSS allows sensitivity analysis with respect to changes in design objectives, test workload, and test facility configuration.>

A decentralized binary hypothesis-testing problem is considered in which a number of subordinate decision makers (DMs) transmit their opinions, based on their own data, to a primary decision maker who, in turn, combines the opinions with his own data to make the final team decision. The necessary conditions for the person-by-person optimal decision rules of the DMs are derived. A nonlinear Gauss-Seidel iterative algorithm is developed to solve for the decision thresholds of a person-by-person optimal strategy. The algorithm is illustrated with several examples, and implications for distributed organizational design are pointed out.>

A distributed binary detection problem with binary communications is considered, wherein the nodes (sensors and decision-makers) of the system are organized in a series configuration. It is shown that this problem can be reformulated as a deterministic multistage nonlinear optimal control problem. The necessary and sufficient conditions of optimality using Bayes' risk as the optimization criterion are then derived, and a physical interpretation of how the costates relate to the decision threshold at each node is provided. Using the min-H method of optimal control theory, a computationally efficient algorithm with linear complexity in the number of nodes per iteration is proposed to solve for the optimal decision strategy. The algorithm is then extended to solve a Neyman-Pearson version of the problem to obtain the optimal team (network) receiver operating characteristic curve. Two easily implemented suboptimal decision rules termed the asymptotic decision strategy and the constant control strategy are proposed and their properties are investigated.>

A file assignment problem (FAP) designed specifically for file servers and work stations on an extended local area network (ELAN) is formulated and solved. Key properties of such an environment are modeled onto the FAP formulation. The FAP problem is NP-hard, and the approximate solution technique adopted uses Lagrangian (dual) relaxation. The dual FAP is solved by use of an accelerated subgradient method. The approach is efficient and also provides an estimate, called the approximate relative duality gap, of the quality of the solution. In all instances in which the method has been employed, the approximate relative duality gap is less than 1%. The algorithm is illustrated by several examples.>

An exploration is made of the use of Lagrangian relaxation to schedule job shops, which include multiple machine types, generic precedence constraint, and simple routing considerations. From an augmented Lagrangian formulation, a decomposed solution methodology is developed using a Jacobi-type iterative approach. The subgradient method and the multiplier method are used to update the multipliers and the penalty coefficients. The dual solution forms the basis of a list scheduling algorithm which generates a feasible schedule. Unfortunately, the dual cost is not a lower bound on the optimal cost because of the Jacobi iterative technique employed. In order to evaluate the schedule, a second problem formulation is adopted. Its solution would ordinarily require prohibitive memory and considerable computation time. By utilizing part of the multipliers obtained from the first problem formulation, however, an effective lower bound on the optimal cost can be quickly obtained. A numerical example is given in which schedule cost is within 2% of its lower bound.>

This paper is concerned with the parameter optimization in closed product-form queueing networks. Our approach is to combine the techniques of the calculus of variations with the mean value analysis (MVA) recursion of closed queueing networks. We view the MVA recursion as nonlinear difference equations describing a multi-stage system, wherein a stage corresponds to the network population, and the response times at each node constitute the state variables of the multi-stage system. This viewpoint leads to a two-point boundary value problem , in which the forward system corresponds to the MVA recursion and the backward system corresponds to an MVA-like adjoint recursion. The method allows for a very general class of objective functions, and the adjoint equations provide the necessary information to compute the gradient of the cost function. The optimization problem can then be solved by any of the gradient-based methods. For the special case when the objective function is the network delay function, the gradient vector is shown to be related to the moments of the queue lengths. In addition, the adjoint vector offers the potential for the on-line adaptive control of queueing networks based on the state information (e.g., actual degree of multi-programming, response times at the devices.) The theory is illustrated via application to the problem of determining the optimal disk routing probabilities in a large scale, modern I/O (Input/Output) subsystem. A subsequent paper will deal with extensions of the theory to multi-class networks.

This paper is concerned with the properties of nonlinear equations associated with the Scheweitzer-Bard (S-B) approximate mean value analysis (MVA) heuristic for closed product-form queuing networks. Three forms of nonlinear S-B approximate MVA equations in multiclass networks are distinguished: Schweitzer, minimal, and the nearly decoupled forms. The approximate MVA equations have enabled us to: (a) derive bounds on the approximate throughput; (b) prove the existence and uniqueness of the S-B throughput solution, and the convergence of the S-B approximation algorithm for a wide class of monotonic, single-class networks; (c) establish the existence of the S-B solution for multiclass, monotonic networks; and (d) prove the asymptotic (i.e., as the number of customers of each class tends to ∞) uniqueness of the S-B throughput solution, and (e) the convergence of the gradient projection and the primal-dual algorithms to solve the asymptotic versions of the minimal, the Schweitzer, and the nearly decoupled forms of MVA equations for multiclass networks with single server and infinite server nodes. The convergence is established by showing that the approximate MVA equations are the gradient vector of a convex function, and by using results from convex programming and the convex duality theory.

It is shown that the (scaled) conditional moments of performability in Markov models are the states of a cascaded, linear, continuous-time dynamic system with identical system matrices in each stage. This interpretation leads to a simple method of computing the first moment for nonhomogeneous Markov models with finite mission time. In addition, the cascaded system representation leads to the derivation of a set of two stable algorithms for propagating the conditional moments of performability in homogeneous Markov models. In particular, a very fast doubling algorithm using diagonal Pade approximation to compute the matrix exponential and repeated squaring is derived. The algorithms are widely recognized, to be superior to those based on eigenvalue analysis in terms of both the computational efficiency and stability. The algorithms have obvious implications in solving reliability/availability models with large mission times.>

A methodology for scheduling independent jobs with due dates on identical, parallel machines is presented. The jobs have different levels of importance and various processing times on the machines, and the objective is to minimize the total weighted job tardiness of the schedule. Since the problem is NP hard, the goal is not to obtain the optimal schedule. Rather, an efficient near-optimal algorithm based on Lagrangian relaxation is presented. This approach provides a lower bound on the cost, which can be used as a measure of suboptimality. According to an implementation for a work center at Pratt and Whitney, most schedules generated are within 1% of the optima with reasonable CPU times. Furthermore, the method provides valuable job interaction information, which shop floor management uses to answer 'what if' questions, to reconfigure the schedule to accommodate dynamic changes, and to schedule new jobs.>

The problem of constructing optimal and near-optimal test sequences to diagnose permanent faults in electronic and electromechanical systems is considered. The test sequencing problem is formulated as an optimal binary AND/OR decision tree construction problem, whose solution is known to be NP-complete. The approach used is based on integrated concepts from information theory and heuristic AND/OR graph search methods to subdue the computational explosion of the optimal test-sequencing problem. Lower bounds on the optimal cost-to-go from the information-theoretic concepts of Huffman coding and entropy are derived. These lower bounds ensure that an optimal solution is found using the heuristic AND/OR graph search algorithms; they have made it possible to obtain optimal test sequences to problems that are intractable with traditional dynamic programming techniques. In addition, a class of test-sequencing algorithms that provide a tradeoff between solution quality and complexity have been derived using the epsilon -optimal and limited search strategies.>

The authors present a methodology for scheduling independent jobs with due dates on identical parallel machines. The jobs have different levels of importance and various processing times on the machines, and the objective is to minimize the total weighted job tardiness of the schedule. Since the problem is NP-hard, the goal is not to obtain the optimal schedule. Rather, an efficient near-optimal algorithm based on Lagrangian relaxation is presented. A nice feature of this approach is that it provides a lower bound on the cost, which can be used as a measure of suboptimality. On most problems tested, results are within 1% of the optima and have reasonable CPU times. Furthermore, the method provides job interaction information, which is then used to provide quick answers to 'what if' questions, to reconfigure the schedule to accommodate dynamic changes, and also to schedule jobs.>

The authors present an algorithm to map processes onto organizations. The organization consists of resources and communication links that must be used to complete all the processes. The objective is to minimize the completion time of the terminal process without violating the constraints which are defined in terms of the requirements of the processes and the capabilities of the resources. The organization performing the processes, with the process mapping specified by the algorithm, is then simulated using Petri nets. The simulation model can be generated automatically from the definition of the organizational structure and the solution of the process mapping problem. Then simulations can be performed to examine the sensitivity of the overall performance to changes in the parameters of the mission and of the organization.>

An engineering software tool is described that was developed to support efficient and cost-effective design of large-scale, parallel, fault-tolerant computer architectures (FTCAs). The tool, termed CAPRES (computer-aided performance and reliability evaluation system), allows the user to predict, by analytical means, the performance, reliability, and performability of candidate computer architectures executing candidate workloads. The algorithms of CAPRES use multidisciplinary techniques from hierarchical queuing-network theory, semi-Markov processes, hybrid-state systems theory and numerical integration. The sophisticated user interface and high-level front-end of CAPRES make this software system a truly integrated package for FTCA analysis and evaluation. To illustrate the role of CAPRES as a tool to aid in the analysis of FTCAs, an example of an Encore Multimax multiprocessor executing a parallel weapon-target-assignment algorithm is presented.>

Distributed information processing by a three-person team operating in a binary hypothesis-testing environment is considered. The team is hierarchical, with a primary decision-maker (DM0) and two subordinate DMs (DM1 and DM2). Given a set of measurements, the team has to decide whether a contact is a threat or a neutral. The subordinates are experts, one at detecting threats and the other at detecting neutrals. The team has access to noisy measurements from three sensors; one global, shared by all three DMs, and two local, dedicated to each of the two subordinates. The primary DM makes the final team decision based on the reports of the subordinates and the global measurement, and attaches a confidence level to the decision. A normative model for the distributed detection process is developed. The normative predictions are compared with the experimental data to identify cognitive biases of human DMs. A normative-descriptive model that accounts for these biases is developed, and is shown to provide an excellent match with the experimental data.>

Motivated by the need to increase the availability of systems, the primary focus of diagnosis in field maintenance is to locate the faculty modules. The authors consider the problem of constructing optimal test sequences to diagnose faults in such modular systems. This generalized test sequencing problem is solved by an AND/OR graph search procedure, wherein information-theoretic heuristic evaluation functions are modified to account for modular fault diagnosis. The effectiveness of the algorithm is demonstrated on various test cases.>

The problem of evaluating the performability and instantaneous availability of gracefully degradable computer systems is considered. The key to the development of a unifying mathematical framework is the introduction of two related performability processes: forward performability process over the interval (0,t) and the performability-to-go process over the interval (t,T), where T is the mission time. Using the techniques of partial differential equations, it is shown that the joint distribution of the forward performability and configuration states satisfies a linear, hyperbolic partial differential equation (PDE) running forward in time, while the performability-to-go process satisfies a similar PDE running in reverse time. The method includes nonhomogeneous Markov models of the configuration mode. A numerical method for solving the PDEs is presented and illustrated with examples. Practical implications of the reverse-time equations for the sensitivity analysis of instantaneous availability is discussed.>

A decentralized binary hypothesis-testing problem is considered in which a number of subordinate decision-makers (DMs) transmit their opinions based on their data to a primary decisionmaker who, in turn, combines the opinions with his own data to make the final team decision. The necessary conditions for the optimal decision rules of the DMs are derived. A nonlinear Gauss-Seidel iterative algorithm is developed for solving the decision thresholds of a person-by-person optimal strategy, and its monotonic convergence is established. The algorithm is illustrated with several examples, and implications for distributed organizational design are pointed out.>

This paper presents new formulations of the approximate mean value analysis (MVA) algorithms for the performance evaluation of closed product-form queueing networks. The key to the development of the algorithms is the derivation of vector nonlinear equations for the approximate network throughput. We solve this set of throughput equations using a nonlinear Gauss-Seidel type distributed algorithms, coupled with a quadratically convergent Newton's method for scalar nonlinear equations. The throughput equations have enabled us to: (a) derive bounds on the approximate throughput; (b) prove the existence, uniqueness, and convergence of the Schweitzer-Bard (S-B) approximation algorithm for a wide class of monotone, single class networks, (c) establish the existence of the S-B solution for multi-class, monotone networks, and (d) prove the asymptotic (i.e., as the number of customers of each class tends to ∞) uniqueness of the S-B throughput solution, and the asymptotic convergence of the various versions of the distributed algorithms in multi-class networks with single server and infinite server nodes. The asymptotic convergence is established using results from convex programming and convex duality theory. Extension of our algorithms to mixed networks is straighfoward. Only multi-class results are presented in this paper.

Human information processing and task selection procedures in a dynamic multitask supervisory control environment are discussed. The results of a joint experimental and analytic program were assimilated into a normative dynamic-decision model for predicting human task-selection performance. To this end a general multitask experimental paradigm has been developed, wherein tasks of different value, time requirement, and deadline compete for a human's attention. Via this framework, the effects of various task related variables on human-decision processes have been studied empirically. Conceptually the normative dynamic-decision model (DDM) is an outgrowth of the well-known optimal control modeling technology as applied to multitask situations. Thus the analytic framework of the DDM is rooted in modern control, estimation, and semiMarkov decision-process theories. In order to validate the model via comparison with experimental results, several time history and scalar measures of performance similarity are proposed. Excellent model-data agreement is obtained for all the experimental conditions studied.

Present researh has sought to expand our understanding of human information processing and control behavior In target tracking tasks. Specifically, It has focused on the problem of quantifying the human's "internal" model that charaterizes his perception of short-term target motion, and on the development of concomitant adaptive schemes for generating esimates of target velodty and acceleation using these models. A combined experimental and analytic program has studied simulated target trking performance as modified by short periods (~1 s) of target blanking. The blankin occur at pseudorandom times during a run. During the blanking period, human operator performance is governed almost entirely by his internal model representation of the target motion. Ensemble data from these blanking experiments have been used to suitably refine the optimal control model, including the target submodel. The resulting model represents the state of the art with regard to human operator modeing In dynamic antiaircraft-artillery (AAA) systems.