Large multimodal foundation models, particularly in the domains of language and vision, have significantly advanced various tasks, including robotics, autonomous driving, information retrieval, and grounding. However, many of these models perceive objects as indivisible, overlooking the components that constitute them. Understanding these components and their associated affordances provides valuable insights into an object’s functionality, which is fundamental for performing a wide range of tasks. In this work, we introduce a novel real-world benchmark, InstructPart, comprising hand-labeled part segmentation annotations and task-oriented instructions to evaluate the performance of current models in understanding and executing part-level tasks within everyday contexts. Through our experiments, we demonstrate that task-oriented part segmentation remains a challenging problem, even for state-of-the-art Vision-Language Models (VLMs). In addition to our benchmark, we introduce a simple baseline that achieves a twofold performance improvement through fine-tuning with our dataset. With our dataset and benchmark, we aim to facilitate research on task-oriented part segmentation and enhance the applicability of VLMs across various domains, including robotics, virtual reality, information retrieval, and other related fields. Project website: https://zifuwan.github.io/InstructPart/.

Recent Large Vision-Language Models (LVLMs) have introduced a new paradigm for understanding and reasoning about image input through textual responses. Although they have achieved remarkable performance across a range of multi-modal tasks, they face the persistent challenge of hallucination, which introduces practical weaknesses and raises concerns about their reliable deployment in real-world applications. Existing work has explored contrastive decoding approaches to mitigate this issue, where the output of the original LVLM is compared and contrasted with that of a perturbed version. However, these methods require two or more queries that slow down LVLM response generation, making them less suitable for real-time applications. To overcome this limitation, we propose ONLY, a training-free decoding approach that requires only a single query and a one-layer intervention during decoding, enabling efficient real-time deployment. Specifically, we enhance textual outputs by selectively amplifying crucial textual information using a text-to-visual entropy ratio for each token. Extensive experimental results demonstrate that our proposed ONLY consistently outperforms state-of-the-art methods across various benchmarks while requiring minimal implementation effort and computational cost. Code is available at https://github.com/zifuwan/ONLY.

Semantic segmentation relying solely on RGB data often struggles in challenging conditions such as low illumination and obscured views, limiting its reliability in critical applications like autonomous driving. To address this, integrating additional thermal radiation data with RGB images demonstrates enhanced performance and robustness. However, how to effectively reconcile the modality discrepancies and fuse the RGB and thermal features remains a well-known challenge. In this work, we address this challenge from a novel spectral perspective. We observe that the multi-modal features can be categorized into two spectral components: low-frequency features that provide broad scene context, including color variations and smooth areas, and high-frequency features that capture modality-specific details such as edges and textures. Inspired by this, we propose the Spectral-aware Global Fusion Network (SGFNet) to effectively enhance and fuse the multi-modal features by explicitly modeling the interactions between the high-frequency, modality-specific features. Our experimental results demonstrate that SGFNet outperforms the state-of-the-art methods on the MFNet and PST900 datasets.

While recent Large Vision-Language Models (LVLMs) have shown remarkable performance in multi-modal tasks, they are prone to generating hallucinatory text responses that do not align with the given visual input, which restricts their practical applicability in real-world scenarios. In this work, inspired by the observation that the text-to-image generation process is the inverse of image-conditioned response generation in LVLMs, we explore the potential of leveraging text-to-image generative models to assist in mitigating hallucinations in LVLMs. We discover that generative models can offer valuable self-feedback for mitigating hallucinations at both the response and token levels. Building on this insight, we introduce self-correcting Decoding with Generative Feedback (DeGF), a novel training-free algorithm that incorporates feedback from text-to-image generative models into the decoding process to effectively mitigate hallucinations in LVLMs. Specifically, DeGF generates an image from the initial response produced by LVLMs, which acts as an auxiliary visual reference and provides self-feedback to verify and correct the initial response through complementary or contrastive decoding. Extensive experimental results validate the effectiveness of our approach in mitigating diverse types of hallucinations, consistently surpassing state-of-the-art methods across six benchmarks. Code is available at https://github.com/zhangce01/DeGF.

Decomposing geometry, materials and lighting from a set of images, namely inverse rendering, has been a long-standing problem in computer vision and graphics. Recent advances in neural rendering enable photo-realistic and plausible inverse rendering results. The emergence of 3D Gaussian Splatting has boosted it to the next level by showing real-time rendering potentials. An intuitive finding is that the models used for inverse rendering do not take into account the dependency of opacity w.r.t. material properties, namely cross section, as suggested by optics. Therefore, we develop a novel approach that adds this dependency to the modeling itself. Inspired by radiative transfer, we augment the opacity term by introducing a neural network that takes as input material properties to provide modeling of cross section and a physically correct activation function. The gradients for material properties are therefore not only from color but also from opacity, facilitating a constraint for their optimization. Therefore, the proposed method incorporates more accurate physical properties compared to previous works. We implement our method into 3 different baselines that use Gaussian Splatting for inverse rendering and achieve significant improvements universally in terms of novel view synthesis and material modeling.

We introduce a novel distributed source seeking framework, DIAS, designed for multi-robot systems in scenarios where the number of sources is unknown and potentially exceeds the number of robots. Traditional robotic source seeking methods typically focused on directing each robot to a specific strong source and may fall short in comprehensively identifying all potential sources. DIAS addresses this gap by introducing a hybrid controller that identifies the presence of sources and then alternates between exploration for data gathering and exploitation for guiding robots to identified sources. It further enhances search efficiency by dividing the environment into Voronoi cells and approximating source density functions based on Gaussian process regression. Additionally, DIAS can be integrated with existing source seeking algorithms. We compare DIAS with existing algorithms, including DOSS and GMES in simulated gas leakage scenarios where the number of sources outnumbers or is equal to the number of robots. The numerical results show that DIAS outperforms the baseline methods in both the efficiency of source identification by the robots and the accuracy of the estimated environmental density function.

Exploration is a critical challenge in robotics, centered on understanding unknown environments. In this work, we focus on structured indoor environments, which often exhibit predictable, repeating patterns. Conventional frontier-based exploration approaches have difficulty leveraging this predictability, relying on simple heuristics such as ‘closest first’ for exploration. More recent deep learning-based methods predict unknown regions of the map for information gain computation, but these approaches are often sensitive to the predicted map quality or fail to account for sensor coverage. To overcome these issues, our key insight is to jointly reason over what the robot can observe and its uncertainty to calculate probabilistic information gain. We introduce MapEx, a new exploration framework that uses predicted maps to form probabilistic sensor model for information gain estimation. MapEx generates multiple predicted maps based on observed information, and takes into consideration both the computed variances of predicted maps and estimated visible area to estimate the information gain of a given viewpoint. Experiments on the real-world KTH dataset showed on average 12.4% improvement than representative map-prediction based exploration and 25.4% improvement than nearest frontier approach. Website: https://mapex-explorer.github.io/

Learning to predict spatiotemporal (ST) environmental processes from a sparse set of samples collected autonomously is a difficult task from both a sampling perspective (collecting the best sparse samples) and from a learning perspective (predicting the next timestep). In this work, we focus on investigating the sample collection process via multirobot informative path planning. We present an approach for incorporating multi-robot informative path planning into a spatiotemporal adaptive sampling framework while considering path length constraints for sampling location selection. We also incorporate informative path planning to determine the best path to collect samples along while en route to collecting the desired sample. We achieve this in a decentralized manner by decoupling the process into two stages: the first stage uses our spatiotemporal mixture of Gaussian Processes (STMGP) model to determine the most informative sampling location via a mutual information lower bound heuristic and the second stage plans an informative path to collect the desired sample and other additional informative samples via submodular function optimization. Moreover, we effectively leverage peer-to-peer communication to enable coordination. Simulation results on real-world spatiotemporal data are provided to validate the effectiveness of our proposed approach.

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.

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.

Large-scale pre-trained Vision-Language Models (VLMs) have exhibited impressive zero-shot performance and transferability, allowing them to adapt to downstream tasks in a data-efficient manner. However, when only a few labeled samples are available, adapting VLMs to distinguish subtle differences between similar classes in specific downstream tasks remains challenging. In this work, we propose a Simple yet effective Negative Learning approach, SimNL, to more efficiently exploit the task-specific knowledge from few-shot labeled samples. Unlike previous methods that focus on identifying a set of representative positive features defining “what is a {CLASS} ”, SimNL discovers a complementary set of negative features that define “what is not a {CLASS}”, providing additional insights that supplement the positive features to enhance task-specific recognition capability. Further, we identify that current adaptation approaches are particularly vulnerable to potential noise in the fewshot sample set. To mitigate this issue, we introduce a plug-and-play few-shot instance reweighting technique to suppress noisy outliers and amplify clean samples for more stable adaptation. Our extensive experimental results across 15 datasets validate that the proposed SimNL outperforms existing state-of-the-art methods on both few-shot learning and domain generalization tasks while achieving competitive computational efficiency. Code is available at https://github.com/zhangce01/SimNL.

Multi-modal semantic segmentation significantly enhances AI agents' perception and scene understanding, especially under adverse conditions like low-light or overexposed environments. Leveraging additional modalities (X-modality) like thermal and depth alongside traditional RGB provides complementary information, enabling more robust and reliable prediction. In this work, we introduce Sigma, a Siamese Mamba network for multi-modal semantic segmentation utilizing the advanced Mamba. Unlike conventional methods that rely on CNNs, with their limited local receptive fields, or Vision Transformers (ViTs), which offer global receptive fields at the cost of quadratic complexity, our model achieves global receptive fields with linear complexity. By employing a Siamese encoder and innovating a Mamba-based fusion mechanism, we effectively select essential information from different modalities. A decoder is then developed to enhance the channel-wise modeling ability of the model. Our proposed method is rigorously evaluated on both RGB-Thermal and RGB-Depth semantic segmentation tasks, demonstrating its superiority and marking the first successful application of State Space Models (SSMs) in multi-modal perception tasks. Code is available at https://github.com/zifuwan/Sigma.

Being able to understand visual scenes is a precursor for many downstream tasks, including autonomous driving, robotics, and other vision-based approaches. A common approach enabling the ability to reason over visual data is Scene Graph Generation (SGG); however, many existing approaches assume undisturbed vision, i.e., the absence of real-world corruptions such as fog, snow, smoke, as well as non-uniform perturbations like sun glare or water drops. In this work, we propose a novel SGG benchmark containing procedurally generated weather corruptions and other trans-formations over the Visual Genome dataset. Further, we in-troduce a corresponding approach, Hierarchical Knowledge Enhanced Robust Scene Graph Generation (HiKER-SGG), providing a strong baseline for scene graph generation under such challenging setting. At its core, HiKER-SGG utilizes a hierarchical knowledge graph in order to refine its predictions from coarse initial estimates to detailed predictions. In our extensive experiments, we show that HiKER-SGG does not only demonstrate superior performance on corrupted images in a zero-shot manner, but also outperforms current state-of-the-art methods on uncorrupted SGG tasks. Code is available at https://github.com/zhangce01/HiKER-SGG.

Task-oriented grasping of unfamiliar objects is a necessary skill for robots in dynamic in-home environments. Inspired by the human capability to grasp such objects through intuition about their shape and structure, we present a novel zero-shot task-oriented grasping method leveraging a geometric decomposition of the target object into simple, convex shapes that we represent in a graph structure, including geometric attributes and spatial relationships. Our approach employs minimal essential information – the object’s name and the intended task – to facilitate zero-shot task-oriented grasping. We utilize the commonsense reasoning capabilities of large language models to dynamically assign semantic meaning to each decomposed part and subsequently reason over the utility of each part for the intended task. Through extensive experiments on a real-world robotics platform, we demonstrate that our grasping approach’s decomposition and reasoning pipeline is capable of selecting the correct part in 92% of the cases and successfully grasping the object in 82% of the tasks we evaluate. Additional videos, experiments, code, and data are available on our project website: https://shapegrasp.github.io/.

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.

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

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.

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.

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/.

While Large Language Models (LLMs) have demonstrated impressive accomplishments in both reasoning and planning, their abilities in multi-agent collaborations remains largely unexplored.This study evaluates LLMbased agents in a multi-agent cooperative text game with Theory of Mind (ToM) inference tasks, comparing their performance with Multi-Agent Reinforcement Learning (MARL) and planning-based baselines.We observed evidence of emergent collaborative behaviors and high-order Theory of Mind capabilities among LLM-based agents.Our results reveal limitations in LLM-based agents' planning optimization due to systematic failures in managing long-horizon contexts and hallucination about the task state.We explore the use of explicit belief state representations to mitigate these issues, finding that it enhances task performance and the accuracy of ToM inferences for LLMbased agents.

Action advising is a knowledge transfer technique for reinforcement learning based on the teacher-student paradigm. An expert teacher provides advice to a student during training in order to improve the student's sample efficiency and policy performance. Such advice is commonly given in the form of state-action pairs. However, it makes it difficult for the student to reason with and apply to novel states. We introduce Explainable Action Advising, in which the teacher provides action advice as well as associated explanations indicating why the action was chosen. This allows the student to self-reflect on what it has learned, enabling advice generalization and leading to improved sample efficiency and learning performance - even in environments where the teacher is sub-optimal. We empirically show that our framework is effective in both single-agent and multi-agent scenarios, yielding improved policy returns and convergence rates when compared to state-of-the-art methods.

Communication enables agents to cooperate to achieve their goals. Learning when to communicate, i.e., sparse (in time) communication, and whom to message is particularly important when bandwidth is limited. However, recent work in learning sparse individualized communication suffers from high variance during training, where decreasing communication comes at the cost of decreased reward, particularly in cooperative tasks. We use the information bottleneck to reframe sparsity as a representation learning problem, which we show naturally enables lossless sparse communication at lower budgets than prior art. In this paper, we propose a method for true lossless sparsity in communication via Information Maximizing Gated Sparse Multi-Agent Communication (IMGS-MAC). Our model uses two individualized regularization objectives, an information maximization autoencoder and sparse communication loss, to create informative and sparse communication. We evaluate the learned communication ‘language’ through direct causal analysis of messages in non-sparse runs to determine the range of lossless sparse budgets, which allow zero-shot sparsity, and the range of sparse budgets that will inquire a reward loss, which is minimized by our learned gating function with few-shot sparsity. To demonstrate the efficacy of our results, we experiment in cooperative multi-agent tasks where communication is essential for success. We evaluate our model with both continuous and discrete messages. We focus our analysis on a variety of ablations to show the effect of message representations, including their properties, and lossless performance of our model.

We present the Wildland-fire Infrared Thermal (WIT-UAS) dataset for long-wave infrared sensing of crew and vehicle assets amidst prescribed wildland fire environments. While such a dataset is crucial for safety monitoring in wildland fire applications, to the authors' awareness, no such dataset focusing on assets near fire is publicly available. Presumably, this is due to the barrier to entry of collaborating with fire management personnel. We present two related data subsets: WIT-UAS-ROS consists of full ROS bag files containing sensor and robot data of UAS flight over the fire, and WIT-UAS-Image contains hand-labeled long-wave infrared (LWIR) images extracted from WIT-UAS-ROS. Our dataset is the first to focus on asset detection in a wildland fire environment. We show that thermal detection models trained without fire data frequently detect false positives by classifying fire as people. By adding our dataset to training, we show that the false positive rate is reduced significantly. Yet asset detection in wildland fire environments is still significantly more challenging than detection in urban environments, due to dense obscuring trees, greater heat variation, and overbearing thermal signal of the fire. We publicize this dataset to encourage the community to study more advanced models to tackle this challenging environment. The dataset, code and pretrained models are available at https://github.com/castacks/WIT-UAS-Dataset.

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.

In this paper we describe the intervention framework of ATLAS, an artificial socially intelligent agent that advises teams. The framework treats interventions as atomic components, and manages the lifecycle of each intervention through presentation, as well as followups to interventions. The key benefit of this framework is that it allows for rapid development of scenario-specific Interventions that leverage scenario-agnostic team models. The implementation of this framework is reported for three player teams in a Search and Rescue task simulated in Minecraft. Low competence teams advised by ATLAS improved more between first and second trials than those with a human advisor while the reverse was found for high competence. Four times as many interventions were proposed as were presented. 15 % of advice was withheld to avoid repetitive advice, excessive rate of advice, and needlessly advising high performing teams, while a Theory of Mind model and delay for confirmation mechanism filtered out other unnecessary advice.

In this paper, we propose a novel personalized decision support system that combines Theory of Mind (ToM) modeling and explainable Reinforcement Learning (XRL) to provide effective and interpretable interventions. Our method leverages DRL to provide expert action recommendations while incorporating ToM modeling to understand users' mental states and predict their future actions, enabling appropriate timing for intervention. To explain interventions, we use counterfactual explanations based on RL's feature importance and users' ToM model structure. Our proposed system generates accurate and personalized interventions that are easily interpretable by end-users. We demonstrate the effectiveness of our approach through a series of crowd-sourcing experiments in a simulated team decision-making task, where our system outperforms control baselines in terms of task performance. Our proposed approach is agnostic to task environment and RL model structure, therefore has the potential to be generalized to a wide range of applications.

In this paper, we present a heterogeneous robot swarm system that can physically couple with each other to form functional structures and dynamically decouple to perform individual tasks. The connection between robots can be formed with a passive coupling mechanism, ensuring minimum energy consumption during coupling and decoupling behavior. The heterogeneity of the system enables the robots to perform structural enhancement configurations based on specific environmental requirements. We propose a connection-pair oriented configuration control algorithm to form different assemblies. We show experiments of up to nine robots performing the coupling, gap-crossing, and decoupling behaviors.

Theory of Mind (ToM) refers to the ability to make inferences about other’s mental states. Such ability is fundamental for human social activities such as empathy, teamwork, and communication. As intelligent agents come to be involved in diverse human-agent teams, they will also be expected to be socially intelligent in order to become effective teammates. In this paper, we describe a computational ToM model which observes team behaviors and infers their mental states in a urban search and rescue (US&R) task. Our modular ToM model approximates human inference by explicitly representing beliefs, belief updates, and action prediction/generation using Deep Neural Networks (DNNs). To validate our model we compare its performance to the gold standard of human observers asked to make the same inferences. The ToM model proved superior to the average judgments of human observers on all four tests of inference and better than 90th percentile observers on three of the four. While the learning bias provided by modularizing belief and prediction proved sufficient for the simple inferences tested, substantial refinement will be needed to replicate the complex nuanced chains of inference observed in human social interaction.

In this paper, we consider the dynamic multi-robot distribution problem where a heterogeneous group of networked robots is tasked to spread out and simultaneously move towards multiple moving task areas while maintaining connectivity. The heterogeneity of the system is characterized by various categories of units and each robot carries different numbers of units per category representing heterogeneous capabilities. Every task area with different importance demands a total number of units contributed by all of the robots within its area. Moreover, we assume the importance and the total number of units requested from each task area is initially unknown. The robots need first to explore, i.e., reach those areas, and then be allocated to the tasks so to fulfill the requirements. The multi-robot distribution problem is formulated as designing controllers to distribute the robots that maximize the overall task fulfillment while minimizing the traveling costs in presence of connectivity constraints. We propose a novel connectivity-aware multi-robot redistribution approach that accounts for dynamic task allocation and connectivity maintenance for a heterogeneous robot team. Such an approach could generate sub-optimal robot controllers so that the amount of total unfulfilled requirements of the tasks weighted by their importance is minimized and robots stay connected at all times. Simulation and numerical results are provided to demonstrate the effectiveness of the proposed approaches.

Multi-robot systems can perform task-related collaborative behaviors while maintaining connectivity within the system. However, some robots may fail to execute tasks or converge relatively slowly due to connectivity constraints. We consider the case that some robots may not have tasks assigned at a certain time frame, and they may help the task robots to achieve their goals by forming a connectivity graph with flexible topology. Therefore, we introduce a topology correction controller to provide flexibility for the task robots to perform task behaviors by modifying the topology of the connectivity graph for a faster convergence rate. We propose a distributed approach of blending weighted rendezvous and weighted flocking to form the correction controller. We prove that this scheme can guarantee a faster convergence rate and provide flexible connectivity graph topology. We then present our result of a system of up to thirty robots in various cluttered environments and show that our approach of behavior combination is robust and scalable.

Robot swarms have been shown to improve the ability of individual robots by inter-robot collaboration. In this paper, we present the PuzzleBots - a low-cost robotic swarm system where robots can physically couple with each other to form functional structures with minimum energy consumption while maintaining individual mobility to navigate within the environment. Each robot has knobs and holes along the sides of its body so that the robots can couple by inserting the knobs into the holes. We present the characterization of knob design and the result of gap-crossing behavior with up to nine robots. We show with hardware experiments that the robots are able to couple with each other to cross gaps and decouple to perform individual tasks. We anticipate the PuzzleBots will be useful in unstructured environments as individuals and coupled systems in real-world applications.

Leader-follower navigation is a popular class of multi-robot algorithms where a leader robot leads the follower robots in a team. The leader has specialized capabilities or mission critical information (e.g. goal location) that the followers lack, and this makes the leader crucial for the mission’s success. However, this also makes the leader a vulnerability -an external adversary who wishes to sabotage the robot team’s mission can simply harm the leader and the whole robot team’s mission would be compromised. Since robot motion generated by traditional leader-follower navigation algorithms can reveal the identity of the leader, we propose a defense mechanism of hiding the leader’s identity by ensuring the leader moves in a way that behaviorally camouflages it with the followers, making it difficult for an adversary to identify the leader. To achieve this, we combine Multi-Agent Reinforcement Learning, Graph Neural Networks and adversarial training. Our approach enables the multi-robot team to optimize the primary task performance with leader motion similar to follower motion, behaviorally camouflaging it with the followers. Our algorithm outperforms existing work that tries to hide the leader’s identity in a multi-robot team by tuning traditional leader-follower control parameters with Classical Genetic Algorithms. We also evaluated human performance in inferring the leader’s identity and found that humans had lower accuracy when the robot team used our proposed navigation algorithm.

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.

To build an agent providing assistance to human rescuers in an urban search and rescue task, it is crucial to understand not only human actions but also human beliefs that may influence the decision to take these actions. Developing data-driven models to predict a rescuer’s strategies for navigating the environment and triaging victims requires costly data collection and training for each new environment of interest. Transfer learning approaches can be used to mitigate this challenge, allowing a model trained on a source environment/task to generalize to a previously unseen target environment/task with few training examples. In this paper, we investigate transfer learning (a) from a source environment with smaller number of types of injured victims to one with larger number of victim injury classes and (b) from a smaller and simpler environment to a larger and more complex one for navigation strategy. Inspired by hierarchical organization of human spatial cognition, we used graph division to represent spatial knowledge, and Transfer Learning Diffusion Convo-lutional Recurrent Neural Network (TL-DCRNN), a spatial and temporal graph-based recurrent neural network suitable for transfer learning, to predict navigation. To abstract the rescue strategy from a rescuer’s field-of-view stream, we used attention-based LSTM networks. We experimented on various transfer learning scenarios and evaluated the performance using mean average error. Results indicated our assistant agent can improve predictive accuracy and learn target tasks faster when equipped with transfer learning methods.

When developing AI systems that interact with humans, it is essential to design both a system that can understand humans, and a system that humans can understand. Most deep network based agent-modeling approaches are 1) not interpretable and 2) only model external behavior, ignoring internal mental states, which potentially limits their capability for assistance, interventions, discovering false beliefs, etc. To this end, we develop an interpretable modular neural framework for modeling the intentions of other observed entities. We demonstrate the efficacy of our approach with experiments on data from human participants on a search and rescue task in Minecraft, and show that incorporating interpretability can significantly increase predictive performance under the right conditions.

The ability to collaborate with previously unseen human teammates is crucial for artificial agents to be effective in human-agent teams (HATs). Due to individual differences and complex team dynamics, it is hard to develop a single agent policy to match all potential teammates. In this article, we study both human-human and HAT in a dyadic cooperative task, Team Space Fortress. Results show that the team performance is influenced by both players’ individual skill level and their ability to collaborate with different teammates by adopting complementary policies. Based on human-human team results, we propose an adaptive agent that identifies different human policies and assigns a complementary partner policy to optimize team performance. The adaptation method relies on a novel similarity metric to infer human policy and then selects the most complementary policy from a pretrained library of exemplar policies. We conducted human-agent experiments to evaluate the adaptive agent and examine mutual adaptation in HAT. Results show that both human adaptation and agent adaptation contribute to team performance.

In many cases the multi-robot systems are desired to execute simultaneously multiple behaviors with different controllers, and sequences of behaviors in real time, which we call behavior mixing. Behavior mixing is accomplished when different subgroups of the overall robot team change their controllers to collectively achieve given tasks while maintaining connectivity within and across subgroups in one connected communication graph. In this paper, we present a provably minimum connectivity maintenance framework to ensure the subgroups and overall robot team stay connected at all times while providing the highest freedom for behavior mixing. In particular, we propose a real-time distributed Minimum Connectivity Constraint Spanning Tree (MCCST) algorithm to select the minimum inter-robot connectivity constraints preserving subgroup and global connectivity that are least likely to be violated by the original controllers. With the employed safety and connectivity barrier certificates for the activated connectivity constraints and collision avoidance, the behavior mixing controllers are thus minimally modified from the original controllers. We demonstrate the effectiveness and scalability of our approach via simulations of up to 100 robots with multiple behaviors.

In this work, we focus on developing algorithms to maintain and enhance the connectivity of a multi-robot system with minimal disruption to the primary tasks that the robots are performing. Such algorithms are useful for collaborating robots to be resilient to reduction in connectivity of the communication graph of the robot team when robots can arrive or leave. These algorithms are also useful in a supervisory control setting when an operator wants to enhance the connectivity of the robot team. In contrast to many existing works that can only maintain the current connectivity of the multi-robot graph, we propose a generalized connectivity control framework that allows for reconfiguration of the multi-robot system to provably satisfy any connectivity demand, while minimally disrupting the execution of their original tasks. In particular, we propose a novel k-Connected Minimum Resilient Graph (k-CMRG) algorithm to compute an optimal k-connectivity graph that minimally constrains the robots' original task-related motion, and employ the Finite-Time Convergence Control Barrier Function (FCBF) to enforce the pairwise robot motion constraints defined by the edges of the graph. The original controllers are minimally modified to drive the robots and form the k-CMRG. We demonstrate the effectiveness of our approach via simulations in the presence of multiple tasks and robot failures.

Multi-robot systems are widely used in environmental exploration and modeling, especially in hazardous environments. However, different types of robots are limited by different mobility, battery life, sensor type, etc. Heterogeneous robot systems are able to utilize various types of robots and provide solutions where robots are able to compensate each other with their different capabilities. In this paper, we consider the problem of sampling and modeling environmental characteristics with a heterogeneous team of robots. To utilize heterogeneity of the system while remaining computationally tractable, we propose an environmental partitioning approach that leverages various robot capabilities by forming a uniformly defined heterogeneity cost space. We combine with the mixture of Gaussian Processes model-learning framework to adaptively sample and model the environment in an efficient and scalable manner. We demonstrate our algorithm in field experiments with ground and aerial vehicles.

Human behaviors are often prohibited, or permitted by social norms. Therefore, if autonomous agents interact with humans, they also need to reason about various legal rules, social and ethical social norms, so they would be trusted and accepted by humans. Inverse Reinforcement Learning (IRL) can be used for the autonomous agents to learn social norm-compliant behavior via expert demonstrations. However, norms are context-sensitive, i.e. different norms get activated in different contexts. For example, the privacy norm is activated for a domestic robot entering a bathroom where a person may be present, whereas it is not activated for the robot entering the kitchen. Representing various contexts in the state space of the robot, as well as getting expert demonstrations under all possible tasks and contexts is extremely challenging. Inspired by recent work on Modularized Normative MDP (MNMDP) and early work on context-sensitive RL, we propose a new IRL framework, Context-Sensitive Norm IRL (CNIRL). CNIRL treats states and contexts separately, and assumes that the expert determines the priority of every possible norm in the environment, where each norm is associated with a distinct reward function. The agent chooses the action to maximize its cumulative rewards. We present the CNIRL model and show that its computational complexity is scalable in the number of norms. We also show via two experimental scenarios that CNIRL can handle problems with changing context spaces.

One main challenge to robot decision making in human-robot teams involves predicting the intents of a human team member through observations of the human's behavior. Inverse Reinforcement Learning (IRL) is one approach to predicting human intent, however, such approaches typically assume that the human's intent is stationary. Furthermore, there are few approaches that identify when the human's intent changes during observations. Modeling human decision making as a Markov decision process, we address these two limitations by maintaining a belief over the reward parameters of the model (representing the human's preference for tasks or goals), and updating the parameters using IRL estimates from short windows of observations. We posit that a human's preferences can change with time, due to gradual drift of preference and/or discrete, step-wise changes of intent. Our approach maintains an estimate of the human's preferences under such conditions, and is able to identify changes of intent based on the divergence between subsequent belief updates. We demonstrate that our approach can effectively track dynamic reward parameters and identify changes of intent in a simulated environment, and that this approach can be leveraged by a robot team member to improve team performance.

The reported study compares groups of 120 participants each, from the United States (U.S.), Taiwan (TW), and Turkey (TK), interacting with versions of an automated path planner that vary in transparency and degree of automation. The nationalities were selected in accordance with the theory of cultural syndromes as representatives of Dignity (U.S.), Face (TW), and Honor (TK) cultures, and were predicted to differ in readiness to trust automation, degree of transparency required to use automation, and willingness to use systems with high degrees of automation. Three experimental conditions were tested. In the first, highlight, path conflicts were highlighted leaving rerouting to the participant. In the second, replanner made requests for permission to reroute when a path conflict was detected. The third combined condition increased transparency of the replanner by combining highlighting with rerouting to make the conflict on which decision was based visible to the user. A novel framework relating transparency, stages of automation, and trust in automation is proposed in which transparency plays a primary role in decisions to use automation but is supplemented by trust where there is insufficient information otherwise. Hypothesized cultural effects and framework predictions were confirmed.

In this paper, we study human trust and its computational models in supervisory control of swarm robots with varied levels of autonomy (LOA) in a target foraging task. We implement three LOAs: manual, mixed-initiative (MI), and fully autonomous LOA. While the swarm in the MI LOA is controlled by a human operator and an autonomous search algorithm collaboratively, the swarms in the manual and autonomous LOAs are fully directed by the human and the search algorithm, respectively. From user studies, we find that humans tend to make their decisions based on physical characteristics of the swarm rather than its performance since the task performance of swarms is not clearly perceivable by humans. Based on the analysis, we formulate trust as a Markov decision process whose state space includes the factors affecting trust. We develop variations of the trust model for different LOAs. We employ an inverse reinforcement learning algorithm to learn behaviors of the operator from demonstrations where the learned behaviors are used to predict human trust. Compared to an existing model, our models reduce the prediction error by at most 39.6%, 36.5%, and 28.8% in the manual, MI, and auto-LOA, respectively.

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.

As domestic service robots become more common and widespread, they must be programmed to efficiently accomplish tasks while aligning their actions with relevant norms. The first step to equip domestic robots with normative reasoning competence is understanding the norms that people apply to the behavior of robots in specific social contexts. To that end, we conducted an online survey of Chinese and United States participants in which we asked them to select the preferred normative action a domestic service robot should take in a number of scenarios. The paper makes multiple contributions. Our extensive survey is the first to: (a) collect data on attitudes of people on normative behavior of domestic robots, (b) across cultures and (c) study relative priorities among norms for this domain. We present our findings and discuss their implications for building computational models for robot normative reasoning.

Persistent surveillance of a target space using multiple unmanned aerial vehicles (UAVs) has multiple applications such as geographical surveys, air quality monitoring, and security monitoring. The limited onboard battery capacity challenges the continuous operation in these applications of persistent robots. We consider the problem for recharging persistent robots using mobile depots. The mobile depots collectively compute a set of tours to recharge all persistent robots with the minimum total cost. Compared to other works, the persistent UAVs are not required to detour to a static depot for energy replenishment such as recharging or battery swapping. We formulate this problem as a Generalized Multiple Depots Travelling Salesman Problem (GMDTSP) on a complete graph. A heuristic-based algorithm Multiple Depots Random Select (RSMD) is proposed to solve the recharging problem efficiently. The RSMD has proved to have an analytical constant upper bound in the worst-case scenario. We also propose a post-processing heuristic (RSMD-IM) to improve the solution quality further. We demonstrate the efficiency and effectiveness of our algorithm via benchmark on multiple instances from TSPLIB and GTSPLIB. The simulation results show that RSMD and RSMD-IM will perform significantly faster than the state of the art heuristic solver LKH with a loss of about 10% of solution quality.

In many multi-robot applications, it is critical to maintain connectivity within the robotic team to allow for information exchange and coordination. While most of the existing works focus on connectivity control that ensures robotic team remain connected as one component without faults, we consider the problem of robust connectivity maintenance that seeks to maintain k-connectivity, such that the multi-robot network could stay connected with the removal of fewer than k robots. In this paper, we propose provably minimum k-connectivity maintenance algorithms for multi-robot systems. This ensures the robustness of the multi-robot network connectivity at all time and also in a flexible and optimal way to provide the highest freedom for robots task-related controllers. Particularly, we propose a k-Connected Minimum Constraints Subgraph (k-CMCS) algorithm that activates the minimum k-connectivity constraints to the original controllers, and then revise the original controllers in a minimally invasive fashion. We demonstrate the effectiveness of our approach via simulations of up to 40 robots in the presence of multiple behaviors.

Research in deep reinforcement learning (RL) has coalesced around improving performance on benchmarks like the Arcade Learning Environment. However, these benchmarks do not emphasize two important characteristics that are often present in real-world domains: requirement of changing strategy conditioned on latent contexts, and temporal sensitivity. As a result, research in RL has not given these challenges their due, resulting in algorithms which do not understand critical changes in context, and have little notion of real world time. This paper introduces the game of Space Fortress as a RL benchmark which specifically targets these characteristics. We show that existing state-of-the-art RL algorithms are unable to learn to play the Space Fortress game, and then confirm that this poor performance is due to the RL algorithms' context insensitivity. We also identify independent axes along which to vary context and temporal sensitivity, allowing Space Fortress to be used as a testbed for understanding both characteristics in combination and also in isolation. We release Space Fortress as an open-source Gym environment.

Swarm robots are coordinated via simple control laws to generate emergent behaviors such as flocking, rendezvous, and deployment. Human-swarm teaming has been widely proposed for scenarios, such as human-supervised teams of unmanned aerial vehicles (UAV) for disaster rescue, UAV and ground vehicle cooperation for building security, and soldier-UAV teaming in combat. Effective cooperation requires an appropriate level of trust, between a human and a swarm. When an UAV swarm is deployed in a real-world environment, its performance is subject to real-world factors, such as system reliability and wind disturbances. Degraded performance of a robot can cause undesired swarm behaviors, decreasing human trust. This loss of trust, in turn, can trigger human intervention in UAVs' task executions, decreasing cooperation effectiveness if inappropriate. Therefore, to promote effective cooperation we propose and test a trust-repairing method (Trust-repair) restoring performance and human trust in the swarm to an appropriate level by correcting undesired swarm behaviors. Faulty swarms caused by both external and internal factors were simulated to evaluate the performance of the Trust-repair algorithm in repairing swarm performance and restoring human trust. Results show that Trust-repair is effective in restoring trust to a level intermediate between normal and faulty conditions.

In recent years, there has been increasing interest in transparency in Deep Neural Networks. Most of the works on transparency have been done for image classification. In this paper, we report on work of transparency in Deep Reinforcement Learning Networks (DRLNs). Such networks have been extremely successful in learning action control in Atari games. In this paper, we focus on generating verbal (natural language) descriptions and explanations of deep reinforcement learning policies. Successful generation of verbal explanations would allow better understanding by people (e.g., users, debuggers) of the inner workings of DRLNs which could ultimately increase trust in these systems. We present a generation model which consists of three parts: an encoder on feature extraction, an attention structure on selecting features from the output of the encoder, and a decoder on generating the explanation in natural language. Four variants of the attention structure full attention, global attention, adaptive attention and object attention - are designed and compared. The adaptive attention structure performs the best among all the variants, even though the object attention structure is given additional information on object locations. Additionally, our experiment results showed that the proposed encoder outperforms two baseline encoders (Resnet and VGG) on the capability of distinguishing the game state images.

Autonomous AI systems will be entering human society in the near future to provide services and work alongside humans. For those systems to be accepted and trusted, the users should be able to understand the reasoning process of the system, i.e. the system should be transparent. System transparency enables humans to form coherent explanations of the system's decisions and actions. Transparency is important not only for user trust, but also for software debugging and certification. In recent years, Deep Neural Networks have made great advances in multiple application areas. However, deep neural networks are opaque. In this paper, we report on work in transparency in Deep Reinforcement Learning Networks (DRLN). Such networks have been extremely successful in accurately learning action control in image input domains, such as Atari games. In this paper, we propose a novel and general method that (a) incorporates explicit object recognition processing into deep reinforcement learning models, (b) forms the basis for the development of "object saliency maps", to provide visualization of internal states of DRLNs, thus enabling the formation of explanations and (c) can be incorporated in any existing deep reinforcement learning framework. We present computational results and human experiments to evaluate our approach.

Robotic swarms are decentralized multi-robot systems whose members use local information from proximal neighbors to execute simple reactive control laws that result in emergent collective behaviors. In contrast, members of a general multi-robot system may have access to global information, all-to-all communication or sophisticated deliberative collaboration. Some algorithms in the literature are applicable to robotic swarms. Others require the extra complexity of general multi-robot systems. Given an application domain, a system designer or supervisory operator must choose an appropriate system or algorithm respectively that will enable them to achieve their goals while satisfying mission constraints (e.g, bandwidth, energy, time limits). In this paper, we compare representative swarm and general multi-robot algorithms in two application domains - navigation and dynamic area coverage - with respect to several metrics (e.g, completion time, distance travelled). Our objective is to characterize each class of algorithms to inform offline system design decisions by engineers or online algorithm selection decisions by supervisory operators. Our contributions are (a) an empirical performance comparison of representative swarm and general multi-robot algorithms in two application domains, (b) a comparative analysis of the algorithms based on the theory of information invariants, which provides a theoretical characterization supported by our emnirical results.

We consider the problem of online environmental sampling and modeling for multi-robot sensor coverage, where a team of robots spread out over the workspace in order to optimize the overall sensing performance. In contrast to most existing works on multi-robot coverage control that assume prior knowledge of the distribution of environmental phenomenon, also known as density function, we relax this assumption and enable the robot team to efficiently learn the model of the unknown density function Online using adaptive sampling and non-parametric inference such as Gaussian Process (GP). To capture significantly different components of the environmental phenomenon, we propose a new approach with mixture of locally learned Gaussian Processes for collective model learning and an information-theoretic criterion for simultaneous adaptive sampling in multi-robot coverage. Our approach demonstrates a better generalization of the environment modeling and thus the improved performance of coverage without assuming the density function is known a priori. We demonstrate the effectiveness of our algorithm via simulations of information gathering from indoor static sensors.

Swarm search and service (SSS) missions require large swarms to simultaneously search an area while servicing jobs as they are encountered. Jobs must be immediately serviced and can be one of several different job types - each requiring a different service time and number of vehicles to complete its service successfully. After jobs are serviced, vehicles are returned to the swarm and become available for reallocation. As part of SSS mission planning, human operators must determine the number of vehicles needed to achieve this balance. The complexities associated with balancing vehicle allocation to multiple as yet unknown tasks with returning vehicles makes this extremely difficult for humans. Previous work assumes that all system jobs are known ahead of time or that vehicles move independently of each other in a multi-agent framework. We present a dynamic vehicle routing (DVR) framework whose policies optimally allocate vehicles as jobs arrive. By incorporating time constraints into the DVR framework, an M/M/k/k queuing model can be used to evaluate overall steady state system performance for a given swarm size. Using these estimates, operators can rapidly compare system performance across different configurations, leading to more effective choices for swarm size. A sensitivity analysis is performed and its results are compared with the model, illustrating the appropriateness of our method to problems of plausible scale and complexity.

Autonomous robots are envisioned to increasingly become part of our lives in the house, restaurants, hospitals and offices. Additionally, self-driving cars will be soon appearing in city streets and highways and they will have to interact with cars driven by humans as well as other self-driving cars. In these settings the robots not only need to efficiently perform their tasks but also be able to interact with humans in socially appropriate ways. To accomplish this, robots must be able to reason not only on how to perform their tasks, but also incorporate societal values, social norms and legal rules so they can gain human acceptability and trust. Moreover, interactions with these robots will be long term. Long-term human interaction with robots as well as robot combined reasoning about both tasks and social norms generate multiple modeling and computational challenges. In this paper, we address one of the most important of these challenges, namely what is an appropriate and scalable computational framework that enables simultaneous task and normative reasoning. In particular, we report on our work on a novel computational framework, Modular Normative Markov Decision Processes (MNMDP) that integrates reasoning for domain tasks and normative reasoning for long-term autonomy. The MNMDP framework applies normative reasoning considering only the norms that are activated in appropriate contexts, rather than considering the full set of norms, thus significantly reducing computational complexity. The model modularity is also advantageous for long-term human-robot interaction. We present computational experiments that show significant computational improvements as compared with a base Normative Markov Decision Process (MDP) framework that includes the full set of norms.

As part of swarm search and service (SSS) missions, robots are tasked with servicing jobs as they are sensed. This requires small sub-swarm teams to leave the swarm for a specified amount of time to service the jobs. In doing so, fewer robots are required to change motion than if the whole swarm were diverted, thereby minimizing the job's overall effect on the swarm's main goal. We explore the problem of removing the required number of robots from the swarm, while maintaining overall swarm connectivity. By preserving connectivity, robots are able to successfully rejoin the swarm upon completion of their assigned job. These robots are then made available for reallocation. We propose a decentralized and asynchronous method for breaking off sub-swarm groups and rejoining them with the main swarm using the swarm's communication graph topology. Both single and multiple job site cases are explored. The results are compared against a full swarm movement method. Simulation results show that the proposed method outperforms a full swarm method in the average number of messages sent per robot in each step, as well as, the distance traveled by the swarm.

The interaction between swarm robots and human operators is significantly different from the traditional humanrobot interaction due to unique characteristics of the system, such as high cognitive complexity and difficulties in state estimation. In this paper, we concentrated on the method of conveying input from the operator to the swarm. Previous research has shown that control through switching between behaviors offers the greatest flexibility but is particularly difficult for human operators. A recently developed method for finding optimal sequences for composing behaviors offered a potential tool for aiding human operators controlling swarms through behavior switching. This paper compared participants performing a navigation task with and without the availability of the optimal sequencing aid. Results showed that the task of preplanning a sequence of behaviors and durations appeared more difficult for participants than switching between executing behaviors to navigate. Users who used the aid frequently was found to create shorter paths than infrequent users and the control group. In the trails that the aid was used, participants tended to generate more complicated sequences and achieve the first attempt more rapidly, compared to the trails that the aid was not used.

In this paper, we study trust-related human factors in supervisory control of swarm robots with varied levels of autonomy (LOA) in a target foraging task. We compare three LOAs: manual, mixed-initiative (MI), and fully autonomous LOA. In the manual LOA, the human operator chooses headings for a flocking swarm, issuing new headings as needed. In the fully autonomous LOA, the swarm is redirected automatically by changing headings using a search algorithm. In the mixed-initiative LOA, if performance declines, control is switched from human to swarm or swarm to human. The result of this work extends the current knowledge on human factors in swarm supervisory control. Specifically, the finding that the relationship between trust and performance improved for passively monitoring operators (i.e., improved situation awareness in higher LOAs) is particularly novel in its contradiction of earlier work. We also discover that operators switch the degree of autonomy when their trust in the swarm system is low. Last, our analysis shows that operator's preference for a lower LOA is confirmed for a new domain of swarm control.

Trust in automation has become a topic of intensive study since the late 1990s and is of increasing importance with the advent of intelligent interacting systems. While the earliest trust experiments involved human interventions to correct failures/errors in automated control systems, a majority of subsequent studies have investigated information acquisition and analysis decision aiding tasks such as target detection for which automation reliability is more easily manipulated. Despite the high level of international dependence on automation in industry, almost all current studies have employed Western samples primarily from the U.S. The present study addresses these gaps by running a large sample experiment in three (U.S., Taiwan, and Turkey) diverse cultures using a “trust sensitive task” consisting of both automated control and target detection subtasks. This article presents results for the target detection subtask for which reliability and task load were manipulated. The current experiments allow us to determine whether reported effects are universal or specific to Western culture, vary in baseline or magnitude, or differ across cultures. Results generally confirm consistent effects of manipulations across the three cultures as well as cultural differences in initial trust and variation in effects of manipulations consistent with 10 cultural hypotheses based on Hofstede's Cultural Dimensions and Leung and Cohen's theory of Cultural Syndromes. These results provide critical implications and insights for correct trust calibration and to enhance human trust in intelligent automation systems across cultures. Additionally, our results would be useful in designing intelligent systems for users of different cultures. Our article presents the following contributions: First, to the best of our knowledge, this is the first set of studies that deal with cultural factors across all the cultural syndromes identified in the literature by comparing trust in the Honor, Face, Dignity cultures. Second, this is the first set of studies that uses a validated cross-cultural trust measure for measuring trust in automation. Third, our experiments are the first to study the dynamics of trust across cultures.

We consider the general problem of moving a large number of networked robots toward a goal position through a cluttered environment while preserving network communication connectivity and avoiding both inter-robot collisions and collision with obstacles. In contrast to previous approaches that either plan complete paths for each individual robot in the high-dimensional joint configuration space or control the robot group as a whole with explicit constraints on the group's boundary and inter-robot pairwise distance, we propose a novel decentralized online behavior-based algorithm that relies on the topological structure of the multi-robot communication and sensing graphs to solve this problem. We formally describe the communication graph as a simplicial complex that enables robots to iteratively identify the frontier nodes and coordinate forward motion through the sensing graph. This approach is proved to automatically deform robot teams for collision avoidance and always preserve connectivity. The effectiveness of our approach is demonstrated using numerical simulations. The algorithm is shown to scale linearly in the number of robots.

Robotic swarms are distributed systems that exhibit global behaviors arising from local interactions between individual robots. Each robot can be programmed with several local control laws that can be activated depending on an operator's choice of global swarm behavior. While some simple behaviors (e.g. rendezvous) with guaranteed performance on known objectives under strict assumptions have been studied in the literature, real missions occur in uncontrolled environments with dynamically arising objectives and require combinations of behaviors. Given a library of swarm behaviors, a supervisory operator commanding the swarm must choose a sequence of behaviors to execute in order to accomplish a particular task during a mission composed of many dynamically arising tasks. In this paper, we formalize the problem of finding an optimal behavior sequence to maximize swarm performance on a complex task. Given the swarm behavior library, a set of decision time points and a performance criterion, we present an informed search algorithm that computes the maximum performance behavior sequence. The algorithm is proven to be optimal and complete. A relevant modification is presented that generates bounded suboptimal solutions more quickly. We apply the algorithm to a swarm navigation application and a dynamic area coverage application, demonstrating the utility of our algorithm even in situations where the behaviors in the library have not been designed for the task at hand.

In this paper, we study the model of human trust where an operator controls a robotic swarm remotely for a search mission. Existing trust models in human-in-the-loop systems are based on task performance of robots. However, we find that humans tend to make their decisions based on physical characteristics of the swarm rather than its performance since task performance of swarms is not clearly perceivable by humans. We formulate trust as a Markov decision process whose state space includes physical parameters of the swarm. We employ an inverse reinforcement learning algorithm to learn behaviors of the operator from a single demonstration. The learned behaviors are used to predict the trust level of the operator based on the features of the swarm.

We demonstrate an implementation of Markov Argumentation Random Fields (MARFs), a novel formalism combining elements of formal argumentation theory and probabilistic graphical models. In doing so MARFs provide a principled technique for the merger of probabilistic graphical models and non-monotonic reasoning, supporting human reasoning in ``messy’’ domains where the knowledge about conflicts should be applied. Our implementation takes the form of a graphical tool which supports users in interpreting complex information. We have evaluated our implementation in the domain of intelligence analysis, where analysts must reason and determine likelihoods of events using information obtained from conflicting sources.

Existing work learning distributed representations of knowledge base entities has largely failed to incorporate rich categorical structure, and is unable to induce category representations. We propose a new framework that embeds entities and categories jointly into a semantic space, by integrating structured knowledge and taxonomy hierarchy from large knowledge bases. Our framework enables to compute meaningful semantic relatedness between entities and categories in a principled way, and can handle both single-word and multiple-word concepts. Our method shows significant improvement on the tasks of concept categorization and dataless hierarchical classification.

In many multi-robot applications such as target search, environmental monitoring and reconnaissance, the multi-robot system operates semi-autonomously, but under the supervision of a remote human who monitors task progress. In these applications, each robot collects a large amount of task-specific data that must be sent to the human periodically to keep the human aware of task progress. It is often the case that the human-robot communication links are extremely bandwidth constrained and/or have significantly higher latency than inter-robot communication links, so it is impossible for all robots to send their task-specific data together. Thus, only a subset of robots, which we call the knowledge leaders, can send their data at a time. In this paper, we study the knowledge leader selection problem, where the goal is to select a subset of robots with a given cardinality that transmits the most informative task-specific data for the human. We prove that the knowledge leader selection is a submodular function maximization problem under explicit conditions and present a novel distributed submodular optimization algorithm that has the same approximation guarantees as the centralized greedy algorithm. The effectiveness of our approach is demonstrated using numerical simulations.

We present a method to validate a cognitive model, based on the cognitive architecture ACT-R, in dynamic human-automation systems with discrete human input. We are inspired by the general problem of K-choice games as a proxy for many decision making applications in dynamical systems. We model the human as a Markovian controller based on gathered experimental data, that is, a non-deterministic control input with known likelihoods of control actions associated with certain configurations of the state-space. We use reachability analysis to predict the outcome of the resulting discrete-time stochastic hybrid system, in which the outcome is defined as a function of the system trajectory. We suggest that the resulting expected outcomes can be used to validate the cognitive model against actual human subject data. We apply our method to a two-choice game in which the human is tasked with maximizing net coverage of a robotic swarm that can operate under rendezvous or deployment dynamics. We validate the corresponding ACTR cognitive model generated with the data from eight human subjects. The novelty of this work is (1) a method to compute expected outcome in a hybrid dynamical system with a Markov chain model of the human's discrete choice, and (2) application of this method to validation of cognitive models with a database of actual human subject data.

The use of autonomous systems has been rapidly increasing in recent decades. To improve human-automation interaction, trust has been closely studied. Research shows trust is critical in the development of appropriate reliance on automation. To examine how trust mediates the human-automation relationships across cultures, the present study investigated the influences of cultural factors on trust in automation. Theoretically guided empirical studies were conducted in the U.S., Taiwan and Turkey to examine how cultural dynamics affect various aspects of trust in automation. The results found significant cultural differences in human trust attitude in automation.

In many scenarios involving human interaction with a remote swarm, the human operator needs to be periodically updated with state information from the robotic swarm. A complete representation of swarm state is high dimensional and perceptually inaccessible to the human. Thus, a summary representation is often required. In addition, it is often the case that the human-swarm communication channel is extremely bandwidth constrained and may have high latency. This motivates the need for the swarm itself to compute a summary representation of its own state for transmission to the human operator. The summary representation may be generated by selecting a subset of robots, known as the information leaders, whose own states suffice to give a bounded approximation of the entire swarm, even in the presence of uncertainty. In this paper, we propose two fully distributed asynchronous algorithms for information leader selection that only rely on inter-robot local communication. In particular, by representing noisy robot states as error ellipsoids with tunable confidence level, the information leaders are selected such that the Minimum-Volume Covering Ellipsoid (MVCE) summarizes the noisy swarm state boundary. We provide bounded optimality analysis and proof of convergence for the algorithms. We present simulation results demonstrating the performance and effectiveness of the proposed algorithms.

Human swarm interaction (HSI) involves operators gathering information about a swarm's state as it evolves, and using it to make informed decisions on how to influence the collective behavior of the swarm. In order to determine the proper input, an operator must have an accurate representation and understanding of the current swarm state, including what emergent behavior is currently happening. In this paper, we investigate how human operators perceive three types of common, emergent swarm behaviors: rendezvous, flocking, and dispersion. Particularly, we investigate how recognition of these behaviors differ from each other in the presence of background noise. Our results show that, while participants were good at recognizing all behaviors, there are indeed differences between the three, with rendezvous being easier to recognize than flocking or dispersion. Furthermore, differences in recognition are also affected by viewing time for flocking. Feedback from participants was also especially insightful for understanding how participants went about recognizing behaviors-allowing for potential avenues of research in future studies.

Large teams of robots that operate collectively, whose behavior emerges from local interactions with neighbors, are known as swarms. While significant progress has been made improving the hardware, communication capabilities, and autonomous operation of these swarms, we still have much to learn about how human operators control and interact with them. This research is necessary if real world swarms are to be deployed in the future. The study presented here investigates different methods of displaying information about the swarm state to operators, and asks them to make predictions about the swarm's future state. In the study, participants are shown swarms performing one of three different behaviors, and are asked to use the information available from the display to make their predictions. Results show that summarizing the swarm's current state to just an average position and bounding ellipse allowed predictions as accurate as those made when full state information was shown. Furthermore, two leader-based methods were used, whereby the operators were shown only a small subset of the swarm. However, such display methods were inferior for prediction than either the summary center and ellipse or full information methods. With these results, and with participant feedback about the helpfulness of the four display types, we hope future studies can make more informed decision about interface design when it comes to the control of swarms.

In this paper, we propose and analyze a distributed negotiation strategy for a multi-agent, multi-attribute negotiation in which the agents have no information about the utility functions of other agents. We analytically prove that, if the zone of agreement is nonempty and the agents concede up to their reservation utilities, agents generating offers using our offer-generation strategy, namely the sequential projection strategy, will converge to an agreement acceptable to all the agents; the convergence property does not depend on the specific concession strategy. In considering agents’ incentive to concede during the negotiation, we propose and analyze a reactive concession strategy. Through computational experiments, we demonstrate that our distributed negotiation strategy yields performance sufficiently close to the Nash bargaining solution and that our algorithms are robust to potential deviation strategies. Methodologically, our paper advances the state of the art of alternating projection algorithms, in that we establish the convergence for the case of multiple, moving sets (as opposed to two static sets in the current literature). Our paper introduces a new analytical foundation for a broad class of computational group decision and negotiation problems.

Recent advances in technology are delivering robots of reduced size and cost. A natural outgrowth of these advances are systems comprised of large numbers of robots that collaborate autonomously in diverse applications. Research on effective autonomous control of such systems, commonly called swarms, has increased dramatically in recent years and received attention from many domains, such as bioinspired robotics and control theory. These kinds of distributed systems present novel challenges for the effective integration of human supervisors, operators, and teammates that are only beginning to be addressed. This paper is the first survey of human-swarm interaction (HSI) and identifies the core concepts needed to design a human-swarm system. We first present the basics of swarm robotics. Then, we introduce HSI from the perspective of a human operator by discussing the cognitive complexity of solving tasks with swarm systems. Next, we introduce the interface between swarm and operator and identify challenges and solutions relating to human-swarm communication, state estimation and visualization, and human control of swarms. For the latter, we develop a taxonomy of control methods that enable operators to control swarms effectively. Finally, we synthesize the results to highlight remaining challenges, unanswered questions, and open problems for HSI, as well as how to address them in future works.

Robotic swarms are distributed systems whose members interact via local control laws to achieve a variety of behaviors, such as flocking. In many practical applications, human operators may need to change the current behavior of a swarm from the goal that the swarm was going towards into a new goal due to dynamic changes in mission objectives. There are two related but distinct capabilities needed to supervise a robotic swarm. The first is comprehension of the swarm's state and the second is prediction of the effects of human inputs on the swarm's behavior. Both of them are very challenging. Prior work in the literature has shown that inserting the human input as soon as possible to divert the swarm from its original goal towards the new goal does not always result in optimal performance (measured by some criterion such as the total time required by the swarm to reach the second goal). This phenomenon has been called Neglect Benevolence, conveying the idea that in many cases it is preferable to neglect the swarm for some time before inserting human input. In this paper, we study how humans can develop an understanding of swarm dynamics so they can predict the effects of the timing of their input on the state and performance of the swarm. We developed the swarm configuration shape-changing Neglect Benevolence Task as a Human Swarm Interaction (HSI) reference task allowing comparison between human and optimal input timing performance in control of swarms. Our results show that humans can learn to approximate optimal timing and that displays which make consensus variables perceptually accessible can enhance performance.

In this paper, we present an algorithm to solve the Multi-Robot Persistent Coverage Problem (MRPCP). Here, we seek to compute a schedule that will allow a fleet of agents to visit all targets of a given set while maximizing the frequency of visitation and maintaining a sufficient fuel capacity by refueling at depots. We also present a heuristic method to allow us to compute bounded suboptimal results in real time. The results produced by our algorithm will allow a team of robots to efficiently cover a given set of targets or tasks persistently over long periods of time, even when the cost to transition between tasks is dynamic.

We propose the Stochastic Multi-Robot Persistent Coverage Problem (SMRPCP) and correspondant methodology to compute an optimal schedule that enables a fleet of energy-constrained unmanned aerial vehicles to repeatedly perform a set of tasks while maximizing the frequency of task completion and preserving energy reserves via recharging depots. The approach enables online modeling of uncertain task costs and yields a schedule that adapts according to an evolving energy expenditure model. A fast heuristic method is formulated that enables online generation of a schedule that concurrently maximizes task completion frequency and avoids the risk of individual robot energy-depletion and consequential platform failure. Failure mitigation is introduced through a recourse strategy that routes robots based on acceptable levels of risk. Simulation and experimental results evaluate the efficacy of the proposed methodology and demonstrate online system-level adaptation due to increasingly certain costs models acquired during the deployment execution.

We present distributed algorithms for multirobot task assignment where the tasks have to be completed within given deadlines. Each robot has a limited battery life and thus there is an upper limit on the amount of time that it has to perform tasks. Performing each task requires certain amount of time (called the task duration) and each robot can have different payoffs for the tasks. Our problem is to assign the tasks to the robots such that the total payoff is maximized while respecting the task deadline constraints and the robot's battery life constraints. Our problem is NP-hard since a special case of our problem is the classical generalized assignment problem (which is NP-hard). There are no known algorithms (distributed or centralized) for this problem with provably good guarantees of performance. We present a distributed algorithm for solving this problem and prove that our algorithm has an approximation ratio of 2. For the special case of constant task duration we present a distributed algorithm that is provably almost optimal. Our distributed algorithms are polynomial in the number of robots and the number of tasks. We also present simulation results to depict the performance of our algorithms. Note to Practitioners-In this paper, we present provably good multirobot task assignment algorithms, while considering practical constraints like task deadlines and limited battery life of robots. Such constraints are relevant in many applications including parts movement by robots in manufacturing, delivery of goods by unmanned vehicles, and search and rescue operations. Our solution is applicable to a group of heterogeneous robots with different suitability (i.e., payoffs) for different tasks. Our distributed approach is independent of the underlying robot communication network topology, and thus can be applied to a wide range of robot network deployments. Finally, our approach is easy to implement, has low communication requirements, and it is scalable, since its running time is linear in the number of robots and tasks.

In this paper, we present provably-good distributed task assignment algorithms for a heterogeneous multi-robot system, in which the tasks form disjoint groups and there are constraints on the number of tasks a robot can do (both within the overall mission and within each task group). Each robot obtains a payoff (or incurs a cost) for each task and the overall objective for task allocation is to maximize (minimize) the total payoff (cost) of the robots. In general, existing algorithms for task allocation either assume that tasks are independent or do not provide performance guarantee for the situation, in which task constraints exist. We present a distributed algorithm to provide an almost optimal solution for our problem. The key aspect of our distributed algorithm is that the overall objective is (almost) maximized by each robot maximizing its own objective iteratively (using a modified payoff function based on an auxiliary variable, called price of a task). Our distributed algorithm is polynomial in the number of tasks, as well as the number of robots.

Many researchers have employed some form of teleoperated leader to influence a robotic swarm; however, the way in which this influence is conveyed has not been well studied. Some researchers employ designated leaders that are known to be leaders by other members of the swarm and hence followed. Others do not impose a leader/follower distinction on the swarm's algorithms and instead choose to influence the swarm indirectly through controlling one or more of its members. Because the robustness of swarm behavior arises from its many distributed interactions, influence through designated leaders might render it susceptible to noise or disrupt its coherence by overriding these mechanisms. Conversely, limiting human influence to indirect control through the local effects of a leader might prove too sluggish to allow effective human control. This paper compares leader-based methods of each type, designated as Tacit leadership via consensus (no explicit leader/follower distinction) and Explicit leadership via flooding (influence propagating from leader takes precedence). These methods were compared in simulation and in human experiments finding that explicit leadership led to faster convergence in simulation and better performance in the experiments. Effects of noise were slightly more pronounced for Explicit leaders and cohesion slightly poorer.

Robotic swarms are distributed systems whose members interact via local control laws to achieve different behaviors. Practical missions may require a combination of different swarm behaviors, where these behavioral combinations are not known a priori but could arise dynamically due to changes in mission goals. Therefore, human interaction with the swarm (HIS) is needed. In this paper, we introduce, formally define and characterize a novel concept, Neglect Benevolence, that captures the idea that it may be beneficial for system performance if the human operator, after giving a command, waits for some time before giving a subsequent command to the swarm. This raises the important question of the existence and means of calculation of the optimal time for the operator to give input to the swarm in order to optimize swarm behavior. Human operators are limited in their ability to estimate the best time to give input to the swarm. Therefore, automated aids that calculate the optimal input time could help the human operator achieve the best system performance. Our contributions are as follows. First, we formally define the new notion of Neglect Benevolence. Second, we prove the existence of Neglect Benevolence for a class of linear dynamical systems. Third, we provide an analytic characterization and an algorithm for calculating the optimal input time. Fourth, we apply the analysis to the human control of swarm configuration.

In this paper, we present both centralized and distributed algorithms for aligning coordinate frames in multi-robot systems based on inter-robot relative position measurements. Robot orientations are not measured, but are computed by our algorithms. Our algorithms are robust to measurement error and are useful in applications where a group of robots need to establish a common coordinate frame based on relative sensing information. The problem of establishing a common coordinate frame is formulated in a least squares error framework minimizing the total inconsistency of the measurements. We assume that robots that can sense each other can also communicate with each other. In this paper, our key contribution is a novel asynchronous distributed algorithm for multi-robot coordinate frame alignment that does not make any assumptions about the sensor noise model. After minimizing the least squares error (LSE) objective for coordinate frame alignment of two robots, we develop a novel algorithm that out-performs state-of-the-art centralized optimization algorithms for minimizing the LSE objective. Furthermore, we prove that for multi-robot systems (a) with redundant noiseless relative sensing information, we will achieve the globally optimal solution (this is non-trivial because the LSE objective is non-convex for our problem), (b) with noisy information but no redundant sensing (e.g. sensing graph has a tree topology), our algorithm will optimally minimize the LSE objective. We also present preliminary results of the real-world performance of our algorithm on TurtleBots equipped with Kinect sensors.

Controlling a swarm of robots after deployment is difficult, due to the unpredictable and emergent behavior of swarm algorithms. Past work has focused on influencing the swarm via statically selected leaders—swarm members that the operator directly controls—that are pre-selected and remain leaders throughout the scenario execution. This paper investigates the use of dynamically selected leaders that are directly controlled by the human operator to guide the rest of the swarm, which is operating under a flocking-style algorithm. The goal of the operator is to move the swarm to goal regions that arise dynamically in the environment. We experimentally investigated (a) the effect of density of leaders on the ease of human control and system performance, and (b) how restriction of information communicated to the human operator affects the ability to guide the swarm to goal regions. The density of leaders is computed based on an extension of the random competition clustering (RCC) algorithm used in wireless sensor networks to select cluster heads. In particular, we studied the effect of different guarantees of the maximum number of hops in the communication graph from any robot to the nearest leader. Increasing the maximum hop guarantee effectively lowers the density of leaders in the swarm. Our results show that, while there was a large drop in the number of goals reached when moving from a 1-hop to a 2-hop guarantee, the difference between a 2-hop and 3-hop guarantee was not statistically significant. Furthermore, we found that performance was just as good when the information returned to the operator was restricted, showing that operators can still navigate a swarm even when they have imperfect information.

Dynamic assignment and re-assignment of large number of simple and cheap robots across multiple sites is relevant to applications like autonomous survey, environmental monitoring and reconnaissance. In this paper, we present supervisory control laws for cost-effective (re)-distribution of a robotic swarm among multiple sites. We consider a robotic swarm consisting of tens to hundreds of simple robots with limited battery life and limited computation and communication capabilities. The robots have the capability to recognize the site that they are in and receive messages from a central supervisory controller, but they cannot communicate with other robots. There is a cost (e.g., energy, time) for the robots to move from one site to another. These limitations make the swarm hard to control to achieve the desired configurations. Our goal is to design control laws to move the robots from one site to another such that the overall cost of redistribution is minimized. This problem can be posed as an optimal control problem (which is hard to solve optimally), and has been studied to a limited extent in the literature when the cost objective is time. We consider the total energy consumed as the cost objective and present a linear programming based heuristic for computing a stochastic transition law for the robots to move between sites. We evaluate our method for different objectives and show through Monte Carlo simulations that our method outperforms other proposed methods in the literature for the objective of time as well as more general objectives (like total energy consumed).

The study of human control of robotic swarms involves designing interfaces and algorithms for allowing a human operator to influence a swarm of robots. One of the main difficulties, however, is determining how to most effectively influence the swarm after it has been deployed. Past work has focused on influencing the swarm via statically selected leaders-swarm members that the operator directly controls. This paper investigates the use of a small subset of the swarm as leaders that are dynamically selected during the scenario execution and are directly controlled by the human operator to guide the rest of the swarm, which is operating under a flocking-style algorithm. The goal of the operator in this study is to move the swarm to goal regions that arise dynamically in the environment.We experimentally investigated three different aspects of dynamic leader-based swarm control and their interactions: leader density (in terms of guaranteed hops to a leader), sensing error, and method of information propagation from leaders to the rest of the swarm. Our results show that, while there was a large drop in the number of goals reached when moving from a 1-hop to a 2-hop guarantee, the difference between a 2-hop, 3-hop, and 4-hop guarantee was not statistically significant. Furthermore, we found that sensing error impacted the explicit information-propagation method more than the tacit method conditions, and caused participants more trouble the lower the density of leaders, although the explicit method performed better overall.

A key challenge in creating a sustainable and energy-efficient society is to make consumer demand adaptive to the supply of energy, especially to the renewable supply. In this article, we propose a partially-centralized organization of consumers (or agents), namely, a consumer cooperative that purchases electricity from the market. In the cooperative, a central coordinator buys the electricity for the whole group. The technical challenge is that consumers make their own demand decisions, based on their private demand constraints and preferences, which they do not share with the coordinator or other agents. We propose a novel multiagent coordination algorithm, to shape the energy demand of the cooperative. To coordinate individual consumers under incomplete information, the coordinator determines virtual price signals that it sends to the consumers to induce them to shift their demands when required. We prove that this algorithm converges to the central optimal solution and minimizes the electric energy cost of the cooperative. Additionally, we present results on the time complexity of the iterative algorithm and its implications for agents' incentive compatibility. Furthermore, we perform simulations based on real world consumption data to (a) characterize the convergence properties of our algorithm and (b) understand the effect of differing demand characteristics of participants as well as of different price functions on the cost reduction. The results show that the convergence time scales linearly with the agent population size and length of the optimization horizon. Finally, we observe that as participants' flexibility of shifting their demands increases, cost reduction increases and that the cost reduction is not sensitive to variation in consumption patterns of the consumers.

A key challenge to create a sustainable and energy-efficient 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.

What does a user do when he logs in to the Twitter website? Does he merely browse through the tweets of all his friends as a source of information for his own tweets, or does he simply tweet a message of his own personal interest? Does he skim through the tweets of all his friends or only of a selected few? A number of factors might influence a user in these decisions. Does this social influence vary across cultures? In our work, we propose a simple yet effective model to predict the behavior of a user - in terms of which hashtag or named entity he might include in his future tweets. We have approached the problem as a classification task with the various influences contributing as features. Further, we analyze the contribution of the weights of the different features. Using our model we analyze data from different cultures and discover interesting differences in social influence.

How to model the process of information diffusion in social networks is a critical research task. Although numerous attempts have been made for this study, few of them can simulate and predict the temporal dynamics of the diffusion process. To address this problem, we propose a novel information diffusion model (GT model), which considers the users in network as intelligent agents. The agent jointly considers all his interacting neighbors and calculates the payoffs for his different choices to make strategic decision. We introduce the time factor into the user payoff, enabling the GT model to not only predict the behavior of a user but also to predict when he will perform the behavior. Both the global influence and social influence are explored in the time-dependent payoff calculation, where a new social influence representation method is designed to fully capture the temporal dynamic properties of social influence between users. Experimental results on Sina Weibo and Flickr validate the effectiveness of our methods.

In this paper, we study the problem of constructing a path for a mobile data collecting robot such that the total data collection cost (i.e., sum of transmission energy of the sensor nodes and movement energy of the robot) in a sensor network is minimized. We assume that the sensor nodes can transmit within a certain region around their position, which is called the communication set. We model the communication set as a convex set to take into account asymmetric transmission systems (like directional antennas). We derive a necessary condition for the optimality of a mobile robot tour through the communication sets. Based on this condition, we design a three-step approach to compute a local minimum of the optimization problem. We prove that our solution is guaranteed to be within a constant factor of the global optimal solution. Our algorithm works for both 2-dimensional and 3-dimensional sensor networks where the sensor nodes are heterogeneous and can have directional communication properties. In contrast, existing algorithms for computing data collecting routes are for planar sensor networks and assume the communication sets to be discs. We also present simulation results depicting the performance of our algorithm.

In this paper, we present provably-good algorithms for multi-robot task assignment, where each task has to be completed within its deadline. Each robot has a upper limit on the maximum number of tasks that it can perform due to its limited battery life, and each task takes the same amount of time to complete. Each robot has a different payoff (or cost) for the tasks and the objective is to assign the tasks to the robots such that the total payoff (cost) is maximized (minimized) while respecting the task deadline constraints. This problem is an extension of a special generalized assignment problem (where each task consumes the same time resource and must be finished), with additional deadline constraints for the time resource assignment. We show that the problem can be reduced to a problem of assigning tasks to robots, where the tasks are organized in overlapping sets, and each robot has a limit on the number of tasks it can perform from each set, which is a variant of multi-robot assignment problem with set precedence constraint (SPC-MAP) discussed in [1].We present a distributed auction-based algorithm for this problem and prove that the solution is almost-optimal. We also present simulation results to depict the performance of our algorithm.

We present a provably-good distributed algorithm for generalized task assignment problem in the context of multirobot systems, where robots cooperate to complete a set of given tasks. In multi-robot generalized assignment problem (MR-GAP), each robot has its own resource constraint (e.g., energy constraint), and needs to consume a certain amount of resource to obtain a payoff for each task. The objective is to find a maximum payoff assignment of tasks to robots such that each task is assigned to at most one robot while respecting robots' resource constraints. MR-GAP is a NP-hard problem. It is an extension of multi-robot linear assignment problem since different robots can use different amount of resource for doing a task (due to the heterogeneity of robots and tasks). We first present an auction-based iterative algorithm for MR-GAP assuming the presence of a shared memory (or centralized auctioneer), where each robot uses a knapsack algorithm as a subroutine to iteratively maximize its own objective (using a modified payoff function based on an auxiliary variable, called price of a task). Our iterative algorithm can be viewed as (an approximation of) best response assignment update rule of each robot to the assignment of other robots at that iteration. We prove that our algorithm converges to an assignment (approximately) at equilibrium under the assignment update rule, with an approximation ratio of 1+α (where α is the approximation ratio for the Knapsack problem). We also combine our algorithm with a message passing mechanism to remove the requirement of a shared memory and make our algorithm totally distributed assuming the robots' communication network is connected. Finally, we present simulation results to depict our algorithm's performance.

A robotic swarm is a decentralized group of robots which overcome failure of individual robots with robust emergent behaviors based on local interactions. These behaviors are not well built for accomplishing complex tasks, however, because of the changing assumptions required in various applications and environments. A new movement in the research field is to add human input to influence the swarm in order to help make the robots goal directed and overcome these problems. This research in Human Swarm Interaction (HSI) focuses on different control laws and ways to integrate the human intent with local control laws of the robots. Previous studies have all used visual feedback through a computer interface to give the user the swarm state information. This study adapted swarm control algorithms to give the operator hap tic feedback as well as visual feedback. The study shows the benefits of the additional feedback in a target searching class. Researchers in multi-robot systems have shown benefits of hap tic feedback in obstacle navigation before, but this study is a novel method because of the decentralized formation of the robotic swarm. In most environments, operators were able to cover significantly more area, increasing the chance of finding more targets. The other environment found no significant difference, showing that the hap tic feedback does not degrade performance in any of the tested environments. This supports our hypothesis that hap tic feedback is useful in HSI and requires further research to maximize its potential.

As swarms are used in increasingly more complex scenarios, further investigation is needed to determine how to give human operators the best tools to properly influence the swarm after deployment. Previous research has focused on relaying influence from the operator to the swarm, either by broadcasting commands to the entire swarm or by influencing the swarm through the teleoperation of a leader. While these methods each have their different applications, there has been a lack of research into how the influence should be propagated through the swarm in leader-based methods. This paper focuses on two simple methods of information propagation-flooding and consensus-and compares the ability of operators to maneuver the swarm to goal points using each, both with and without sensing error. Flooding involves each robot explicitly matching the speed and direction of the leader (or matching the speed and direction of the first neighboring robot that has already done so), and consensus involves each robot matching the average speed and direction of all the neighbors it senses. We discover that the flooding method is significantly more effective, yet the consensus method has some advantages at lower speeds, and in terms of overall connectivity and cohesion of the swarm.

In this paper we present the first study of human-swarm interaction comparing two fundamental types of interaction, coined intermittent and environmental. These types are exemplified by two control methods, selection and beacon control, made available to a human operator to control a foraging swarm of robots. Selection and beacon control differ with respect to their temporal and spatial influence on the swarm and enable an operator to generate different strategies from the basic behaviors of the swarm. Selection control requires an active selection of groups of robots while beacon control exerts an influence on nearby robots within a set range. Both control methods are implemented in a testbed in which operators solve an information foraging problem by utilizing a set of swarm behaviors. The robotic swarm has only local communication and sensing capabilities. The number of robots in the swarm range from 50 to 200. Operator performance for each control method is compared in a series of missions in different environments with no obstacles up to cluttered and structured obstacles. In addition, performance is compared to simple and advanced autonomous swarms. Thirty-two participants were recruited for participation in the study. Autonomous swarm algorithms were tested in repeated simulations. Our results showed that selection control scales better to larger swarms and generally outperforms beacon control. Operators utilized different swarm behaviors with different frequency across control methods, suggesting an adaptation to different strategies induced by choice of control method. Simple autonomous swarms outperformed human operators in open environments, but operators adapted better to complex environments with obstacles. Human controlled swarms fell short of task-specific benchmarks under all conditions. Our results reinforce the importance of understanding and choosing appropriate types of human-swarm interaction when designing swarm systems, in addition to choosing appropriate swarm behaviors.

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.

We study an online task assignment problem for multi-robot systems where robots can do multiple tasks during their mission and the tasks arrive dynamically in groups. Each robot can do at most one task from a group and the total number of tasks a robot can do is bounded by its limited battery life. There is a payoff for assigning each robot to a task and the objective is to maximize the total payoff. A special case, where each group has one task and each robot can do one task is the online maximum weighted bipartite matching problem (MWBMP). For online MWBMP, it is known that, under some assumptions on the payoffs, a greedy algorithm has a competitive ratio of 1 over 3. Our key result is to prove that for the general problem, under the same assumptions on the payoff as in MWBMP and an assumption on the number of tasks arising in each group, a repeated auction algorithm, where each group of tasks is (near) optimally allocated to the available group of robots has a guaranteed competitive ratio. We also prove that (a) without the assumptions on the payoffs, it is impossible to design an algorithm with any performance guarantee and (b) without the assumption on the task profile, the algorithms that can guarantee a feasible allocation (if one exists) have arbitrarily bad performance in the worst case. Additionally, we present simulation results depicting the average case performance of the repeated greedy auction algorithm.

A wide class of multirobot control tasks involves operator interactions with individual robots. Where the robots' actions are independent, as for example in some foraging tasks, the operator can interact with robots sequentially in a round robin fashion. If the need for interaction can be detected by the robot through self-reflection, the robot could communicate its need for interaction to the operator. The resulting human-robot system would form a queuing system in which the operator is the server and the queue of robots requesting interaction, the jobs. As a queuing system, performance could be optimized using standard techniques, providing the operator's attention could be appropriately directed. An earlier study found that Human-Robot Interaction (HRI) performance was improved by communicating requests for interaction to the operator, however, a first-in-first-out (FIFO) aid showing a single request at a time led to poorer performance than one showing the entire (Open) queue. The current experiment compared Open-queue and FIFO conditions from the first experiment with a Priority-queue using a shortest job first (SJF) discipline known to maximize throughput. Performance in the Priority-queue condition was statistically indistinguishable from the best performance for all measures except those for missed victims where it was intermediate between FIFO (best) and Open-queue. Both of the other conditions produced poorest performance on some measures. The results suggest that operator attention can be effectively scheduled allowing the use of scheduling algorithms to improve the efficiency of HRI.

The present study investigates the effect of imperfect automation in a human multi-robot controlled environment with different principles for scheduling an operator's attention in a foraging task. The experiment compared a SJF-queue (shortest job first) presenting a single alarm at a time with an Open-queue which showed all current alarms. Two levels of automation reliability, high (90%) and low (50%), were examined in the study. Performance for the queue mechanisms was equivalent confirming that operator attention can be effectively directed to improve performance. Additionally, the higher reliability condition raised an operator's success rate for resolving robot failures and assisted the operator in allocating attention to emergent events in a timely manner. Although the more frequent alerts contributed to better performance operators experienced increased levels of workload.

Swarm robots use simple local rules to create complex emergent behaviors. The simplicity of the local rules allows for large numbers of low-cost robots in deployment, but the same simplicity creates difficulties when deploying in many applicable environments. These complex missions sometimes require human operators to influence the swarms towards achieving the mission goals. Human swarm interaction (HSI) is a young field with few user studies exploring operator behavior. These studies all assume perfect information between the operator and the swarm, which is unrealistic in many applicable scenarios. Indoor search and rescue or underwater exploration may present environments where radio limitations restrict the bandwidth of the robots. This study explores this bandwidth restriction in a user study. Three levels of bandwidth are explored to determine what amount of information is necessary to accomplish a swarm foraging task. The lowest bandwidth condition performs poorly, but the medium and high bandwidth condition both perform well. The medium bandwidth condition does so by aggregating useful swarm information to compress the state information. Further, the study shows operators preferences that should have hindered task performance, but operator adaptation allowed for error correction.

Autonomous swarm algorithms have been studied extensively in the past several years. However, there is little research on the effect of injecting human influence into a robot swarm-whether it be to update the swarm's current goals or reshape swarm behavior. While there has been growing research in the field of human-swarm interaction (HSI), no previous studies have investigated how humans interact with swarms under communication latency.We investigate the effects of latency both with and without a predictive display in a basic swarm foraging task to see if such a display can help mitigate the effects of delayed feedback of the swarm state. Furthermore, we introduce a new concept called neglect benevolence to represent how a human operator may need to give time for swarm algorithms to stabilize before issuing new commands, and we investigate it with respect to task performance. Our study shows that latency did affect a user's ability to control a swarm to find targets in the foraging task, and that the predictive display helped to remove these effects. We also found evidence for neglect benevolence, and that operators exploited neglect benevolence in different ways, leading to two different, but equally successful strategies in the target-searching task.

In this paper, we present an asynchronous display method, coined image queue, which allows operators to search through a large amount of data gathered by autonomous robot teams. We discuss and investigate the advantages of an asynchronous display for foraging tasks with emphasis on Urban Search and Rescue. The image queue approach mines video data to present the operator with a relevant and comprehensive view of the environment in order to identify targets of interest such as injured victims. It fills the gap for comprehensive and scalable displays to obtain a network-centric perspective for UGVs. We compared the image queue to a traditional synchronous display with live video feeds and found that the image queue reduces errors and operator's workload. Furthermore, it disentangles target detection from concurrent system operations and enables a call center approach to target detection. With such an approach we can scale up to very large multi-robot systems gathering huge amounts of data that is then distributed to multiple operators.

This paper presents a queueing model that ad dresses robot self-assessment in human-robot-interaction systems. We build the model based on a game theoretic queueing approach, and analyze four issues: 1) individual differences in operator skills/capabilities, 2) differences in difficulty of presenting tasks, 3) trade-off between human interaction and performance and 4) the impact of task heterogeneity in the optimal service decision-making and system performance. The subsequent analytical and numerical exploration helps under stand the way the decentralized decision-making scheme is affected by various service environments.

Distributed algorithms for (re)configuring mobile sensors to cover a given area are important for autonomous multi-robot operations in application areas such as surveillance and environmental monitoring. Depending on the assumptions about the choice of the environment, the sensor models, the coverage metric, and the motion models of sensor nodes, there are different versions of the problem that have been formulated and studied. In this paper, we consider a system of holonomic mobile robots equipped with anisotropic sensors (e.g., limited field of view cameras) that are required to cover a polygonal region with polygonal obstacles to detect interesting events. We assume a given probability distribution of the events over a region. Motivated by scenarios where the sensing performance not only depends on the resolution of sensing but also on the relative orientation between the sensing axis and the event, we assume that the probability of detection of an event depends on both sensing parameters and the orientation of observation. We present a distributed gradient-ascent algorithm for reconfiguring the system of mobile robots so that the joint probability of detection of events over the whole region is maximized (i.e., positioning the mobile robots and determining their sensor parameters). As an example case study, we use a system of mobile robots equipped with limited field of view cameras with pan and zoom capabilities. We present simulation results demonstrating the performance of our algorithm.

We address the problem of searching for moving targets in large outdoor environments represented by height maps. To solve the problem we present a complete system that computes from an annotated height map a graph representation and search strategies based on worst-case assumptions about all targets. These strategies are then used to compute a schedule and task assignment for all agents. We improve the graph construction from previous work and for the first time present a method that computes a schedule to minimize the execution time. For this we consider travel times of agents determined by a path planner on the height map. We demonstrate the entire system in a real environment with an area of 700,000m2in which eight human agents search for two intruders using mobile computing devices (iPads). To the best of our knowledge this is the first demonstration of a search system applied to such a large environment.

In this paper, we present task allocation (assignment) algorithms for a multi-robot system where the tasks are divided into disjoint groups and there are precedence constraints between the task groups. Existing auction-based algorithms assume the task independence and hence can not be used directly to solve the class of multi-robot task assignment problems that we consider. In our model, each robot can do a fixed number of tasks and obtains a benefit (or incurs a cost) for each task. The tasks are divided into groups and each robot can do only one task from each group. These constraints arise when the robots have to do a set of tasks that have precedence constraints and each task takes the same time to be completed. We extend the auction algorithm to provide an almost optimal solution to the task assignment problem with set precedence constraints (the theoretical guarantees are the same as that of the original auction algorithm for unconstrained tasks). In other words, we guarantee that we will get a solution within a factor of O(nte) of the optimal solution, where ntis the total number of tasks and ε is a parameter that we choose. We first present our algorithm using a shared memory model and then indicate how consensus algorithms can be used to make the algorithm totally distributed.

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 confi-dent interactions. Societies may break down when trust between agents is too low to motivate inter-actions. In such settings, agents should make de-cisions about who to interact with, given their de-gree of trust in the available partners. We propose a decision-theoretic model of trust decision mak-ing allows controls to be used, as well as trust, to increase confidence in initial interactions. We con-sider explicit incentives, monitoring and reputation as examples of such controls. We evaluate our ap-proach within a simulated, highly-dynamic multi-agent environment, and show how this model sup-ports the making of delegation decisions when trust is low. 1

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.

Controlling a team of Unmanned Aerial Vehicles (UAV) requires the operator to perform continuous surveillance and path planning. The operator's situation awareness is likely to degrade as an increasing number of surveillance videos must be viewed and integrated. The Picture-in-Picture display (PiP) provides one solution for integrating multiple UAV camera video by allowing the operator to view the video feed in the context of surrounding terrain. The experimental SUAVE (Simple Unmanned Areal Vehicle Environment) display extends PiP methods by sampling imagery from the video stream to texture a 3D map of the terrain. The operator can then inspect this imagery using world in miniature (WIM) or fly-through methods. We investigate the properties and advantages of SUAVE in the context of a search mission with 11 UAVs finding a strong advantage for finding targets While performance is expected to improve with increasing numbers of UAVs we did not find differences in performance between models generated by 11 UAVs and those employing 22 UAVs.

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.

Human users trying to plan and accomplish information-dependent goals in highly dynamic environments with prevalent uncertainty must consult various types of information sources in their decision-making processes while the information requirements change as they plan and re-plan. When the users must make time-critical decisions in information-intensive tasks they become cognitively overloaded not only by the planning activities but also by the information-gathering activities at various points in the planning process. We have developed the ANTicipatory Information and Planning Agent (ANTIPA) to manage information adaptively in order to mitigate user cognitive overload. To this end, the agent brings information to the user as a result of user requests but most crucially, it proactively predicts the user's prospective information needs by recognizing the user's plan; pre-fetches information that is likely to be used in the future; and offers the information when it is relevant to the current or future planning decisions. This paper introduces a fully implemented agent of the ANTIPA architecture using a decision-theoretic user model.

For a deployed mobile robotic network to function usefully, the robots should have the capability to adjust their positions, while maintaining the network connectivity. In this paper, we present algorithms that allows a robot to decide when it is feasible for it to move to a desired point by adjusting its own positions (and the positions of some other robots in the network), while maintaining all the network connectivity constraints. Under the assumption of a disc model of communication, we show that the problem can be formulated as a convex optimization (or feasibility) problem (actually a second order cone program). Thus, the problem can be solved in polynomial time by centralized interior point algorithms. However, this requires the robot to have knowledge of the position of all the nodes in the network. Our main contribution is the development of an incremental algorithm, that solves the feasibility problem (of whether the robot can move to its desired goal) by obtaining the information about the position of the robots and their immediate neighbors only if they are required to move. We present simulation results comparing the performance of the centralized algorithm with the incremental algorithm for randomly generated networks. From simulation results, we observe that the time required by the incremental algorithm to solve the feasibility problem is relatively independent of the size of the network.

In this paper we present an approach for a pursuit-evasion problem that considers a 2.5d environment represented by a height map. Such a representation is particularly suitable for large-scale outdoor pursuit-evasion, captures some aspects of 3d visibility and can include target heights. In our approach we construct a graph representation of the environment by sampling strategic locations and computing their detection sets, an extended notion of visibility. From the graph we compute strategies using previous work on graph-searching. These strategies are used to coordinate the robot team and to generate paths for all robots using an appropriate classification of the terrain. In experiments we investigate the performance of our approach and provide examples including a sample map with multiple loops and elevation plateaus and two realistic maps, a village and a mountain range. To the best of our knowledge the presented approach is the first viable solution to 2.5d pursuit-evasion with height maps.

Technology for multirobot systems has advanced to the point where we can consider their use in a variety of important domains, including urban search and rescue. A key to the practical usefulness of multirobot systems is the ability to have a large number of robots effectively controlled by small numbers of operators. In this paper, two modalities for controlling a team of 24 robots in a foraging task in an urban search and rescue environment are compared. In both modalities, multiple operators must monitor video streams from the robots to detect and mark victims on a map as well as teleoperating robots that cannot get themselves out of difficult situations. In the first modality, the operators must also provide waypoints for the robots to explore, using both video and a partially completed map to choose appropriate waypoints. In the second modality, the robots autonomously plan their paths, allowing operators to focus on monitoring the video, but without being able to interpret video streams to guide exploration. Experimental results show that significantly better overall performance is achieved with autonomous path planning, although the reduction in operator workload is not significant.

In this paper, we address the problem of distributed path planning for large teams of hundreds of robots in constrained environments. We introduce two distributed prioritized planning algorithms: an efficient, complete method which is shown to converge to the centralized prioritized planner solution, and a sparse method in which robots discover collisions probabilistically. Planning is divided into a number of iterations, during which every robot simultaneously and independently computes a planning solution based on other robots' path information from the previous iteration. Paths are exchanged in ways that exploit the cooperative nature of the team and a statistical phenomenon known as the “birthday paradox”. Performance is measured in simulated 2D environments with teams of up to 240 robots. We find that in moderately constrained environments, these methods generate solutions of similar quality to a centralized prioritized planner, but display interesting communication and planning time characteristics.

In this paper we explore the effects of service level differentiation on a multi-robot control system. We examine the premise that although long interaction time between robots and operators hurts the efficiency of the system, as it generates longer waiting time for robots, it provides robots with longer neglect time and better performance benefiting the system. In the paper we address the problem of how to choose the optimal service level for an operator in a system through a service level differentiation model. Experimental results comparing system performance for different values of system parameters show that a mixed strategy is a general way to get optimal system performance for a large variety of system parameter settings and in all cases is no worse than a pure strategy.

We are developing a theory for human control of robot teams based on considering how control varies across different task allocations. Our current work focuses on domains such as foraging in which robots perform largely independent tasks. The present study addresses the interaction between automation and organization of human teams in controlling large robot teams performing an Urban Search and Rescue (USAR) task. We identify three subtasks: perceptual search-visual search for victims, assistance-teleoperation to assist robot, and navigation-path planning and coordination. For the studies reported here, navigation was selected for automation because it involves weak dependencies among robots making it more complex and because it was shown in an earlier experiment to be the most difficult. Two possible ways to organize operators were identified as assignment of robots to particular operators or as a shared pool in which operators service robots from the population as needed. The experiment compares two member teams of operators controlling teams of 12 robots each in the assigned robots conditions or sharing control of 24 robots in the shared pool conditions using either waypoint control or autonomous path planning. We identify three self organizing team strategies in the shared pool condition: joint control operators share full authority over robots, mixed control in which one operator takes primary control while the other acts as an assistant, and split control in which operators divide the robots with each controlling a subteam. Automating path planning improved system performance. Effects of team organization favored operator teams who shared authority for the pool of robots.

Team decision-making is a bundle of interdependent activities that involve gathering, interpreting and exchanging information; creating and identifying alternative courses of action; choosing among alternatives by integrating the often different perspectives of team members and implementing a choice and monitoring its consequences. To accomplish joint tasks, human team members often assume distinctive roles in task completion. We believe that to design and build software agents that can assist human teams, we need develop automated techniques to identify the roles of the human decision-makers. If the supporting agents are insensitive to shifts in the team's roles, they cannot effectively monitor the team's activities. This article addresses the problem of doing offline role analysis of battle scenarios from multi-player team games. The ability to identify team roles from observations is important for a wide range of applications including automated commentary generation, game coaching and opponent modeling. We define a role as a preference model over possible actions based on the game state. This article explores two promising approaches for automated role analysis: (1) a model-based system for combining evidence from observed events using the Dempster–Shafer theory and (2) a data-driven discriminative classifier using support vector machines.

In this paper, we describe how agents can support collaborative planning within international coalitions, formed in an ad hoc fashion as a response to military and humanitarian crises. As these coalitions are formed rapidly and without much lead time or co-training, human planners may be required to observe a plethora of policies that direct their planning effort. In a series of experiments, we show how agents can support human planners, ease their cognitive burden by giving advice on the correct use of policies and catch possible violations. The experiments show that agents can effectively prevent policy violations with no significant extra cost.

The present study investigates the effect of the number of controlled robots on performance of an urban search and rescue (USAR) task using a realistic simulation. Participants controlled either 4, 8, or 12 robots. In the fulltask control condition participants both dictated the robots' paths and controlled their cameras to search for victims. In the exploration condition, participants directed the team of robots in order to explore as wide an area as possible. In the perceptual search condition, participants searched for victims by controlling cameras mounted on robots following predetermined paths selected to match characteristics of paths generated under the other two conditions. By decomposing the search and rescue task into exploration and perceptual search subtasks the experiment allows the determination of their scaling characteristics in order to provide a basis for tentative task allocations among humans and automation for controlling larger robot teams. In the fulltask control condition task performance increased in going from four to eight controlled robots but deteriorated in moving from eight to twelve. Workload increased monotonically with number of robots. Performance per robot decreased with increases in team size. Results are consistent with earlier studies suggesting a limit of between 8-12 robots for direct human control.

Majority of service discovery research considers only primitive services as a suitable match for a given query while service combinations are not allowed. However, many realistic queries cannot be matched by individual services and only a combination of several services can satisfy such queries. Allowing service combinations or proper compositions of primitive services as a valid match introduces problems such as unwanted side-effects (i.e., producing an effect that is not requested), effect duplicities (i.e., producing some effect more than once) and contradictory effects (i.e., producing both an effect and its negation). Also the ranking of matched services has to be reconsidered for service combinations. In this paper, we address all the mentioned issues and present a matchmaking algorithm for retrieval of the best top k collision-free service combinations satisfying a given query.

Camera guided teleoperation has long been the preferred mode for controlling remote robots with other modes such as asynchronous control only used when unavoidable. Because controlling multiple robots places additional demands on the operator we hypothesized that removing the forced pace for reviewing camera video might reduce workload and improve performance. In an earlier experiment participants operated four teams performing a simulated urban search and rescue (USAR) task using a conventional streaming video plus map interface or an experimental interface without streaming video but with the ability to store panoramic images on the map to be viewed at leisure. Operators were more accurate in marking victims on maps using the conventional interface; however, ancillary measures suggested that the asynchronous interface succeeded in reducing temporal demands for switching between robots. This raised the possibility that the asynchronous interface might perform better if teams were larger. In this experiment we evaluate the usefulness of asynchronous video for teams of 4, 8, or 12 robots. Operators in the two conditions were equally successful in finding victims, however, the streaming video maintained its advantage for accuracy in locating victims.

We are developing an architecture for controlling robot teams based on considering how control difficulty for different tasks grows with increases in team size. Our analysis suggests that assignments of persons to commander (single commands to entire robot team), operator (commands to individual robots), and coordinator (control of interdependent robots) roles can lead to the most efficient organization. The ability to assign tasks within or between operators makes scheduling these interactions an important factor in team performance. Two possible ways to organize operators are through Individual Assignments of robots or as a Call Center in which operators service robots from the population as needed. In recent experiments we have found that participants performing an Urban Search And Rescue (USAR) foraging task using waypoint control were at or over their limits when controlling 12 robots. The present study uses the same robots, environment, and level of autonomy but with teams of two operators assigned to control 24 robots. These operators controlled teams of 12 robots in the Individual Assignment condition. In the Call Center condition operators shared control of the 24 robots. For this task and level of robot autonomy Individual Assignment participants performed marginally better searching larger regions but without finding more victims.

Teams are a form of organizational structure where the team members engage in information exchanges in order to fulfill team goals. The activities that the team engages in are inter-dependent and usually involve gathering, interpreting and exchanging information; creating and identifying alternative courses of action; choosing among alternatives by considering different viewpoints of team members; choosing among decision alternatives and monitoring the consequences of the decision. Effective teams achieve goals and accomplish tasks that otherwise would not be achievable by groups of uncoordinated individuals. While previous work in teamwork theory has focused on describing ways in which humans coordinate their activities, there has been little previous work on which of those specific activities, information flows and team performance can be enhanced by being aided by software agents. Recent interest in supporting emergency response teams, military interest in operations other than war, and coalition operations, motivates the need for studies that examine agent aiding strategies and their effect on human team performance. This talk will present (a) characteristics and challenges of human teamwork that have not been well studied to date, such as decentralization and self-organization, (b) results of studies of human-only teamwork performance that incorporate these challenges in order to establish a baseline, and (c) identification of fruitful ways for agents to aid human teams with these characteristics. In particular, we will focus on teams that operate in time stressed environments without previous training together. We will also present results of studies where software agents provided decision support for human teams in the performance of a variety of tasks and under different environmental and task constraints. We will close with open challenges and research problems in agent aiding of human teamwork.

Camera guided teleoperation has long been the preferred mode for controlling remote robots, with other modes such as asynchronous control only used when unavoidable. In this experiment we evaluate the usefulness of asynchronous operation for a multirobot search task. Because controlling multiple robots places additional demands on the operator, removing the forced pace for reviewing camera video might reduce workload and improve performance. In the reported experiment participants operated four robot teams performing a simulated urban search and rescue (USAR) task using either conventional streaming video plus a map interface or an experimental interface without streaming video but with the ability to store panoramic images on the map to be viewed at leisure. Search performance was somewhat better using the conventional interface, however, ancillary measures suggest that the asynchronous interface succeeded in reducing temporal demands for switching between robots.

Abstract Web Services providing access to datasources with structured data have an important place in the SOA. In this paper we focus on modeling and discovery of generic data providing services (DPS), with the goal of making data providing services available for interactions with service requesters in contexts such as service composition and mediation. In our model RDF Views are used to represent the content provided by the DPS. A characterization of match between description of DPS as RDF Views and the OWL-S service request is specified, based on which we developed a flexible matchmaking algorithm for discovery of data providing services. Finally, we propose a realization of the DPS using a SOAP version of the SPARQL protocol and a dynamic configuration interface allowing easy interactions of service requesters with data providing services.

The present study investigates the effect of the number of controlled robots on performance of an urban search and rescue (USAR) task using a realistic simulation. Task performance increased in going from four to eight controlled robots but deteriorated in moving from eight to twelve. Workload increased monotonically with number of robots. Performance per robot decreased with increases in team size. Results are consistent with earlier studies suggesting a limit of between 8-12 robots for direct human control. This study demonstrates that these findings generalize to a more realistic setting and complex task.

Many applications require that a group of agents share a coherent distributed picture of the world given communication constraints. This paper describes an analysis and design methodology for coordination algorithms for extremely large groups of agents maintaining a distributed belief. This design methodology creates a probability distribution which relates global properties of the system to agent interaction dynamics using the tools of statistical mechanics. Using this probability distribution we show that this system undergoes a rapid phase transition between low divergence and high divergence in the distributed belief at a critical value of system temperature. We also show empirically that at the critical system temperature the number of messages passed and belief divergence between agents is optimal. Finally, we use this fact to develop an algorithm using system temperature as a local decision parameter for an agent.

This paper presents a decentralized approach to path planning for large numbers of autonomous vehicles in sparse environments. Unlike existing approaches, which are either computationally expensive or communication intensive, the presented approach allows large numbers of vehicles to plan independently with low communication overhead. The key to the algorithm is to observe that, in sparse environments, collisions are exceptional and that most of the time vehicles will simply not hit each other. Hence, it is reasonable to allow vehicles to plan independently and then resolve the small number of conflicts. We operationalize this by having each vehicle send their planned paths to a small number of their team mates via tokens. Each team member is required to check for conflicting paths that they have been informed about via a token and inform those involved when any conflict is detected. Both analytic and empirical results show that the approach has very high probability of detecting all potential collisions for large numbers of vehicles in both 2D and 3D environments.

In today's fast paced military operational environment, vast amounts of information must be sorted out and fused not only to allow commanders to make situation assessments, but also to support the generation of hypotheses about enemy force disposition and enemy intent. An automation methodology and support tools are required to allow commanders to model and assess dynamic situations such as the behavior and intentions of enemy forces based on the flow and fusion of collected information from various sensors. Battlefield situation awareness, including location, movement, and deployment of enemy forces, is essential for commanders to make better decisions than adversaries. Agent-based information fusion and dissemination has great promise to considerably enhance current fusion technology. However, in order for agent-based information fusion to become a reality it must address a multitude of challenges. These challenges can be divided into three general categories: (a) challenges that relate to communication and information dissemination among the different agents in the system, (b) challenges pertaining to algorithms that individual agents use for effective reasoning, and (c) challenges related to integration of overall system aspects and components. In the rest of this overview, we present and discuss what we consider the most important subcategories within these three categories of challenges and briefly summarize work we have done to address them.

A cooperative team's performance strongly depends on the view that the team has of the environment in which it operates. In a team with many autonomous vehicles and many sensors, there is a large volume of information available from which to create that view. However, typically communication bandwidth limitations prevent all sensor readings being shared with all other team members. This paper presents three policies for sharing information in a large team that balance the value of information against communication costs. Analytical and empirical evidence of their effectiveness is provided. The results show that using some easily obtainable probabilistic information about the team dramatically improves overall belief sharing performance. Specifically, by collectively estimating the value of a piece of information, the team can make most efficient use of its communication resources.

The framework for automatic mediation of two process models composed of semantically annotated Web services is presented. Process mediation is hard because of many possible mismatches between process models. We introduce algorithms for the process models analysis to find possible mappings between provider's and requester's process models, or to identify incompatibilities that cannot be reconciled with given set of available data mediators and external services. Results of the analysis phase are used in the mediator runtime component. In particular, we show how the workflow and dataflow mismatches can be resolved.

Price matching policies have been widely adopted in retailing and other industrial markets. The flourishing online channels have made price comparison and matching much easier. Previous research on price matching policy focuses on how this policy impacts the competition among sellers based on simultaneous pricing games. However, besides the role to match the competitors' current price during a purchase (i.e. concurrent price matching), price matching policy usually has another role: to match a seller's own price or the competitors' price if the price drops within a specified period after the purchase (i.e. posterior price matching). This role has important implication for consumers' purchasing behavior. Rational consumers may delay purchasing, hoping for possible markdowns that come later. This delayed purchasing behavior, however, may harm a seller's profit. Posterior price matching allows a seller to induce early purchasing of buyers. This is because with a guarantee to match the lower price that may be offered by the seller later, a buyer cannot gain by waiting. On the other hand, posterior price matching reduces a seller's pricing power, and also changes a seller's pricing strategy over time, influencing a buyer's utility. Therefore whether or not posterior price matching benefits sellers or buyers deserve a close examination. In this paper, we present an analytical model that investigates the impact of posterior price matching on both the buyers' utility and the seller's revenue in three scenarios: (1) the seller is a monopolist in the market; (2) the seller is a semi-monopolist in the market, i.e., he is a monopolist in the first period, but the market is perfectly competitive and he has no pricing power in the second period; and (3) the seller is a price-taking seller, i.e., the market is perfectly competitive, in both periods. We find that in scenario 1 a price matching policy is beneficial for the seller but makes the buyers worse off. However, in scenario 2 and 3, we find that there exists a wide range of situations where a price matching policy surprisingly can benefit both parties.

This paper presents a decentralized model that allows self-interested agents to reach "win-win" agreements in a multi-attribute negotiation. The model is based on an alternating-offer protocol. In each period, the proposing agent is allowed to make a limited number of offers. The responding agent can choose the best offer or reject all of them. In the case of rejection, agents exchange their roles and the negotiation proceeds to the next period. To make counteroffers, an agent first uses the heuristic of choosing, on an indifference curve (or surface), the offer that is closest to the best offer made by the opponent in the previous period, and then taking this offer as the seed, chooses several other offers randomly in a specified neighborhood of this seed offer. Experimental results show that this model can make agents reach near Pareto optimal agreements in general situations where agents have complex preferences on the attributes and incomplete information. Moreover, different from other solutions for multi-attribute negotiations, this model does not require the presence of a mediator.

This paper presents a method for inferring threat in a military campaign through matching of battle field entities to a doctrinal template. In this work the set of random variables denoting the possible template matches for the scenario entities is a realization of a Markov random field. This approach does not separate low level fusion from high level fusion but optimizes both simultaneously. The result of the added high level context is a method that is robust to false positive and false negative, or missed, sensor readings. Furthermore, the high level context helps to direct the search for the best template match. Empirical results illustrate the efficacy of the method both at identifying threats in the face of false negatives, and at negating false positives, as well as illustrating the reduced computational effort resulting from the incorporation of additional high-level context

The problem of decision fusion has been studied for distributed sensor systems in the past two decades. Various techniques have been developed for either binary or multiple hypotheses decision fusion. However, most of them do not address the challenges that come with the changing quality of sensor data. In this paper we investigate adaptive decision fusion rules for multiple hypotheses within the framework of Dempster-Shafer theory. We provide a novel learning algorithm for determining the quality of sensor data in the fusion process. In our approach each sensor actively learns the quality of information from different sensors and updates their reliabilities using the weighted majority technique. Several examples are provided to show the effectiveness of our approach

Geographic routing protocols have been widely used in microsensor networks, however, they cannot directly apply to distributed mobile sensor systems as mobile sensors often do not know their neighbors' exact physical locations. In this paper we consider geographic routing in distributed sensor systems without location information. We address the problem by introducing a lightweight and distributed virtual coordinate assignment protocol. We focus on the effectiveness of routing algorithms for distributed data fusion in the system and provide a detailed analysis of several routing algorithms for a sensor system with group mobility. Our simulation results show that controlled data flows significantly increase the probability of relevant data being fused

The dangerous and time sensitive nature of a disaster area makes it an ideal application for robotic exploration. Our long term goal is to enable humans, software agents, and autonomous robots to work together to save lives. Existing work in coordination for search and rescue does not address the variety of constraints that apply to the problem. This paper provides an expressive language for specifying system constraints. We also describe a coordination architecture capable of quickly finding an optimal or near optimal solution to the combined problems of task allocation, scheduling, and path planning subject to system constraints. We address a perceived lack of benchmarks for this research area by establishing a repository open to the research community which includes a set of benchmarks we designed to illustrate some of the complexities of the problem space. Finally, we evaluate various algorithms on these benchmarks

The Web plays a critical role in hosting Web communities, their content and interactions. A prime example is the open source software (OSS) community, whose members, including software developers and users, interact almost exclusively over the Web, constantly generating, sharing and refining content in the form of software code through active interaction over the Web on code design and bug resolution processes. The Semantic Web is an envisaged extension of the current Web, in which content is given a well defined meaning, through the specification of metadata and ontologies, increasing the utility of the content and enabling information from heterogeneous sources to be integrated. We developed a prototype Semantic Web system for OSS communities, Dhruv. Dhruv provides an enhanced semantic interface to bug resolution messages and recommends related software objects and artifacts. Dhruv uses an integrated model of the OpenACS community, the software, and the Web interactions, which is semi-automatically populated from the existing artifacts of the community.

We present a model for bilateral negotiations that considers the uncertain and dynamic outside options. Outside options affect the negotiation strategies via their impact on the reservation price. The model is composed of three modules: single-threaded negotiations, synchronized multithreaded negotiations, and dynamic multithreaded negotiations. These three modules embody increased sophistication and complexity. The single-threaded negotiation model provides negotiation strategies without specifically considering outside options. The model of synchronized multithreaded negotiations builds on the single-threaded negotiation model and considers the presence of concurrently existing outside options. The model of dynamic multithreaded negotiations expands the synchronized multithreaded model by considering the uncertain outside options that may come dynamically in the future. Experimental analysis is provided to characterize the impact of outside options on the reservation price and thus on the negotiation strategy. The results show that the utility of a negotiator improves significantly if he/she considers outside options, and the average utility is higher when he/she considers both the concurrent outside options and the foresees future options.

Despite the growing number of multi-agent software systems, relatively few physical systems have adopted multi-agent systems technology. Agents that interact with a dynamic physical environment have requirements not shared by virtual agents, including the need to transfer information about the world and their interaction with it. The agent communication languages proven successful in software based multi-agent systems incur overheads that make them impractical or infeasible for the transfer of low-level data. Instead, real world systems typically employ application specific protocols to transfer video, audio, sensory, or telemetry data. These protocols lack the transparency and portability of formal agent communication languages and consequently are limited in their scalability. We propose augmenting the capabilities of current multi-agent systems to provide for the efficient transfer of low-level information, by allowing backchannels of communication between agents with flexible protocols in a carefully principled way. We show that this extension can yield significant performance increases in communication efficiency and discuss the benefits of incorporating backchannels into a search a rescue robot system.

An increasing number of Web services are appearing, users as well as software agents and other web services need to be able to find, select, understand and invoke these services. Today, Web services (e.g. travel services, book selling services, stock reporting services etc) are discovered and invoked manually by human users, which hardcode the interaction between their own programs and the available Web services. Web services standards, such as UDDI, WSDL and SOAP, contribute to this vision by facilitating the interoperation between Web services and software agents or users. As a consequence of these standards is becoming by increasingly easier to connect Web services with their clients. The drawback of these standards is that there is no support for automatic interoperation, and therefore they implicitly assume that a programmer will hardcode the interaction between Web services and his own programs.

In this paper we study the mechanism design problem of coalition formation and cost sharing in an electronic marketplace, where buyers can form coalitions to take advantage of discounts based on volume. The desirable mechanism properties include stability (being in the core), and incentive compatibility with good eficiency, concepts from the perspectives of cooperative and non-cooperative game theory. We first analyze the problem from both these perspectives. We show the impossibility to simultaneously satisfy efficiency, budget balance and individual rationality at a Bayesian-Nash equilibrium, and propose a mechanism in the core of the game. We then present a group of reasonable mechanisms that are derived from the two perspectives, and evaluate their performance in incentive compatibility. Empirical results show positive correlation between stability and incentive compatibility(which is in turn related to efficiency). The mechanism which shares the coalition cost in an egalitarian way is the best in terms of both stability and incentive compatibility.

We envision a future economy where e–markets will play an essential role as exchange hubs for commodities and services. Future e–markets should be designed to be robust to manipulation, flexible, and sufficiently efficient in facilitating exchanges. One of the most important aspects of designing an e–market is market mechanism design. A market mechanism defines the organization, information exchange process, trading procedure, and clearance rules of a market. If we view an e–market as a multi–agent system, the market mechanism also defines the structure and rules of the environment in which agents (buyers and sellers) play the market game. We design an e–market mechanism that is strategy–proof with respect to reservation price, weakly budget–balanced, and individually rational. Our mechanism also makes sellers unlikely to underreport the supply volume to drive up the market price. In addition, by bounding our market’s efficiency loss, we provide fairly unrestrictive sufficient conditions for the efficiency of our mechanism to converge in a strong sense when (1) the number of agents who successfully trade is large, or (2) the number of agents, trading and not, is large. We implement our design using the RETSINA infrastructure, a multi–agent system development toolkit. This enables us to validate our analytically derived bounds by numerically testing our e–market.

To self-adapt ([Schwefel, 1981], [Fogel et al., 1991]) a search parameter, rather than fixing the parameter globally before search begins the value is encoded in each individual along with the other genes. This is done in the hope that the value will then become adapted on a per-individual basis. While this mechanism is very powerful and in some cases essential to achieving good search performance, the dynamics of the adaptation of such traits are often complex and difficult to predict. This paper presents a case study in which self-adapting mutation rates were found to quickly drop below the threshold of effectiveness, bringing productive search to a premature halt. We identify three conditions that may in practice lead to such premature convergence of self-adapting mutation rates. The third condition is of particular interest, involving an interaction between self-adaptation and a process referred to here as "implicit self-adaptation". Our investigation ultimately underlines a key aspect of population-based search: namely, how strongly search is directed toward finding solutions that are not just of high quality, but those which also produce other high quality solutions when subjected to the chosen variation process.

We are investigating techniques for developing distributed and adaptive collections of information agents that coordinate to retrieve, filter and fuse information relevant to the user, task and situation, as well as anticipate user's information needs. In our system of agents, information gathering is seamlessly integrated with decision support. The task for which particular information is requested of the agents does not remain in the user's head but it is explicitly represented and supported through agent collaboration. In this paper we present the distributed system architecture, agent collaboration interactions, and a reusable set of software components for structuring agents. The system architecture has three types of agents: Interface agents interact with the user receiving user specifications and delivering results. They acquire, model, and utilize user preferences to guide system coordination in support of the user's tasks. Task agents help users perform tasks by formulating problem solving plans and carrying out these plans through querying and exchanging information with other software agents. Information agents provide intelligent access to a heterogeneous collection of information sources. We have implemented this system framework and are developing collaborating agents in diverse complex real world tasks, such as organizational decision making, investment counseling, health care and electronic commerce.

Practical optimization problems such as job-shop scheduling often involve optimization criteria that change over time. Repair-based frameworks have been identified as flexible computational paradigms for difficult combinatorial optimization problems. Since the control problem of repair-based optimization is severe, reinforcement learning (RL) techniques can be potentially helpful. However, some of the fundamental assumptions made by traditional RL algorithms are not valid for repair-based optimization. Case-based reasoning compensates for some of the limitations of traditional RL approaches. We present a case-based reasoning RL approach, implemented in the C/sub A/B/sub I/NS system, for repair-based optimization. We chose job-shop scheduling as the testbed for our approach. Our experimental results show that C/sub A/B/sub I/NS is able to effectively solve problems with changing optimization criteria which are not known to the system and only exist implicitly in a extensional manner in the case base.

A model of decentralized problem solving, called distributed constrained heuristic search (DCHS), that provides both structure and focus in individual agent search spaces to optimize decisions in the global space, is presented. The model achieves this by integrating decentralized constraint satisfaction and heuristic search. It is a formalism suitable for describing a large set of distributed artificial intelligence problems. The notion of textures that allow agents to operate in an asynchronous concurrent manner is introduced. The use of textures coupled with distributed asynchronous backjumping, a type of distributed dependency-directed backtracking that the authors have developed, enables agents to instantiate variables in such a way as to substantially reduce backtracking. The approach has been tested experimentally in the domain of decentralized job-shop scheduling. A formulation of distributed job-shop scheduling as a DCHS and experimental results are presented.>

No abstract available.

A formal framework for studying the scheduling problem for task systems with multiple outcome operations and independent control structure is presented Models of sequential programs and their parallel representa tlons (schedules) are developed.Schedules are seen to be restrictions of the parallel program schema of Karp and Mdler The restrictions are that the operations are synchronous and of fixed duration Interpretations of schedules are provided, and it as shown that the schedules are determinate and preserve the results of sequential computations in various senses Various equivalence properties of schedules and their relationships are studied.A number of decldablhty questions are answered by using the notion of "parallel derivatives" introduced by Mlllen Optamallty of schedules IS defined m terms of minimal tame executions, and parallel derivatives are used to generate optimal schedules.Finally, the finite representation of optimal schedules as considered