Many Reinforcement Learning algorithms assume a Markov reward function to guarantee optimality. However, not all reward functions are Markov. This paper proposes a framework for mapping non-Markov reward functions into equivalent Markov ones by learning specialized reward automata, Reward Machines. Unlike the general practice of learning Reward Machines, we do not require a set of high-level propositional symbols from which to learn. Rather, we learn hidden triggers, directly from data, that construct them. We demonstrate the importance of learning Reward Machines over their Deterministic Finite-State Automata counterparts given their ability to model reward dependencies. We formalize this distinction in our learning objective. Our mapping process is constructed as an Integer Linear Programming problem. We prove that our mappings form a suitable proxy for maximizing reward expectations. We empirically validate our approach by learning black-box, non-Markov reward functions in the Officeworld domain. Additionally, we demonstrate the effectiveness of learning reward dependencies in a new domain, Breakfastworld.

There are many applications where an autonomous agent can perform many sets of actions. It must choose one set of actions based on some behavioral constraints on the agent. Past work has used deontic logic to declaratively express such constraints in logic, and developed the concept of a feasible status set (FSS), a set of actions that satisfy these constraints. However, multiple FSSs may exist and an agent needs to choose one in order to act. As there may be many different objective functions to evaluate status sets, we propose the novel concept of Pareto-optimal FSSs or POSS. We show that checking if a status set is a POSS is co-NP-hard. We develop an algorithm to find a POSS and in special cases when the objective functions are monotonic (or anti-monotonic), we further develop more efficient algorithms. Finally, we conduct experiments to show the efficacy of our approach and we discuss possible ways to handle multiple Pareto-optimal Status Sets.

Drone based terrorist attacks are increasing daily. It is not expected to be long before drones are used to carry out terror attacks in urban areas. We have developed the DUCK multi-agent testbed that security agencies can use to simulate drone-based attacks by diverse actors and develop a combination of surveillance camera, drone, and cyber defenses against them.

Successful machine learning methods require a trade-off between memorization and generalization. Too much memorization and the model cannot generalize to unobserved examples. Too much over-generalization and we risk under-fitting the data. While we commonly measure their performance through cross validation and accuracy metrics, how should these algorithms cope in domains that are extremely under-determined where accuracy is always unsatisfactory? We present a novel probabilistic graphical model structure learning approach that can learn, generalize and explain in these elusive domains by operating at the random variable instantiation level. Using Minimum Description Length (MDL) analysis, we propose a new decomposition of the learning problem over all training exemplars, fusing together minimal entropy inferences to construct a final knowledge base. By leveraging Bayesian Knowledge Bases (BKBs), a framework that operates at the instantiation level and inherently subsumes Bayesian Networks (BNs), we develop both a theoretical MDL score and associated structure learning algorithm that demonstrates significant improvements over learned BNs on 40 benchmark datasets. Further, our algorithm incorporates recent off-the-shelf DAG learning techniques enabling tractable results even on large problems. We then demonstrate the utility of our approach in a significantly under-determined domain by learning gene regulatory networks on breast cancer gene mutational data available from The Cancer Genome Atlas (TCGA).

Deception detection has been studied for hundreds of years. A particularly challenging problem is to not only identify truth from deception, but also discriminate misinformation, i.e. errors, from deception. Misinformation has generally been ignored in the study of deception detection, but through analysing the foundations of deception, it may be possible to pinpoint a fundamental difference between deception and all other benign communications – namely, the intent of the speaker. We present a detection model that captures a speaker’s intent by measuring his patterns of reasoning. The reasoning patterns of deceivers may serve as indicators of intentional deception. Through empirical studies, these intent-driven reasoning patterns can identify as well as explain deceptive communications.

Understanding the human decision-making process and evaluating the quality of these decisions has been the focus of many researchers. Previously, we proposed a computational, cognitive framework called the Double Transition Model (DTM) to study human decision-making processes. We applied it to simulate a couple of scenarios developed through a naval warfare simulation game called Steel Ocean. This framework concentrated on the cognitive process of an individual's decision-making process and capturing his cognitive style. One of the key functionalities of this framework has been to provide a reward distribution indicating the quality of decisions made under certain conditions. In this paper, we present a rigorous investigation of our models capturing individual characteristics with respect to decision-making style and the reward distributions. In particular, our models explored the following questions: 1) whether individual models are different from each other like human beings are; 2) whether these models exhibit particular decision-making styles; and 3) whether these models can capture different situations as human beings do. We evaluated the capability of our models capturing these individuals' characteristics by comparing multiple DTMs against each other, each built from a couple of individuals under various circumstances. We confirmed that individual characteristics could be captured in the DTMs. Furthermore, we compared individuals' trajectories (i.e., a sequence of decisions) identified by multiple DTMs in addition to their associated neighbors to verify that decision-making process in various social conditions could be described with DTMs. Our empirical study was conducted on two sets of real-world data: Supervisory Control Operations User Testbed (SCOUT) and the naval warfare simulation game (Steel Ocean).

This paper examines the impact of social influence on collective intelligence that causes the divergence of individual decisions from the expected collective decision. An important application of collective intelligence is national election predictions, which may encounter spectacular failures. While experts have provided various explanations, this paper posits that such influence among different types of voters is the primary reason. The 2015 UK Election as a case was studied, which demonstrates that such influence is intrinsic to collective intelligence. This paper then proposes a social influence-based prediction model to remedy these failures. Experiments demonstrate that the new model can account for the existence of such social influence.

In order to rigorously characterize the difference or similarity between two probabilistic knowledge bases, a distance/divergence metric must be established. This becomes increasingly important when conducting parameter learning or tuning of a knowledge base. When tuning a knowledge base, it is essential to characterize the global probabilistic belief change as the knowledge base is tuned to ensure the underlying probability distribution of the knowledge base is not drastically compromised. In this paper, we develop an entropy-based distance measure for a Bayesian Knowledge Base (BKB) derived from the Chan-Darwiche distance measure used in a variety of probabilistic belief network analyses. Through this distance measure it is possible to calculate the theoretical minimum distance required to correct a BKB when the system's answer contradicts that of an expert. Having a theoretical minimization limit on distance allows for a quick calculation to test the integrity of either the BKB or the expert's judgement, since a high minimum distance would suggest the necessary tuning is not consistent with the rest of the knowledge base. Further still, this distance measure can be used to prove that in some cases the standard single causal rule set BKB tuning procedure (discussed in our prior work) in fact minimizes the global BKB distance. The final portion of this paper presents a few practical examples which analyze the utility of the BKB distance measure along with evidence supporting the proposition that the Causal Rule Set tuning procedure minimizes the distance between the original and tuned knowledge base in many cases.

One of the primary challenges of modeling the social resilience of communities is that resilience may depend on a number of multidomain factors, ranging from ecological to political. In addition, the impacts and interactions of the relevant factors may not be fully understood. There is also the challenge of representing the intricate behaviors of the social actors, both individuals and groups, in order to model their responses to perturbations in the environment and to internal changes. In light of these challenges, current works tend to make a number of simplifying assumptions. In this paper, we propose a computational framework to formulate multiple resilience functions, each modeling a particular hypothesis about the system's resilience. One of our key contributions is the ability to use social theories to compose these individual resilience functions into an umbrella resilience function, while providing qualitative analysis. We validate our framework by modeling the resilience of a fishing community in Somalia over the period of 1999-2012, as it underwent a series of dramatic ecological, political, and economic changes. We formulated resilience functions to computationally model the competing support for the community's traditional occupation of fishing and alternatively for taking up piracy on the high seas. We then provide an overall resilience function by combining these individual resilience functions using social theories such as the social norm theory and risk theory.

Social Network Analysis (SNA) is a powerful tool for analyzing social phenomena that is based on studying how actors are connected or interact with each other. All Social Networks (SNs) are inherently embedded in particular cultures. However, the effect of cultural influence is often missing from SNA techniques. Moreover, to incorporate culture, modeling approaches have to deal with inaccurate, unrealistic, and incomplete cultural data. In order to address this problem, we propose a generic approach to systematically represent culture in the form of relevant factors and relationships, while leveraging relevant social theories, and to infuse them into SNs in order to obtain more realistic and complete analyses. Using two sets of experiments, we validate the effectiveness of our approach and demonstrate the significant advantages obtained through culturally infused SNA.

our transaction’s name has changed - from IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS PART B: CYBERNETICS to a more concise Transactions on Cybernetics (TCyb). For the past many months, the publications of the IEEE Systems, Man, and Cybernetics Society (SMCS) have been undergoing a major reorganization. The reorganization was based on numerous discussions with the SMCS membership and positive feedback that were received and on recommendations from the 2006 IEEE Periodicals Review. In November 2011, the IEEE Technical Activities Board approved the name and scope changes of all three transactions: 1) IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS PART A: SYSTEMS AND HUMANS to IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS: SYSTEMS; 2) IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS PART C: APPLICATIONS AND REVIEWS to IEEE TRANSACTIONS ON HUMAN–MACHINE SYSTEMS; and 3) this transaction. The realignment of the three transactions is meant to help better situate research topics, areas, and articles for the society through its publications. Here are the associated scopes for the three transactions. IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS: SYSTEMS - The scope of the IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS: SYSTEMS includes the fields of systems engineering. It includes issue formulation, analysis and modeling, decision making, and issue interpretation for any of the systems engineering life cycle phases associated with the definition, development, and deployment of large systems. In addition, it includes systems management, systems engineering processes, and a variety of systems engineering methods such as optimization, modeling, and simulation. IEEE TRANSACTIONS ON CYBERNETICS - The scope of IEEE TCyb includes computational approaches to the field of cybernetics. Specifically, the transactions welcomes papers on communication and control across machines or between machine, human, and organizations. The scope of TCyb includes areas such as computational intelligence, computer vision, neural networks, genetic algorithms, machine learning, fuzzy systems, cognitive systems, decision making, and robotics, to the extent that they contribute to the theme of cybernetics or demonstrate an application of cybernetics principles. IEEE TRANSACTIONS ON HUMAN–MACHINE SYSTEMS - The scope of the IEEE TRANSACTIONS ON HUMAN-MACHINE SYSTEMS includes the fields of human machine systems. It covers human systems and human organizational interactions, including cognitive ergonomics, system test and evaluation, and human information processing concerns in systems and organizations.

As this issue closes out the 2013 publication year for IEEE Transactions on Cybernetics, it also concludes my term as Editor-in-Chief (EiC).In my six years as EiC our Transactions has been through several major changes.In 2008, our scope was updated to better reflect and tighten the concepts of cybernetics in order to better help foster next-generation cutting-edge research areas.In 2013, we were renamed from IEEE Transactions on Systems, Man, and Cybernetics: Part B to IEEE Transactions on Cybernetics.This followed a long-term reorganization of the IEEE Systems, Man, and Cybernetics Society to more accurately reflect the three principle areas as highlighted in our society name.As such, the IEEE Transactions on Human-Machine Systems and IEEE Transactions on Systems, Man, Cybernetics: Systems (SMCS) were the other two Transactions reorganized from our original IEEE Transactions on Systems, Man, and Cybernetics: Parts A, B, and C. The upcoming year should be an exciting one, with the introduction of a new Transactions for IEEE SMCS entitled the IEEE Transactions on Computational Social Systems.I am particularly enthusiastic about this new Transactions, as this is a critical new area of research natural to IEEE SMCS.IEEE Transactions on Cybernetics (TCYB) has been seeing a sharp increase of papers in this area, which is clearly demonstrating great fertilization across disciplines not normally seen together in the past; from engineering to computer science to social science and the humanities.All four of our Transactions will play key roles in modern complex human-cyber-physical systems, complex dynamic behavior modeling, and new ways of solving challenges faced by human-kind, just to name a few, for this decade.Since 2008, our Transactions has continued to significantly grow in research article submissions.Ten years ago, in 2003, we had 731 submissions.In my first year as EiC in 2008, we had just under 1400.This has increased to almost 1700 as projected for 2013 at the time of this writing.

Research in Information Retrieval (IR) experienced a paradigm shift from first having too few documents to search from to now having way too many of them. When users have trouble finding relevant documents, they tend to become frustrated and give up searching. Scholars have attempted to reduce instances of search frustration via query expansion, information filtering, and incorporating user feedback. However, these approaches are not effective as users still experience a period of frustration before getting more relevant results. The aim of this conceptual paper is to explore possible improvements to the field by revisiting two fundamental concepts: topicality and novelty. First, we elaborate various issues with existing IR models in capturing these two concepts. Second, we illustrate a potential improvement to these issues: namely, a new simple graph space model with new topicality and novelty measures that can better capture these features of a document based on rewards and penalties for corresponding matching and missing semantic links. Lastly, we demonstrate a walk-through example using the new graph-based IR model.

We are working on the problem of developing a flexible, generic metal earning process that supports algorithm selection based on studying the algorithms' past performance behaviors. State of the art machine learning systems display limitations in that they require a great deal of human supervision to select an effective algorithm with corresponding options for a specific domain. Additionally, very little guidance is available for algorithm-parameter selection and the number of available choices is overwhelming. In this paper, we develop a flexible, large-scale experimental framework for a metacontroller that supports explorations through algorithm-parameter space and recommend algorithm for a given dataset. First, we aim to facilitate an easy to use process to create a search space for algorithm selection by automatically exploring some possible combinations of algorithms and key parameters. Secondly, our goal is to come up with an algorithm recommendation by looking at the past behaviors of related datasets. Our main contribution is the implemented framework itself which is based on the use of a wide variety of strategies to automatically generate a search space and recommend algorithms for a specific dataset. We evaluate our system with 40 major algorithms on 20 datasets from the UCI repository. Each dataset is represented by 25 data characteristics. We generate and run 7510 combinations of algorithm, parameters and datasets. Our experiments show that our framework offers a friendly way of setting up a machine learning experiment while providing accurate ranking of recommended algorithms based on past behaviors. Specifically, 88% of recommended algorithm rankings significantly correlated with the true rankings for a given dataset.

In the intelligence community, the existence of a malicious insider poses a severe threat to information, to the actual analytic process, and, ultimately, to any decision-making process relying on such information and analyses. An analyst with malicious intent can create irreversible short-term, as well as long-term, damage that is hard to detect. In this paper, we propose a novel methodology that detects malicious analysts who attempt to manipulate decision makers' perceptions through their intelligence reports. This detection method relies on each analyst's working style, which we assume to be consistent from task to task. In order to measure an analyst's degree of consistency, we employ a user-modeling technique that automatically builds a computational model of each analyst based on observation of their activities. We hypothesize that inconsistency is mainly caused by malicious actions. Therefore, the detection method evaluates how consistent an analyst is across different tasks and raises an alert if any significantly large inconsistency is detected. A normalization procedure is employed which allows us to compare across a group of analysts and is shown to reduce noise and amplify inconsistency that is due to malicious actions. We show that this improves detection performance. Our experiments demonstrate the effectiveness of our approach in detecting malicious insiders. In the experiments, the percentage of malicious insiders grouped with legitimate ones is varied, and results are collected with and without normalization in order to provide a comprehensive analysis of our approach.

Even though people deal with deceptions throughout their whole lives, deception detection remains a challenging problem. The average detection rate for humans is only around chance, and detection skill is unlikely to be improved through training. Therefore, researchers have studied the features of deceptive behaviors that were largely ignored in human detection. For example, physiologists look at the physiological signals such as breathing rate and blood pressure, psychologists focus on non-verbal cues such as facial expressions and gestures, and computer scientists search for linguistic cues such as length of sentences. Although they all provide promising results, they seem to neglect a critical part in a person's communication: the reasoning behind the communicated content. In this paper, a method is proposed to detect deception by identifying inconsistencies, explaining the reasoning behind the inconsistencies, and measuring the likelihood of deception based on cues in reasoning. The initial experiment demonstrates the effectiveness of the approach in identifying and explaining communications containing inconsistencies. Reasoning cues that can best discriminate deception from truth are proposed, and aspects of the verification and measurement of such cues as possible future directions of work are discussed.

Knowledge acquisition is an essential process in improving the problem-solving capabilities of existing knowledge-based systems through the absorption of new information and facilitating change in current knowledge. However, without a verification mechanism, these changes could result in violations of semantic soundness of the knowledge causing inconsistencies and ultimately, contradictions. Therefore, maintaining semantic consistency is of primary concern, especially when dealing with incompleteness and uncertainty. In this paper, we consider the semantic completability of a knowledge system as a means of ensuring long-term semantic soundness. In particular, we focus on how to preserve semantic completability as the knowledge evolves over time. Among numerous methods of knowledge representation under uncertainty, we examine Bayesian Knowledge-Bases, which are a rule-based probabilistic model that allows for incompleteness and cycles between variables. A formal definition of full/partial completability of BKB is first introduced. A principle to check the overall completability of a BKB is then formulated with a formal proof of correctness. Furthermore, we show how to use this principle as a guide for maintaining semantic soundness and completability during incremental knowledge acquisition. In particular, we consider two primary modifications to the knowledge base: 1) adding/fusing knowledge, and 2) changing/tuning conditional probabilities.

Uncertainty handling for semantic networks is a difficult problem which has slowed the effort to fully develop a semantic web. Uncertainty handling becomes particularly challenging when incompleteness is present in a domain, as it frequently is when modeling real-world complexity. To date, work on uncertainty frameworks for semantic networks has not intuitively captured a useful notion of uncertainty, for reasons including weaknesses in underlying uncertainty theories and assumption conflicts with semantic networks. We propose a framework which is a synthesis of semantic networks and Bayesian Knowledge Bases, which are a generalization of Bayesian Networks to accommodate incompleteness. This synthesis represents knowledge as “if-then” conditional probability rules between description logic assertions. We define simple methods for reasoning about semantic information under uncertainty and about uncertainty itself. Our results show potential to remove some obstructions in the path to a semantic web.

Modeling complex real world scenarios require representing and analyzing information from multiple domains including social, economic and political aspects. However, most of the current frameworks in social networks are not generic enough to incorporate multi-domain information or to be applied in different scenarios. Current frameworks also make simplifications in other modeling aspects such as incorporating dynamism and providing multi-scale analyses. Representing culture is critical to truly capture the nuances of various social processes. It also helps to make the framework generic enough to be applied in multiple application domains.We will leverage a novel framework called the Culturally Infused Social Network (CISN) to represent culture using probabilistic reasoning networks called Bayesian Knowledge Bases (BKBs), in representations known as cultural fragments. Cultural fragments model the intent of actors by relating their actions to underlying beliefs and goals. CISN also supports analysis algorithms to make predictions and provide explanations. We validate CISN by simulating the 2006 Somali conflict involving the Islamic Court Union (ICU). The Somali conflict is a complex scenario requiring deep understanding of myriad factors. We focus on analyzing the group stability of ICU, how changing alliance caused conflicts and led to its ultimate demise. We define a metric to measure instability in a group, identify critical factors that led to instability in ICU and provide analyses.

Text summarization techniques have been found to be effective with regard to helping users find relevant information faster. The effectiveness and efficiency of a user's performance in an information-seeking task can greatly be improved if he/she needs to only look at a summary that includes the relevant information presented in his/her preferred manner. On the other hand, if the main idea is misrepresented and/or omitted altogether from a summary, it may take users more time to solve a target problem or, even worse, lead users to make incorrect decisions. There is an important need to design a personalized text summarization system that takes into account both what a user is currently interested in and how a user perceives information. The latter factor is referred to as a user's cognitive styles. Although there are some existing approaches that have employed a user's interests to help in the design of a personalized text summarization system, there has been inadequate focus on exploring cognitive styles. This paper aims at studying the impact of a user's cognitive styles when assessing multidocument summaries. In particular, we choose two dimensions of a user's cognitive style - the analytic/wholist and verbal/imagery dimensions - and study their impacts on how a user assesses a summary that was generated from a set of documents. In particular, the type of a document set refers to whether the set's content is loosely or closely related. We use a document set type to explore if there are any differences in the users' assessments of summaries that were generated from sets of different types. The results of this paper show that different users have different assessments with regard to information coverage and the way that information is presented in both loosely and closely related document sets. In addition, we found that the coherency ratings that were given to summaries from the two types of document sets were significantly different between the analytic and wholist groups. This result leads us to investigate the impact of a user's cognitive styles and the following two factors that directly relate to the coherence of a summary: 1) graph entropy and 2) the percentage of stand-alone concepts. We found that these two factors and a user's cognitive styles affect a user's ratings on the coherency of a summary.

A user’s cognitive style has been found to affect how they search for information, how they analyze the information, and how they make decisions in an analytical process. In this paper, we propose an approach that uses Hidden Markov Models (HMM) to dynamically capture a user’s cognitive style by automatically exploring the sequence of actions and relevant information with respect to the content of the actions. The evaluation results show that our HMM model achieves an average of 72% recall with the APEX 07 collection. We also study the link between a user’s cognitive style and the various attributes relating to document content during an analytical process. The results show that the “analytic” group tends to focus on documents with significantly more specific information than the “wholist” group. The specific/general attribute of documents can help us in classifying a user’s cognitive styles automatically

Deception detection plays an important role in safely and reliably using multientity advisory models such as multiagent intelligence systems. The benevolence assumption people have based their implementations of multiagent (human and/or synthetic) systems on is rarely valid in the real world. Unfortunately, deception detection is extremely challenging. The average detection rate by humans alone is only above chance, and the skill for detection has been shown to be difficult to improve even with training. In psychological studies, deception detection is typically based on examining a person's nonverbal cues and expressions such as facial expressions, gestures, and movements. In this paper, our approach instead is focused on the agent's reasoning process. We detect deception by observing the correlations between agents, which can be used to make a reasonable prediction of the agents' reasoning processes. Our experiments demonstrate the effectiveness of this method and show the impact of different factors on detection rate. We further conduct some preliminary experiments to explore its performance at detecting both disinformation and misinformation and that of identifying more than one deceiver in the system.

Time is the key stimulus to change, causality and interaction which are the main components of a dynamic world. Therefore, the modeling of knowledge, especially in complex and dynamic domains like economics, sociology, and ecology, must incorporate the concept of time. Although there has been much research over the years on the representation of knowledge (causality, implication, and uncertainty) and on the representation of time, it has been a continuing challenge to unify them in a meaningful and useful fashion. In this paper, we propose a framework for reasoning under uncertainty with temporal constraints. The framework is extended from Bayesian knowledge-bases (BKBs), which represent knowledge in an ¿if-then¿ structure and represent uncertainty based on probability theory. By adding temporal constraints to BKBs, the framework provides a comprehensive model that incorporates the semantics of both time and uncertainty.

One of the greatest challenges in accurately modeling a human system is the integration of dynamic, fine-grained information in a meaningful way. A model must allow for reasoning in the face of uncertain and incomplete information and be able to provide an easy to understand explanation of why the system is behaving as it is. To date, work in multi-agent systems has failed to come close to capturing these critical elements. Much of the problem is due the fact that most theories about the behavior of such a system are not computational in nature, they come from the social sciences. It is very difficult to successfully get from these qualitative social theories to meaningful computational models of the same phenomena. We focus on analysis of human populations where discerning the opinions of the members of the populace is integral in understanding behavior on an individual and group level. Our approach allows the easy aggregation and de-aggregation of information from multiple sources and in multiple data types into a unified model. We also present an algorithm that can be used to automatically detect the variables in the model that are causing changes in opinion over time. This gives our model the capability to explain why swings in opinion may be experienced in a principled, computational manner. An example is given based on the 2008 South Carolina Democratic Primary election. We show that our model is able to provide both predictions of how the population may vote and why they are voting this way. Our results compare favorably with the election results and our explanation of the changing trends compares favorably with the explanations given by experts.

Along with research on information retrieval and filtering, text summarization is an effective technique to help users save time in finding critical information and making timely decisions. Some existing summarization approaches have used a userpsilas interests to develop a personalized text summarization system. However, there is inadequate focus on exploring cognitive styles, which have been found to affect the ways users think, perceive and remember information. Our main objective of this evaluation is to investigate the effect of a userpsilas cognitive style on multi-document summarization. We examine two dimensions of a userpsilas cognitive style which are the analytic/who list and verbal/imagery dimensions. We conducted an experiment to determine the impact of a userpsilas cognitive style when working with different types of document sets. The type of a document set refers to whether the content of this set is loosely related or closely related. Our results show that users in general are insensitive to the types of document sets both in terms of information covered in a summary as well as the way that a summary is written and presented. However, if we group users by the analytic/who list dimension, we found that people in groups are sensitive to the way that the information is presented for different types of document sets.

Modeling or simulating Complex Adaptive Systems (CASs) is a very important and challenging endeavor. Previously, we introduced a generic framework for addressing this problem, and included a number of critical criteria including emergence, self-organization, adaptivity, and others. In this paper, we present the methodology used for designing a particularly key component of our framework: the short-term adaptivity model. We test our short-term adaptivity model and framework within the biological science application domain, which have a number of critical CASs. In particular we model the aggregation process of Dictyostelium. The comparison between established biological experimental results and our simulation results validate the effectiveness of our model and framework.

Many maintenance networks as well as supply networks and virtual enterprises consist of multiple organizations. A common problem arising in these different domains is multiorganization scheduling and coordination. The traditional centralized methods are not appropriate because of the existence of private information and decision-making authorities at different organizations. Although many distributed mechanisms have been presented for supply networks and virtual enterprises, they may not be effective for maintenance networks because of the difficulties of scheduling the tightly related maintenance operations and handling the massive uncertainties involved. These difficulties as well as the heterogeneity of the distributed environment make it challenging to develop an efficient framework for maintenance networks that can obtain a high-quality solution under different conditions, schedule in a timely manner, solve large-scale problems, and so on. In this paper, a price-based multiagent scheduling and coordination framework for maintenance networks is explored, and a systematic experimental study is carried out to evaluate the effects of different factors on its performance. The results show that the framework is able to overcome these difficulties and could be a step toward the next generation of e-scheduling for maintenance networks

In this article, we present a general representation for constraint satisfaction problems with disjunctive relations called cluster constraint systems (CCS). For this representation, we develop a novel and simple approach for solving CCSs using convex envelopes. These envelopes can be used to decompose the feasible space of the CCS through convex approximations. We explore interval reasoning as a case study of CCS. Our experimental results demonstrate that such CCS can be effectively and efficiently solved through convex enveloping with very modest branching requirements in comparison to other generic as well as specialized algorithms for interval reasoning. In fact, convex enveloping solves significantly more cases and more efficiently than other methods used in our test bed.

Predicting the native conformation using computational protein models requires a large number of energy evaluations even with simplified models such as hydrophobic-hydrophilic (HP) models. Clearly, energy evaluations constitute a significant portion of computational time. We hypothesize that given the structured nature of algorithms that search for candidate conformations such as stochastic methods, energy evaluation computations can be cached and reused, thus saving computational time and effort. In this paper, we present a caching approach and apply it to the triangular 2D-HP lattice model. We provide theoretical analysis and prediction of the expected savings from caching as applied this model. We conduct experiments using a sophisticated evolutionary algorithm that contains elements of local search, memetic algorithms, diversity replacement, etc. in order to verify our hypothesis and demonstrate a significant level of savings in computational effort and time that caching can provide.

Our goal is to develop a technology that enables information uncertainty portrayal, which provides battlespace decision makers with effective means to incorporate uncertainty into their decision making process. In This work, we describe the prototype uncertainty prediction system, which supports visualization and assessment of event uncertainty within the context of predictive battlespace awareness.

Knowledge validation is a vital phase in knowledge engineering which is ultimately aimed at correcting the knowledge-base such that when inferenced over, it satisfy all test cases specified by the expert users. Naturally, such a goal is unachievable if there is some contradiction in the given set of test cases. In this work, we analyze this property of test case sets in knowledge validation for knowledge bases that are modelled in terms of Bayesian knowledge bases (BKBs) in order to determine the necessary and sufficient condition for a test case set to be contradiction-free, i.e., "Does there exist a knowledge base satisfying all test cases in the set?" We show that the complexity of deciding if a test case set meets that condition is NP-compete. As such, we also present some special cases in which it is tractable to make this determination.

Knowledge about the characteristics of a discrete optimization problem can often be leveraged for improved algorithm performance. Having an understanding of the relationship between knowledge and performance can provide us useful hints and better prediction of algorithm behavior when we choose or design algorithms. Previously, we developed a directional tree (DT) model [X. Zhong et al., (2003)], which concurrently describes algorithm behavior and represents knowledge explicitly, and thus provided us with a tool to analyze the impact of knowledge on algorithm performance. By using DT, we analyzed the performance of an algorithm when that algorithm is used for solving problems from a problem space P. In our previous analysis, we only considered the situation where there is only one optimal solution in the solution space. Furthermore, our DT model assumes that knowledge about the problem is obtained prior to the execution of any probabilistic or deterministic algorithm. However, such prior knowledge may not be readily or immediately available. In this paper, we extend our DT results to cover multiple optimal solutions and then generalize our DT model to take into account acquisition of problem knowledge during execution. Our generalized directional tree (GDT) model provides a framework for incorporating knowledge obtained online into algorithms, and thus enables us to develop online optimization algorithms that dynamically updates their search decisions in response to obtained knowledge so far.

Real world maintenance networks often involve multi-organizational scheduling. The traditional centralized methods are not appropriate for solving the maintenance-scheduling problem because of the existence of private information and decision-making authorities at different organizations. Multi-agent scheduling and coordination is able to protect the private information and retain the decision-making authorities at different organizations. However, it presents its own challenges, such as obtaining a high-quality solution in a timely manner, providing the organizations with guidance on operating economically, being able to solve large-scale problems, and so on. In this paper, a price-based multi-agent scheduling and coordination framework is explored and a systematic study is carried out to evaluate the effects of factors on its performance. The empirical results not only show that the framework is able to quickly find high quality solutions for large-scale problems, but also reflect interesting relationships between selected factors such as resource utilization and performance measures such as mean asset turn-around-time.

In this paper, we develop an efficient online approach for belief revision over Bayesian networks by using a reinforcement learning controller to direct a genetic algorithm. The random variables of a Bayesian network can be grouped into several sets reflecting the strong probabilistic correlations between random variables in the group. We build a reinforcement learning controller to identify these groups and recommend the use of "group" mutation and "group" crossover for the genetic algorithm based on these groupings online. The system then evaluates the performance of the genetic algorithm based on these groupings online. The system then evaluates the performance of the genetic algorithm and continues with reinforcement learning to further tune the controller to search for a better grouping.

Managing uncertainty during the knowledge engineering process from elicitation to validation and verification requires a flexible, intuitive, and semantically sound knowledge representation. This is especially important since this process is typically highly interactive with the human user to add, update, and maintain knowledge. In this paper, we present a model of knowledge representation called Bayesian Knowledge-Bases (BKBs). It unifies a ‘if-then’ style rules with probability theory. We also consider the computational efficiency of reasoning over BKBs. We can show that through careful construction of the knowledge-base, reasoning is computationally tractable and can in fact be polynomial-time. BKBs are currently fielded in the PESKI intelligent system development environment.

Computation of marginal probabilities in Bayes nets is central to numerous reasoning and automatic decision-making systems. This paper presents a deterministic approximation scheme for this hard problem that supplies provably correct bounds by aggregating probability mass in independence-based (IB) assignments. It refines belief updating methods. It approximates posterior probabilities by finding a small number of the highest probability complete (or evidentially supported) assignments. Under certain assumptions, the probability mass in the union of these assignments is sufficient to obtain a good approximation. Such methods are especially useful for highly connected networks. Since IB assignments contain fewer assigned variables, the probability mass in each assignment is greater than in the respective complete assignment. Thus, fewer assignments are sufficient, and a good approximation can be obtained efficiently. Two classes of algorithms for finding high-probability assignments are suggested: best-first heuristic search and a special integer linear program (ILP). Since IB assignments may be overlapping events in probability space, accumulating the mass in a set of assignments may be hard. In the ILP variant, it is easy to avoid the problem by adding equations that prohibit overlap. In the best-first search algorithm, other schemes are necessary, but experimental results suggest that using inclusion-exclusion (potentially exponential-time in the worst case) in the overlap cases is not too expensive for most problem instances.

For a computer generated force (CGF) application to be useful in training environments, it must exhibit complex, realistic behavior within the battlespace. To achieve this level of fidelity, it must operate at multiple skill levels and exhibit competency at assigned missions. CGF applications must also have adaptable decisions mechanisms and behaviors even when operating under uncertainty and the application must learn from past experience. Furthermore, simply correct performance of individual entity behaviors is not sufficient. Issues related to complex inter entity behavioral interactions, such as the need to maintain formation and share information, must also be considered. To achieve these necessary capabilities, an extensible software architecture, an expandable knowledge base, and an adaptable decision making mechanism are required. Our labs have addressed these issues in the context of the Automated Wingman (AW) project. The AW is based on fuzzy logic, the Common Object DataBase (CODE) software architecture, and hierarchical knowledge structure. Decision making is founded on multi layered, fuzzy logic controlled situational analyses combined with adversarial game tree techniques.

The employment of computer generated forces (CGFs) within distributed virtual environments (DVEs) dramatically increases the number of entities in a simulated training environment. However, current CGF limitations produce behaviours that can be defeated using methods ineffective against humans. Our research focuses on developing aircraft CGFs. It is necessary to deal with uncertainty, ambiguity, and approximation. The Fuzzy Wingman (FW) relies on fuzzy logic to provide these abilities. In this manner, the FW presents a reasonable approach to effectively populating the simulated training environment with low cost CGFs while maintaining the realism of training with human controlled entities.

Generic expert systems are reasoning systems that can be used in many application domains, thus requiring domain independence. The user interface for a generic expert system must contain intelligence in order to maintain this domain independence and manage the complex interactions between the user and the expert system. This paper explores the uncertainty-based reasoning contained in an intelligent user interface called GESIA. GESIA's interface architecture and dynamically constructed Bayesian network are examined in detail to show how uncertainty-based reasoning enhances the capabilities of this user interface.

Probabilistic reasoning suffers from NP-hard implementations. In particular, the amount of probabilistic information necessary to the computations is often overwhelming. For example, the size of conditional probability tables in Bayesian networks has long been a limiting factor in the general use of these networks. We present a new approach for manipulating the probabilistic information given. This approach avoids being overwhelmed by essentially compressing the information using approximation functions called linear potential functions. We can potentially reduce the information from a combinatorial amount to roughly linear in the number of random variable assigments. Furthermore, we can compute these functions through closed form equations. As it turns out, our approximation method is quite general and may be applied to other data compression problems.

Existing models of diagnosis have not unified the notions of time, uncertainty and abduction which are necessary in domains such as clinical diagnosis, dynamic systems modelling, and fault diagnosis. We present a new approach which models information through linear constraints and find that many aspects of our knowledge-base and inferencing mechanism are naturally suited towards these constraints. Furthermore, this approach properly subsumes existing abductive and temporal models and provides a precise framework for explanatory reasoning.

Integer linear programming (ILP) has long been an important tool for operations research akin to the AI search heuristics for NP-hard problems. However, there has been relatively little incentive to use it in AI, even though it also deals with optimization. The problem stems from the misperception that because the general ILP problem is difficult to solve, then it will be difficult for all cases. It is known that AI search at first glance also seems this way until one begins to apply it to a specific domain. Clearly, there are many gains to be had from studying the problem with a different perspective like ILP. The authors look at probabilistic reasoning with Bayesian networks. For some time now, they have been stalled by its computational complexities. Algorithms have been designed for small classes of networks, but have been mainly inextensible to the general case. In particular, the authors consider belief revision in Bayesian networks which is the search for the most probable explanation for some given evidence. They present a new approach for computing belief revision from the ILP point of view. By observing various properties inherent in Bayesian networks, one can successfully develop a hill-climbing strategy which does not require an energy function. This approach can handle the entire class of Bayesian networks. Furthermore, experimental results indicate that finding the most probable explanation can be accomplished fairly easily.

Abductive reasoning (explanation) is a backward-chaining process on a collection of logical rules. Cost-based abduction is a model for abductive reasoning which provides a concrete formulation of the explanation process. Unfortunately, abduction is an NP-hard task. Current approaches for performing abductive reasoning have been based on graph searching heuristics. However, they are very restrictive and still exhibit expected-case exponential growth rates. One particularly stringent restriction can be found in cost-based abduction whereby the knowledge base must be acyclic. The existence of cyclicity results in anamolous behaviour. In this paper, we present an extended model called generalized cost-based abduction for general knowledge bases. We provide two approaches for solving this model by using a recently introduced technique different from graph searching. This technique uses linear constraints to flexibly represent our knowledge. The problem can then be recast into 0-1 integer linear programming. The flexibility of the new representation scheme can be naturally exploited to handle cyclicity. Our first approach is based on explicitly identifying each reasoning cycle. The second is somewhat more general and based on graph topology. Each approach provides different strengths depending on the abduction problem to be solved.