In this article, we consider how to increase trust in development processes in which there is a risk for adversarial manipulation, and the adversary's objectives and resources are either ill-specified, imprecisely specified, or unknown. In such problems, we must hedge against the risk of misapprehension of attacker objectives and resources, which is further complicated in the absence of adversarial training data. We show how to model dynamic agent interaction, on the basis of partially observed or noise-corrupted data, using a partially observable Markov game (POMG) framework. We then propose a threefold heuristic solution procedure that: 1) uses the POMG to generate potential adversarial policies; 2) explicitly incorporates these adversarial policies in the construction of a robust defender policy by solving a robust dynamic program (DP); and 3) employs a probability matching heuristic in partially observable environments.

Inspired by the idealism embodied in Russell and Whitehead’s “Principia Mathematica,” Wiener marched along a different and unique path toward sciences of intelligence and behavior which culminated at “Cybernetics: Or Control and Communication in the Animal and the Machine” 70 years ago. Since then, we have witnessed the birth of Cognitive Science, Artificial Intelligence (AI), Computational Intelligence, and many other new research fields and disciplines, all of which have been catalyzed by Cybernetics. The IEEE Systems, Man, AND Cybernetics Society and this Transactions on Cybernetics have become the focal point of the broad cybernetics community by promoting the theory, practice, and interdisciplinary aspects of systems science and engineering, human-machine systems, and cybernetics principles. It is a time of celebration and reflection.

The deliberate contamination of food is well recognized as a major public health threat. A food supply chain offers several possible targets for the intentional insertion of a biological or chemical toxin by a perpetrator, which can result in significant morbidity and mortality. We assume that both manager (defender) of the food production facility and perpetrator (attacker) select actions at each of a possibly countable number of decision epochs, based on possibly inaccurate real-time observations of the other agent. The defender's objectives are to maximize long-run expected total discounted system productivity and to minimize the long-run expected total discounted consequence of an attack. The attacker's objective is to maximize its reward, which combines the long-run expected total discounted consequence of an attack with a penalty if the attack is unsuccessful. We model this problem as a leader-follower, two-agent partially observed Markov game. We show that system risk is dynamic, determine the impact of observation accuracy on facility productivity and risk, thus providing a measure of the value of information, and perform a sensitivity analysis on key parameters. We present an illustrative example involving a liquid egg production system.

We investigate the value of choosing the next stop to visit in a multistop trip based on current traffic conditions to minimize the expected total travel time of the tour. We model this problem as a Markov decision process. Numerical examples are presented that indicate that the value of using current traffic information for dynamic tour determination can be significant.

The paper discusses the journal efforts on intelligent transport systems. 2009 marks the end of the first decade of our IEEE Transactions on Intelligent Transportation Systems (T-ITS). Over the past ten years, we have experienced various ups and downs, but we survived, and now, we thrive. In this last issue of the passing decade, the Founding, Past, and Current Editors in Chief would like to join everyone in celebrating the tenth anniversary of this great journal. We would like to take this opportunity to share some ideas and reflections on the past, present, and future of this publication.

We consider an alternative selection process that involves multiple and conflicting objectives. A facilitator asks a decision maker (DM), or a decision-making body, questions and obtains responses to help the DM select a most preferred alternative. The DM responses to these questions do not necessarily result in precisely determined parameter values (e.g., weights and value scores corresponding to a given model of preference). The goal of this research is to guide the facilitator in selecting what question to ask next and determining when to terminate the question-response process. We model the facilitator's question selection problem as a Markov decision process and present conditions that guarantee the existence of a question-response policy to identify a most preferred alternative in a finite number of questions. We also present conditions that guarantee the existence of a question-response policy that will identify a most preferred alternative as the number of questions asked goes to infinity. Both of these sets of conditions are easily identified a priori and may be used to aid a facilitator in determining which questions to ask and when to terminate the alternative selection process because identification of a most preferred alternative is not possible.

Several important application areas that will dominate systems, man, and cybernetic (SMC) efforts for at least the next decade, together with the methods that will require further research and development in order to appropriately address these application domains, are considered herein. More specifically, four broad and pervasive system domains are examined: service systems, infrastructure and transportation systems, environmental and energy systems, and defense and space systems. Given the nature of these four application domains, a number of new systems [i.e., holistic-oriented, including system-of-systems (SoS)], man (i.e., decision-oriented, including decision informatics), and cybernetic (i.e., adaptive-oriented, including real-time control) methods are identified and their further development are discussed. Clearly, the IEEE Society on Systems, Man, and Cybernetics has a great future; its systems, man, and cybernetic methods are relevant for addressing challenging problems arising in system domains that are becoming dominant in this 21st century. However, the methods must be refined and expanded to meet the changing needs of the 21st century; from a system to a system-of-systems vision, from a disciplinary to a multidisciplinary outlook, from a mass production to a mass customization focus, from a steady state to a real-time perspective, and from an optimal to an adaptive approach.

This paper examines the value of real-time traffic information to optimal vehicle routing in a nonstationary stochastic network. We present a systematic approach to aid in the implementation of transportation systems integrated with real-time information technology. We develop decision-making procedures for determining the optimal driver attendance time, optimal departure times, and optimal routing policies under time-varying traffic flows based on a Markov decision process formulation. With a numerical study carried out on an urban road network in Southeast Michigan, we demonstrate significant advantages when using this information in terms of total cost savings and vehicle usage reduction while satisfying or improving service levels for just-in-time delivery.

Routing vehicles based on real-time traffic conditions has been shown to significantly reduce travel time, and hence cost, in high-volume traffic situations. However, taking real-time traffic data and transforming them into optimal route decisions are a computational challenge. This is in a large part due to the amount of data available that could be valuable in the route selection. The authors model the dynamic route determination problem as a Markov decision process (MDP) and present procedures for identifying traffic data having no decision-making value. Such identification can be used to reduce the state space of the MDP, thereby improving its computational tractability. This reduction can be achieved by a two-step process. The first is an a priori reduction that may be performed using a stationary deterministic network with upper and lower bounds on the cost functions before the trip begins. The second part of the process reduces the state space further on the nonstationary stochastic road network as the trip optimally progresses. The authors demonstrate the potential computational advantages of the introduced methods based on actual data collected on a road network in southeast Michigan.

The partially observed Markov decision process (POMDP) is a generalization of a Markov decision process that allows for noise-corrupted and costly observations of the underlying system state. The value function of the infinite horizon POMDP is known to be piecewise affine and convex in the probability mass vector over the state space. Such a function can be represented by a finite set of affine functions. In this paper, we develop and evaluate an exact algorithm, GAMIP, which combines a genetic algorithm and a mixed integer program to construct the minimal set of affine functions that describes the value function. Numerical results indicate that GAMIP takes up to 60% less time to construct the minimal set than does the most efficient linear programming-based exact solution method in the literature.

We consider the problem of routing a vehicle making multiple intermediate stops, assuming a non-order-preserving, multiattribute reward structure. Sub-paths of optimal paths may not be optimal for such a reward structure, which may result from routing a pick-up and delivery vehicle carrying hazardous materials that is routed on the basis of minimizing cost and risk. We assume that a priori bounds exist on the rewards from the vehicle's current position to each of the intermediate destinations and to the depot through all the intermediate destinations that have yet to be visited. Precise calculations of these rewards would require additional computational effort. Two heuristic search algorithms, BU* and DU*, are developed and analyzed. Both algorithms satisfy termination, completeness, and admissibility properties. Results indicate that BU* is guaranteed to perform no worse given better heuristic information, a guarantee that cannot be made for DU*. Computational requirements are illustrated through examples based on a real network in northeast Ohio.

Presents a study of the development and deployment of intelligent transportation systems technology and its impact on the trucking industry. In order to understand the role of information in the trucking industry, the study objectives were to determine: how information and communication technologies are enabling the availability of data on which pertinent information is based; how this information is being used by the industry; and the opportunities and barriers to the development and deployment of effective freight mobility systems. Using data from 32 interviews focused on freight mobility systems, we analyzed the information technology management practices of firms in various segments of the trucking industry. These data suggest that the roles of information technology vary greatly between different industry segments. We identify trends, issues and opportunities for researchers and managers in both the trucking industry and in the emerging intelligent transportation systems industry.

We present and analyze an algorithm, adaptive A*(AA*), for finding a least-cost-path from start node to goal node set in a directed graph. Arc costs are assumed to be scalar-valued, and the cost of each path is the sum of the concomitant arc costs. Search is guided by: 1) a collection of real-valued functions on the node set, which is a generalization of the heuristic function associated with A*; 2) a set of predetermined optimal paths; and 3) a set of paths in the graph that are considered desirable but may or may not be optimal. The knowledge representations described in (1) and (3) can be useful in describing knowledge acquired from humans. The knowledge representation described in (2) can be used to automate knowledge acquisition, so that A* exhibits a form of machine learning. Additionally, the collection of real-valued functions on the node set can be useful in describing bounds on the perfect heuristic function, i.e., the solution of the related dynamic program. A numerical analysis, using a specialization of AA* applied to a model of the Cleveland, OH, road network demonstrated significant performance improvement relative to A*.

Two generalizations of A*, BA* and DA*, are presented and analyzed. Both consider the problem of finding a minimum cost path from the start node to a finite goal node set in a directed OR-graph, assuming that estimates of the optimal costs from each node to the goal node set are given (as described by the heuristic function), estimates of all arc costs are given, but the actual arc costs require determination. DA* tends to determine a solution (not necessarily optimal) more rapidly than BA*. Improved admissible heuristics and arc cost estimates tend to reduce node expansions and arc cost determination steps for BA*; however, these results do not necessarily hold for DA*. We also show that BA* tends to require more arc cost determination steps and fewer node expansions than does DA*.

A bimodal dial-a-ride problem (BDARP) considered in this paper is a dial-a-ride problem that involves two transportation modes: paratransit vehicles and fixed route buses. Riders in such a system might be transferred between different transportation modes during the service process. The motivation of this research is that by efficiently coordinating paratransit vehicles with fixed route buses we can improve the accessibility and efficiency of a dial-a-ride system. In this paper, we design a decision support system (DSS) which automatically constructs efficient paratransit vehicle routes and schedules for the BDARP. This DSS has been tested using actual data from the Ann Arbor Transportation Authority (AATA) in Ann Arbor, MI. The results show that this DSS produces an average increase of 10% in the number of requests that can be accommodated and an average decrease of 10% in the number of paratransit vehicles required, as compared to the manual results where no fixed route buses are involved.

Presents an algorithm, called A/sup G/, for finding the least-cost path from start node to goal node set in an OR-graph, where arc costs are scalar-valued and the cost of each path is the sum of the concomitant arc costs. Search is guided by a set, H, of real-valued functions on the node set. Such a heuristic set can be a useful representation of knowledge acquired from human knowledge sources. If H.>

Develops and analyzes a heuristic search algorithm that determines the nondominated set of solution graphs for a multiobjective AND/OR graph. This algorithm, MOAO*, is a multiobjective generalization of AO*. MOAO* uses sets of vector-valued heuristic estimates to give guidance to the search. The authors show that MOAO* satisfies termination, completeness, and admissibility conditions, generalizing results associated with AO*. Further, the authors prove that if the heuristic sets satisfy a monotonicity condition, then MOAO* possesses an efficiency property reminiscent of a well-known result associated with A*.>

Presents a categorized bibliography of heuristic search research materials gathered largely from the artificial intelligence (AI) literature. The intent is to provide an introduction to this information for researchers and practitioners in operations research.>

In imprecisely specified multiattribute utility theory (ISMAUT), a pairwise comparison of two alternatives produces a bilinear inequality, composed of trade-off weights and value scores. This correspondence investigates a penalty function approach for solving the concomitant nonlinear programs that may be necessary to solve in order to determine an accurate partial order on the alternatives.>

A multiobjective generalization of the heuristic search algorithm A* is presented.called A40A*.The research is motivated by the observation that most real-world problems involve multiple.

A methodology for multiobjective intelligent computer-aided design (MICAD) of large-scale systems is proposed. The proposed MICAD methodology partitions the knowledge base required for the design system to include a progressively acquired preferential component captured using a decision theoretic model and an a priori acquired operational component that can be represented using a wide range of artificial intelligence and expert systems techniques. User preferences are employed to personalize the search for improved designs and dynamic acquisition of those preferences enables the systems, to some extent, to mimic and conform to different users, decision-making styles, and design goals. The primary emphasis is the decision theoretic treatment of user preference in a general search strategy and design domain. The construction of the operational knowledge base is demonstrated to be an opportunity for application of existing artificial intelligence techniques.>

The author presents a survey of how multiattribute decision analysis and expert systems for decision support have been and can be integrated to produce problem-solving systems that are sensitive to the key role played by user preference in the problem-solving process. The intent of this survey is to provide insight as to how system capability and acceptability can be enhanced by this integration.>

A process model and preliminary specifications are described for a knowledge-based system that incorporates user preference in supporting an important engineering design problem. The specific design problem of interest is the development of minimum (or near minimum) cost fossil fuel boilers. The current process of design involves multiple experts who interact to produce a design meeting customer specifications at the lowest possible cost. This iterative procedure is both tedious and frequently ineffective. Our approach integrates concepts from rule-based expert systems and the decision and cognitive sciences to produce an interactive knowledge-based system to support the design process. The central feature of this system is the inclusion of multiple sources of expertise in combination with formal reasoning and user preference to create the required design.

A new mathematical interpretation of alternative pairwise comparisons for a recently developed model of single-stage multiattribute decisionmaking and trade-off weight determination under uncertainty is presented. This model includes the following key features: 1) parameter values, i.e., lowest level attribute utility scores and trade-off weights, are described by set membership, and 2) use is made of directly expressed preferences among pairs of alternatives. The original mathematical interpretation of pairwise comparisons produced the following undesirable result: more precise lowest level attribute utility scores produce a more imprecise description of the trade-off weights. The new more conservative interpretation guarantees that more precise lowest level attribute utility scores will not increase the imprecision of the trade-off weights.

Two simple generalizations of Bayes' rule are presented that 1) allow both a priori probabilities and conditional probabilities to be described by linear inequalities and 2) produce an extreme point description and a linear inequality description of a set containing all possible a posteriori probabilities. Linear inequalities to describe a priori and conditional probabilities are used since many natural language statements that describe ambiguity, unpredictability, or randomness can be adequately modeled by such constraints. The perceived potential usefulness of these results is to support inference mechanisms in knowledge systems.

An approach to conflict resolution in rule-based expert systems that incorporates a behaviorally relevant generalization of multiattri-bute utility theory is proposed. The intent of this approach is to take into account preferential knowledge, specific to the user and/or situation, in rule selection. This knowledge will enhance the user's perception of the system's capability and hence the system's acceptability.

The development of an interactive planning and decision support process for multiple-criteria alternative selection situations is discussed. Probabilities, utility scores for the lowest level attributes, and attribute tradeoff weights, i.e. the parameters, can be imprecisely described by set inclusion. Within a specified structural model of the decision situation, the process allows the decision-maker to iteratively select the mix of parameter value precision and alternative ranking specificity. By selecting this mix, the decision-maker is able to direct the alternative selection process in an iterative manner, using alternative selection strategies based on behaviorally meaningful dominance search strategies.

Several behaviourally relevant extensions of the standard decision analysis paradigm are generalized by the model, and an inverse decision-aiding feature is included that permits the use of directly expressed preferences among the alternatives. Parameter values (lowest-level-attribute utility scores and trade-off weight) are described by set membership which can be used to describe many natural language expressions of preference, interval descriptions of value, and ordinal and cardinal rankings. Procedures are presented for ranking the alternatives and determining trade-off weights if the preference information gleaned from utility score assessment, trade-off weight assessment, and directly expressed preferences among the alternatives is consistent. For inconsistent information, procedures are presented for identifying the inconsistencies.

An approach for choicemaking under certainty, based in part upon multiple objectve optimizatin is presented in this paper. With this approach dearly inferior alternatives are eliminated and subsets of alternatives are determined whih are guaranteed to contain the most preferred alternatives through use of an induced partial order on the set of alternatives. Use of such a relation to order the alternative set partially is reminicent of multiobjective optimization theory (MOOT). Our MOOT based approach is believed behaviorally relevant in that it is interactive and can accommodate a variety of cogitive styles and levels of on-line decisionmaker preference feedback. It does not requir elicitation of all criterion or attribute weights as does the multiple attribute utility theory (MAUT) approch. MAUT is compatible with and can be used to complement and potentially enhance the effectiveness of the approach for value elicitation for choicemaking. Applicadon of the MOOT based approach is illustrated by several examples.

Sequential decision-making via dynamic programming. Unified approach to optimal control of stochastic dynamic systems and Markovian decision problems. Applications in linear-quadratic control, inventory control, and resource allocation models. Optimal decision making under perfect and imperfect state information. Certainty equivalent and open loop-feedback control, and self-tuning controllers. Infinite horizon problems, successive approximation, and policy iteration. Discounted problems, stochastic shortest path problems, and average cost problems. Optimal stopping, scheduling, and control of queues. Approximations and neurodynamic programming. From the course home page: Course Description This course covers the basic models and solution techniques for problems of sequential decision making under uncertainty (stochastic control). Approximation methods for problems involving large state spaces are also presented and discussed.

A finite-horizon partially observed stochastic optimization problem is presented, where the underlying (or core) process subject to control is a finite-state discrete-time controlled semi-Markov vector process, the information pattern is classical, and times of control reset and noise corrupted observation occur at times of core process transition. Conditions for optimality are stated. The new problem formulation is shown to generalize several well-known problem formulations. Cost equality and inequality results associated with observation quality are determined, and the subsequent simplified dynamic programming equations obtained. Particular attention is given to cases where not all elements of the vector core process are either completely observed or completely unobserved.