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.
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.
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.
10197051
Dynamic service matchmaking among agents in open information environments
The amount of services and deployed software agents in the most famous o spring of the Internet, the World Wide Web, is exponentially increasing. In addition, the Internet is an open environment, where information sources, communication links and agents themselves may appear and disappear unpredictably. Thus, an e ective, automated search and selection of relevant services or agents is essential for human users and agents as well. We distinguish three general agent categories in the Cyberspace, service providers, service requester, and middle agents. Service providers provide some type of service, such as nding information, or performing some particular domain speci c problem solving. Requester agents need provider agents to perform some service for them. Agents that help locate others are called middle agents[2]. Matchmaking is the process of nding an appropriate provider for a requester through a middle agent, and has the following general form: (1) Provider agents advertise their capabilities to middle agents, (2) middle agents store these advertisements, (3) a requester asks some middle agent whether it knows of providers with desired capabilities, and (4) the middle agent matches the request against the stored advertisements and returns the result, a subset of the stored advertisements. While this process at rst glance seems very simple, it is complicated by the fact that not only local information sources but even providers and requesters in the Cyberspace are usually heterogeneous and incapable of understanding each other.
9632017
Bayesian learning in negotiation
Negotiation has been extensively discussed in game-theoretic, economic and management science literatures for decades. Recent growing interest in autonomous interacting software agents and their potential application in areas such as electronic commerce has give increased importance to automated negotiation. Evidence both from theoretical analysis and from observations of human interactions suggests that if decision makers can somehow take into consideration what other agents are thinking and furthermore learn during their interactions how other agents behave, their payoff might increase. In this paper, we propose a sequential decision-making model of negotiation, called Bazaar. It provides an adaptive, multi-issue negotiation model capable of exhibiting a rich set of negotiation behaviors. Within the proposed negotiation framework, we model learning as a Bayesian belief update process. In this paper, we present both theoretical analysis and initial experimental results showing that learning is beneficial in the sequential negotiation model.
440209
Benefits of Learning in Negotiation
Negotiation has been extensively discussed in game-theoretic, economic, and management science literatures for decades. Recent growing interest in electronic commerce has given increased importance to automated negotiation. Evidence both from theoretical analysis and from observations of human interactions suggests that if decision makers can somehow take into consideration what other agents are thinking and furthermore learn during their interactions how other agents behave, their payoff might increase. In this paper, we propose a sequential decision making model of negotiation, called Bazaar. Within the proposed negotiation framework, we model learning as a Bayesian belief update process. In this paper, we explore the hypothesis that learning is beneficial in sequential negotiation and present initial experimental results.
2720113
Backtracking Techniques for the Job Shop Scheduling Constraint Satisfaction Problem
Abstract This paper studies a version of the job shop scheduling problem in which some operations have to be scheduled within non-relaxable time windows (i.e. earliest/latest possible start time windows). This problem is a well-known NP-complete Constraint Satisfaction Problem (CSP). A popular method for solving this type of problems involves using depth-first backtrack search. In our earlier work, we focused on the development of consistency enforcing techniques and variable/value ordering heuristics that improve the efficiency of this search procedure. In this paper, we combine these techniques with new look-back schemes that help the search procedure recover from so-called deadend search states (i.e. partial solutions that cannot be completed without violating some constraints). More specifically, we successively describe three “intelligent” backtracking schemes: (1) Dynamic Consistency Enforcement dynamically identifies critical subproblems and determines how far to backtrack by selectively enforcing higher levels of consistency among variables participating in these critical subproblems, (2) Learning Ordering From Failure dynamically modifies the order in which variables are instantiated based on earlier conflicts, and (3) Incomplete Backjumping Heuristic abandons areas of the search space that appear to require excessive computational efforts. These schemes are shown to (1) further reduce the average complexity of the backtrack search procedure, (2) enable our system to efficiently solve problems that could not be solved otherwise due to excessive computation cost, and (3) be more effective at solving job shop scheduling problems than other look-back schemes advocated in the literature.