Katia Sycara

JAAMAS Journal 2026 Journal Article

A Roadmap of Agent Research and Development

• Nicholas R. Jennings
• Katia Sycara
• Michael Wooldridge

Abstract This paper provides an overview of research and development activities in the field of autonomous agents and multi-agent systems. It aims to identify key concepts and applications, and to indicate how they relate to one-another. Some historical context to the field of agent-based computing is given, and contemporary research directions are presented. Finally, a range of open issues and future challenges are highlighted.

JAAMAS Journal 2026 Journal Article

Editorial

• NICK JENNINGS
• Katia Sycara
• Mike Georgeff

JAAMAS Journal 2026 Journal Article

In Appreciation

• Katia Sycara
• Mike Wooldridge

AAMAS Conference 2026 Conference Paper

InteractFormer: Inter-Agent Spatiotemporal Attention for Multi-Agent Action Anticipation

• Yiqi Jin
• Simon Stepputtis
• Carl Busart
• Katia Sycara
• Yaqi Xie

Action anticipation in multi-agent scenarios is critical for embodied intelligence but remains under-explored compared to single-agent settings. Effective anticipation requires capturing complex interagent correlations across both momentary interactions and temporal evolutions. We propose InteractFormer, a model specifically designed to jointly predict future actions of all agents by modeling their inherent cooperation. Our approach captures fine-grained relationships through visual cross-attention and incorporates spatial bounding-box cues to ground inter-agent dynamics. Extensive experiments on two benchmarks—household collaborative tasks (LEMMA) and multi-agent sports (SportsHHI)—demonstrate that InteractFormer consistently outperforms state-of-the-art methods. Visualizationsfurtherconfirmthatourmodelprovidesinterpretable insights into collaborative behavior.

JAAMAS Journal 2026 Journal Article

Larks: Dynamic Matchmaking Among Heterogeneous Software Agents in Cyberspace

• Katia Sycara
• Seth Widoff
• Jianguo Lu

Abstract Service matchmaking among heterogeneous software agents in the Internet is usually done dynamically and must be efficient. There is an obvious trade-off between the quality and efficiency of matchmaking on the Internet. We define a language called Larks for agent advertisements and requests, and present a flexible and efficient matchmaking process that uses Larks. The Larks matchmaking process performs both syntactic and semantic matching, and in addition allows the specification of concepts (local ontologies) via ITL, a concept language. The matching process uses five different filters: context matching, profile comparison, similarity matching, signature matching and constraint matching. Different degrees of partial matching can result from utilizing different combinations of these filters. We briefly report on our implementation of Larks and the matchmaking process in Java. Fielded applications of matchmaking using Larks in several application domains for systems of information agents are ongoing efforts.

JAAMAS Journal 2026 Journal Article

Short System Descriptions: Introducing a New Feature of the Journal

• Katia Sycara

JAAMAS Journal 2026 Journal Article

The RETSINA MAS Infrastructure

• Katia Sycara
• Massimo Paolucci
• Joseph Giampapa

Abstract RETSINA is an implemented Multi-Agent System infrastructure that has been developed for several years and applied in many domains ranging from financial portfolio management to logistic planning. In this paper, we distill from our experience in developing MASs to clearly define a generic MAS infrastructure as the domain independent and reusable substratum that supports the agents' social interactions. In addition, we show that the MAS infrastructure imposes requirements on an individual agent if the agent is to be a member of a MAS and take advantage of various components of the MAS infrastructure. Although agents are expected to enter a MAS and seamlessly and effortlessly interact with the agents in the MAS infrastructure, the current state of the art demands agents to be programmed with the knowledge of what infrastructure they will utilize, and what are various fall-back and recovery mechanisms that the infrastructure provides. By providing an abstract MAS infrastructure model and a concrete implemented instance of the model, RETSINA, we contribute towards the development of principles and practice to make the MAS infrastructure “invisible” and ubiquitous to the interacting agents.

NeurIPS Conference 2025 Conference Paper

Adaptively Coordinating with Novel Partners via Learned Latent Strategies

• Benjamin Li
• Shuyang Shi
• Lucia Romero
• Huao Li
• Yaqi Xie
• Woojun Kim
• Stefanos Nikolaidis
• Charles Lewis

Adaptation is the cornerstone of effective collaboration among heterogeneous team members. In human-agent teams, artificial agents need to adapt to their human partners in real time, as individuals often have unique preferences and policies that may change dynamically throughout interactions. This becomes particularly challenging in tasks with time pressure and complex strategic spaces, where identifying partner behaviors and selecting suitable responses is difficult. In this work, we introduce a strategy-conditioned cooperator framework that learns to represent, categorize, and adapt to a broad range of potential partner strategies in real-time. Our approach encodes strategies with a variational autoencoder to learn a latent strategy space from agent trajectory data, identifies distinct strategy types through clustering, and trains a cooperator agent conditioned on these clusters by generating partners of each strategy type. For online adaptation to novel partners, we leverage a fixed-share regret minimization algorithm that dynamically infers and adjusts the partner's strategy estimation during interaction. We evaluate our method in a modified version of the Overcooked domain, a complex collaborative cooking environment that requires effective coordination among two players with a diverse potential strategy space. Through these experiments and an online user study, we demonstrate that our proposed agent achieves state of the art performance compared to existing baselines when paired with novel human, and agent teammates.

NeurIPS Conference 2025 Conference Paper

Fair Cooperation in Mixed-Motive Games via Conflict-Aware Gradient Adjustment

• Woojun Kim
• Katia Sycara

Multi-agent reinforcement learning in mixed-motive settings presents a fundamental challenge: agents must balance individual interests with collective goals, which are neither fully aligned nor strictly opposed. To address this, reward restructuring methods such as gifting and intrinsic motivation have been proposed. However, these approaches primarily focus on promoting cooperation by managing the trade-off between individual and collective returns, without explicitly addressing fairness with respect to agents’ task-specific rewards. In this paper, we propose an adaptive conflict-aware gradient adjustment method that promotes cooperation while ensuring fairness in individual rewards. The proposed method dynamically balances policy gradients derived from individual and collective objectives in situations where the two objectives are in conflict. By explicitly resolving such conflicts, our method improves collective performance while preserving fairness across agents. We provide theoretical results that guarantee monotonic non-decreasing improvement in both the collective and individual objectives and ensure fairness. Empirical results in sequential social dilemma environments demonstrate that our approach outperforms baselines in terms of social welfare, while maintaining fairness.

NeurIPS Conference 2024 Conference Paper

Dual Prototype Evolving for Test-Time Generalization of Vision-Language Models

• Ce Zhang
• Simon Stepputtis
• Katia Sycara
• Yaqi Xie

Test-time adaptation, which enables models to generalize to diverse data with unlabeled test samples, holds significant value in real-world scenarios. Recently, researchers have applied this setting to advanced pre-trained vision-language models (VLMs), developing approaches such as test-time prompt tuning to further extend their practical applicability. However, these methods typically focus solely on adapting VLMs from a single modality and fail to accumulate task-specific knowledge as more samples are processed. To address this, we introduce Dual Prototype Evolving (DPE), a novel test-time adaptation approach for VLMs that effectively accumulates task-specific knowledge from multi-modalities. Specifically, we create and evolve two sets of prototypes—textual and visual—to progressively capture more accurate multi-modal representations for target classes during test time. Moreover, to promote consistent multi-modal representations, we introduce and optimize learnable residuals for each test sample to align the prototypes from both modalities. Extensive experimental results on 15 benchmark datasets demonstrate that our proposed DPE consistently outperforms previous state-of-the-art methods while also exhibiting competitive computational efficiency.

NeurIPS Conference 2024 Conference Paper

GL-NeRF: Gauss-Laguerre Quadrature Enables Training-Free NeRF Acceleration

• Silong Yong
• Yaqi Xie
• Simon Stepputtis
• Katia Sycara

Volume rendering in neural radiance fields is inherently time-consuming due to the large number of MLP calls on the points sampled per ray. Previous works would address this issue by introducing new neural networks or data structures. In this work, we propose GL-NeRF, a new perspective of computing volume rendering with the Gauss-Laguerre quadrature. GL-NeRF significantly reduces the number of MLP calls needed for volume rendering, introducing no additional data structures or neural networks. The simple formulation makes adopting GL-NeRF in any NeRF model possible. In the paper, we first justify the use of the Gauss-Laguerre quadrature and then demonstrate this plug-and-play attribute by implementing it in two different NeRF models. We show that with a minimal drop in performance, GL-NeRF can significantly reduce the number of MLP calls, showing the potential to speed up any NeRF model. Code can be found in project page https: //silongyong. github. io/GL-NeRF project page/.

NeurIPS Conference 2024 Conference Paper

Language Grounded Multi-agent Reinforcement Learning with Human-interpretable Communication

• Huao Li
• Hossein N. Mahjoub
• Behdad Chalaki
• Vaishnav Tadiparthi
• Kwonjoon Lee
• Ehsan Moradi-Pari
• Michael Lewis
• Katia Sycara

Multi-Agent Reinforcement Learning (MARL) methods have shown promise in enabling agents to learn a shared communication protocol from scratch and accomplish challenging team tasks. However, the learned language is usually not interpretable to humans or other agents not co-trained together, limiting its applicability in ad-hoc teamwork scenarios. In this work, we propose a novel computational pipeline that aligns the communication space between MARL agents with an embedding space of human natural language by grounding agent communications on synthetic data generated by embodied Large Language Models (LLMs) in interactive teamwork scenarios. Our results demonstrate that introducing language grounding not only maintains task performance but also accelerates the emergence of communication. Furthermore, the learned communication protocols exhibit zero-shot generalization capabilities in ad-hoc teamwork scenarios with unseen teammates and novel task states. This work presents a significant step toward enabling effective communication and collaboration between artificial agents and humans in real-world teamwork settings.

NeurIPS Conference 2024 Conference Paper

LogiCity: Advancing Neuro-Symbolic AI with Abstract Urban Simulation

• Bowen Li
• Zhaoyu Li
• Qiwei Du
• Jinqi Luo
• Wenshan Wang
• Yaqi Xie
• Simon Stepputtis
• Chen Wang

Recent years have witnessed the rapid development of Neuro-Symbolic (NeSy) AI systems, which integrate symbolic reasoning into deep neural networks. However, most of the existing benchmarks for NeSy AI fail to provide long-horizon reasoning tasks with complex multi-agent interactions. Furthermore, they are usually constrained by fixed and simplistic logical rules over limited entities, making them far from real-world complexities. To address these crucial gaps, we introduce LogiCity, the first simulator based on customizable first-order logic (FOL) for an urban-like environment with multiple dynamic agents. LogiCity models diverse urban elements using semantic and spatial concepts, such as $\texttt{IsAmbulance}(\texttt{X})$ and $\texttt{IsClose}(\texttt{X}, \texttt{Y})$. These concepts are used to define FOL rules that govern the behavior of various agents. Since the concepts and rules are abstractions, they can be universally applied to cities with any agent compositions, facilitating the instantiation of diverse scenarios. Besides, a key feature of LogiCity is its support for user-configurable abstractions, enabling customizable simulation complexities for logical reasoning. To explore various aspects of NeSy AI, LogiCity introduces two tasks, one features long-horizon sequential decision-making, and the other focuses on one-step visual reasoning, varying in difficulty and agent behaviors. Our extensive evaluation reveals the advantage of NeSy frameworks in abstract reasoning. Moreover, we highlight the significant challenges of handling more complex abstractions in long-horizon multi-agent scenarios or under high-dimensional, imbalanced data. With its flexible design, various features, and newly raised challenges, we believe LogiCity represents a pivotal step forward in advancing the next generation of NeSy AI. All the code and data are open-sourced at our website.

NeurIPS Conference 2024 Conference Paper

Map It Anywhere: Empowering BEV Map Prediction using Large-scale Public Datasets

• Cherie Ho
• Jiaye Zou
• Omar Alama
• Sai M. Kumar
• Benjamin Chiang
• Taneesh Gupta
• Chen Wang
• Nikhil Keetha

Top-down Bird's Eye View (BEV) maps are a popular perception representation for ground robot navigation due to their richness and flexibility for downstream tasks. While recent methods have shown promise for predicting BEV maps from First-Person View (FPV) images, their generalizability is limited to small regions captured by current autonomous vehicle-based datasets. In this context, we show that a more scalable approach towards generalizable map prediction can be enabled by using two large-scale crowd-sourced mapping platforms, Mapillary for FPV images and OpenStreetMap for BEV semantic maps. We introduce Map It Anywhere (MIA), a data engine that enables seamless curation and modeling of labeled map prediction data from existing open-source map platforms. Using our MIA data engine, we display the ease of automatically collecting a 1. 2 million FPV & BEV pair dataset encompassing diverse geographies, landscapes, environmental factors, camera models & capture scenarios. We further train a simple camera model-agnostic model on this data for BEV map prediction. Extensive evaluations using established benchmarks and our dataset show that the data curated by MIA enables effective pretraining for generalizable BEV map prediction, with zero-shot performance far exceeding baselines trained on existing datasets by 35%. Our analysis highlights the promise of using large-scale public maps for developing & testing generalizable BEV perception, paving the way for more robust autonomous navigation. Website: mapitanywhere. github. io

AAMAS Conference 2024 Conference Paper

Optimal Task Assignment and Path Planning using Conflict-Based Search with Precedence and Temporal Constraints

• Yu Quan Chong
• Jiaoyang Li
• Katia Sycara

This paper examines the Task Assignment and Path Finding with Precedence and Temporal Constraints (TAPF-PTC) problem. We augment Conflict-Based Search (CBS) to generate task assignments and collision-free paths that adhere to precedence and temporal constraints for agents to maximize a user-defined objective.

NeurIPS Conference 2023 Conference Paper

Characterizing Out-of-Distribution Error via Optimal Transport

• Yuzhe Lu
• Yilong Qin
• Runtian Zhai
• Andrew Shen
• Ketong Chen
• Zhenlin Wang
• Soheil Kolouri
• Simon Stepputtis

Out-of-distribution (OOD) data poses serious challenges in deployed machine learning models, so methods of predicting a model's performance on OOD data without labels are important for machine learning safety. While a number of methods have been proposed by prior work, they often underestimate the actual error, sometimes by a large margin, which greatly impacts their applicability to real tasks. In this work, we identify pseudo-label shift, or the difference between the predicted and true OOD label distributions, as a key indicator of this underestimation. Based on this observation, we introduce a novel method for estimating model performance by leveraging optimal transport theory, Confidence Optimal Transport (COT), and show that it provably provides more robust error estimates in the presence of pseudo-label shift. Additionally, we introduce an empirically-motivated variant of COT, Confidence Optimal Transport with Thresholding (COTT), which applies thresholding to the individual transport costs and further improves the accuracy of COT's error estimates. We evaluate COT and COTT on a variety of standard benchmarks that induce various types of distribution shift -- synthetic, novel subpopulation, and natural -- and show that our approaches significantly outperform existing state-of-the-art methods with up to 3x lower prediction errors.

AAMAS Conference 2023 Conference Paper

Emergent Compositional Concept Communication through Mutual Information in Multi-Agent Teams

• Seth Karten
• Siva Kailas
• Katia Sycara

In multi-agent reinforcement learning (MARL) with communication, coordination information (ordinal) is often required in addition to referential info about one’s observations. The information bottleneck defines a trade-off between complexity and utility, which loses structure of latent information when compressed solely for utility. Thus, in this work, we use information theory to introduce information-rich, variational compositional communication to adequately embed referential information and to provide a contrastive objective to ground communication in intent-specific features without relying on reward. Each message is composed of a set of emergent concepts, which we show span the observations and intents. Messages are naturally compressed to the least number of bits.

NeurIPS Conference 2021 Conference Paper

Emergent Discrete Communication in Semantic Spaces

• Mycal Tucker
• Huao Li
• Siddharth Agrawal
• Dana Hughes
• Katia Sycara
• Michael Lewis
• Julie A Shah

Neural agents trained in reinforcement learning settings can learn to communicate among themselves via discrete tokens, accomplishing as a team what agents would be unable to do alone. However, the current standard of using one-hot vectors as discrete communication tokens prevents agents from acquiring more desirable aspects of communication such as zero-shot understanding. Inspired by word embedding techniques from natural language processing, we propose neural agent architectures that enables them to communicate via discrete tokens derived from a learned, continuous space. We show in a decision theoretic framework that our technique optimizes communication over a wide range of scenarios, whereas one-hot tokens are only optimal under restrictive assumptions. In self-play experiments, we validate that our trained agents learn to cluster tokens in semantically-meaningful ways, allowing them communicate in noisy environments where other techniques fail. Lastly, we demonstrate both that agents using our method can effectively respond to novel human communication and that humans can understand unlabeled emergent agent communication, outperforming the use of one-hot communication.

AAMAS Conference 2019 Conference Paper

Active Learning with Gaussian Processes for High Throughput Phenotyping

• Sumit Kumar
• Wenhao Luo
• George Kantor
• Katia Sycara

A looming question that must be solved before robotic plant phenotyping capabilities can have significant impact to crop improvement programs is scalability. High Throughput Phenotyping (HTP) uses robotic technologies to analyze crops in order to determine species with favorable traits, however, the current practices rely on exhaustive coverage and data collection from the entire crop field being monitored under the breeding experiment. This works well in relatively small agricultural fields but can not be scaled to the larger ones, thus limiting the progress of genetics research. In this work, we propose an active learning algorithm to enable an autonomous system to collect the most informative samples in order to accurately learn the distribution of phenotypes in the field with the help of a Gaussian Process model. We demonstrate the superior performance of our proposed algorithm compared to the current practices on sorghum phenotype data collection.

AAMAS Conference 2019 Conference Paper

Community Regularization of Visually-Grounded Dialog

• Akshat Agarwal
• Swaminathan Gurumurthy
• Vasu Sharma
• Mike Lewis
• Katia Sycara

The task of conducting visually grounded dialog involves learning goal-oriented cooperative dialog between autonomous agents who exchange information about a scene through several rounds of questions and answers in natural language. We posit that requiring artificial agents to adhere to the rules of human language, while also requiring them to maximize information exchange through dialog is an ill-posed problem. We observe that humans do not stray from a common language because they are social creatures who live in communities, and have to communicate with many people everyday, so it is far easier to stick to a common language even at the cost of some efficiency loss. Using this as inspiration, we propose and evaluate a multi-agent community-based dialog framework where each agent interacts with, and learns from, multiple agents, and show that this community-enforced regularization results in more relevant and coherent dialog (as judged by human evaluators) without sacrificing task performance (as judged by quantitative metrics).

AAMAS Conference 2019 Conference Paper

Distributed Environmental Modeling and Adaptive Sampling for Multi-Robot Sensor Coverage

• Wenhao Luo
• Changjoo Nam
• George Kantor
• Katia Sycara

We consider the problem of online distributed environmental modeling and adaptive sampling for multi-robot sensor coverage, where a team of robots spread out over the workspace in order to optimize the sensing performance over environmental phenomena, whose distribution is often referred to as a density function. Unlike most existing works that either assume certain knowledge of the density function beforehand or centrally learn the density function assuming global knowledge of collected data from all the robots, we propose a fully distributed adaptive sampling approach to allow robots to efficiently learn the unknown density function online. In particular, we developed adaptive coverage controllers based on the learned density functions for minimizing the sensing cost. To capture significantly different components of the environmental phenomenon with only locally collected data for each robot when global knowledge is not available, we propose a distributed mixture of Gaussian Processes algorithm that enables robots to collaboratively learn the global density function by exchanging only modelrelated parameters. We empirically demonstrate the effectiveness of our algorithm via evaluation on real-world data gathered from agricultural field robot and indoor static sensors.

AAAI Conference 2019 Conference Paper

Towards Better Interpretability in Deep Q-Networks

• Raghuram Mandyam Annasamy
• Katia Sycara

Deep reinforcement learning techniques have demonstrated superior performance in a wide variety of environments. As improvements in training algorithms continue at a brisk pace, theoretical or empirical studies on understanding what these networks seem to learn, are far behind. In this paper we propose an interpretable neural network architecture for Q-learning which provides a global explanation of the model’s behavior using key-value memories, attention and reconstructible embeddings. With a directed exploration strategy, our model can reach training rewards comparable to the state-of-the-art deep Q-learning models. However, results suggest that the features extracted by the neural network are extremely shallow and subsequent testing using out-of-sample examples shows that the agent can easily overfit to trajectories seen during training.

AAMAS Conference 2019 Conference Paper

Trust-Aware Behavior Reflection for Robot Swarm Self-Healing

• Rui Liu
• Fan Jia
• Wenhao Luo
• Meghan Chandarana
• Changjoo Nam
• Michael Lewis
• Katia Sycara

The deployment of robot swarms is influenced by real-world factors, such as motor issues, sensor failure, and wind disturbances. These factors cause the appearance of faulty robots. In a decentralized swarm, sharing incorrect information from faulty robots will lead to undesired swarm behaviors, such as swarm disconnection and incorrect heading directions. We envision a system where a human operator is exerting supervisory control over a remote swarm by indicating changes in trust to the swarm via a "trust-signal". By correcting faulty behaviors, trust between the human and the swarm is maintained to facilitate human-swarm cooperation. In this research, a trust-aware behavior reflection method – Trust-R – is designed based on a weighted mean subsequence reduced algorithm (WMSR). By using Trust-R, detected faulty behaviors are automatically corrected by the swarm in a decentralized fashion by referring to the motion status of their trusted neighbors and isolating failed robots from the others. Based on real-world scenarios, three types of robot faults – degraded performance caused by motor wear, abnormal motion caused by system uncertainty and motion deviation caused by an external disturbance such as wind – were simulated to test the effectiveness of Trust-R. Results show that Trust-R is effective in correcting swarm behaviors for swarm self-healing.

AAMAS Conference 2018 Conference Paper

Exploiting Asynchrony in Multi-agent Consensus to Change the Agreement Point

• Sasanka Nagavalli
• Ramitha Sundar
• Katia Sycara

Reaching agreement through consensus is fundamental to the operation of distributed systems such as sensor networks, social networks or multi-robot networks. Consensus requires agents in the system to reach an agreement over a variable of interest only through local interactions. In real systems, limitations in resources available to the individual agents and delays in communication typically result in asynchronous discrete time control models for consensus. In this paper, we model the problem where an adversary (or a friend) can exploit asynchrony in updates in a group of agents that use the same control law. By modifying the update frequency of a subset of the agents, the adversary (or friend) can change the final value that the system agrees on.

AAMAS Conference 2017 Conference Paper

Exploiting Robotic Swarm Characteristics for Adversarial Subversion in Coverage Tasks

• Navyata Sanghvi
• Sasanka Nagavalli
• Katia Sycara

Multi-robot systems, such as swarms, with large number of members that are homogeneous and anonymous are robust to deletion and addition of members. However, these same properties that make the system robust, create vulnerabilities under certain circumstances. In this paper, we study such a case, namely the insertion by adversarial agents, called moles, that subvert the performance of the system. The adversary monitors the swarm’s movements during surveillance operations for the presence of holes, i. e. areas that were left uncovered by the swarm. The adversary then adds moles that get positioned in the swarm, in such a way as to deceive the swarms regarding the existence of holes and thus preventing the swarm from discovering and repairing the holes. This problem has significant military applications. Our contributions are as follows: First, to the best of our knowledge, this is the first paper that studies this problem. Second, we provide a formalization of the problem. Third, we provide several algorithms, and characterize them formally and also experimentally.

AAAI Conference 2016 Conference Paper

Markov Argumentation Random Fields

• Yuqing Tang
• Nir Oren
• Katia Sycara

IJCAI Conference 2015 Conference Paper

A Crowdfunding Model for Green Energy Investment

• Ronghuo Zheng
• Ying Xu
• Nilanjan Chakraborty
• Katia Sycara

This paper studies a new renewable energy investment model through crowdfunding, which is motivated by emerging community solar farms. In this paper we develop a sequential game theory model to capture the interactions among crowdfunders, the solar farm owner, and an electricity company who purchases renewable energy generated by the solar farm in a multi-period framework. By characterizing a unique subgame-perfect equilibrium, and comparing it with a benchmark model without crowdfunding, we find that under crowdfunding although the farm owner reduces its investment level, the overall green energy investment level is increased due to the contribution of crowdfunders. We also find that crowdfunding can increase the penetration of green energy in consumption and thus reduce the energy procurement cost of the electricity company. Finally, the numerical results based on real data indicates crowdfunding is a simple but effective way to boost green generation.

IJCAI Conference 2015 Conference Paper

Nonnegative Matrix Tri-Factorization with Graph Regularization for Community Detection in Social Networks

• Yulong Pei
• Nilanjan Chakraborty
• Katia Sycara

Community detection on social media is a classic and challenging task. In this paper, we study the problem of detecting communities by combining social relations and user generated content in social networks. We propose a nonnegative matrix tri-factorization (NMTF) based clustering framework with three types of graph regularization. The NMTF based clustering framework can combine the relations and content seamlessly and the graph regularization can capture user similarity, message similarity and user interaction explicitly. In order to design regularization components, we further exploit user similarity and message similarity in social networks. A unified optimization problem is proposed by integrating the NMTF framework and the graph regularization. Then we derive an iterative learning algorithm for this optimization problem. Extensive experiments are conducted on three real-world data sets and the experimental results demonstrate the effectiveness of the proposed method.

JAAMAS Journal 2014 Journal Article

Distributed constraint optimization for teams of mobile sensing agents

• Roie Zivan
• Harel Yedidsion
• Katia Sycara

Abstract Coordinating a mobile sensor team (MST) to cover targets is a challenging problem in many multiagent applications. Such applications are inherently dynamic due to changes in the environment, technology failures, and incomplete knowledge of the agents. Agents must adaptively respond by changing their locations to continually optimize the coverage of targets. We propose distributed constraint optimization problems (DCOP)_MST, a new model for representing MST problems that is based on DCOP. In DCOP_MST, agents maintain variables for their physical positions, while each target is represented by a constraint that reflects the quality of coverage of that target. In contrast to conventional, static DCOPs, DCOP_MST not only permits dynamism but exploits it by restricting variable domains to nearby locations; consequently, variable domains and constraints change as the agents move through the environment. DCOP_MST confers three major advantages. It directly represents the multiple forms of dynamism inherent in MSTs. It also provides a compact representation that can be solved efficiently with local search algorithms, with information and communication locality based on physical locality as typically occurs in MST applications. Finally, DCOP_MST facilitates organization of the team into multiple sub-teams that can specialize in different roles and coordinate their activity through dynamic events. We demonstrate how a search-and-detection team responsible for finding new targets and a surveillance sub-team tasked with coverage of known targets can effectively work together to improve performance while using the DCOP_MST framework to coordinate. We propose different algorithms to meet the specific needs of each sub-team and several methods for cooperation between sub-teams. For the search-and-detection team, we develop an algorithm based on the DSA that forces intensive exploration for new targets. For the surveillance sub-team, we adapt several incomplete DCOP algorithms, including MGM, DSA, DBA, and Max-sum, which requires us to develop an efficient method for agents to find the value assignment in their local environment that is optimal in minimizing the maximum unmet coverage requirement over all targets. The disadvantage of dynamic domains based on physical locality is that adaptations of standard local search algorithms tend to become trapped in local optima where targets beyond the immediate range of the agents go uncovered. To address this shortcoming we develop exploration methods to be used with the local search algorithms. Our algorithms are extensively evaluated in a simulation environment. We use a reputation model to determine the individual credibility of agents and consider both additive and submodular joint credibility functions for determining coverage of targets by multiple agents. The performance is measured on two objectives: minimizing the maximum remaining coverage requirement, and minimizing the sum of remaining coverage requirements. Our results show that DSA and MGM with the exploration heuristics outperform the other incomplete algorithms across a wide range of settings. Furthermore, organizing the team into two sub-teams leads to significant gains in performance, and performance continues to improve with greater cooperation between the sub-teams.

IS Journal 2014 Journal Article

Supporting Trust Assessment and Decision Making in Coalitions

• Chris Burnett
• Timothy J. Norman
• Katia Sycara
• Nir Oren

Modern multiorganizational coalitions can bring diverse sets of capabilities, assets, and information sources to bear on complex and dynamic operations. However, successfully completing these operations places demands on the trust between coalition partners. When it's necessary to rely on other partners, decision makers must be able to make rapid and effective trust assessments and decisions. Here, the authors focus on coalition information acquisition and discuss mechanisms for assessing trust and arriving at decisions about how to act when trust can be supplemented by controls. They also discuss future directions for these systems and highlight outstanding challenges.

AAAI Conference 2013 Conference Paper

Multiagent Coordination for Energy Consumption Scheduling in Consumer Cooperatives

• Andreas Veit
• Ying Xu
• Ronghuo Zheng
• Nilanjan Chakraborty
• Katia Sycara

A key challenge to create a sustainable and energyefficient society is in making consumer demand adaptive to energy supply, especially renewable supply. In this paper, we propose a partially-centralized organization of consumers, namely, a consumer cooperative for purchasing electricity from the market. We propose a novel multiagent coordination algorithm to shape the energy consumption of the cooperative. In the cooperative, a central coordinator buys the electricity for the whole group and consumers make their own consumption decisions based on their private consumption constraints and preferences. To coordinate individual consumers under incomplete information, we propose an iterative algorithm in which a virtual price signal is sent by the coordinator to induce consumers to shift demand. We prove that our algorithm converges to the central optimal solution. Additionally we analyze the convergence rate of the algorithm via simulations on randomly generated instances. The results indicate scalability with respect to the number of agents and consumption slots.

AAMAS Conference 2013 Conference Paper

Multiagent Negotiation on Multiple Issues with Incomplete Information

• Ronghuo Zheng
• Nilanjan Chakraborty
• Tinglong Dai
• Katia Sycara

We present a reactive offer generation method for general multiagent multi-attribute negotiation, where the agents have non-linear utility functions and no information about the utility functions of other agents. We prove the convergence of the proposing method and characterize the convergence rate under a finite negotiation time. We also prove that rational agents do not have any incentive to deviate from the proposed strategy. We further present simulation results to demonstrate that on randomly generated problem instances the solution obtained from our protocol is quite close to the Nash bargaining solution.

EAAI Journal 2013 Journal Article

Prognostic normative reasoning

• Jean Oh
• Felipe Meneguzzi
• Katia Sycara
• Timothy J. Norman

Human users planning for multiple objectives in complex environments are subjected to high levels of cognitive workload, which can severely impair the quality of the plans created. This paper describes a software agent that can proactively assist cognitively overloaded users by providing normative reasoning about prohibitions and obligations so that the user can focus on her primary objectives. In order to provide proactive assistance, we develop the notion of prognostic normative reasoning (PNR) that consists of the following steps: (1) recognizing the user's planned activities, (2) reasoning about norms to evaluate those predicted activities, and (3) providing necessary assistance so that the user's activities are consistent with norms. The idea of PNR integrates various AI techniques, namely, user intention recognition, normative reasoning over a user's intention, and planning, execution and replanning for assistive actions. In this paper, we describe an agent architecture for PNR and discuss practical applications.

TIST Journal 2013 Journal Article

Stereotypical trust and bias in dynamic multiagent systems

• Chris Burnett
• Timothy J. Norman
• Katia Sycara

Large-scale multiagent systems have the potential to be highly dynamic. Trust and reputation are crucial concepts in these environments, as it may be necessary for agents to rely on their peers to perform as expected, and learn to avoid untrustworthy partners. However, aspects of highly dynamic systems introduce issues which make the formation of trust relationships difficult. For example, they may be short-lived, precluding agents from gaining the necessary experiences to make an accurate trust evaluation. This article describes a new approach, inspired by theories of human organizational behavior, whereby agents generalize their experiences with previously encountered partners as stereotypes, based on the observable features of those partners and their behaviors. Subsequently, these stereotypes are applied when evaluating new and unknown partners. Furthermore, these stereotypical opinions can be communicated within the society, resulting in the notion of stereotypical reputation. We show how this approach can complement existing state-of-the-art trust models, and enhance the confidence in the evaluations that can be made about trustees when direct and reputational information is lacking or limited. Furthermore, we show how a stereotyping approach can help agents detect unwanted biases in the reputational opinions they receive from others in the society.

AAMAS Conference 2012 Conference Paper

A cognitive architecture for emergency response

• Felipe Meneguzzi
• Siddharth Mehrotra
• James Tittle
• Jean Oh
• Nilanjan Chakraborty
• Katia Sycara
• Michael Lewis

Plan recognition, cognitive workload estimation and human assistance have been extensively studied in the AI and human factors communities, but have seldom been integrated and evaluated as complete systems. In this paper, we develop an assistant agent architecture integrating plan recognition, current and future user information needs, workload estimation and adaptive information presentation to aid an emergency response manager in making high quality decisions under time stress, while avoiding cognitive overload. We describe its main components as well as results for en experiment simulating various possible executions of the emergency response plans used in the real world, comparing reaction time of an assisted versus an unassisted human.

AAMAS Conference 2012 Conference Paper

On the benefits of argumentation schemes in deliberative dialogue

• Alice Toniolo
• Timothy Norman
• Katia Sycara

We present a model of argumentation-based deliberative dialogue for decision making in a team of agents. The model captures conflicts among agents’ plans due to scheduling and causality constraints, and conflicts between actions, goals and norms. We evaluate this model in complex collaborative planning problems to assess its ability to resolve such conflicts. We show that a model grounded on appropriate argumentation schemes facilitates the sharing of relevant information about plan, goal and norm conflicts. Our results show also that this information-sharing leads to more effective conflict resolution.

AAMAS Conference 2012 Conference Paper

Prioritized Shaping of Models for Solving DEC-POMDPs

• Pradeep Varakantham
• William Yeoh
• Prasanna Velagapudi
• Katia Sycara
• Paul Scerri

An interesting class of multi-agent POMDP planning problems can be solved by having agents iteratively solve individual POMDPs, find interactions with other individual plans, shape their transition and reward functions to encourage good interactions and discourage bad ones and then recompute a new plan. D-TREMOR showed that this approach can allow distributed planning for hundreds of agents. However, the quality and speed of the planning process depends on the prioritization scheme used. Lower priority agents shape their models with respect to the models of higher priority agents. In this paper, we introduce a new prioritization scheme that is guaranteed to converge and is empirically better, in terms of solution quality and planning time, than the existing prioritization scheme for some problems.

AAMAS Conference 2012 Conference Paper

Solving Non-Zero Sum Multiagent Network Flow Security Games with Attack Costs

• Steven Okamoto
• Noam Hazon
• Katia Sycara

Moving assets through a transportation network is a crucial challenge in hostile environments such as future battlefields where malicious adversaries have strong incentives to attack vulnerable patrols and supply convoys. Intelligent agents must balance network costs with the harm that can be inflicted by adversaries who are in turn acting rationally to maximize harm while trading off against their own costs to attack. Furthermore, agents must choose their strategies even without full knowledge of their adversaries' capabilities, costs, or incentives. In this paper we model this problem as a non-zero sum game between two players, a sender who chooses flows through the network and an adversary who chooses attacks on the network. We advance the state of the art by: (1) moving beyond the zero-sum games previously considered to non-zero sum games where the adversary incurs attack costs that are not incorporated into the payoff of the sender; (2) introducing a refinement of the Stackelberg equilibrium that is more appropriate to network security games than previous solution concepts; and (3) using Bayesian games where the sender is uncertain of the capabilities, payoffs, and costs of the adversary. We provide polynomial time algorithms for finding equilibria in each of these cases. We also show how our approach can be applied to games where there are multiple adversaries.

TIST Journal 2011 Journal Article

Activity Recognition for Dynamic Multi-Agent Teams

• Gita Sukthankar
• Katia Sycara

This article addresses the problem of activity recognition for dynamic, 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 article 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. We suggest two methods for improving the computational efficiency of the multi-agent plan recognition process in these cases of changing team composition; our proposed approach is robust to sensor observation noise and errors in behavior classification.

IJCAI Conference 2011 Conference Paper

Agent-Oriented Incremental Team and Activity Recognition

• Daniele Masato
• Timothy J. Norman
• Wamberto W. Vasconcelos
• Katia Sycara

Monitoring team activity is beneficial when human teams cooperate in the enactment of a joint plan. Monitoring allows teams to maintain awareness of each other's progress within the plan and it enables anticipation of information needs. Humans find this difficult, particularly in time-stressed and uncertain environments. In this paper we introduce a probabilistic model, based on Conditional Random Fields, to automatically recognise the composition of teams and the team activities in relation to a plan. The team composition and activities are recognised incrementally by interpreting a stream of spatio-temporal observations.

AAMAS Conference 2011 Conference Paper

Allocating Spatially Distributed Tasks in Large, Dynamic Robot Teams

• Steven Okamoto
• Nathan Brooks
• Sean Owens
• Katia Sycara
• Paul Scerri

For an interesting class of emerging applications, a large robot team will need to distributedly allocate many more tasks than there are robots, with dynamically appearing tasks and a limited ability to communicate. The LA-DCOP algorithm can conceptually handle both large-scale problems and multiple tasks per robot, but has key limitations when allocating spatially distributed tasks. In this paper, we extend LA-DCOP with several alternative acceptance rules for robots to determine whether to take on an additional task, given the interaction with the tasks it has already committed to. We show that these acceptance rules dramatically outperform a naive LA-DCOP implementation. In addition, we developed a technique that lets the robots use completely local knowledge to adjust their task acceptance criteria to get the best possible performance at a given communication bandwidth level.

IJCAI Conference 2011 Conference Paper

An Agent Architecture for Prognostic Reasoning Assistance

• Jean Oh
• Felipe Meneguzzi
• Katia Sycara
• Timothy J. Norman

In this paper we describe a software assistant agent that can proactively assist human users situated in a time-constrained environment to perform normative reasoning--reasoning about prohibitions and obligations--so that the user can focus on her planning objectives. In order to provide proactive assistance, the agent must be able to 1) recognize the user's planned activities, 2) reason about potential needs of assistance associated with those predicted activities, and 3) plan to provide appropriate assistance suitable for newly identified user needs. To address these specific requirements, we develop an agent architecture that integrates user intention recognition, normative reasoning over a user's intention, and planning, execution and replanning for assistive actions. This paper presents the agent architecture and discusses practical applications of this approach.

AAMAS Conference 2011 Conference Paper

An Investigation of the Vulnerabilities of Scale Invariant Dynamics in Large Teams

• Robin Glinton
• Paul Scerri
• Katia Sycara

Large heterogeneous teams in a variety of applications must make joint decisions using large volumes of noisy and uncertain data. Often not all team members have access to a sensor, relying instead on information shared by peers to make decisions. These sensors can become permanently corrupted through hardware failure or as a result of the actions of a malicious adversary. Previous work showed that when the trust between agents was tuned to a specific value the resulting dynamics of the system had a property called scale invariance which led to agents reaching highly accurate conclusion with little communication. In this paper we show that these dynamics also leave the system vulnerable to most agents coming to incorrect conclusions as a result of small amounts of anomalous information maliciously injected in the system. We conduct an analysis that shows that the efficiency of scale invariant dynamics is due to the fact that large number of agents can come to correct conclusions when the difference between the percentage of agents holding conflicting opinions is relatively small. Although this allows the system to come to correct conclusions quickly, it also means that it would be easy for an attacker with specific knowledge to tip the balance. We explore different methods for selecting which agents are Byzantine and when attacks are launched informed by the analysis. Our study reveals global system properties that can be used to predict when and where in the network the system is most vulnerable to attack. We use the results of this study to design an algorithm used by agents to effectively attack the network, informed by local estimates of the global properties revealed by our investigation.

AAMAS Conference 2011 Conference Paper

Distributed Model Shaping for Scaling to Decentralized POMDPs with Hundreds of Agents

• Prasanna Velagapudi
• Pradeep Varakantham
• Katia Sycara
• Paul Scerri

The use of distributed POMDPs for cooperative teams has been severely limited by the incredibly large joint policyspace that results from combining the policy-spaces of the individual agents. However, much of the computational cost of exploring the entire joint policy space can be avoided by observing that in many domains important interactions between agents occur in a relatively small set of scenarios, previously defined as coordination locales (CLs). Moreover, even when numerous interactions might occur, given a set of individual policies there are relatively few actual interactions. Exploiting this observation and building on an existing model shaping algorithm, this paper presents D-TREMOR, an algorithm in which cooperative agents iteratively generate individual policies, identify and communicate possible interactions between their policies, shape their models based on this information and generate new policies. D-TREMOR has three properties that jointly distinguish it from previous DEC-POMDP work: (1) it is completely distributed; (2) it is scalable (allowing 100 agents to compute a "good" joint policy in under 6 hours) and (3) it has low communication overhead. D-TREMOR complements these traits with the following key contributions, which ensure improved scalability and solution quality: (a) techniques to ensure convergence; (b) faster approaches to detect and evaluate CLs; (c) heuristics to capture dependencies between CLs; and (d) novel shaping heuristics to aggregate effects of CLs. While the resulting policies are not globally optimal, empirical results show that agents have policies that effectively manage uncertainty and the joint policy is better than policies generated by independent solvers.

AAMAS Conference 2011 Conference Paper

Maximizing Revenue in Symmetric Resource Allocation Systems When User Utilities Exhibit Diminishing Returns

• Roie Zivan
• Miroslav Dud
• iacute; k
• Praveen Paruchuri
• Katia Sycara

Consumers of resources in realistic applications (e. g. , web, multimedia) typically derive diminishing-return utilities from the amount of resource they receive. A resource provider who is deriving an equal amount of revenue from each satisfied user (e. g. , by online advertising), can maximize the number of users by identifying a satisfaction threshold for each user, i. e. , the minimal amount of resource the user requires in order to use the service (rather than drop out). A straightforward approach is to ask users to submit their minimal demands (direct revelation). Unfortunately, self-interested users may try to manipulate the system by submitting untruthful requirements. We propose an incentive-compatible mechanism for maximizing revenue in a resource allocation system where users are ex-ante symmetric (same amount of revenue for any satisfied user) and have diminishing-return utility functions. Users are encouraged by the mechanism to submit their true requirements and the system aims to satisfy as many users as possible. Unlike previous solutions, our mechanism does not require monetary payments from users or downgrading of service. Our mechanism satisfies the number of users within a constant factor of the optimum. Our empirical evaluation demonstrates that in practice, our mechanism can be significantly closer to the optimum than implied by the worst-case analysis. Our mechanism can be generalized to settings when revenue from each user can differ. Also, under some assumptions and adjustments, our mechanism can be used to allocate resource periodically over time.

AAMAS Conference 2011 Conference Paper

Probabilistic Hierarchical Planning over MDPs

• Yuqing Tang
• Felipe Meneguzzi
• Katia Sycara
• Simon Parsons

In this paper, we propose a new approach to using probabilistic hierarchical task networks (HTNs) as an effective method for agents to plan in conditions in which their problem-solving knowledge is uncertain, and the environment is non-deterministic. In such situations it is natural to model the environment as a Markov decision process (MDP). We show that using Earley graphs, it is possible to bridge the gap between HTNs and MDPs. We prove that the size of the Earley graph created for given HTNs is bounded by the total number of tasks in the HTNs and show that from the Earley graph we can then construct a plan for a given task that has the maximum expected value when it is executed in an MDP environment.

AAMAS Conference 2011 Conference Paper

Prognostic Normative Reasoning in Coalition Planning

• Jean Oh
• Felipe Meneguzzi
• Katia Sycara
• Timothy J. Norman

In this paper we describe a software assistant agent that can proactively assist human users situated in a time-constrained coalition environment. The cognitive workload is significantly increased when the user must not only cope with a complex environment, but also with a set of unaccustomed rules that prescribe how the coalition planning process must be carried out. In this context, we introduce the notion of prognostic norm reasoning to predict the user's likely normative violations, allowing the assistant agent to plan and take remedial actions before the violations actually occur. To the best of our knowledge, our approach is the first that manages norms in a proactive and autonomous manner.

AAMAS Conference 2011 Conference Paper

The Evolution of Cooperation in Self-Interested Agent Societies: A Critical Study

• Lisa-Maria Hofmann
• Nilanjan Chakraborty
• Katia Sycara

We study the phenomenon of evolution of cooperation in a society of self-interested agents using repeated games in graphs. A repeated game in a graph is a multiple round game, where, in each round, an agent gains payoff by playing a game with its neighbors and updates its action (state) by using the actions and/or payoffs of its neighbors. The interaction model between the agents is a two-player, two-action (cooperate and defect) Prisoner's Dilemma (PD) game (a prototypical model for interaction between self-interested agents). The conventional wisdom is that the presence of network structure enhances cooperation and current models use multiagent simulation to show evolution of cooperation. However, these results are based on particular combination of interaction game, network model and state update rules (e. g. , PD game on a grid with imitate your best neighbor rule leads to evolution of cooperation). The state-of-the-art lacks a comprehensive picture of the dependence of the emergence of cooperation on model parameters like network topology, interaction game, state update rules and initial fraction of cooperators. We perform a thorough study of the phenomenon of evolution of cooperation using (a) a set of popular categories of networks, namely, grid, random networks, scale-free networks, and small-world networks and (b) a set of cognitively motivated update rules. Our simulation results show that the evolution of cooperation in networked systems is quite nuanced and depends on the combination of network type, update rules and the initial fraction of cooperating agents. We also provide an analysis to support our simulation results.

IJCAI Conference 2011 Conference Paper

Trust Decision-Making in Multi-Agent Systems

• Chris Burnett
• Timothy J. Norman
• Katia Sycara

Trust is crucial in dynamic multi-agent systems, where agents may frequently join and leave, and the structure of the society may often change. In these environments, it may be difficult for agents to form stable trust relationships necessary for confident interactions. Societies may break down when trust between agents is too low to motivate interactions. In such settings, agents should make decisions about who to interact with, given their degree of trust in the available partners. We propose a decision-theoretic model of trust decision making allows controls to be used, as well as trust, to increase confidence in initial interactions. We consider explicit incentives, monitoring and reputation as examples of such controls. We evaluate our approach within a simulated, highly-dynamic multi-agent environment, and show how this model supports the making of delegation decisions when trust is low.

AAMAS Conference 2010 Conference Paper

Analyzing the impact of human bias on human-agent teams in resource allocation domains

• Praveen Paruchuri
• Pradeep Varakantham
• Katia Sycara
• Paul Scerri

As agent-human teams get increasingly deployed in the real-world, agent designers need to take into account that humans and agentshave different abilities to specify preferences. In this paper, we focus on how human biases in specifying preferences for resourcesimpacts the performance of large, heterogeneous teams. In particular, we model the inclination of humans to simplify their preference functions and to exaggerate their utility for desired resources. We then study the effect of these biases on two different problems, which are representative of most resource allocation problems addressed in literature.

AAMAS Conference 2010 Conference Paper

Bootstrapping Trust Evaluations through Stereotypes

• Chris Burnett
• Timothy Norman
• Katia Sycara

In open, dynamic multi-agent systems, agents may form short-term ad-hoc groups, such as coalitions, in order to meet their goals. Trust and reputation are crucial concepts in these environments, as agents must rely on their peers to perform as expected, and learn to avoid untrustworthy partners. However, ad-hoc groups introduce issues which impede the formation of trust relationships. For example, they may be short-lived, precluding agents from gaining the necessary experiences to make an accurate trust evaluation. This paper describes a new approach, inspired by theories of human organisational behaviour, whereby agents generalise their experiences with known partners as \emph{stereotypes} and apply these when evaluating new and unknown partners. We show how this approach can complement existing state of the art trust models, and enhance the confidence in the evaluations that can be made about trustees when direct and reputational information is lacking or limited.

AAMAS Conference 2010 Conference Paper

Deception in Networks of Mobile Sensing Agents

• Viliam Lis
• yacute;
• Roie Zivan
• Katia Sycara
• Michal Péchouček

Recent studies have investigated how a team of mobile sensors can cope withreal world constraints, such as uncertainty in the reward functions, dynamically appearing and disappearing targets, technology failures endchanges in the environment conditions. In this study we consider an additional element, deception by an adversary, which is relevant in many (military) applications. The adversary isexpected to use deception to prevent the sensor team from performing itstasks. We employ a game theoretic model to analyze the expected strategy ofthe adversary and find the best response. More specifically we considerthat the adversary deceptively changes the importance that agents give totargets in the area. The opponent is expected to use camouflage in order to create confusionamong the sensors regarding the importance of targets, and reduce the team'sefficiency in target coverage. We represent a Mobile Sensor Team problem using the Distributed ConstraintOptimization Problem (DCOP) framework. We propose an optimal method for theselection of a position of a single agent facing a deceptive adversary. Thismethod serves as a heuristic for agents to select their position in a fullscale problem with multiple agents in a large area. Our empirical study demonstrates the success of our model as compared withexisting models in the presence of deceptions.

AAMAS Conference 2010 Conference Paper

Exploiting Scale Invariant Dynamics for Efficient Information Propagation in Teams

• Robin Glinton
• Paul Scerri
• Katia Sycara

Large heterogeneous teams will often be in situations where sensor datathat is uncertain and conflicting is shared across a peer-to-peer network. Not every team member will have direct access to sensors and team members will be influenced mostly by teammates with whom they communicatedirectly. In this paper, we investigate the dynamics and emergent behaviors of a large team sharing beliefs to reach conclusions about the world. We find empirically that the dynamics of information propagation in suchbelief sharing systems are characterized by information avalanches of belief changes caused by a single additional sensor reading. The distributionof the size of these avalanches dictates the speed and accuracy with whichthe team reaches conclusions. A key property of the system is that it exhibits qualitatively different dynamics and system performance over smallchanges in system parameter ranges. In one particular range, the systemexhibits behavior known as scale-invariant dynamics which we empiricallyfind to correspond to dramatically more accurate conclusions being reachedby team members. Due to the fact that the ranges are very sensitive toconfiguration details, the parameter ranges over which specific system dynamics occur are extremely difficult to predict precisely. In this paper we(a) develop techniques to mathematically characterize the dynamics of theteam belief propagation (b) obtain through simulations the relation betweenthe dynamics and overall system performance, and (c) develop a novel distributed algorithms that the agents in the team use locally to steer the wholeteam to areas of optimized performance.

AAMAS Conference 2009 Conference Paper

Analyzing the Performance of Randomized Information Sharing

• Prasanna Velagapudi
• Oleg Prokopyev
• Katia Sycara
• Paul Scerri

In large, collaborative, heterogeneous teams, team members often collect information that is useful to other members of the team. Recognizing the utility of such information and delivering it efficiently across a team has been the focus of much research, with proposed approaches ranging from flooding to complex filters and matchmakers. Interestingly, random forwarding of information has been found to be a surprisingly effective information sharing approach in some domains. In this paper, we investigate this phenomenon in detail and show that in certain systems, random forwarding of information performs almost half as well as a globally optimal approach. We present analytic and empirical results comparing random methods with theoretically optimal sharing in small-worlds, scale-free, and random networks. In addition, we demonstrate a method for modeling real domains that allows our results to be applied toward estimating information sharing performance.

IS Journal 2009 Journal Article

Scaling Up Wide-Area-Search-Munition Teams

• Michael Lewis
• Katia Sycara
• Paul Scerri

Wide area search munitions (WASMs) are a cross between an unmanned aerial vehicle (UAV) and a munition. The first of these high-concept munitions, the low-cost autonomous attack system, was a miniature, autonomous WASM capable of broad-area search, identification, and destruction of a range of mobile ground targets. The LoCAAS used a small turbojet engine capable of powering the vehicle for up to 30 minutes and laser radar (ladar) with automatic target recognition to identify potential targets. The original LoCAAS was a fire-and-forget munition designed to operate independently. It flew preprogrammed search patterns until it located a target or ran out of fuel.

AAMAS Conference 2008 Conference Paper

A Decentralized Approach to Cooperative Situation Assessment in Multi-Robot Systems

• Giuseppe Settembre
• Alessandro Farinelli
• Paul Scerri
• Katia Sycara
• Daniele Nardi

To act effectively under uncertainty, multi-robot teams need to accurately estimate the state of the environment. Although individual robots, with uncertain sensors, may not be able to accurately determine the current situation, the team as a whole should have the capability to perform situation assessment. However, sharing all information with all other team mates is not scalable nor is centralization of all information possible. This paper presents a decentralized approach to cooperative situation assessment that balances use of communication bandwidth with the need for good situation assessment. When a robot believes locally that a particular plan should be executed, it sends a proposal for that plan, to one of its team mates. The robot receiving the plan proposal, can either agree with the plan and forward it on, or it can provide sensor information to suggest that an alternative plan might have higher expected utility. Once sufficient robots agree with the proposal, the plan is initiated. The algorithm successfully balances the value of cooperative sensing against the cost of sharing large volumes of information. Experiments verify the utility of the approach, showing that the algorithm dramatically out-performs individual decisionmaking and obtains performance similar to a centralized approach.

AAMAS Conference 2008 Conference Paper

Robust and Efficient Plan Recognition for Dynamic Multi-agent Teams

• Gita Sukthankar
• Katia Sycara

This paper addresses the problem of plan recognition for multiagent teams. Complex multi-agent tasks typically require dynamic teams where the team membership changes over time. Teams split into subteams to work in parallel, merge with other teams to tackle more demanding tasks, and disband when plans are completed. We introduce a new multi-agent plan representation that explicitly encodes dynamic team membership and demonstrate the suitability of this formalism for plan recognition. From our multi-agent plan representation, we extract local temporal dependencies that dramatically prune the hypothesis set of potentially-valid team plans. The reduced plan library can be efficiently processed to obtain the team state history. Naive pruning can be inadvisable when low-level observations are unreliable due to sensor noise and classification errors. In such conditions, we eschew pruning in favor of prioritization and show how our scheme can be extended to rank-order the hypotheses. Experiments show that this robust pre-processing approach ranks the correct plan within the top 10%, even under conditions of severe noise.

AAMAS Conference 2008 Conference Paper

Transitioning Multiagent Technology to UAV Applications

• Paul Scerri
• Tracy Von Gonten
• Gerald Fudge
• Sean Owens
• Katia Sycara

This paper describes the transition of academically developed multiagent technology for UAV coordination to an industrially developed application. The specific application is the use of lightweight UAVs with small Received Signal Strength Indicator sensors to cooperatively locate targets emitting radio frequency signals in a large area. It is shown that general techniques can be effectively transitioned, sometimes with minimal changes. However, clear differences in engineering and testing requirements of academia and commercialization require extensive effort in developing simulation and live flight testbeds. Although the technology has not yet been commercialized, initial live flight testing shows the potential of the approach.

AAMAS Conference 2007 Conference Paper

A Pareto Optimal Model for Automated Multi-attribute Negotiations

• Guoming Lai
• Katia Sycara
• Cuihong Li

This paper presents an applicable model for complex multi-attribute negotiations between autonomous agents. The model adopts a novel protocol which decomposes the original n -dimensional negotiation space into a series of negotiation base lines and in each period agents negotiate locally based on a given base line. A belief based negotiation strategy and an offer enhancement process are proposed for agents to make base offer on the negotiation base line and search for Pareto optimal enhancements of the base offer. The model achieves asymptotic Pareto optimality.

AAMAS Conference 2007 Conference Paper

An Incentive Mechanism for Message Relaying in Unstructured Peer-to-Peer Systems

• Cuihong Li
• Bin Yu
• Katia Sycara

Distributed message relaying is an important function of a peer-topeer system to discover service providers. Existing search protocols in unstructured peer-to-peer systems either create huge burden on communications or cause long response time. Moreover, these systems are also vulnerable to the free riding problem. In this paper we present an incentive mechanism that not only mitigates the free riding problem, but also achieves good system efficiency in message relaying for peer discovery. In this mechanism promised rewards are passed along the message propagation process. A peer is rewarded if a service provider is found via a relaying path that includes this peer. We provide some analytic insights to the symmetric Nash equilibrium strategies of this game, and an approximate approach to calculate this equilibrium. Experiments show that this incentive mechanism brings a system utility generally higher than breadth-first search and random walks, based on both the estimated utility from our approximate equilibrium and the utility generated from learning in the incentive mechanism.

AAMAS Conference 2007 Conference Paper

Locating RF Emitters with Large UAV Teams

• Paul Scerri
• Robin Glinton
• Sean Owens
• Steven Okamoto
• Katia Sycara

AAMAS Conference 2007 Conference Paper

Policy Recognition for Multi-Player Tactical Scenarios

• Gita Sukthankar
• Katia Sycara

This paper addresses the problem of recognizing policies given logs of battle scenarios from multi-player games. The ability to identify individual and team policies from observations is important for a wide range of applications including automated commentary generation, game coaching, and opponent modeling. We define a policy as a preference model over possible actions based on the game state, and a team policy as a collection of individual policies along with an assignment of players to policies. This paper explores two promising approaches for policy recognition: (1) a modelbased system for combining evidence from observed events using Dempster-Shafer theory, and (2) a data-driven discriminative classifier using support vector machines (SVMs). We evaluate our techniques on logs of real and simulated games played using Open Gaming Foundation d20, the rule system used by many popular tabletop games, including Dungeons and Dragons.

IS Journal 2007 Journal Article

Semantic Web Services, Part 2

• David Martin
• John Domingue
• Amit Sheth
• Steve Battle
• Katia Sycara
• Dieter Fensel

In part 2 of this Trends & Controversies installment, we continue exploring the state of the art, current practices, and future directions for Semantic Web services. SWS aims to bring Semantic Web technology - for representing, sharing, and reasoning about knowledge - to bear in Web service contexts. The objective is to enable a fuller, more flexible automation of service provision and use and the construction of more powerful tools and methodologies for working with services.

AAMAS Conference 2007 Conference Paper

Subjective Approximate Solutions for Decentralized POMDPs

• Anton Chechetka
• Katia Sycara

A problem of planning for cooperative teams under uncertainty is a crucial one in multiagent systems. Decentralized partially observable Markov decision processes (DEC-POMDPs) provide a convenient, but intractable model for specifying planning problems in cooperative teams. Compared to the single-agent case, an additional challenge is posed by the lack of free communication between the teammates. We argue, that acting close to optimally in a team involves a tradeoff between opportunistically taking advantage of agent's local observations and being predictable for the teammates. We present a more opportunistic version of an existing approximate algorithm for DEC-POMDPs and investigate the tradeoff. Preliminary evaluation shows that in certain settings oportunistic modification provides significantly better performance.

AAMAS Conference 2006 Conference Paper

A Constraint Optimization Framework for Fractured Robot Teams

• Mary Koes
• Katia Sycara
• Illah Nourbakhsh

AAMAS Conference 2006 Conference Paper

Automated Semantic Web Service Discovery with OWLS-MX

• Matthias Klusch
• Benedikt Fries
• Mahboob Alam Khalid
• Katia Sycara

AAMAS Conference 2006 Conference Paper

Comparing Market and Token-Based Coordination

• Yang Xu
• Paul Scerri
• Katia Sycara
• Michael Lewis

AAMAS Conference 2006 Conference Paper

CSC: Criticality-Sensitive Coordination Pedro Szekely, Marcel Becker, Stephen Fitzpatrick, Gergely Gati, David Hanak, Jing Jin, Gabor Karsai, Rajiv T. Maheswaran, Bob Neches, Craig M. Rogers, Romeo Sanchez, Chris van Buskirk CALO Conflict Negotiation (PTIME and DCOP) Pauline M. Berry, Cory Albright, Emma Bowring, Kenneth Conley, Kenneth Nitz, Jonathan Pearce, Bart Peintner, Shahin Saadati, Milind Tambe, Tomas Uribe, and Neil Yorke-Smith Synergistic Integration of Agent Technologies for Military Simulation

• Sean Owens
• Paul Scerri
• Robin Glinton
• Bin Yu
• Katia Sycara

AAMAS Conference 2006 Conference Paper

No-Commitment Branch and Bound Search for Distributed Constraint Optimization

• Anton Chechetka
• Katia Sycara

AAMAS Conference 2006 Conference Paper

Robust Recognition of Physical Team Behaviors Using Spatio-temporal Models

• Gita Sukthankar
• Katia Sycara

AAMAS Conference 2006 Conference Paper

Scalable and Reliable Data Delivery in Mobile Ad Hoc Sensor Networks

• Bin Yu
• Paul Scerri
• Katia Sycara
• Yang Xu
• Michael Lewis

AAMAS Conference 2006 Conference Paper

Toward an Understanding of the Impact of Personal Assistants on Human Organizations

• Steven Okamoto
• Paul Scerri
• Katia Sycara

AAMAS Conference 2005 Conference Paper

A Cost Minimization Approach to Human Behavior Recognition

• Gita Sukthankar
• Katia Sycara

AAMAS Conference 2004 Conference Paper

Modeling Physical Capabilities of Humanoid Agents Using Motion Capture Data

• Gita Sukthankar
• Michael Mandel
• Katia Sycara
• Jessica Hodgins

AAMAS Conference 2004 Conference Paper

Scaling Teamwork to Very Large Teams

• Scerri Paul
• Yang Xu
• Elizabeth Liao
• Guoming Lai
• Katia Sycara

AAMAS Conference 2003 Conference Paper

Discovery of Infrastructure in Multi-Agent Systems

• Brent K Langley
• Massimo Paolucci
• Katia Sycara

AAMAS Conference 2003 Conference Paper

Multi-agent Learning in Extensive Games with Complete Information

• Pu Huang
• Katia Sycara

AAMAS Conference 2002 Conference Paper

Algorithm for Combinatorial Coalition Formation and Payoff Division in an Electronic Marketplace

• Cuihong Li
• Katia Sycara

AAAI Conference 2000 Conference Paper

Matchmaking to Support Intelligent Agents for Portfolio Management

• Massimo Paolucci
• Katia Sycara
• Sean Owens

A-Match is a matchmaking system that allows agents to enter and exit the system dynamically. It employs a Matchmaker to support agents in the system in their exchange of services. A-Match lets human users interact with the Matchmaker: through the A-Match users find agents that can provide needed services or advertise new agents. The functionality of the A-Match is displayed in the context of the Warren System, a system that supports the user to manage its own stock portfolio.

AIJ Journal 1998 Journal Article

Reaching agreements through argumentation: a logical model and implementation

• Sarit Kraus
• Katia Sycara
• Amir Evenchik

In a multi-agent environment, where self-motivated agents try to pursue their own goals, cooperation cannot be taken for granted. Cooperation must be planned for and achieved through communication and negotiation. We present a logical model of the mental states of the agents based on a representation of their beliefs, desires, intentions, and goals. We present argumentation as an iterative process emerging from exchanges among agents to persuade each other and bring about a change in intentions. We look at argumentation as a mechanism for achieving cooperation and agreements. Using categories identified from human multi-agent negotiation, we demonstrate how the logic can be used to specify argument formulation and evaluation. We also illustrate how the developed logic can be used to describe different types of agents. Furthermore, we present a general Automated Negotiation Agent which we implemented, based on the logical model. Using this system, a user can analyze and explore different methods to negotiate and argue in a noncooperative environment where no centralized mechanism for coordination exists. The development of negotiating agents in the framework of the Automated Negotiation Agent is illustrated with an example where the agents plan, act, and resolve conflicts via negotiation in a Blocks World environment.

AIJ Journal 1995 Journal Article

Backtracking techniques for the job shop scheduling constraint satisfaction problem

• Norman Sadeh
• Katia Sycara
• Yalin Xiong

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.

AIJ Journal 1995 Journal Article

CABINS: a framework of knowledge acquisition and iterative revision for schedule improvement and reactive repair

• Kazuo Miyashita
• Katia Sycara

Practical scheduling problems generally require allocation of resources in the presence of a large, diverse and typically conflicting set of constraints and optimization criteria. The ill-structuredness of both the solution space and the desired objectives make scheduling problems difficult to formalize. This paper describes a case-based learning method for acquiring context-dependent user optimization preferences and tradeoffs and using them to incrementally improve schedule quality in predictive scheduling and reactive schedule management in response to unexpected execution events. The approach, implemented in the CABINS system, uses acquired user preferences to dynamically modify search control to guide schedule improvement. During iterative repair, cases are exploited for: (1) repair action selection, (2) evaluation of intermediate repair results and (3) recovery from revision failures. The method allows the system to dynamically switch between repair heuristic actions, each of which operates with respect to a particular local view of the problem and offers selective repair advantages. Application of a repair action tunes the search procedure to the characteristics of the local repair problem. This is achieved by dynamic modification of the search control bias. There is no a priori characterization of the amount of modification that may be required by repair actions. However, initial experimental results show that the approach is able to (a) capture and effectively utilize user scheduling preferences that were not present in the scheduling model, (b) produce schedules with high quality, without unduly sacrificing efficiency in predictive schedule generation and reactive response to unpredictable execution events along a variety of criteria that have been recognized as important in real operating environments.

IJCAI Conference 1995 Conference Paper

Improving System Performance in Case-Based Iterative Optimization through Knowledge Filtering

• Kazuo Miyashita
• Katia Sycara

Adding knowledge to a knowledge-based system is not monotonically beneficial. We discuss and experimentally validate this observation in the context of CABINS, a system that learns control knowledge for iterative repair in ill-structured optimization problems. In CAB- INS, situation-dependent user's decisions that guide the repair process are captured in cases together with contextual problem information. During iterative revision in CABINS, cases are exploited for both selection of repair actions and evaluation of repair results. In this paper, we experimentally demonstrated that unfiltered learned knowledge can degrade problem solving performance. We developed and experimentally evaluated the effectiveness of a set of knowledge filtering strategies that are designed to increase problem solving efficiency of the intractable iterative optimization process without sacrificing solution quality. These knowledge filtering strategies utilize progressive case base retrievals and failure information to (1) validate the effectiveness of selected repair actions and (2) give-up further repair if the likelihood of success is low. The filtering strategies were experimentally evaluated in the context of job-shop scheduling, a well known ill-structured problem.

AAAI Conference 1994 Conference Paper

Case-Based Acquisition of User Preferences for Solution Improvement in Ill-Structured Domains

• Katia Sycara

1 We have developed an approach to acquire complicated user optimization criteria and use them to guide iterative solution improvement. The effectiveness of the approach was tested on job shop scheduling problems. The ill-structuredness of the domain and the desired optimization objectives in real-life problems, such as factory scheduling, makes the problems difficult to formalize and costly to solve. Current optimization technology requires explicit global optimization criteria in order to control its search for the optimal solution. But often, a user’ s optimization preferences are state-dependent and cannot be expressed in terms of a single global optimization criterion. In our approach, the optimization preferences are represented implicitly and extensionally in a case base. Experimental results in job shop scheduling problems support the hypotheses that our approach (1) is capable of capturing diverse user optimization preferences and re-using them to guide solution quality improvement, (2) is robust in the sense that it improves solution quality independent of the method of initial solution generation, and (3) produces high quality solutions, which are comparable with solutions generated by traditional iterative optimization techniques, such as simulated annealing, at much lower computational cost.