Gal Kaminka

AAMAS Conference 2019 Conference Paper

Swarms Can be Rational

• Yinon Douchan
• Ran Wolf
• Gal Kaminka

A fundamental challenge in multi-robot systems is spatial coordination (avoiding collisions) between robots, each under its own control. Swarm methods, where by robots coordinate ad-hoc and locally, offer a promising approach. However, while empirically demonstrated to be viable in practice, no guarantees of performance are known. This paper formalizes a class of multi-robot cooperative tasks as differential extensive-form games. We show that the system coordination overhead is a differential function, forming a connection between the theoretical maximum-payoff equilibrium of the system, and the rational self-interested choices of individual robots during task execution: robot swarms can be rational in theory. We then show how to approximate the rational decision-making in practice using reinforcement learning, using internal measures for rewards. We empirically show this leads to consistent optimal performance in with physical and simulated robots.

AAAI Conference 2018 Conference Paper

Plan Recognition in Continuous Domains

• Gal Kaminka
• Mor Vered
• Noa Agmon

Plan recognition is the task of inferring the plan of an agent, based on an incomplete sequence of its observed actions. Previous formulations of plan recognition commit early to discretizations of the environment and the observed agent’s actions. This leads to reduced recognition accuracy. To address this, we first provide a formalization of recognition problems which admits continuous environments, as well as discrete domains. We then show that through mirroring— generalizing plan-recognition by planning—we can apply continuous-world motion planners in plan recognition. We provide formal arguments for the usefulness of mirroring, and empirically evaluate mirroring in more than a thousand recognition problems in three continuous domains and six classical planning domains.

AAMAS Conference 2012 Conference Paper

Detection of Suspicious Behavior from a Sparse Set of Multiagent Interactions

• Boštjan Kaluža
• Gal Kaminka
• Milind Tambe

In many multiagent domains, no single observation event is sufficient to determine that the behavior of individuals is suspicious. Instead, suspiciousness must be inferred from a combination of multiple events, where events refer to the individual's interactions with other individuals. Hence, a detection system must employ a detector that combines evidence from multiple events, in contrast to most previous work, which focuses on the detection of a single, clearly suspicious event. This paper proposes a two-step detection system, where it first detects trigger events from multiagent interactions, and then combines the evidence to provide a degree of suspicion. The paper provides three key contributions: (i) proposes a novel detector that generalizes a utility-based plan recognition with arbitrary utility functions, (ii) specifies conditions that any reasonable detector should satisfy, and (iii) analyzes three detectors and compares them with the proposed approach. The results on a simulated airport domain and a dangerous-driver domain show that our new algorithm outperforms other approaches in several settings.

AAMAS Conference 2012 Conference Paper

Robot Exploration with Fast Frontier Detection: Theory and Experiments

• Matan Keidar
• Gal Kaminka

Frontier-based exploration is the most common approach to exploration, a fundamental problem in robotics. In frontier-based exploration, robots explore by repeatedly computing (and moving towards) \emph{frontiers}, the segments which separate the known regions from those unknown. However, most frontier detection algorithms process the entire map data. This can be a time consuming process which slows down the exploration. In this paper, we present two novel frontier detection algorithms: \emph{WFD}, a graph search based algorithm and \emph{FFD}, which is based on processing only the new laser readings data. In contrast to state-of-the-art methods, both algorithms do not process the entire map data. We implemented both algorithms and showed that both are faster than a state-of-the-art frontier detector implementation (by several orders of magnitude).

AAMAS Conference 2012 Conference Paper

The Impact of Cultural Differences on Crowd Dynamics

• Natalie Fridman
• Avishay Zilka
• Gal Kaminka

AAAI Conference 2010 Conference Paper

Ad Hoc Autonomous Agent Teams: Collaboration without Pre-Coordination

• Peter Stone
• Gal Kaminka
• Sarit Kraus
• Jeffrey Rosenschein

As autonomous agents proliferate in the real world, both in software and robotic settings, they will increasingly need to band together for cooperative activities with previously unfamiliar teammates. In such ad hoc team settings, team strategies cannot be developed a priori. Rather, an agent must be prepared to cooperate with many types of teammates: it must collaborate without pre-coordination. This paper challenges the AI community to develop theory and to implement prototypes of ad hoc team agents. It defines the concept of ad hoc team agents, specifies an evaluation paradigm, and provides examples of possible theoretical and empirical approaches to challenge. The goal is to encourage progress towards this ambitious, newly realistic, and increasingly important research goal.

AAMAS Conference 2008 Conference Paper

A Realistic Model of Frequency-Based Multi-Robot Fence Patrolling

• Yehuda Elmaliach
• Asaf Shiloni
• Gal Kaminka

There is growing interest in multi-robot frequency-based patrolling, in which a team of robots optimizes its frequency of point visits, for every point in a target work area. In particular, recent work on patrolling of open polygons (e. g. , open-ended fences) has proposed a general cooperative patrolling algorithm, in which robots move back and forth along the polygon, in an synchronized manner, such that their assigned areas of movement overlap. If the overlap factor is carefully chosen—based on the motion models of the robots—specific performance criteria are optimized. Unfortunately, previous work has presented analysis of motion models in which there are no errors in the movement of the robots, and no velocity changes. We go a step beyond existing work, and develop a realistic model of robot motion, that considers velocity uncertainties. We mathematically analyze the model and show how to use it to find optimal patrolling parameters, given known bounds of uncertainty on the motion. We then use the model to analyze the independently-programmed patrolling movements of physical robots, in extensive experiments. We show that the model predicts the behavior of the robots much more accurately than previouslydescribed models.

AAMAS Conference 2008 Conference Paper

The Impact of Adversarial Knowledge on Adversarial Planning in Perimeter Patrol

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

This paper considers the problem of multi-robot patrolling around a closed area, in the presence of an adversary trying to penetrate the area. Previous work on planning in similar adversarial environments addressed worst-case settings, in which the adversary has full knowledge of the defending robots. It was shown that non deterministic algorithms may be effectively used to maximize the chances of blocking such a full-knowledge opponent, and such algorithms guarantee a “lower bound” to the performance of the team. However, an open question remains as to the impact of the knowledge of the opponent on the performance of the robots. This paper explores this question in depth and provides theoretical results, supported by extensive experiments with 68 human subjects concerning the compatibility of algorithms to the extent of information possessed by the subjects. First, we analytically examine the case of a zero-knowledge opponent—a different extreme—and show that surprisingly, this seemingly best-case scenario (from the point of view of defending robots) is optimally addressed by a deterministic, non-randomizing patrol. Moreover, we show empirically that an optimal algorithm for the full-knowledge opponent fails miserably in this case. We then address the case in which the adversary gained partial information, propose the Combine algorithm that maximizes the expected probability of penetration detection along with minimizing the deviation between the probabilities of penetration detection along the perimeter, and support the performance of this algorithm in the experiments.

AAMAS Conference 2008 Conference Paper

Towards Bidirectional Distributed Matchmaking

• Victor Shafran
• Gal Kaminka
• Sarit Kraus
• Claudia Goldman

Matchmaking is the process of introducing two or more agents to each other. Current matchmaking techniques are unidirectional and fail to address large-scale and highly dynamic systems with time constraints. We propose a new distributed technique which scales well, and still maintains relatively low matchmaking time and communication overhead. Our technique introduces very low storage and computational overhead to the agents. We suggest using a matching cache which can take advantage of the multidirectional nature of the matchmaking problem. We empirically evaluate the proposed technique on bilateral matchmaking and show that it outperforms the existing techniques.

AAMAS Conference 2007 Conference Paper

An Adversarial Environment Model for Bounded Rational Agents in Zero-Sum Interactions

• Inon Zuckerman
• Sarit Kraus
• Jeffrey S. Rosenschein
• Gal Kaminka

Multiagent environments are often not cooperative nor collaborative; in many cases, agents have conflicting interests, leading to adversarial interactions. This paper presents a formal Adversarial Environment model for bounded rational agents operating in a zero-sum environment. In such environments, attempts to use classical utility-based search methods can raise a variety of difficulties (e. g. , implicitly modeling the opponent as an omniscient utility maximizer, rather than leveraging a more nuanced, explicit opponent model).

AAMAS Conference 2004 Conference Paper

Towards a Formal Approach to Overhearing: Algorithms for Conversation Identification

• Gery Gutnik
• Gal Kaminka

AAMAS Conference 2003 Conference Paper

MONAD: A Flexible Multi-Agent Control Architecture

• Thuc Vu
• Jared Go
• Gal Kaminka
• Manuela Veloso
• Brett Browning