10504344
The adaptive agent architecture: achieving fault-tolerance using persistent broker teams
Brokered multi-agent systems can be incapacitated and rendered non-functional when the brokers become inaccessible due to failures that can occur in any distributed software system. We propose that the theory of teamwork can be used to specify robust brokered architectures that can recover from broker failures, and we present the adaptive agent architecture (AAA) to show the feasibility of this approach. The previous teamwork theory based on joint intentions assumes that team members remain in a team as long as the team exists. We extend this theory to allow dynamic broker teams whose members can change with time. We also introduce a theory of restorative maintenance goals that enables the brokers in an AAA broker team to start new brokers and recruit them to the broker team. As a result, an AAA-based multi-agent system can maintain a specified number of functional brokers in the system despite broker failures, thus effectively becoming a self-healing system.
9907384
Integrating Joint Intention Theory, Belief Reasoning, and Communicative Action for Generating Team-Oriented Dialogue
The goal of this research is to develop an architecture that can guide an agent during collaborative teamwork. The architecture should generate communication and dialogue during the performance of collaborative multi-agent tasks as a byproduct of the agent's rationally pursuing its intentions. This paper describes how a joint intention interpreter that is integrated with a reasoner over beliefs and communicative acts can form the core of a dialogue engine. As an interpreter of joint actions, the architecture enables agent programmers to describe a domain declaratively, specifying an agent's individual and joint intentions, plans and actions at a high level. The interpreter attempts to fulfill the agent's individual and joint intentions, subject to its beliefs and mutual beliefs. As a consequence, the system engages in dialogue through the planning and execution of communicative acts necessary to attain the collaborative task at hand. The dialogue engine is general enough to be applicable to both agent-agent and agent-human teams. The system has been implemented in a combination of Java and Prolog, and can be shown to obey the predictions of joint intention.
13307472
Direct execution of team specifications in STAPLE
Formal theories of teamwork are typically treated as software design specifications of team behavior. We take a different approach to programming teamwork by directly executing logical specifications of joint commitment and joint intention. This approach leads to a domain-independent framework for programming teamwork where one can modify (or add new) behavior for a team of agents just by modifying (or adding) logical sentences. One may also be able to predict the behavior of an agent team offline using its team intention specification and verify it by running the actual system.
15419677
STAPLE: An agent programming language based on the joint intention theory
Joint intention theory has been used for rule based creation of teams and to provide a formal semantics for communicative acts but there were no agent programming languages linked to this theory. We proposed a declarative agent programming language called STAPLE whose logical semantics is given by the joint intention theory. This paper illustrates the STAPLE support for communication and teamwork in a unified framework.
17321819
Toward A Formalism for Conversation Protocols Using Joint Intention Theory
Conversation protocols are meant to achieve certain tasks or to bring about certain state of affairs in the world. Therefore, one may identify the landmarks or the state of affairs that must be brought about during the execution of a protocol in order to achieve its goal. Accordingly, the most important aspect of protocols is these landmarks rather than the communicative actions needed to achieve the landmarks. We show that families of conversation protocols can be expressed formally as partially ordered landmarks where each landmark is characterized by propositions that are true in the state represented by that landmark. Dialogue in natural languages is regarded as joint activity. Conversation protocols in multi-agent systems are treated as dialogue templates and are composed using speech acts from natural language dialogues. As such, we treat conversation protocols as joint action expressions and gainfully apply existing formal theories of dialogue, specifically the Joint Intention Theory, to protocols and their compositions. Conversation protocols may require agents to communicate with groups as well as individuals. However, most contemporary agent communication languages, notably FIPA and KQML, have either no provision or no well-defined semantics for group communication. Furthermore, the research on protocols so far does not correctlymore » incorporate groups into the protocols. We give a formal semantics to group communicative acts and use it to handle group communication in a formal treatment of protocols.« less
3185097
Towards a fault-tolerant multi-agent system architecture
Multi-agent systems are prone to failures typical of any distributed system. Agents and resources may become unavailable due to machine crashes, communication breakdowns, process failures, and numerous other hardware and software failures. Most of the work done in fault handling in multi-agent systems deals with detection and recovery from faults such as state-inconsistencies, relying on the traditional techniques for recovering from other distributed systems failure. However, the traditional fault-tolerance techniques are designed for specific situations and they require special infrastructural support. We argue for fault-tolerance techniques that can be readily implemented using a generic agent shell with minimal or no modification to the agent infrastructure. We propose that theories from multi-agent systems literature can be effectively combined with basic fault-tolerance principles to design robust multi-agent systems. In particular, we argue that (1) teamwork may be used to create a robust brokered architecture that can recover a multi-agent system from broker failures without incurring undue overheads, (2) teamwork may also be used to guarantee a specified number of brokers in a large multi-agent system, and (3) agent autonomy can be used to prevent thrashing and guarantee acceptable levels of quality of service by an agent. We also describe the Adaptive Agent Architecture (AAA), a fault-tolerant brokered multi-agent system architecture, and present experimental evidence using the AAA to validate our approach.
10689850
Discriminative random fields: a discriminative framework for contextual interaction in classification
In this work we present discriminative random fields (DRFs), a discriminative framework for the classification of image regions by incorporating neighborhood interactions in the labels as well as the observed data. The discriminative random fields offer several advantages over the conventional Markov random field (MRF) framework. First, the DRFs allow to relax the strong assumption of conditional independence of the observed data generally used in the MRF framework for tractability. This assumption is too restrictive for a large number of applications in vision. Second, the DRFs derive their classification power by exploiting the probabilistic discriminative models instead of the generative models used in the MRF framework. Finally, all the parameters in the DRF model are estimated simultaneously from the training data unlike the MRF framework where likelihood parameters are usually learned separately from the field parameters. We illustrate the advantages of the DRFs over the MRF framework in an application of man-made structure detection in natural images taken from the Corel database.
13984585
A novel progressive thick slab paradigm for volumetric medical image compression and navigation
In this paper, we propose a novel thick slab paradigm which provides an efficient scheme to navigate through large three dimensional (3-D) medical data sets within the framework of wavelet based lossless volumetric compression. We also propose a 3-D wavelet-like multi-resolution decomposition to perform 3-D image compression, which provides better compression ratio and 3 times faster decoding than JPEG-2000 for large data sets of computed tomography modality, along with a clinical workflow for navigation application. The proposed method suits radiology applications better than JPEG-2000 as it improves the productivity of radiologists by reducing their waiting time while the data is being transferred from a remote database over the network, along with reduction in diagnosis time, by providing an efficient navigation scheme with high compression performance.
882
A combinatorial approach for studying LOCC transformations of multipartite states
We develop graph theoretic methods for analysing maximally entangled pure states distributed between a number of different parties. We introduce a technique called {\it bicolored merging}, based on the monotonicity feature of entanglement measures, for determining combinatorial conditions that must be satisfied for any two distinct multiparticle states to be comparable under local operations and classical communication (LOCC). We present several results based on the possibility or impossibility of comparability of pure multipartite states. We show that there are exponentially many such entangled multipartite states among $n$ agents. Further, we discuss a new graph theoretic metric on a class of multi-partite states, and its implications.
5723404
Dynamic tracking of page miss ratio curve for memory management
Memory can be efficiently utilized if the dynamic memory demands of applications can be determined and analyzed at run-time. The page miss ratio curve(MRC), i.e. page miss rate vs. memory size curve, is a good performance-directed metric to serve this purpose. However, dynamically tracking MRC at run time is challenging in systems with virtual memory because not every memory reference passes through the operating system (OS).This paper proposes two methods to dynamically track MRC of applications at run time. The first method is using a hardware MRC monitor that can track MRC at fine time granularity. Our simulation results show that this monitor has negligible performance and energy overheads. The second method is an OS-only implementation that can track MRC at coarse time granularity. Our implementation results on Linux show that it adds only 7--10% overhead.We have also used the dynamic MRC to guide both memory allocation for multiprogramming systems and memory energy management. Our real system experiments on Linux with applications including Apache Web Server show that the MRC-directed memory allocation can speed up the applications' execution/response time by up to a factor of 5.86 and reduce the number of page faults by up to 63.1%. Our execution-driven simulation results with SPEC2000 benchmarks show that the MRC-directed memory energy management can improve the Energy * Delay metric by 27--58% over previously proposed static and dynamic schemes.
29916406
Scheduling advertisements on a web page to maximize revenue
Many web sites (e.g. Hotmail, Yahoo) provide free services to the users while generating revenues from advertising. Advertising revenue is, therefore, critical for these sites. This in turn raises the question, how should advertisements at a web site be scheduled in a planning horizon to maximize revenue. Advertisements on the web are specified by geometry and display frequency and both of these factors need to be considered in developing a solution to the advertisement scheduling problem. Since this problem belongs to the class of NP-hard problems, we first develop a heuristic called LSMF to solve the problem. This heuristic is then combined with a genetic algorithm (GA) to develop a hybrid GA. The hybrid GA solution is first compared with the upper bound obtained by running CPLEX for the integer programming formulation of the problem. It is then also compared with an existing algorithm proposed in the literature. Our computational results show that the hybrid GA performs exceptionally well in the sense that it provides optimal or near optimal solution for a wide range of problem instances of realistic sizes and the improvements over existing algorithm are substantial. Finally we present a case study to illustrate how revenue could be significantly increased with a small improvement in the advertisement schedule. It is the first such study in this setup.