11049649
Resource allocation in distributed factory scheduling
A distributed factory scheduling model that is based on the concept of constraint-directed search within a centralized framework is presented. A set of texture measures that quantify several characteristics of the problem space being searched has been developed into heuristics that direct the searches conducted by scheduling agents. The heuristics have been used to direct the searches of a centralized activity-based scheduler, achieving good schedule quality and minimizing the likelihood of backtracking. The model discussed uses textures to direct distributed scheduling, optimizing decisions in the global search space by allowing agents to focus and direct searches in their individual search spaces. Experimental results are presented and confirm the effectiveness of the approach.<<ETX>>
53957
Exploiting Problem Structure for Distributed Constraint Optimization
Distributed constraint optimization imposes considerable complexity in agents’ coordinated search for an optimal solution. However, in many application domains, problems often exhibit special structures that can be exploited to facilitate more efficient problem solving. One of the most recurrent structures involves disparity among subpmblems. We present a coordination mechanism, Anchor&Ascend, for distributed constraint optimization that takes advantage of disparity among subpmblems to efficiently guide distributed local search for global optimality. The coordination mechanism assigns different overlapping subpmblems to agents who must interact and iteratively converge on a solution. In particular, an anchor agent who conducts local best first search to optimize its subsolution interacts with the rest of the agents who perform distributed constraint satisfaction to enforce problem constraints and constraints imposed by the anchor agent. We focus our study on the well-known NP-complete job shop scheduling problem. We define and study two problem structure measures, disparity ratio and disparity composition ratio. We experimentally evaluated the effectiveness of the Anchor&Ascend mechanism on a suite of job shop scheduling problems over a wide range of values of disparity composition. Our experimental results show that (1) considerable advantage can be obtained by explicitly exploiting disparity (2) disparity composition ratio plays a more important role than disparity ratio in finding high quality solution with little computational cost.
1816609
DAML-S: Semantic Markup for Web Services
The Semantic Web should enable greater access not only to content but also to services on the Web. Users and software agents should be able to discover, invoke, compose, and monitor Web resources offering particular services and having particular properties. As part of the DARPA Agent Markup Language program, we have begun to develop an ontology of services, called DAML-S, that will make these functionalities possible. In this paper we describe the overall structure of the ontology, the service profile for advertising services, and the process model for the detailed description of the operation of services. We also compare DAML-S with several industry efforts to define standards for characterizing services on the Web.
2588941
Browsing Schedules - An Agent-Based Approach to Navigating the Semantic Web
The Semantic Web promises to change the way agents navigate, harvest and utilize information on the internet. By providing a structured, distributed representation for expressing concepts and relationships defined by multiple ontologies, it is now possible for agents to read and reason about published knowledge, without the need for scrapers, information agents, and centralized ontologies. Agents can utilize this knowledge to seek and invoke other agents and web services, thus supporting navigation across the Semantic Web. We demonstrate how agents support enhanced navigation within a conference-schedule domain, and present three agent-based services: the RETSINA Calendar Agent, which reasons about schedules marked up on the Semantic Web; the DMA2ICal Translation Agent which provides translation services between schedules grounded in different ontologies, and a Conference Agent that invokes the Calendar Agent.
8965477
Configuration management for multi-agent systems
As heterogeneous distributed systems, multi-agent systems present some challenging configuration management issues. There are the problems of knowing how to allocate agents to computers, launch them on remote hosts, and once the agents have been launched, how to monitor their runtime status so as to manage computing resources effectively.
In this paper, we present the RETSINA Configuration Manager, \emph{RECoMa}. We describe its architecture, how it uses agent infrastructure such as service discovery, to assist the multi-agent system administrator in allocating, launching, and monitoring a heterogeneous distributed agent system in a distributed and networked computing environment.\footnote{The authors would like to acknowledge the significant contributions of Matthew W. Easterday in his earlier and exhaustive implementations of configuration management programs and CM design proposals. This research has been sponsored in part by DARPA Grant F-30602-98-2-0138 and the Office of Naval Research Grant N-00014-96-16-1-1222.}
31490698
Cloning for Intelligent Adaptive Information Agents
Adaptation in open, multi-agent information gathering systems is important for several reasons. These reasons include the inability to accurately predict future problem-solving workloads, future changes in existing information requests, future failures and additions of agents and data supply resources, and other future task environment characteristic changes that require system reorganization. We are developing a multi-agent financial portfolio management system that must deal with all of these problems. This paper will briefly describe our approaches and solutions at several different levels within the agents: adaptation at the organizational, planning, scheduling, and execution levels. We discuss our solution for execution-level adaptation (“cloning”) in detail, and present empirical evidence backing up the theory behind this execution-level solution.
2746951
Cost-Sensitive Access Control for Illegitimate Confidential Access by Insiders
In many organizations, it is common to control access to confidential information based on the need-to-know principle; The requests for access are authorized only if the content of the requested information is relevant to the requester’s current information analysis project. We formulate such content-based authorization, i.e. whether to accept or reject access requests as a binary classification problem. In contrast to the conventional error-minimizing classification, we handle this problem in a cost-sensitive learning framework in which the cost caused by incorrect decision is different according to the relative importance of the requested information. In particular, the cost (i.e., damaging effect) for a false positive (i.e., accepting an illegitimate request) is more expensive than that of false negative (i.e., rejecting a valid request). The former is a serious security problem because confidential information, which should not be revealed, can be accessed. From the comparison of the cost-sensitive classifiers with error-minimizing classifiers, we found that the costing with a logistic regression showed the best performance, in terms of the smallest cost paid, the lowest false positive rate, and the relatively low false negative rate.
13216385
Multiagent Systems
Agent-based systems technology has generated lots of excitement in recent years because of its promise as a new paradigm for conceptualizing, designing, and implementing software systems. This promise is particularly attractive for creating software that operates in environments that are distributed and open, such as the internet Currently, the great majority of agent-based systems consist of a single agent However as the technology matures and addresses increasingly complex applications, the need for systems that consist of multiple agents that communicate in a peer-to-peer fashion is becoming apparent. Central to the design and effective operation of such multiagent systems (MASs) are a core set of issues and research questions that have been studied over the years by the distributed AI community. In this article, I present some of the critical notions in MASs and the research work that has addressed themI organize these notions around the concept of problem-solving coherence, which I believe is one of the most critical overall characteristics that an MAS should exhibit
11307805
A constraint optimization framework for fractured robot teams
In dangerous and uncertain environments initial plans must be revised. Communication failures hamper this replanning. We introduce fractured subteams as a novel formalism for modeling breakdowns in communication. We present a hybrid approach that employs distributed coordination mechanisms to provide robustness to these communication breakdowns and exploits opportunistic centralization. By modeling the problem as a mixed integer linear programming problem, we are able to apply constraint optimization techniques to efficiently find optimal or near optimal solutions to the difficult class of time critical tight coordination team planning problems. We then demonstrate that explicitly reasoning about communication failures through the incorporation of selective disruption minimization can improve team performance.
2246359
Simultaneous Team Assignment and Behavior Recognition from Spatio-Temporal Agent Traces
This paper addresses the problem of activity recognition for physically-embodied agent teams. We define team activity recognition as the process of identifying team behaviors from traces of agent positions over time; for many physical domains, military or athletic, coordinated team behaviors create distinctive spatio-temporal patterns that can be used to identify low-level action sequences. This paper focuses on the novel problem of recovering agent-to-team assignments for complex team tasks where team composition, the mapping of agents into teams, changes over time. Without a priori knowledge of current team assignments, the behavior recognition problem is challenging since behaviors are characterized by the aggregate motion of the entire team and cannot generally be determined by observing the movements of a single agent in isolation. To handle this problem, we introduce a new algorithm, Simultaneous Team Assignment and Behavior Recognition (STABR), that generates behavior annotations from spatio-temporal agent traces. The proposed approach is able to perform accurate team behavior recognition without an exhaustive search over the combinatorial space of potential team assignments, as demonstrated on several scenarios of simulated military maneuvers.