Arrow Research search

Author name cluster

Gal A. Kaminka

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

55 papers
2 author rows

Possible papers

55

JAAMAS Journal 2026 Journal Article

Performance Competitions as Research Infrastructure: Large Scale Comparative Studies of Multi-Agent Teams

  • Gal A. Kaminka
  • Ian Frank
  • Kumiko Tanaka-Ishii

Abstract Performance competitions (events that pit many different programs against each other on a standardized task) provide a way for a research community to promote research progress towards challenging goals. In this paper, we argue that for maximum research benefit, any such competition must involve comparative studies under closely controlled, varying conditions. We demonstrate the critical role of comparative studies in the context of one well-known and growing performance competition: the annual Robotic Soccer World Cup (RoboCup) Championship. Specifically, over the past three years, we have carried out annual large-scale comparative evaluations—distinct from the competition itself—of the multi-agent teams taking part in the largest RoboCup league. Our study, which involved 30 different teams of agents produced by dozens of different research groups, focused on robustness. We show that (i) multi-agent teams exhibit a clear performance-robustness tradeoff; (ii) teams tend to over-specialize, so that they cannot handle beneficial changes we make to their operating environment; and (iii) teams improve in performance more than in robustness from one year to the next, despite the emphasis by RoboCup organizers on robustness as a key challenge. These results demonstrate the potential of large-scale comparative studies for producing important results otherwise difficult to discover, and are significant both in the lessons they raise for designers of multi-agent teams, and in understanding the place of performance competitions within the multi-agent research infrastructure.

Details DOI

ECAI Conference 2024 Conference Paper

Planning to be Healthy: Towards Personalized Medication Planning

  • Lee-or Alon
  • Hana Weitman
  • Alexander Shleyfman
  • Gal A. Kaminka

Personalized medication plans determine the selection, dosage, and administration schedule of medications, to achieve medical goals that are specific to the patient and to its individual health constraints. This paper introduces medication planning as a novel domain for artificial intelligence planning, using PDDL+. We evaluate the suggested representation via experiments based on data collected from medical studies conducted on mice and rats.

Details

ICAPS Conference 2024 Conference Paper

Tightest Admissible Shortest Path

  • Eyal Weiss 0001
  • Ariel Felner
  • Gal A. Kaminka

The shortest path problem in graphs is fundamental to AI. Nearly all variants of the problem and relevant algorithms that solve them ignore edge-weight computation time and its common relation to weight uncertainty. This implies that taking these factors into consideration can potentially lead to a performance boost in relevant applications. Recently, a generalized framework for weighted directed graphs was suggested, where edge-weight can be computed (estimated) multiple times, at increasing accuracy and run-time expense. We build on this framework to introduce the problem of finding the tightest admissible shortest path (TASP); a path with the tightest suboptimality bound on the optimal cost. This is a generalization of the shortest path problem to bounded uncertainty, where edge-weight uncertainty can be traded for computational cost. We present a complete algorithm for solving TASP, with guarantees on solution quality. Empirical evaluation supports the effectiveness of this approach.

Details

ECAI Conference 2023 Conference Paper

A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates

  • Eyal Weiss 0001
  • Ariel Felner
  • Gal A. Kaminka

The shortest path problem in graphs is a cornerstone of AI theory and applications. Existing algorithms generally ignore edge weight computation time. We present a generalized framework for weighted directed graphs, where edge weight can be computed (estimated) multiple times, at increasing accuracy and run-time expense. This raises several generalized variants of the shortest path problem. We introduce the problem of finding a path with the tightest lower-bound on the optimal cost. We then present two complete algorithms for the generalized problem, and empirically demonstrate their efficacy.

Details

ICAPS Conference 2023 Conference Paper

Planning with Multiple Action-Cost Estimates

  • Eyal Weiss 0001
  • Gal A. Kaminka

AI Planning require computing the costs of ground actions. While often assumed to be negligible, the run-time of this computation can become a major component in the overall planning run-time. To address this, we introduce planning with multiple action cost estimates, a generalization of classical planning, where action cost can be incrementally determined using multiple estimation procedures, which trade computational effort for increasingly tightening bounds on the exact cost. We then present ACE, a generalized A*, to solve such problems. We provide theoretical guarantees, and extensive experiments that show considerable run-time savings compared to alternatives.

Details

AAMAS Conference 2019 Conference Paper

Is Agent Software More Complex than Other Software?

  • Alon Zanbar
  • Gal A. Kaminka

We empirically investigate agent software repositories using commonly used software metrics, which are used in software engineering literature to quantify meaningful characteristics of software based on its source code. We contrast the measurements with those of software in other categories. Analyzing hundreds of software projects, we find that agent software may be different from other types of software, in terms of software complexity measures.

PDF

TIST Journal 2018 Journal Article

Simulating Urban Pedestrian Crowds of Different Cultures

  • Gal A. Kaminka
  • Natalie Fridman

Models of crowd dynamics are critically important for urban planning and management. They support analysis, facilitate qualitative and quantitative predictions, and synthesize behaviors for simulations. One promising approach to crowd modeling relies on micro-level agent-based simulations, where the interactions of simulated individual agents in the crowd result in macro-level crowd dynamics which are the object of study. This article reports on an agent-based model of urban pedestrian crowds, where culture is explicitly modeled. We extend an established agent-based social agent model, inspired by social psychology, to account for individual cultural attributes discussed in social science literature. We then embed the model in a simulation of pedestrians and explore the resulting macro-level crowd behaviors, such as pedestrian flow, lane changes rate, and so on. We validate the model by quantitatively comparing the simulation results to the pedestrian dynamics in movies of human crowds in five different countries: Iraq, Israel, England, Canada, and France. We conclude that the model can faithfully replicate urban pedestrians in different cultures. Encouraged by these results, we explore simulations of mixed-culture pedestrian crowds.

Details DOI

IJCAI Conference 2017 Conference Paper

Heuristic Online Goal Recognition in Continuous Domains

  • Mor Vered
  • Gal A. Kaminka

Goal recognition is the problem of inferring the goal of an agent, based on its observed actions. An inspiring approach—plan recognition by planning (PRP)—uses off-the-shelf planners to dynamically generate plans for given goals, eliminating the need for the traditional plan library. However, existing PRP formulation is inherently inefficient in online recognition, and cannot be used with motion planners for continuous spaces. In this paper, we utilize a different PRP formulation which allows for online goal recognition, and for application in continuous spaces. We present an online recognition algorithm, where two heuristic decision points may be used to improve run-time significantly over existing work. We specify heuristics for continuous domains, prove guarantees on their use, and empirically evaluate the algorithm over hundreds of experiments in both a 3D navigational environment and a cooperative robotic team task.

PDF Details

IJCAI Conference 2016 Conference Paper

Rule-Based Programming of Molecular Robot Swarms for Biomedical Applications

  • Inbal Wiesel-Kapah
  • Gal A. Kaminka
  • Guy Hachmon
  • Noa Agmon
  • Ido Bachelet

Molecular robots (nanobots) are being developed for biomedical applications, e. g. , to deliver medications without worrying about side-effects. Future treatments will require swarms of heterogeneous nanobots. We present a novel approach to generating such swarms from a treatment program. A compiler translates medications, written in a rule-based language, into specifications of a swarm built by specializing generic nanobot platforms to specific pay-loads and action-triggering behavior. The mixture of nanobots, when deployed, carries out the treatment program. We describe the medication programming language, and the associated compiler. We prove the validity of the compiler output, and report on in-vitro experiments using generated nanobot swarms.

PDF Details

IROS Conference 2014 Conference Paper

A novel user-guided interface for robot search

  • Shahar Kosti
  • David Sarne
  • Gal A. Kaminka

Human operators play a key role in robotic exploration and search missions, as the interpretation of camera images typically requires the visual perception skills of humans. Thus one the key challenges in building effective robotic systems for such missions lies in developing good operator interfaces. In this paper, we present a novel asynchronous user-guided interface for human operators of robotic search of an unknown area. Enabled by efficient methods to store and retrieve recorded images (and meta information) in real-time, our interface allows the operator to click on any point of interest. The operator is then presented with highly-relevant images that cover the point, without occlusion. This, in contrast with system-guided approaches, where an automated system selects areas and images for inspection. Experiments with 32 human subjects in two different-size maps favor the user-guided approach we present over the system-guided approach. Additional experiments with human subjects provide an explanation as to the environment characteristics that favor our approach.

Details

IROS Conference 2014 Conference Paper

Safest path adversarial coverage

  • Roi Yehoshua
  • Noa Agmon
  • Gal A. Kaminka

Coverage is a fundamental problem in robotics, where one or more robots are required to visit each point in a target area at least once. While most previous work concentrated on finding a solution that completes the coverage as quickly as possible, in this paper we consider a new version of the problem: adversarial coverage. Here, the robot operates in an environment that contains threats that might stop the robot. We introduce the problem of finding the safest adversarial coverage path, and present different optimization criteria for the evaluation of these paths. We show that finding an optimal solution to the safest coverage problem is NP-Complete. We therefore suggest two heuristic algorithms: STAC, a spanning-tree based coverage algorithm, and GSAC, which follows a greedy approach. These algorithms produce close to optimal solutions in polynomial time. We establish theoretical bounds on the total risk involved in the coverage paths created by these algorithms and on their lengths. Lastly, we compare the effectiveness of these two algorithms in various types of environments and settings.

Details

IROS Conference 2013 Conference Paper

Robotic adversarial coverage: Introduction and preliminary results

  • Roi Yehoshua
  • Noa Agmon
  • Gal A. Kaminka

This paper discusses the problem of generating efficient coverage paths for a mobile robot in an adversarial environment, where threats exist that might stop the robot. First, we formally define the problem of adversarial coverage, and present optimization criteria used for evaluation of coverage algorithms in adversarial environments. We then present a coverage area planning algorithm based on a map of the probable threats. The algorithm tries to minimize the total risk involved in covering the target area while taking into account coverage time constrains. The algorithm is based on incrementally extending the coverage path to the nearest safe cells while allowing the robot to repeat its steps. By allowing the robot to visit each cell in the target area more than once, the accumulated risk can be reduced at the expense of extending the coverage time. We show the effectiveness of this algorithm in extensive experiments.

Details

TIST Journal 2013 Journal Article

Using qualitative reasoning for social simulation of crowds

  • Natalie Fridman
  • Gal A. Kaminka

The ability to model and reason about the potential violence level of a demonstration is important to the police decision making process. Unfortunately, existing knowledge regarding demonstrations is composed of partial qualitative descriptions without complete and precise numerical information. In this article we describe a first attempt to use qualitative reasoning techniques to model demonstrations. To our knowledge, such techniques have never been applied to modeling and reasoning regarding crowd behaviors, nor in particular demonstrations. We develop qualitative models consistent with the partial, qualitative social science literature, allowing us to model the interactions between different factors that influence violence in demonstrations. We then utilize qualitative simulation to predict the potential eruption of violence, at various levels, based on a description of the demographics, environmental settings, and police responses. We incrementally present and compare three such qualitative models. The results show that while two of these models fail to predict the outcomes of real-world events reported and analyzed in the literature, one model provides good results. We also examine whether a popular machine learning algorithm (decision tree learning) can be used. While the results show that the decision trees provide improved predictions, we show that the QR models can be more sensitive to changes, and can account for what-if scenarios, in contrast to decision trees. Moreover, we introduce a novel analysis algorithm that analyzes the QR simulations, to automatically determine the factors that are most important in influencing the outcome in specific real-world demonstrations. We show that the algorithm identifies factors that correspond to experts' analysis of these events.

Details DOI

AAMAS Conference 2011 Conference Paper

ESCAPES - Evacuation Simulation with Children, Authorities, Parents, Emotions, and Social comparison

  • Jason Tsai
  • Natalie Fridman
  • Emma Bowring
  • Matthew Brown
  • Shira Epstein
  • Gal A. Kaminka
  • Stacy Marsella
  • Andrew Ogden

In creating an evacuation simulation for training and planning, realistic agents that reproduce known phenomenon are required. Evacuation simulation in the airport domain requires additional features beyond most simulations, including the unique behaviors of first-time visitors who have incomplete knowledge of the area and families that do not necessarily adhere to often-assumed pedestrian behaviors. Evacuation simulations not customized for the airport domain do not incorporate the factors important to it, leading to inaccuracies when applied to it. In this paper, we describe ESCAPES, a multiagent evacuation simulation tool that incorporates four key features: (i) different agent types; (ii) emotional interactions; (iii) informational interactions; (iv) behavioral interactions. Our simulator reproduces phenomena observed in existing studies on evacuation scenarios and the features we incorporate substantially impact escape time. We use ESCAPES to model the International Terminal at Los Angeles International Airport (LAX) and receive high praise from security officials.

PDF

AAMAS Conference 2011 Conference Paper

Online Anomaly Detection in Unmanned Vehicles

  • Eliahu Khalastchi
  • Gal A. Kaminka
  • Meir Kalech
  • Raz Lin

Autonomy requires robustness. The use of unmanned (autonomous) vehicles is appealing for tasks which are dangerous or dull. However, increased reliance on autonomous robots increases reliance on their robustness. Even with validated software, physical faults can cause the controlling software to perceive the environment incorrectly, and thus to make decisions that lead to task failure. We present an online anomaly detection method for robots, that is light-weight, and is able to take into account a large number of monitored sensors and internal measurements, with high precision. We demonstrate a specialization of the familiar Mahalanobis Distance for robot use, and also show how it can be used even with very large dimensions, by online selection of correlated measurements for its use. We empirically evaluate these contributions in different domains: commercial Unmanned Aerial Vehicles (UAVs), a vacuum-cleaning robot, and a high-fidelity flight simulator. We find that the online Mahalanobis distance technique, presented here, is superior to previous methods.

PDF

AAMAS Conference 2011 Conference Paper

Who Goes There? Selecting a Robot to Reach a Goal Using Social Regret

  • Meytal Traub
  • Gal A. Kaminka
  • Noa Agmon

A common decision problem in multi-robot applications involves deciding on which robot, out of a group of N robots, should travel to a goal location, to carry out a task there. Trivially, this decision problem can be solved greedily, by selecting the robot with the shortest expected travel time. However, this ignores the inherent uncertainty in path traversal times; we may prefer a robot that is slower (but always takes the same time), over a robot that is expected to reach the goal faster, but on occasion takes a very long time to arrive. We make several contributions that address this challenge. First, we bring to bear economic decision-making theory, to distinguish between different selection policies, based on risk (risk averse, risk seeking, etc. ). Second, we introduce social regret (the difference between the actual travel time by the selected robot, and the hypothetical time of other robots) to augment decision-making in practice. Then, we carry out experiments in simulation and with real robots, to demonstrate the usefulness of the selection procedures under real-world settings, and find that travel-time distributions have repeating characteristics.

PDF

ICRA Conference 2010 Conference Paper

Adaptive multi-robot coordination: A game-theoretic perspective

  • Gal A. Kaminka
  • Dan Erusalimchik
  • Sarit Kraus

Multi-robot systems researchers have been investigating adaptive coordination methods for improving spatial coordination in teams. Such methods adapt the coordination method to the dynamic changes in density of the robots. Unfortunately, while their empirical success is evident, none of these methods has been understood in the context of existing formal work on multi-robot learning. This paper presents a reinforcement-learning approach to coordination algorithm selection, which is not only shown to work well in experiments, but is also analytically grounded. We present a reward function (Effectiveness Index, EI), that reduces time and resources spent coordinating, and maximizes the time between conflicts that require coordination. It does this by measuring the resource-spending velocity. We empirically show its success in simulations of multi-robot foraging. In addition, we analytically explore the reasons that EI works well. We show that under some assumptions, spatial coordination opportunities can be modeled as matrix games in which the payoffs are directly a function of EI estimates. The use of reinforcement learning leads to robots maximizing their EI rewards in equilibrium. This work is a step towards bridging the gap between the theoretical study of interactions, and their use in multi-robot coordination.

Details

ICRA Conference 2010 Conference Paper

Detecting anomalies in unmanned vehicles using the Mahalanobis distance

  • Raz Lin
  • Eliahu Khalastchi
  • Gal A. Kaminka

The use of unmanned autonomous vehicles is becoming more and more significant in recent years. The fact that the vehicles are unmanned (whether autonomous or not), can lead to greater difficulties in identifying failure and anomalous states, since the operator cannot rely on its own body perceptions to identify failures. Moreover, as the autonomy of unmanned vehicles increases, it becomes more difficult for operators to monitor them closely, and this further exacerbates the difficulty of identifying anomalous states, in a timely manner. Model-based diagnosis and fault-detection systems have been proposed to recognize failures. However, these rely on the capabilities of the underlying model, which necessarily abstracts away from the physical reality of the robot. In this paper we propose a novel, model-free, approach for detecting anomalies in unmanned autonomous vehicles, based on their sensor readings (internal and external). Experiments conducted on Unmanned Aerial Vehicles (UAVs) and Unmanned Ground Vehicles (UGVs) demonstrate the efficacy of the approach by detecting the vehicles deviations from nominal behavior.

Details

IJCAI Conference 2009 Conference Paper

  • Noa Agmon
  • Sarit Kraus
  • Gal A. Kaminka
  • Vladimir Sadov

We study the problem of multi-robot perimeter patrol in adversarial environments, under uncertainty of adversarial behavior. The robots patrol around a closed area using a nondeterministic patrol algorithm. The adversary’s choice of penetration point depends on the knowledge it obtained on the patrolling algorithm and its weakness points. Previous work investigated full knowledge and zero knowledge adversaries, and the impact of their knowledge on the optimal algorithm for the robots. However, realistically the knowledge obtained by the adversary is neither zero nor full, and therefore it will have uncertainty in its choice of penetration points. This paper considers these cases, and offers several approaches to bounding the level of uncertainty of the adversary, and its influence on the optimal patrol algorithm. We provide theoretical results that justify these approaches, and empirical results that show the performance of the derived algorithms used by simulated robots working against humans playing the role of the adversary is several different settings.

PDF Details

AAMAS Conference 2009 Conference Paper

Of Robot Ants and Elephants

  • Asaf Shiloni
  • Noa Agmon
  • Gal A. Kaminka

Investigations of multi-robot systems often make implicit assumptions concerning the computational capabilities of the robots. Despite the lack of explicit attention to the computational capabilities of robots, two computational classes of robots emerge as focal points of recent research: Robot Ants and robot Elephants. Ants have poor memory and communication capabilities, but are able to communicate using pheromones, in effect turning their work area into a shared memory. By comparison, elephants are computationally stronger, have large memory, and are equipped with strong sensing and communication capabilities. Unfortunately, not much is known about the relation between the capabilities of these models in terms of the tasks they can address. In this paper, we present formal models of both ants and elephants, and investigate if one dominates the other. We present two algorithms: AntEater, which allows elephant robots to execute ant algorithms; and ElephantGun, which converts elephant algorithms—specified as Turing machines—into ant algorithms. By exploring the computational capabilities of these algorithms, we reach interesting conclusions regarding the computational power of both models.

PDF

JAAMAS Journal 2008 Journal Article

Detecting disagreements in large-scale multi-agent teams

  • Gal A. Kaminka

Abstract Intermittent sensory, actuation and communication failures may cause agents to fail in maintaining their commitments to others. Thus to collaborate robustly, agents must monitor others to detect coordination failures. Previous work on monitoring has focused mainly on small-scale systems, with only a limited number of agents. However, as the number of monitored agents is scaled up, two issues are raised that challenge previous work. First, agents become physically and logically disconnected from their peers, and thus their ability to monitor each other is reduced. Second, the number of possible coordination failures grows exponentially, with all potential interactions. Thus previous techniques that sift through all possible failure hypotheses cannot be used in large-scale teams. This paper tackles these challenges in the context of detecting disagreements among team-members, a monitoring task that is of particular importance to robust teamwork. First, we present new bounds on the number of agents that must be monitored in a team to guarantee disagreement detection. These bounds significantly reduce the connectivity requirements of the monitoring task in the distributed case. Second, we present YOYO, a highly scalable disagreement-detection algorithm which guarantees sound detection. YOYO’s run-time scales linearly in the number of monitored agents, despite the exponential number of hypotheses. It compactly represents all valid hypotheses in single structure, while allowing for a complex hierarchical organizational structure to be considered in the monitoring. Both YOYO and the new bounds are explored analytically and empirically in monitoring problems involving thousands of agents.

Details DOI

ICRA Conference 2008 Conference Paper

Multi-robot perimeter patrol in adversarial settings

  • Noa Agmon
  • Sarit Kraus
  • Gal A. Kaminka

This paper considers the problem of multi-robot patrol around a closed area with the existence of an adversary attempting to penetrate into the area. In case the adversary knows the patrol scheme of the robots and the robots use a deterministic patrol algorithm, then in many cases it is possible to penetrate with probability 1. Therefore this paper considers a non-deterministic patrol scheme for the robots, such that their movement is characterized by a probability p. This patrol scheme allows reducing the probability of penetration, even under an assumption of a strong opponent that knows the patrol scheme. We offer an optimal polynomial-time algorithm for finding the probability p such that the minimal probability of penetration detection throughout the perimeter is maximized. We describe three robotic motion models, defined by the movement characteristics of the robots. The algorithm described herein is suitable for all three models.

Details

AAMAS Conference 2007 Conference Paper

Dynamics Based Control with an Application to Area-Sweeping Problems

  • Zinovi Rabinovich
  • Jeffrey S. Rosenschein
  • Gal A. Kaminka

In this paper we introduce Dynamics Based Control (DBC), an approach to planning and control of an agent in stochastic environments. Unlike existing approaches, which seek to optimize expected rewards (e. g. , in Partially ObservableMarkov Decision Problems (POMDPs)), DBC optimizes system behavior towards specified system dynamics. We show that a recently developed planning and control approach, Extended Markov Tracking (EMT) is an instantiation of DBC. EMT employs greedy action selection to provide an efficient control algorithm in Markovian environments. We exploit this efficiency in a set of experiments that applied multitarget EMT to a class of area-sweeping problems (searching for moving targets). We show that such problems can be naturally defined and efficiently solved using the DBC framework, and its EMT instantiation.

PDF

ICRA Conference 2007 Conference Paper

Integration of Coordination Mechanisms in the BITE Multi-Robot Architecture

  • Gal A. Kaminka
  • Inna Frenkel

Recent years are seeing a renewed interest in general multi-robot architectures, capable of automating coordination. However, few architectures explore integration of multiple coordination mechanisms. Thus the question of how to best integrate coordination mechanisms is left open. This paper focuses on the micro-kernel integration approach used in BITE (Bar Ilan Teamwork Engine), a multi-robot behavior-based architecture. This approach allows the developer to plug in coordination mechanisms (teamwork behaviors) to be used depending on the context of execution. BITE imposes constraints on the specification of taskwork behaviors, which allow BITE's control algorithm to automatically determine sequencing and task-allocation points during task execution. At such points, teamwork behaviors (known as interaction behaviors) are triggered to automate the coordination processes. We argue that BITE's approach is preferable to the methodology of existing architectures, and provide analysis of experiments in using BITE with Sony AIBO robots, to support our argument

Details

AAMAS Conference 2007 Conference Paper

Matrix-Based Representation for Coordination Fault Detection: A Formal Approach

  • Meir Kalech
  • Michael Lindner
  • Gal A. Kaminka

Teamwork requires that team members coordinate their actions. The representation of the coordination is a key requirement since it influences the complexity and flexibility of reasoning team–members. One aspect of this requirement is detecting coordination faults as a result of intermittent failures of sensors, communication failures, etc. Detection of such failures, based on observations of the behavior of agents, is of prime importance. Though different solutions have been presented thus far, none has presented a comprehensive and formal resolution to this problem. This paper presents a formal approach to representing multi-agent coordination, and multi-agent observations, using matrix structures. This representation facilitates easy representation of coordination requirements, modularity, flexibility and reuse of existing systems. Based on this representation we present a novel solution for fault-detection that is both generic and efficient for large-scale teams.

PDF

ICRA Conference 2007 Conference Paper

Multi-Robot Area Patrol under Frequency Constraints

  • Yehuda Emaliah
  • Noa Agmon
  • Gal A. Kaminka

This paper discusses the problem of generating patrol paths for a team of mobile robots inside a designated target area. Patrolling requires an area to be visited repeatedly by the robot(s) in order to monitor its current state. First, we present frequency optimization criteria used for evaluation of patrol algorithms. We then present a patrol algorithm that guarantees maximal uniform frequency, i. e. , each point in the target area is covered at the same optimal frequency. This solution is based on finding a circular path that visits all points in the area, while taking into account terrain directionality and velocity constraints. Robots are positioned uniformly along this path, using a second algorithm. Moreover, the solution is guaranteed to be robust in the sense that uniform frequency of the patrol is achieved as long as at least one robot works properly.

Details

AAMAS Conference 2007 Conference Paper

On the Robustness of Preference Aggregation in Noisy Environments

  • Ariel D. Procaccia
  • Jeffrey S. Rosenschein
  • Gal A. Kaminka

In an election held in a noisy environment, agents may unintentionally perturb the outcome by communicating faulty preferences. We investigate this setting by introducing a theoretical model of noisy preference aggregation and formally defining the (worst-case) robustness of a voting rule. We use our model to analytically bound the robustness of various prominent rules. The results show that the robustness of voting rules is diverse, with different rules positioned at either end of the spectrum. These results allow selection of voting rules that support preference aggregation in the face of noise.

PDF

AAMAS Conference 2007 Conference Paper

Social Comparison in Crowds: A Short Report

  • Gal A. Kaminka
  • Natalie Fridman

Modeling crowd behavior is an important challenge for cognitive modelers. We propose a novel model of crowd behavior, based on Festinger's Social Comparison Theory, a social psychology theory known and expanded since the early 1950's. We propose a concrete framework for SCT, and evaluate its implementations in several crowd behavior scenarios. Results from task measures and human judges evaluation shows that the SCT model produces improved results compared to base models from the literature.

PDF

AAMAS Conference 2007 Conference Paper

Towards Collaborative Task and Team Maintenance

  • Gal A. Kaminka
  • Ari Yakir
  • Dan Erusalimchik
  • Nirom Cohen-Nov

There is significant interest in modeling teamwork in agents. In recent years, it has become widely accepted that it is possible to separate teamwork from taskwork, providing support for domainindependent teamwork at an architectural level, using teamwork models. However, existing teamwork models (both in theory and practice) focus almost exclusively on achievement goals, and ignore maintenance goals, where the value of a proposition is to be maintained over time. Such maintenance goals exist both in taskwork (i. e. , agents take actions to maintain a condition while a task is executing), as well as in teamwork (i. e. , agents take actions to maintain the team). This paper presents mechanisms for collaborative maintenance in both taskwork and teamwork, allowing for fiexible selection of the maintenance protocol. The mechanism is integrated and evaluated in two teamwork architectures for situated agent teams: DIESEL, an implemented teamwork and taskwork architecture, built on top of Soar, and BITE, an architecture for physical behavior-based robots. We provide details of these implementations, and the results from experiments demonstrating the benefits of support for collaborative maintenance processes, in several dynamic rich domains. We show that the use of collaborative maintenance leads to significant improvement in task performance in all domains.

PDF

AAMAS Conference 2007 Conference Paper

Utility-Based Plan Recognition: An Extended Abstract

  • Dorit Avrahami-Zilberbrand
  • Gal A. Kaminka

Plan recognition is the process of inferring other agents' plans and goals based on their observable actions. Essentially all previous work in plan recognition has focused on the recognition process itself, with no regard to the use of the information in the recognizing agent. As a result, low-likelihood recognition hypotheses that may imply significant meaning to the observer, are ignored in existing work. In this paper, we present novel efficient algorithms that allows the observer to incorporate her own biases and preferences—in the form of a utility function—into the plan recognition process. This allows choosing recognition hypotheses based on their expected utility to the observer. We call this Utility-based Plan Recognition (UPR). We briefly discuss a hybrid symbolic decisiontheoretic plan recognizer, and demonstrate the efficacy of this approach in an example.

PDF

ICRA Conference 2006 Conference Paper

Constructing Spanning Trees for Efficient Multi-robot Coverage

  • Noa Agmon
  • Noam Hazon
  • Gal A. Kaminka

This paper discusses the problem of building efficient coverage paths for a team of robots. An efficient multirobot coverage algorithm should result in a coverage path for every robot, such that the union of all paths generates a full coverage of the terrain and the total coverage time is minimized. A method, underlying several coverage algorithms, suggests the use of spanning trees as base for creating coverage paths. Current studies assume that the spanning tree is given, and try to make the most out of the given configuration. However, overall performance of the coverage is heavily dependent on the given spanning tree. This paper tackles the open challenge of constructing a coverage spanning tree that minimizes the time to complete coverage. We argue that the choice of the initial spanning tree has far reaching consequences concerning the coverage time, and if the tree is constructed appropriately, it could considerably reduce the coverage time of the terrain. Therefore the problem studied here is finding spanning trees that would decrease the coverage time of the terrain when used as base for multi-robot coverage algorithms. The main contributions of this paper are twofold. First, it provides initial sound discussion and results concerning the construction of the tree as a crucial base for any efficient coverage algorithm. Second, it describes a polynomial-time tree construction algorithm that, as shown in extensive simulations, dramatically improves the coverage time even when used as a basis for a simple, inefficient, coverage algorithm

Details

ICRA Conference 2006 Conference Paper

Experiments with an Ecological Interface for Monitoring Tightly-coordinated Robot Teams

  • Gal A. Kaminka
  • Yehuda Emaliah

Many robotics applications require a human operator to monitor multiple robots that collaborate to achieve the operator's goals. Most approaches to such monitoring focus on each robot independently of its peers. When robots are tightly-coordinated, the operator is thus cognitively burdened to build a mental picture of the state of coordination. We report on extensive experiments (approximately 100 hours) with up to 25 human operators, working in two coordinated multi-robot tasks. In these, we contrasted standard displays, which assume each robot is independent, with an ecological socially-attentive display that makes the state of coordination explicit. The results show significant improvements in task completion time, number of failures, and the failure rate. Moreover, the display reduces the variance in operator control, thus leading to significantly more consistent operator performance

Details

ICRA Conference 2006 Conference Paper

Towards Robust Multi-robot Formations

  • Gal A. Kaminka
  • Ruti Glick

Robots in formations move while maintaining a predefined geometric shape. Previous work has examined formation-maintenance algorithms that would ensure the stability of the formation. However, for each geometric formation, an exponential number of stable controllers exists. Thus a key question is how to select (construct) a formation controller that optimizes desired properties, such as sensor usage for robustness. This paper presents a monitoring multi-graph framework for formation controller selection, based on sensor-morphology considerations. We instantiate the framework, and present two contributions. First, we show that graph-theoretic techniques can then be used to compute sensing policies that maintain a given formation. In particular, sensor-based control laws for separation-bearing (distance-angle) formation control can be automatically constructed. Second, we present a protocol allowing controllers to be switched on-line, to allow robots to adjust to sensory failures. We report on results from comprehensive experiments with physical robots. The results show that the use of the dynamic protocol allows formations of physical robots to move significantly faster and with greater precision, while reducing the number of formation failures

Details

ICRA Conference 2006 Conference Paper

Towards Robust on-line Multi-robot Coverage

  • Noam Hazon
  • Fabrizio Mieli
  • Gal A. Kaminka

Area coverage is an important task for mobile robots, with many real-world applications. In many cases, the coverage has to be completed without the use of a map or any a priori knowledge about the area, a process referred-to as on-line coverage. Previous investigations of multi-robot on-line coverage focused on the improved efficiency gained from the use of multiple robots, but did not formally addressed the potential for greater robustness. We present a novel multi-robot on-line coverage algorithm, based on approximate cell decomposition. We analytically show that the algorithm is complete and robust, in that as long as a single robot is able to move, the coverage would be completed. We analyze the assumptions underlying the algorithm requirements and present a number of techniques for executing it in real robots. We show empirical coverage-time results of running the algorithm in two different environments and several group sizes

Details

AAAI Conference 2005 Conference Paper

Flexible Teamwork in Behavior-Based Robots

  • Gal A. Kaminka

A key challenge in deploying teams of robots in real-world applications is to automate the control of teamwork, such that the designer can focus on the taskwork. Existing teamwork architectures seeking to address this challenge are monolithic, in that they commit to interaction protocols at the architectural level, and do not allow the designer to mix and match protocols for a given task. We present BITE, a behaviorbased teamwork architecture that automates collaboration in physical robots, in a distributed fashion. BITE separates task behaviors that control a robot’s interaction with its task, from interaction behaviors that control a robot’s interaction with its teammates. This distinction provides for flexibility and modularity in terms of the interactions used by teammates to collaborate effectively. It also allows BITE to synthesize and significantly extend existing teamwork architectures. BITE also incorporates key lessons learned in applying multi-agent teamwork architectures in physical robot teams. We present empirical results from experiments with teams of Sony AIBO robots executing BITE, and discuss the lessons learned.

PDF Details

ICRA Conference 2005 Conference Paper

Redundancy, Efficiency and Robustness in Multi-Robot Coverage

  • Noam Hazon
  • Gal A. Kaminka

Area coverage is an important task for mobile robots, with many real-world applications. Motivated by potential efficiency and robustness improvements, there is growing interest in the use of multiple robots in coverage. Previous investigations of multi-robot coverage focuses on completeness and eliminating redundancy, but does not formally address robustness, nor examine the impact of the initial positions of robots on the coverage time. Indeed, a common assumption is that non-redundancy leads to improved coverage time. We address robustness and efficiency in a family of multi-robot coverage algorithms, based on spanning-tree coverage of approximate cell decomposition. We analytically show that the algorithms are robust, in that as long as a single robot is able to move, the coverage will be completed. We also show that non-redundant (non-back tracking) versions of the algorithms have a worst-case coverage time virtually identical to that of a single robot—thus no performance gain is guaranteed in non-redundant coverage. Moreover, this worst-case is in fact common in real-world applications. Surprisingly, however, redundant coverage algorithms lead to guaranteed performance which halves the coverage time even in the worst case.

Details

AAAI Conference 2005 Conference Paper

Supporting Collaborative Activity

  • Meirav Hadad
  • Gal A. Kaminka

This paper presents a model—SharedActivity—for collaborative agents acting in a group. The model suggests mental states for agents with different levels of cooperation and permits the formation of groups in which members increase individual benefits. Unlike previous models, the model covers group member behavior where group members do not have a joint goal, but act collaboratively. The model defines key components of a collaborative activity and provides a platform for supporting such activity. We studied the behavior of the model in a simulation environment. Results show how the benefit attained by cooperation is influenced by the complexity of the environment, the number of group members, and the social dependencies between the members. The results demonstrate that the model covers social behavior both in settings previously addressed, as well as in novel settings.

PDF Details

IJCAI Conference 2003 Conference Paper

On the Design of Social Diagnosis Algorithms for Multi-Agent Teams

  • Meir Kalech
  • Gal A. Kaminka

Teamwork demands agreement among teammembers to collaborate and coordinate effectively. When a disagreement between teammates occurs (due to failures), team-members should ideally diagnose its causes, to resolve the disagreement. Such diagnosis of social failures can be expensive in communication and computation overhead, which previous work did not address. We present a novel design space of diagnosis algorithms, distinguishing several phases in the diagnosis process, and providing alternative algorithms for each phase. We then combine these algorithms in different ways to empirically explore specific design choices in a complex domain, on thousands of failure cases. The results show that centralizing the diagnosis disambiguation process is a key factor in reducing communications, while run-time is affected mainly by the amount of reasoning about other agents. These results contrast sharply with previous work in disagreement detection, in which distributed algorithms reduce communications.

PDF

AAAI Conference 1999 Short Paper

Execution Monitoring and Diagnosis in Multi-Agent Environments

  • Gal A. Kaminka
  • University of Southern California

We investigate a novel complementary paradigm for multi-agent monitoring and diagnosis. Socially-Attentive Monitoring (SAM) focuses on monitoring the social relationships between the agents as they are executing their tasks, and uses models of multiple agents and their relationships in monitoring and diagnosis.

PDF Details

IJCAI Conference 1999 Conference Paper

Two Fielded Teams and Two Experts: A RoboCup Challenge Response from the Trenches

  • Milind Tambe
  • Gal A. Kaminka
  • Stacy Marsella
  • Ion Muslea
  • Taylor Raines

The RoboCup (robot world-cup soccer) effort, initiated to stimulate research in multi-agents and robotics, has blossomed into a significant effort of international proportions. RoboCup is simultaneously a fundamental research effort and a set of competitions for testing research ideas. At IJ- CAI'97, a broad research challenge was issued for the RoboCup synthetic agents, covering areas of multi-agent learning, teamwork and agent modeling. This paper outlines our attack on the entire breadth of the RoboCup research challenge, on all of its categories, in the form of two fielded, contrasting RoboCup teams, and two off-line soccer analysis agents. We compare the teams and the agents to generalize the lessons learned in learning, teamwork and agent modeling.

PDF