Arrow Research search

Author name cluster

Victor Lesser

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

59 papers
1 author row

Possible papers

59

JAAMAS Journal 2026 Journal Article

Domain Monotonicity and the Performance of Local Solutions Strategies for CDPS-based Distributed Sensor Interpretation and Distributed Diagnosis

  • Norman Carver
  • Victor Lesser

Abstract The growth in computer networks has created the potential to harness a great deal of computing power, but new models of distributed computing are often required. Cooperative distributed problem solving (CDPS) is the subfield of multi-agent systems (MAS) that is concerned with how large-scale problems can be solved using a network of intelligent agents working together. Building CDPS systems for real-world applications is still very difficult, however, in large part because the effects that domain and strategy characteristics have on the performance of CDPS systems are not well understood. This paper reports on the first results from a new simulation-based analysis system that has been created to study the performance of CDPS-based distributed sensor interpretation (DSI) and distributed diagnosis (DD). To demonstrate the kind of results that can be obtained, we have investigated how the monotonicity of a domain affects the performance of a potentially very efficient class of strategies for CDPS-based DSI/DD. Local solutions strategies attempt to limit communications among the agents by focusing on using the agents' local solutions to produce global solutions. While these strategies have been described as being important for effective CDPS-based DSI/DD, they need not perform well if a domain is nonmonotonic. We had previously suggested that the reason they have performed well in several research systems was that many DSI/DD domains are what we termed nearly monotonic. In this paper, we will provide quantitative results that relate the performance of local solutions strategies to the monotonicity of a domain. The experiments confirm that domain monotonicity can be important to consider, but they also show that it is possible for these strategies to be effective even when domains are relatively nonmonotonic. What is required is that the agents receive a significant fraction of the data that is relevant to their subproblems. This has important implications for the design of DSI/DD systems using local solutions strategies. In addition, while the work indicates that many DSI/DD domains are likely to be “nearly monotonic” according to our original definitions, it also shows that these measures are not as predictive of performance as other measures we define. This means that near monotonicity alone does not explain why local solutions strategies have performed well in previous systems. Instead, a likely explanation is that these systems typically involved only a small number of agents.

Details DOI

JAAMAS Journal 2026 Journal Article

Efficient Management of Multi-Linked Negotiation Based on a Formalized Model

  • Xiaoqin Zhang
  • Victor Lesser
  • Sherief Abdallah

abstract A Multi-linked negotiation problem occurs when an agent needs to negotiate with multiple other agents about different subjects (tasks, conflicts, or resource requirements), and the negotiation over one subject has influence on negotiations over other subjects. The solution of the multi-linked negotiations problem will become increasingly important for the next generation of advanced multi-agent systems. However, most current negotiation research looks only at a single negotiation and thus does not present techniques to manage and reason about multi-linked negotiations. In this paper, we first present a technique based on the use of a partial-order schedule and a measure of the schedule, called flexibility, which enables an agent to reason explicitly about the interactions among multiple negotiations. Next, we introduce a formalized model of the multi-linked negotiation problem. Based on this model, a heuristic search algorithm is developed for finding a near-optimal ordering of negotiation issues and their parameters. Using this algorithm, an agent can evaluate and compare different negotiation approaches and choose the best one. We show how an agent uses this technology to effectively manage interacting negotiation issues. Experimental work is presented which shows the efficiency of this approach.

Details DOI

JAAMAS Journal 2026 Journal Article

Multi-Dimensional, MultiStep Negotiation

  • Xiaoqin Zhang
  • Victor Lesser
  • Rodion Podorozhny

Abstract We present a multi-dimensional, multi-step negotiation mechanism for task allocation among cooperative agents based on distributed search. This mechanism uses marginal utility gain and marginal utility cost to structure this search process, so as to find a solution that maximizes the agents’ combined utility. These two utility values together with temporal constraints summarize the agents’ local information and reduce the communication load. This mechanism is anytime in character: by investing more time, the agents increase the likelihood of getting a better solution. We also introduce a multiple attribute utility function into negotiations. This allows agents to negotiate over the multiple attributes of the commitment, which produces more options, making it more likely for agents to find a solution that increases the global utility. A set of protocols are constructed and the experimental result shows a phase transition phenomenon as the complexity of negotiation situation changes. A measure of negotiation complexity is developed that can be used by an agent to choose an appropriate protocol, allowing the agents to explicitly balance the gain from the negotiation and the resource usage of the negotiation.

Details DOI

AAMAS Conference 2017 Conference Paper

Context-Based Concurrent Experience Sharing in Multiagent Systems

  • Dan Garant
  • Bruno C. da Silva
  • Victor Lesser
  • Chongjie Zhang

One of the key challenges for multi-agent learning is scalability. We introduce a technique for speeding up multi-agent learning by exploiting concurrent and incremental experience sharing. This solution adaptively identifies opportunities to transfer experiences between agents and allows for the rapid acquisition of appropriate policies in large-scale, stochastic, multi-agent systems. We introduce an online, supervisor-directed transfer technique for constructing high-level characterizations of an agent’s dynamic learning environment—called contexts—which are used to identify groups of agents operating under approximately similar dynamics within a short temporal window. Supervisory agents compute contextual information for groups of subordinate agents, thereby identifying candidates for experience sharing. We show that our approach results in significant performance gains, that it is robust to noise-corrupted or suboptimal context features, and that communication costs scale linearly with the supervisor-to-subordinate ratio.

PDF

AAAI Conference 2014 Conference Paper

DJAO: A Communication-Constrained DCOP Algorithm that Combines Features of ADOPT and Action-GDL

  • Yoonheui Kim
  • Victor Lesser

In this paper we propose a novel DCOP algorithm, called DJAO, that is able to efficiently find a solution with low communication overhead; this algorithm can be used for optimal and bounded approximate solutions by appropriately setting the error bounds. Our approach builds on distributed junction trees used in Action-GDL to represent independence relations among variables. We construct an AND/OR search space based on these junction trees. This new type of search space results in higher degrees for each OR node, consequently yielding a more efficient search graph in the distributed settings. DJAO uses a branch-and-bound search algorithm to distributedly find solutions within this search graph. We introduce heuristics to compute the upper and lower bound estimates that the search starts with, which is integral to our approach for reducing communication overhead. We empirically evaluate our approach in various settings.

PDF Details

TIST Journal 2012 Journal Article

An Ensemble Architecture for Learning Complex Problem-Solving Techniques from Demonstration

  • Xiaoqin Shelley Zhang
  • Bhavesh Shrestha
  • Sungwook Yoon
  • Subbarao Kambhampati
  • Phillip DiBona
  • Jinhong K. Guo
  • Daniel McFarlane
  • Martin O. Hofmann

We present a novel ensemble architecture for learning problem-solving techniques from a very small number of expert solutions and demonstrate its effectiveness in a complex real-world domain. The key feature of our “Generalized Integrated Learning Architecture” (GILA) is a set of heterogeneous independent learning and reasoning (ILR) components, coordinated by a central meta-reasoning executive (MRE). The ILRs are weakly coupled in the sense that all coordination during learning and performance happens through the MRE. Each ILR learns independently from a small number of expert demonstrations of a complex task. During performance, each ILR proposes partial solutions to subproblems posed by the MRE, which are then selected from and pieced together by the MRE to produce a complete solution. The heterogeneity of the learner-reasoners allows both learning and problem solving to be more effective because their abilities and biases are complementary and synergistic. We describe the application of this novel learning and problem solving architecture to the domain of airspace management, where multiple requests for the use of airspaces need to be deconflicted, reconciled, and managed automatically. Formal evaluations show that our system performs as well as or better than humans after learning from the same training data. Furthermore, GILA outperforms any individual ILR run in isolation, thus demonstrating the power of the ensemble architecture for learning and problem solving.

Details DOI

JAAMAS Journal 2012 Journal Article

Bilateral bargaining with one-sided uncertain reserve prices

  • Bo An
  • Nicola Gatti
  • Victor Lesser

Abstract The problem of finding agents’ rational strategies in bargaining with incomplete information is well known to be challenging. The literature provides a collection of results for very narrow uncertainty settings, but no generally applicable algorithm. This lack has led researchers to develop heuristic approaches in an attempt to find outcomes that, even if not being of equilibrium, are mutually satisfactory. In the present paper, we focus on the principal bargaining protocol (i. e. , the alternating-offers protocol) where there is uncertainty regarding one agent’s reserve price. We provide an algorithm based on the combination of game theoretic analysis and search techniques which finds pure strategy sequential equilibria when they exist. Our approach is sound, complete and, in principle, can be applied to other uncertainty settings, e. g. , uncertain discount factors, and uncertain weights of negotiation issues in multi-issue negotiation. We experimentally evaluate our algorithm with a number of case studies showing that the average computational time is less than 30 s and at least one pure strategy equilibrium exists in almost all (about 99. 7 %) the bilateral bargaining scenarios we have looked at in the paper.

Details DOI

AAMAS Conference 2011 Conference Paper

Agent-Mediated Multi-Step Optimization for Resource Allocation in Distributed Sensor Networks

  • Bo An
  • Victor Lesser
  • David Westbrook
  • Michael Zink

Distributed collaborative adaptive sensing (DCAS) of the atmosphere is a new paradigm for detecting and predicting hazardous weather using a large dense network of short-range, low-powered radars to sense the lowest few kilometers of the earths atmosphere. In DCAS, radars are controlled by a collection of Meteorological Command and Control (MC&C) agents that instruct where to scan based on emerging weather conditions. Within this context, this work concentrates on designing efficient approaches for allocating sensing resources to cope with restricted real-time requirements and limited computational resources. We have developed a new approach based on explicit goals that can span multiple system heartbeats. This allows us to reason ahead about sensor allocations based on expected requirements of goals as they project forward in time. Each goal explicitly specifies end-users' preferences as well as a prediction of how a phenomena will move. We use a genetic algorithm to generate scanning strategies of each single MC&C and a distributed negotiation model to coordinate multiple MC&Cs' scanning strategies over multiple heartbeats. Simulation results show that as compared to simpler variants of our approach, the proposed distributed model achieved the highest social welfare. Our approach also has exhibited similarly very good performance in an operational radar testbed that is deployed in Oklahoma to observe severe weather events.

PDF

AAAI Conference 2011 Conference Paper

Coordinated Multi-Agent Reinforcement Learning in Networked Distributed POMDPs

  • Chongjie Zhang
  • Victor Lesser

In many multi-agent applications such as distributed sensor nets, a network of agents act collaboratively under uncertainty and local interactions. Networked Distributed POMDP (ND-POMDP) provides a framework to model such cooperative multi-agent decision making. Existing work on ND-POMDPs has focused on offline techniques that require accurate models, which are usually costly to obtain in practice. This paper presents a model-free, scalable learning approach that synthesizes multi-agent reinforcement learning (MARL) and distributed constraint optimization (DCOP). By exploiting structured interaction in ND-POMDPs, our approach distributes the learning of the joint policy and employs DCOP techniques to coordinate distributed learning to ensure the global learning performance. Our approach can learn a globally optimal policy for ND-POMDPs with a property called groupwise observability. Experimental results show that, with communication during learning and execution, our approach significantly outperforms the nearly-optimal non-communication policies computed offline.

PDF Details

AAMAS Conference 2011 Conference Paper

Effective Variants of Max-Sum Algorithm to Radar Coordination and Scheduling

  • Yoonheui Kim
  • Michael Krainin
  • Victor Lesser

This work proposes new techniques for saving communication and computational resources when solving distributed constraint optimization problems in an environment where system hardware resources are clustered. Using a pre-computed policy and two phase propagation on Max-Sum algorithm, the system performance on Radar scheduling problem improves in terms of communication and computation.

PDF

AAMAS Conference 2011 Conference Paper

Genetic Algorithm Aided Optimization of Hierarchical Multiagent System Organization

  • Ling Yu
  • Zhiqi Shen
  • Chunyan Miao
  • Victor Lesser

In this paper, we propose a genetic algorithm aided optimization scheme for designing the organization of hierarchical multiagent systems. We introduce the hierarchical genetic algorithm, in which hierarchical crossover with a repair strategy and mutation of small perturbation are used. The phenotypic hierarchical structure space is translated to the genome-like array representation space, which makes the algorithm genetic-operator-literate. Our experiments show that competitive structures can be found by the proposed algorithm. Compared with traditional operators, the new operators produced better organizations of higher utility more consistently. The proposed algorithm extends the search processes of the state-of-the-art multiagent organization design methodologies, and is more computationally efficient in a large search space.

PDF

AAMAS Conference 2011 Conference Paper

Negotiation Over Decommitment Penalty

  • Bo An
  • Victor Lesser

We consider the role of negotiation in deciding decommitment penalties. In our model, agents simultaneously negotiate over both the contract price and decommitment penalty in the contracting game and then decide whether to decommit from contracts in the decommitment game. Experimental results show that setting penalties through negotiation achieved higher social welfare than other exogenous penalty setting mechanisms.

PDF

AAMAS Conference 2010 Conference Paper

Automated Negotiation with Decommitment for Dynamic Resource Allocation in Cloud Computing

  • Bo An
  • Victor Lesser
  • David Irwin
  • Michael Zink

We consider the problem of allocating networked resources in dynamic environment, such as cloud computing platforms, where providers strategically price resources to maximize their utility. Resource allocation in these environments, where both providers and consumers are selfish agents, presents numerous challenges since the number of consumers and their resource demand is highly dynamic. While numerous auction-based approaches have been proposed in the literature, this paper explores an alternative approach where providers and consumers automatically negotiate resource leasing contracts. Since resource demand and supply can be dynamic and uncertain, we propose a distributed negotiation mechanism where agents negotiate over both a contract price and a decommitment penalty, which allows agents to decommit from contracts at a cost. We compare our approach experimentally, using representative scenarios and workloads, to both combinatorial auctions and the fixed-price model used by Amazon's Elastic Compute Cloud, and show that the negotiation model achieves a higher social welfare.

PDF

AAAI Conference 2010 Conference Paper

Multi-Agent Learning with Policy Prediction

  • Chongjie Zhang
  • Victor Lesser

Due to the non-stationary environment, learning in multi-agent systems is a challenging problem. This paper first introduces a new gradient-based learning algorithm, augmenting the basic gradient ascent approach with policy prediction. We prove that this augmentation results in a stronger notion of convergence than the basic gradient ascent, that is, strategies converge to a Nash equilibrium within a restricted class of iterated games. Motivated by this augmentation, we then propose a new practical multi-agent reinforcement learning (MARL) algorithm exploiting approximate policy prediction. Empirical results show that it converges faster and in a wider variety of situations than state-of-the-art MARL algorithms.

PDF Details

AAMAS Conference 2010 Conference Paper

Searching for Pure Strategy Equilibria in Bilateral Bargaining With One-sided Uncertainty

  • Bo An
  • Nicola Gatti
  • Victor Lesser

The problem of finding agents' rational strategies in bargaining with incomplete information is well known to be challenging. The literature provides a collection of results for very narrow uncertainty settings, but no generally applicable algorithm. In this paper, we focus on the alternating-offers finite horizon bargaining protocol with one-sided uncertainty regarding agents' reserve prices. We provide an algorithm based on the combination of game theoretic analysis and search techniques which finds agents' equilibrium in pure strategies when they exist. Our approach is sound, complete and, in principle, can be applied to other uncertainty settings.

PDF

AAMAS Conference 2010 Conference Paper

Self-Organization for Coordinating Decentralized Reinforcement Learning

  • Chongjie Zhang
  • Victor Lesser
  • Sherief Abdallah

Decentralized reinforcement learning (DRL) has been applied to a number of distributed applications. However, oneof the main challenges faced by DRL is its convergence. Previous work has shown that hierarchically organizational control is an effective way of coordinating DRL to improve itsspeed, quality, and likelihood of convergence. In this paper, we develop a distributed, negotiation-based approach todynamically forming such hierarchical organizations. To reduce the complexity of coordinating DRL, our self-organizationapproach groups strongly-interacting learning agents together, whose exploration strategies are coordinated by one supervisor. We formalize this idea by characterizing interactionsamong agents in a decentralized Markov Decision Processmodel and defining and analyzing a measure that explicitlycaptures the strength of such interactions. Experimental results show that our dynamically evolving organizations outperform predefined organizations for coordinating DRL.

PDF

JAAMAS Journal 2010 Journal Article

Strategic agents for multi-resource negotiation

  • Bo An
  • Victor Lesser
  • Kwang Mong Sim

Abstract In electronic commerce markets where selfish agents behave individually, agents often have to acquire multiple resources in order to accomplish a high level task with each resource acquisition requiring negotiations with multiple resource providers. Thus, it is crucial to efficiently coordinate these interrelated negotiations. This paper presents the design and implementation of agents that concurrently negotiate with other entities for acquiring multiple resources. Negotiation agents in this paper are designed to adjust (1) the number of tentative agreements for each resource and (2) the amount of concession they are willing to make in response to changing market conditions and negotiation situations. In our approach, agents utilize a time-dependent negotiation strategy in which the reserve price of each resource is dynamically determined by (1) the likelihood that negotiation will not be successfully completed ( conflict probability ), (2) the expected agreement price of the resource, and (3) the expected number of final agreements. The negotiation deadline of each resource is determined by its relative scarcity. Agents are permitted to decommit from agreements by paying a time-dependent penalty, and a buyer can make more than one tentative agreement for each resource. The maximum number of tentative agreements for each resource made by an agent is constrained by the market situation. Experimental results show that our negotiation strategy achieved significantly more utilities than simpler strategies.

Details DOI

AAAI Conference 2010 Conference Paper

Towards Multiagent Meta-level Control

  • Shanjun Cheng
  • Anita Raja
  • Victor Lesser

Embedded systems consisting of collaborating agents capable of interacting with their environment are becoming ubiquitous. It is crucial for these systems to be able to adapt to the dynamic and uncertain characteristics of an open environment. In this paper, we argue that multiagent meta-level control (MMLC) is an effective way to determine when this adaptation process should be done and how much effort should be invested in adaptation as opposed to continuing with the current action plan. We describe a reinforcement learning based approach to learn decentralized meta-control policies offline. We then propose to use the learned reward model as input to a global optimization algorithm to avoid conflicting meta-level decisions between coordinating agents. Our initial experiments in the context of NetRads, a multiagent tornado tracking application show that MMLC significantly improves performance in a 3-agent network.

PDF Details

IJCAI Conference 2009 Conference Paper

  • Chongjie Zhang
  • Victor Lesser
  • Prashant Shenoy

Resource allocation in computing clusters is traditionally centralized, which limits the cluster scale. Effective resource allocation in a network of computing clusters may enable building larger computing infrastructures. We consider this problem as a novel application for multiagent learning (MAL). We propose a MAL algorithm and apply it for optimizing online resource allocation in cluster networks. The learning is distributed to each cluster, using local information only and without access to the global system reward. Experimental results are encouraging: our multiagent learning approach performs reasonably well, compared to an optimal solution, and better than a centralized myopic allocation approach in some cases.

PDF Details

AAMAS Conference 2009 Conference Paper

Integrating Organizational Control into Multi-Agent Learning

  • Chongjie Zhang
  • Sherief Abdallah
  • Victor Lesser

Multi-Agent Reinforcement Learning (MARL) algorithms suffer from slow convergence and even divergence, especially in largescale systems. In this work, we develop an organization-based control framework to speed up the convergence of MARL algorithms in a network of agents. Our framework defines a multi-level organizational structure for automated supervision and a communication protocol for exchanging information between lower-level agents and higher-level supervising agents. The abstracted states of lower-level agents travel upwards so that higher-level supervising agents generate a broader view of the state of the network. This broader view is used in creating supervisory information which is passed down the hierarchy. The supervisory policy adaptation then integrates supervisory information into existing MARL algorithms, guiding agents’ exploration of their state-action space. The generality of our framework is verified by its applications on different domains (distributed task allocation and network routing) with different MARL algorithms. Experimental results show that our framework improves both the speed and likelihood of MARL convergence.

PDF

AAMAS Conference 2008 Conference Paper

Decommitment in Multi-resource Negotiation

  • Bo An
  • Victor Lesser
  • Kwang Mong Sim

This paper presents the design and implementation of negotiation agents that negotiate with other entities for acquiring multiple resources. In our approach, agents utilize a time-dependent negotiation strategy in which the reserve price of each negotiation issue is dynamically determined by 1) the likelihood that negotiation will not be successfully completed (conflict probability), 2) the expected agreement price of the issue, and 3) the expected number of final agreements. Results from a series of experiments indicate that on average, our negotiation strategy achieved higher average utility than traditional negotiation strategies.

PDF

AAMAS Conference 2008 Conference Paper

Efficient Multi-Agent Reinforcement Learning through Automated Supervision

  • Chongjie Zhang
  • Sherief Abdallah
  • Victor Lesser

Multi-Agent Reinforcement Learning (MARL) algorithms suffer from slow convergence and even divergence, especially in large-scale systems. In this work, we develop a supervision framework to speed up the convergence of MARL algorithms in a network of agents. The framework defines an organizational structure for automated supervision and a communication protocol for exchanging information between lower-level agents and higher-level supervising agents. The abstracted states of lower-level agents travel upwards so that higher-level supervising agents generate a broader view of the state of the network. This broader view is used in creating supervisory information which is passed down the hierarchy. We present a generic extension to MARL algorithms that integrates supervisory information into the learning process, guiding agents’ exploration of their stateaction space.

PDF

AAMAS Conference 2008 Conference Paper

Non-linear Dynamics in Multiagent Reinforcement Learning Algorithms

  • Sherief Abdallah
  • Victor Lesser

Several multiagent reinforcement learning (MARL) algorithms have been proposed to optimize agents’ decisions. Only a subset of these MARL algorithms both do not require agents to know the underlying environment and can learn a stochastic policy (a policy that chooses actions according to a probability distribution). Weighted Policy Learner (WPL) is a MARL algorithm that belongs to this subset and was shown, experimentally in previous work, to converge and outperform previous MARL algorithms belonging to the same subset. The main contribution of this paper is analyzing the dynamics of WPL and showing the effect of its non-linear nature, as opposed to previous MARL algorithms that had linear dynamics. First, we represent the WPL algorithm as a set of differential equations. We then solve the equations and show that it is consistent with experimental results reported in previous work. We finally compare the dynamics of WPL with earlier MARL algorithms and discuss the interesting differences and similarities we have discovered.

PDF

AAMAS Conference 2008 Conference Paper

Self-Interested Database Managers Playing The View Maintenance Game

  • Hala Mostafa
  • Victor Lesser
  • Gerome Miklau

A database view is a dynamic virtual table composed of the result set of a query, often executed over different underlying databases. The view maintenance problem concerns how a view is refreshed when the data sources are updated. We study the view maintenance problem when self-interested database managers from different institutions are involved, each concerned about the privacy of its database. We regard view maintenance as an incremental, sequential process where an action taken at a stage affects what happens at later stages. The contribution of this paper is twofold. First, we formulate the view maintenance problem as a sequential game of incomplete information where at every stage, each database manager decides what information to disclose, if any, without knowledge of the number or nature of updates at other managers. This allows us to adopt a satisficing approach where the final view need not reflect 100% of the databases updates. Second, we present an anytime algorithm for calculating -Bayes-Nash equilibria that allows us to solve the large games which our problem translates to. Our algorithm is not restricted to games originating from the view maintenance problem; it can be used to solve general games of incomplete information. In addition, experimental results demonstrate our algorithm’s attractive anytime behavior, which allows it to find good-enough solutions to large games within reasonable amounts of time.

PDF

AAMAS Conference 2008 Conference Paper

Using Organization Knowledge to Improve Routing Performance in Wireless Multi-Agent Networks

  • Huzaifa Zafar
  • Victor Lesser
  • Dan Corkill
  • Deepak Ganesan

Multi-agent systems benefit greatly from an organization design that guides agents in determining when to communicate, how often, with whom, with what priority, and so on. However, this same organization knowledge is not utilized by general-purpose wireless network routing algorithms normally used to support agent communication. We show that incorporating organization knowledge (otherwise available only to the application layer) in the network-layer routing algorithm increases bandwidth available at the application layer by as much as 35 percent. This increased bandwidth is especially important in communication-intensive application settings, such as agent-based sensor networks, where node failures and link dynamics make providing sufficient inter-agent communication especially challenging.

PDF

JAAMAS Journal 2007 Journal Article

A framework for meta-level control in multi-agent systems

  • Anita Raja
  • Victor Lesser

Abstract Sophisticated agents operating in open environments must make decisions that efficiently trade off the use of their limited resources between dynamic deliberative actions and domain actions. This is the meta-level control problem for agents operating in resource-bounded multi-agent environments. Control activities involve decisions on when to invoke and the amount to effort to put into scheduling and coordination of domain activities. The focus of this paper is how to make effective meta-level control decisions. We show that meta-level control with bounded computational overhead allows complex agents to solve problems more efficiently than current approaches in dynamic open multi-agent environments. The meta-level control approach that we present is based on the decision-theoretic use of an abstract representation of the agent state. This abstraction concisely captures critical information necessary for decision making while bounding the cost of meta-level control and is appropriate for use in automatically learning the meta-level control policies.

Details DOI

AAMAS Conference 2007 Conference Paper

A Reinforcement Learning based Distributed Search Algorithm For Hierarchical Peer-to-Peer Information Retrieval Systems

  • Haizheng Zhang
  • Victor Lesser

The dominant existing routing strategies employed in peerto- peer(P2P) based information retrieval(IR) systems are similarity-based approaches. In these approaches, agents depend on the content similarity between incoming queries and their direct neighboring agents to direct the distributed search sessions. However, such a heuristic is myopic in that the neighboring agents may not be connected to more relevant agents. In this paper, an online reinforcement-learning based approach is developed to take advantage of the dynamic run-time characteristics of P2P IR systems as represented by information about past search sessions. Specically, agents maintain estimates on the downstream agents'abilities to provide relevant documents for incoming queries. These estimates are updated gradually by learning from the feedback information returned from previous search sessions. Based on this information, the agents derive corresponding routing policies. Thereafter, these agents route the queries based on the learned policies and update the estimates based on the new routing policies. Experimental results demonstrate that the learning algorithm improves considerably the routing performance on two test collection sets that have been used in a variety of distributed IR studies.

PDF

JAAMAS Journal 2007 Journal Article

Automated organization design for multi-agent systems

  • Mark Sims
  • Daniel Corkill
  • Victor Lesser

Abstract The ability to create effective multi-agent organizations is key to the development of larger, more diverse multi-agent systems. In this article we present KB-ORG: a fully automated, knowledge-based organization designer for multi-agent systems. Organization design is the process that accepts organizational goals, environmental expectations, performance requirements, role characterizations, and agent descriptions and assigns roles to each agent. These long-term roles serve as organizational-control guidelines that are used by each agent in making moment-to-moment operational control decisions. An important aspect of KB-ORG is its efficient, knowledge-informed search process for designing multi-agent organizations. KB-ORG uses both application-level and coordination-level organization design knowledge to explore the combinatorial search space of candidate organizations selectively. KB-ORG also delays making coordination-level organizational decisions until it has explored and elaborated candidate application-level agent roles. This approach significantly reduces the exploration effort required to produce effective designs as compared to modeling and evaluation-based approaches that do not incorporate design expertise. KB-ORG designs are not restricted to a single organization form such as a hierarchy, and the organization designs described here contain both hierarchical and peer-to-peer elements. We use examples from the distributed sensor network (DSN) domain to show how KB-ORG uses situational parameters as well as application-level and coordination-level knowledge to generate organization designs. We also show that KB-ORG designs effective, yet substantially different, organizations when given different organizational requirements and environmental expectations.

Details DOI

AAMAS Conference 2007 Conference Paper

Meta-Level Coordination for Solving Negotiation Chains in Semi-Cooperative Multi-Agent Systems

  • Xiaoqin Zhang
  • Victor Lesser

A negotiation chain is formed when multiple related negotiations are spread over multiple agents. In order to appropriately order and structure the negotiations occurring in the chain so as to optimize the expected utility, we present an extension to a singleagent concurrent negotiation framework. This work is aimed at semi-cooperative multi-agent systems, where each agent has its own goals and works to maximize its local utility; however, the performance of each individual agent is tightly related to other agent's cooperation and the system's overall performance. We introduce a pre-negotiation phase that allows agents to transfer meta-level information. Using this information, the agent can build a more accurate model of the negotiation in terms of modeling the relationship of flexibility and success probability. This more accurate model helps the agent in choosing a better negotiation solution in the global negotiation chain context. The agent can also use this information to allocate appropriate time for each negotiation, hence to find a good ordering of all related negotiations. The experimental data shows that these mechanisms improve the agents' and the system's overall performance significantly.

PDF

AAMAS Conference 2007 Conference Paper

Multiagent Reinforcement Learning and Self-Organization in a Network of Agents

  • Sherief Abdallah
  • Victor Lesser

To cope with large scale, agents are usually organized in a network such that an agent interacts only with its immediate neighbors in the network. Reinforcement learning techniques have been commonly used to optimize agents local policies in such a network because they require little domain knowledge and can be fully distributed. However, all of the previous work assumed the underlying network was fixed throughout the learning process. This assumption was important because the underlying network defines the learning context of each agent. In particular, the set of actions and the state space for each agent is defined in terms of the agent's neighbors. If agents dynamically change the underlying network structure (also called self-organize) during learning, then one needs a mechanism for transferring what agents have learned so far before (in the old network structure) to their new learning context (in the new network structure).

PDF

JAAMAS Journal 2007 Journal Article

Using quantitative models to search for appropriate organizational designs

  • BRYAN HORLING
  • Victor Lesser

Abstract As the scale and scope of distributed and multi-agent systems grow, it becomes increasingly important to design and manage the participants’ interactions. The potential for bottlenecks, intractably large sets of coordination partners, and shared bounded resources can make individual and high-level goals difficult to achieve. To address these problems, many large systems employ an additional layer of structuring, known as an organizational design, that assigns agents different roles, responsibilities and peers. These additional constraints can allow agents to operate more efficiently within the system by limiting the options they must consider. Different designs applied to the same problem will have different performance characteristics, therefore it is important to understand the behavior of competing candidate designs. In this article, we describe a new representation for capturing such designs, and in particular we show how quantitative information can form the basis of a flexible, predictive organizational model. The representation is capable of capturing a wide range of multi-agent characteristics in a single, succinct model. We demonstrate the language’s capabilities and efficacy by comparing a range of metrics predicted by detailed models of a distributed sensor network and information retrieval system to empirical results. These same models also describe the space of possible organizations in those domains and several search techniques are described that can be used to explore this space, using those quantitative predictions and context-specific definitions of utility to evaluate alternatives. The results of such a search process can be used to select the organizational design most appropriate for a given situation.

Details DOI

JAAMAS Journal 2005 Journal Article

The Soft Real-Time Agent Control Architecture

  • BRYAN HORLING
  • Victor Lesser
  • Thomas Wagner

Abstract Real-time control has become increasingly important as technologies are moved from the lab into real world situations. The complexity associated with these systems increases as control and autonomy are distributed, due to such issues as temporal and ordering constraints, shared resources, and the lack of a complete and consistent world view. In this paper we describe a soft real-time architecture designed to address these requirements, motivated by challenges encountered in a real-time distributed sensor allocation environment. The system features the ability to generate schedules respecting temporal, structural and resource constraints, to merge new goals with existing ones, and to detect and handle unexpected results from activities. We will cover a suite of technologies being employed, including quantitative task representation, alternative plan selection, partial-order scheduling, schedule consolidation and execution and conflict resolution in an uncertain environment. Technologies which facilitate on-line real-time control, including meta-level accounting, schedule caching and variable time granularities are also discussed.

Details DOI

KER Journal 2004 Journal Article

A survey of multi-agent organizational paradigms

  • BRYAN HORLING
  • Victor Lesser

Many researchers have demonstrated that the organizational design employed by an agent system can have a significant, quantitative effect on its performance characteristics. A range of organizational strategies have emerged from this line of research, each with different strengths and weaknesses. In this article we present a survey of the major organizational paradigms used in multi-agent systems. These include hierarchies, holarchies, coalitions, teams, congregations, societies, federations, markets, and matrix organizations. We will provide a description of each, discuss their advantages and disadvantages, and provide examples of how they may be instantiated and maintained. This summary will facilitate the comparative evaluation of organizational styles, allowing designers to first recognize the spectrum of possibilities, and then guiding the selection of an appropriate organizational design for a particular domain and environment.

Details DOI

AIJ Journal 2000 Journal Article

BIG: An agent for resource-bounded information gathering and decision making

  • Victor Lesser
  • BRYAN HORLING
  • Frank Klassner
  • Anita Raja
  • Thomas Wagner
  • Shelley XQ. Zhang

The World Wide Web has become an invaluable information resource but the explosion of available information has made Web search a time consuming and complex process. The large number of information sources and their different levels of accessibility, reliability and associated costs present a complex information gathering control problem. This paper describes the rationale, architecture, and implementation of a next generation information gathering system—a system that integrates several areas of Artificial Intelligence research under a single umbrella. Our solution to the information explosion is an information gathering agent, BIG, that plans to gather information to support a decision process, reasons about the resource trade-offs of different possible gathering approaches, extracts information from both unstructured and structured documents, and uses the extracted information to refine its search and processing activities.

Details DOI

AAAI Conference 1999 Conference Paper

Learning Quantitative Knowledge for Multiagent Coordination

  • David Jensen
  • Michael Atighetchi
  • Régis Vincent
  • Victor Lesser
  • University of Massachusetts at Amherst

A central challenge of multiagent coordination is reasoning about howthe actions of one agent affect the actions of another. Knowledge of these interrelationships can help coordinate agents -- preventing conflicts and exploiting beneficial relationships among actions. Weexplore three interlocking methods that learn quantitative knowledge of such non-local effects in T/EMS, a well-developed frameworkfor multiagent coordination. Thesurprising simplicity and effectiveness of these methods demonstrates howagents can learn domain-specificknowledge quickly, extendingthe utility of coordination frameworks that explicitly represent coordination knowledge.

PDF Details

AAAI Conference 1998 Conference Paper

BIG: A Resource-Bounded Information Gathering Agent

  • Victor Lesser
  • Frank Klassner
  • Thomas Wagner

Effective information gathering on the WWW is a complex task requiring planning, scheduling, text processing, and interpretation-style reasoning about extracted data to resolve inconsistencies and to refine hypotheses about the data. This paper describes the rationale, architecture, and implementation of a next generation information gathering system – a system that integrates several areas of AI research under a single research umbrella. The goal of this system is to exploit the vast number of information sources available today on the NII including a growing number of digital libraries, independent news agencies, government agencies, as well as human experts providing a variety of services. The large number of information sources and their different levels of accessibility, reliability and associated costs present a complex information gathering coordination problem. Our solution is an information gathering agent, BIG, that plans to gather information to support a decision process, reasons about the resource tradeoffs of different possible gathering approaches, extracts information from both unstructured and structured documents, and uses the extracted information to refine its search and processing activities.

PDF Details

IJCAI Conference 1993 Conference Paper

An Approach to Analyzing the Need for Meta-Level Communication

  • Keith Decker
  • Victor Lesser

This paper presents an analysis of static and dynamic organizational structures for naturally distributed, homogeneous, cooperative problem solving environments, exemplified by distributed sensor networks. We first show how the performance of any static organization can be statistically described, and then show under what conditions dynamic organizations do better and worse than static ones. Finally, we show how the variance in the agents' performance leads to uncertainty about whether a dynamic organization will perform better than a static one given only agent a priori expectations. In these cases, we show when meta-level communication about the actual state of problem solving will be useful to agents in constructing a dynamic organizational structure that outperforms a static one. Viewed in its entirety, this paper also presents a methodology for answering questions about the design of distributed problem solving systems by analysis and simulation of the characteristics of a complex environment rather than by relying on single-instance examples.

PDF

AAAI Conference 1993 Conference Paper

IPUS: An Architecture for Integrated Signal Processing and Signal Interpretation in Complex Environments

  • Victor Lesser
  • Frank Klassner

This paper presents the IPUS (Integratecl Processing and Understanding of Signals) architecture to address the traditional perceptual paradigm’ s shortcomings in complex environments. It has two premises: (1) the search for correct interpretations of signal processing algorithms’ (SPAS) outputs requires concurrent search for SPAS and control parameters appropriate for the environment, and (2) interaction between these search processes must be structured by a formal theory of how inappropriate SPA usage can distort SPA output. We describe IPUS’ s key components (discrepancy detection, diagnosis, reprocessing, and differential diagnosis) and their instantiation in an acoustic interpretation system. This application, along with another in the radar domain, supports our claim that the IPUS paradigm is feasible and generic.

PDF Details

IJCAI Conference 1989 Conference Paper

Controlling a Language Generation Planner

  • Sergei Nirenburg
  • Victor Lesser
  • Eric Nybcrg

The set of partially interdependent lexical and syntactic decisions that have to be made in the process of natural language generation are best seen as a complex planning and search problem. This paper discusses the phenomena involved in natural language generation planning and argues that a blackboard-type architecture with agenda-style control is more appropriate for this task than a sequential control architecture with backtracking. The blackboard architecture we describe is implemented in the language generator DIOGENES.

PDF