An algorithm for distributing coalitional value calculations among cooperating agents

The process of forming coalitions of software agents generally requires calculating a value for every possible coalition which indicates how beneficial that coalition would be if it was formed. Now, instead of having a single agent calculate all these values (as is typically the case), it is more efficient to distribute this calculation among the agents, thus using all the computational resources available to the system and avoiding the existence of a single point of failure. Given this, we present a novel algorithm for distributing this calculation among agents in cooperative environments. Specifically, by using our algorithm, each agent is assigned some part of the calculation such that the agents' shares are exhaustive and disjoint. Moreover, the algorithm is decentralized, requires no communication between the agents, has minimal memory requirements, and can reflect variations in the computational speeds of the agents. To evaluate the effectiveness of our algorithm, we compare it with the only other algorithm available in the literature for distributing the coalitional value calculations (due to Shehory and Kraus). This shows that for the case of 25 agents, the distribution process of our algorithm took less than 0.02% of the time, the values were calculated using 0.000006% of the memory, the calculation redundancy was reduced from 383229848 to 0, and the total number of bytes sent between the agents dropped from 1146989648 to 0 (note that for larger numbers of agents, these improvements become exponentially better).     

User interface design for cooperating agents in industrial process supervision and control applications

Computer systems based on cooperating agent architectures are currently introduced in industrial process supervision and control applications as operator support systems in tasks such as fault diagnosis, system restoration etc. Cooperating agents are relevant to these applications since they involve a high degree of physical distribution, the operators' decisions are often based on multiple conflicting views which can be moderated by the cooperating agents, and the domains are complex with high degree of modularity.In the frame of the research project ARCHON, a multi-agent system architecture has been defined in order to be used in industrial process supervision and control applications. An issue of high importance in this context is the interaction with the human operator and the design of a user interface which supports this interaction. The impact of multi-agent architectures on the user interface design of industrial process supervision and control systems is the subject of this paper. An example of an interface designed for a multi-agent system in the area of electrical network supervision is provided.     

Modelling disruptions and resolving conflicts optimally in a railway schedule

Resolving disruptions, by dispatching and rescheduling conflicting trains is an NP-complete problem. Earlier literature classify railway operations as: (i) tactical scheduling, (ii) operational scheduling, and (iii) rescheduling. We distinguish the three based on operational criticality. Existing optimisation models do not distinguish precisely between scheduling and rescheduling based on constraints modelling; the only difference is in their objective function. Our model is the first of its kind to incorporate disruptions in an MILP model and to include conflicts-resolving constraints in the model itself. The major advantage of such a formulation is that only those trains which are disrupted are rescheduled and other non-conflicting trains retain their original schedules. Our model reschedules disrupted train movements on both directions of a single track layout with an objective to minimise total delay of all trains at their destinations. Using a small sized data it is proved that all possible conflicts out of a disruption are resolved. Apart from achieving optimal resolutions, we infer through experimental verification that a non-standard dispatch ordering is a requisite for global optimality, as cogitated by other authors.     

Detecting and resolving deadlocks in mobile agent systems

Mobile agents environment is a new application paradigm with unique features such as mobility and autonomy. Traditional deadlock detection algorithms in distributed computing systems do not work well in mobile agent systems due to the unique feature property of the mobile agent. Existing deadlock detection and resolution algorithms in mobile agent systems have limitations such as performance inefficiency and duplicate detection/resolution when multiple mobile agents simultaneously detect/resolve the same deadlock. To address these problems, we propose an improved deadlock detection and resolution algorithm that adopts priority-based technique and lazy reaction strategy. The priority-based technique aims to ensure that there is only one instance of deadlock detection and resolution, and it also helps reduce mobile agent movement and data traffic together with the lazy reaction strategy. The liveness and safety properties of the proposed algorithm are proved in this paper. Theoretical analysis and experimental results show that the proposed algorithm provides better performance in terms of agent movement, data traffic, and execution time.     

Reasoning with contextual requirements: Detecting inconsistency and conflicts

ContextThe environment in which the system operates, its context, is variable. The autonomous ability of a software to adapt to context has to be planned since the requirements analysis stage as a strong mutual influence between requirements and context does exist. On the one hand, context is a main factor to decide whether to activate a requirement, the applicable alternatives to meet an activated requirement as well as their qualities. On the other hand, the system actions to reach requirements could cause changes in the context.ObjectivesModelling the relationship between requirements and context is a complex task and developing error-free models is hard to achieve without an automated support. The main objective of this paper is to develop a set of automated analysis mechanisms to support the requirements engineers to detect and analyze modelling errors in contextual requirements models.MethodWe study the analysis of the contextual goal model which is a requirements model that weaves together the variability of both context and requirements. Goal models are used during the early stages of software development and, thus, our analysis detects errors early in the development process. We develop two analysis mechanisms to detect two kinds of modelling errors. The first mechanism concerns the detection of inconsistent specification of contexts in a goal model. The second concerns the detection of conflicting context changes that arise as a consequence of the actions performed by the system to meet different requirements simultaneously. We support our analysis with a CASE tool and provide a systematic process that guides the construction and analysis of contextual goal models. We illustrate and evaluate our framework via a case study on a smart-home system for supporting the life of people having dementia problems.ResultsThe evaluation showed a significant ability of our analysis mechanisms to detect errors which were not notable by requirements engineers. Moreover, the evaluation showed acceptable performance of these mechanisms when processing up to medium-sized contextual goal models. The modelling constructs which we proposed as an input to enable the analysis were found easy to understand and capture.ConclusionsOur developed analysis for the detection of inconsistency and conflicts in contextual goal models is an essential step for the entire system correctness. It avoids us developing unusable and unwanted functionalities and functionalities which lead to conflicts when they operate together. Further research to improve our analysis to scale with large-sized models and to consider other kinds of errors is still needed.     

Comparison of human and machine-based educational standard assignment networks

Increasing availability of digital libraries of K-12 educational resources, coupled with an increased emphasis on standard-based teaching necessitates assignment of the standards to those resources. Since manual assignment is a laborious and ongoing task, machine-based standard assignment tools have been under development for some time. Unfortunately, data on the performance of these machine-based classifiers are mostly lacking. In this article, we explore network modeling and layout to gain insight into the differences between assignments made by catalogers and those by the well-known Content Assignment Tool (CAT) machine-based classifier. To build the standard assignment networks, we define standards to be linked if they are jointly assigned to a learning resource. Comparative analysis of the topology and layout of the networks shows that whereas the cataloger-based network reflects the underlying curriculum, i.e., clusters of standards separate along lines of lesson content and pedagogical principles, the machine-based network lacks these relationships. This shortcoming is partially traced back to the machine classifier’s difficulties in recognizing standards that express ways and means of conducting science.     

Display dimensionality and conflict geometry effects on maneuver preferences for resolving in-flight conflicts

OBJECTIVE: Two experiments explored the effects of display dimensionality, conflict geometry, and time pressure on pilot maneuvering preferences for resolving en route conflicts. BACKGROUND: With the presence of a cockpit display of traffic information (CDTI) that provides graphical airspace information, pilots can use a variety of conflict resolution maneuvers in response to how they perceive the conflict. Inconsistent preference findings from previous research on conflict resolution using CDTIs may be attributable to inherent ambiguities in 3-D perspective displays and/or a limited range of conflict geometries. METHODS: Pilots resolved predicted conflicts using CDTIs with three levels of display dimensionality; the first had two 2-D orthogonal views, the second depicted the airspace in two alternating 3-D perspective views, and the third had a pilot-controlled swiveling viewpoint. RESULTS: Pilots demonstrated the same preferences that have been observed in previous research for vertical over lateral maneuvers in low workload and climbs over descents for level-flight conflicts. With increasing workload the two 3-D perspective displays, but not the 2-D displays, resulted in an increased preference for lateral over vertical maneuvers. Increased time pressure resulted in increased vertical maneuvers, an effect again limited to the two 3-D perspective displays. CONCLUSION: Resolution preferences were more affected by workload and time pressure when the 3-D perspective displays were used, as compared with the 2-D displays, although overall preferences were milder than in previous studies. APPLICATION: Investigating maneuver preferences using the strategic flight planning paradigm employed in this study may be the key to better ensure pilot acceptance of computer-generated resolution maneuvers.     

Detecting Web requirements conflicts and inconsistencies under a model-based perspective

Web requirements engineering is an essential phase in the software project life cycle for the project results. This phase covers different activities and tasks that in many situations, depending on the analyst's experience or intuition, help getting accurate specifications. One of these tasks is the conciliation of requirements in projects with different groups of users. This article presents an approach for the systematic conciliation of requirements in big projects dealing with a model-based approach. The article presents a possible implementation of the approach in the context of the NDT (Navigational Development Techniques) Methodology and shows the empirical evaluation in a real project by analysing the improvements obtained with our approach. The paper presents interesting results that demonstrate that we can get a reduction in the time required to find conflicts between requirements, which implies a reduction in the global development costs.     

System support for exploration and expert feedback in resolving conflicts during integration of metadata

A critical reality in integration is that knowledge obtained from different sources may often be conflicting. Conflict-resolution, whether performed during the design phase or during run-time, can be costly and, if done without a proper understanding of the usage context, can be ineffective. In this paper, we propose a novel exploration and feedback-based approach [FICSR (Pronounced as “fixer”)] to conflict-resolution when integrating metadata from different sources. Rather than relying on purely automated conflict-resolution mechanisms, FICSR brings the domain expert in the conflict-resolution process and informs the integration based on the expert’s feedback. In particular, instead of relying on traditional model based definition of consistency (which, whenever there are conflicts, picks a possible world among many), we introduce a ranked interpretation of the metadata and statements about the metadata. This not only enables FICSR to avoid committing to an interpretation too early, but also helps in achieving a more direct correspondence between the experts’ (subjective) interpretation of the data and the system’s (objective) treatment of the available alternatives. Consequently, the ranked interpretation leads to new opportunities for exploratory feedback for conflict-resolution: within the context of a given statement of interest, (a) a preliminary ranking of candidate matches, representing different resolutions of the conflicts, informs the user about the alternative interpretations of the metadata, while (b) user feedback regarding the preferences among alternatives is exploited to inform the system about the expert’s relevant domain knowledge. The expert’s feedback, then, is used for resolving not only the conflicts among different sources, but also possible mis-alignments due to the initial matching phase. To enable this feedback process, we develop data structures and algorithms for efficient off-line conflict/agreement analysis of the integrated metadata. We also develop algorithms for efficient on-line query processing, candidate result enumeration, validity analysis, and system feedback. The results are brought together and evaluated in the Feedback-based InConSistency Resolution (FICSR) system. This research has been funded with NSF Grant, AOC: Archaeological Data Integration for the Study of Long-Term Human and Social Dynamics, 2007–2009. This work was done while the M. L. Sapino was at ASU for sabbatical.     

Fast decentralized algorithms for resolving conflicts and deadlocks in resource allocation in data processing and control systems

We give efficient algorithms for resolving conflicts and deadlocks in resource allocation for multiprocessor and multicomputer real time systems based on the methods of combining computations and data transmission. We develop a way technique of decentralized self-organization of communication channels that allows to dynamically restructure the system in order to enhance the quality of deadlock resolution.     

Semantic conflict resolution ontology (SCROL): an ontology for detecting and resolving data and schema-level semantic conflicts

Establishing semantic interoperability among heterogeneous information sources has been a critical issue in the database community for the past two decades. Despite the critical importance, current approaches to semantic interoperability of heterogeneous databases have not been sufficiently effective. We propose a common ontology called semantic conflict resolution ontology (SCROL) that addresses the inherent difficulties in the conventional approaches, i.e., federated schema and domain ontology approaches. SCROL provides a systematic method for automatically detecting and resolving various semantic conflicts in heterogeneous databases. SCROL provides a dynamic mechanism of comparing and manipulating contextual knowledge of each information source, which is useful in achieving semantic interoperability among heterogeneous databases. We show how SCROL is used for detecting and resolving semantic conflicts between semantically equivalent schema and data elements. In addition, we present evaluation results to show that SCROL can be successfully used to automate the process of identifying and resolving semantic conflicts.     

Context, situations, and design agents

The terms “context” and “situation” are often used interchangeably or to denote a variety of concepts. This paper aims to show that these are two different but related concepts and it reifies their difference within the framework of design agents. The external world of an agent is described as the aggregation of all entities that the agent could possibly sense or effect, where context is from its external world that an agent interacts with and is aware of. The interpreted world of an agent is described in terms of the experiences of that agent, where situations are processes that direct how interactive experiences proceed. Situations determine what part of the external world are in the current context, and situations influence interaction and so influence what and how common ground is acquired.     

Looking at human–computer interface design: Effects of ethnicity in computer agents

This paper presents empirical research findings that identify demonstrated attitude changes in computer users associated with their receiving advice from personified computer agents of two different ethnicities: African American and European American. Our findings indicate that computer users are more likely to change their actions (demonstrating underlying attitudes) based on input from a computer agent whose ethnicity is similar to theirs. These findings directly impact computer agent design in many fields.     

Behavior patterns emerging among mobile robots with a diversity of personalities cooperating in collection and cleaning-up tasks

We investigated the behavior patterns emerging among autonomous mobile robots with diverse personalities. They cooperate with one another in collection and cleaning-up tasks. First, we emphasize the rationale for introducing personalities into robots. Second, we present our assumptions on the common functions of the robots, i.e., visual functions, mobility, and the capturing and conveying of target objects. Third, we define a function which is specific to each robot; its personality. Fourth, we explain the collision avoidance behavior, which is very dependent on the personalities. Finally, we present the results of simulation studies of robots with diverse personalities cooperating in collection and cleaning-up tasks. We discuss the influence of the distribution of various personalities on the performance of the tasks. This work was presented in part at the Sixth International Symposium on Artificial Life and Robotics, Tokyo, January 15–17, 2001     

Two-time scale control and observer design for trajectory tracking of two cooperating robot manipulators moving a flexible beam

In this paper, we present two-time scale control design for trajectory tracking of two cooperating planar rigid robots moving a flexible beam, which does not require vibration measurement for the beam. First, the kinematics and dynamics of the robots and the object are derived. Then, using the relations between different forces acting on the object by the manipulators’ end-effectors, dynamics equations of the robots and the object are combined. The resulting equations show that the coupled dynamics including beam vibration and the rigid motion take place in two different time domains. By applying two-time scale control theory on the combined dynamics, a composite control scheme is elaborated which makes the beam orientation and its center of mass position track a desired trajectory while suppressing the beam vibration. For the controller algorithm, first a slow controller is utilized for the slow (rigid) subsystem and then a fast stabilizing controller is considered for the fast (flexible) subsystem. To avoid requiring measurement of beam vibration for the fast control law, a linear observer is also designed. The simulation results show the efficiency of the proposed control scheme.     

Constructive difference and disagreement: A suprA-cooperation among agents

Differences among agents may be constructive in so far as they can bring solution enhancements or conflicts, the second case leading to solution modifications. What is dealt with in this paper is a cooperation involving different rational agents resulting in more than a mere addition of the agents' individual skills, thanks to a process of approval and refutation of the current solution. Lakatos' work is taken as a basis and adapted to a set of cooperating agents, so as to define the concept of supfA-cooperation and the corresponding interaction model. Three case studies are given, involving SuprA-cooperating human or artificial agents.     

Relationships between obligations and actions in the context of institutional agents, human agents or software agents

The paper presents a logical framework for the representation of interactions between institutional agents, human agents and software agents. A case study is used to analyze how obligations on institutional agents are ??propagated?? to human and software agents, and how actions performed by these agents count as actions that satisfy the obligations imposed to institutional agents. It is shown that the relationship between the different kinds of obligations and actions can be represented in terms of the concept of ??count as?? proposed by Searle, of role and of causality. The logical framework focus on those three concepts.     

Layering and heterogeneity as design principles for animated embedded agents

Animation of three-dimensional digital characters is still a major hurdle in the production of films and video games. This paper analyzes the technology of autonomous embedded agents as a solution to this challenge. Multi-layering and heterogeneity are chosen as desirable principles for the design of digital characters. The FreeWill+ animation framework has been developed with these principles in mind. Its general structure as well as some of its special features are presented. Automatic action acquisition based on the Q-learning technique has been presented as an extended example of the system capabilities.     

Preliminary design and manufacturing planning integration using web-based intelligent agents

Software agents have been increasingly used in the product and process development in industry over the past years due to the rapid evolvement of the Internet technology. This paper describes agents for the integration of conceptual design and process planning. Agents provide mechanisms to interact with each other. This mechanism is important since both of those processes involve negotiations for optimization. A set of design and planning software agents has been developed. These agents are used in a computer-based collaborative environment, called a multi-agent platform. The main purpose of developing such a platform is to support product preliminary design, optimize product form and structure, and reduce the manufacturing cost in the early design stage. The agents on the platform have access to a knowledge base that contains design and planning rules. These rules are derived from an analysis of design factors that influence process and resource planning, such as product material, form, shape complexity, features, dimension, tolerance, surface condition, production volume, and production rate. These rules are used by process planning agents to provide process planners with information regarding selecting preliminary manufacturing processes, determining manufacturing resources, and constructing feedback information to product designers. Additionally, the agents communicate with WEB servers, and they are accessible by users through Internet browsers. During performing design and planning tasks, agents access the data pertinent to design and manufacturing processes by the programming interfaces of existing computer-aided design (CAD) and manufacturing system. The agents are supported by a developed prototype agent platform. The agents and the platform enable the information exchange among agents, based on a previously developed integrated design and manufacturing process object model.     

Issues and approaches in the design of collective autonomous agents

The problem of synthesizing and analyzing collective autonomous agents has only recently begun to be practically studied by the robotics community. This paper overviews the most prominent directions of research, defines key terms, and summarizes the main issues. Finally, it briefly describes our approach to controlling group behavior and its relation to the field as a whole.