Gal A. Kaminka: Research

Gal Kaminka: Research

(Click here if you don't see a menu to the left of this page.)

We live in exciting times. For the first time in history, humanity has reached a technological level that allows it to systematically and empirically explore one of the most fundamental questions of science: The nature of the intelligent mind. While philosophers have theorized about this question for thousands of years, this century is the first in which technological achievement is allowing us to now explore it empirically. Artificial Intelligence, the scientific discipline which investigates Intelligence, is slowly but surely emerging as an exact, rigorous scientific field, much like physics, chemistry, and biology have made this transition in history.

Research Overview

I am interested in the study of Intelligence, a naturally-occurring phenomenon that can be synthesized and replicated (with varying degrees of success) using computational means. My focus is on social intelligence. I want to understand the transition from a single mind, to many. To build robots that are socially-intelligent; that are able to reason about, manipulate, collaborate with, and coordinate with other robots and humans. To build computational models that explain social intelligence, that allow replication of it, that facilitate predictions of its occurrence, and that enable measurement and quantification.

Almost all robots are autistic; very few humans are. And the best evidence we have so far, in both robotics and psychology, suggests that this gap is a computational challenge. Even given the right mechanics and electronics, robots cannot interact effectively with others, unless their computational brains are made to think in a particular way.

Since 1995, my research in multi-agent and multi-robot systems has had two complementary themes: The control of teams of robots and agents, and its complementary monitoring by the agents themselves. The two are inseparable: One cannot build an effective controller without having a feedback mechanism that monitors the results of the controller's actions. In multi-robot systems, this translates to endowing robots with the ability to take social actions, and to understand those of its peers. For instance, a socially-intelligent robot must know when and what to communicate; and it must understand the intents of others from observations of their actions.

The instantiation of these social control and social monitoring themes takes me back and forth through theory and practice, from proofs of algorithmic complexity and logical models, to their use in robots that move in my lab--and outside of it. And from the lessons learned with real robots, back to amending the theory. My research thus explores a variety of tasks, including detecting and diagnosing coordination failures, multi-robot area coverage, search, and coordinated movement, automated coordination and task allocation, understanding group behavior and the differences in distributed and centralized settings. In all of these, the two themes--control and monitoring--are integrated to create robust and effective social behavior.

Understanding What Others are Doing

One particular aspect of intelligent behavior involves the critical ability of an agent to reason about other agents from observations of their actions (or communications). Based on such observations, a robot must be able to infer their intent and recognize their behavior. There are several inherent challenges to such recognition, in multi-robot tracking.

First, there are almost always multiple explanations (hypotheses) for the observed actions of an agent. Keeping track of these is computationally complex; it gets worse when one tracks many agents, since then one has to keep track of the combinations of hypotheses, so there's an exponential number of hypotheses.
Second, one cannot physically observe too many agents at once, nor process too many observations at once.

Since 1995, I have been investigating efficient symbolic and probabilistic algorithms for inferring intents, plans, beliefs, and behaviors, in single-robot and multi-robot settings. I've also been doing research about using the inferred information to detect, identify, and diagnose faults in the coordination of agents and robots. Here are a few highlighted contributions, with colleagues. Please check my publications page:

Highly efficient algorithms for plan recognition in multi-agent teams [JAIR 2002] and when observing a single agent [IJCAI 2005]
Methods for learning the behavior of agents from observations, with no supervision [RoboCup 2002], [IDA 2005]
Overhearing, a technique for monitoring organizations based on their overheard (observed) communications [Agents 2001], [AAMAS 2004], [JAIR 2006]
Techniques for using plan-recognition to detect and diagnose coordination failures [JAIR 2000], [IJCAI 2003], [AAMAS 2005], [JAAMAS 2006], [AAAI 2005], [AAAI 2006]

Additional information can be found on my agent modeling web page.

Planning and Acting in a Social Context

I have been conducting empirical and theoretical research in several real-world, challenging application domains, in which multiple robots or agents interact. The emphasis of the work has been on finding principles and techniques that generalize across domains. My approach to this research is to go back and forth between applications and general architectures that work across domains (please also see my publications page):

Through all of my research, I have been interested in architectures that provide automated teamwork and coordination services. Using such architectures, the developer must only program robots to know who their teammates are: The synchronization and allocation of tasks is then done automatically by the robots themselves. I took part in the evaluation of the STEAM architecture in RoboCup [JAAMAS 2003]; and in development of TEAMCORE [ICMAS 2000]. I later co-designed the MONAD architecture, which was the first to allow multiple task-allocation protocols to be used from within the architecture [AAMAS 2003]. Most recently, we have developed the BITE (Bar Ilan Teamwork Engine) architecture [AAAI 2005].
Coverage is a standard task in robotics, where one or more robots are supposed to visit every point in a given physical area. We have developed a family of robust multi-robot coverage algorithms, that are guaranteed to complete as long as at least one robot is alive. Using these algorithms, we have shown that surprisingly, to minimize the time it takes for a team of robots to cover an area, it is sometimes necessary for them to carry out redundant work (cover an area already previous covered) [ICRA 2005],[ICRA 2006a],[ICRA 2006b].
Formation maintenance (coordinated movement in formation) is another keystone task in multi-robot systems. In this task, robots maintain a geometric formation while moving, by monitoring each other (through vision and range sensors). It is interesting because it is almost purely social: It can only be carried out by multiple robots, and only when they tightly couple control of their own motion with their monitoring of others. We have developed a unique approach to robust formation control, whereby robots the robots automatically respond to sensor failures by switching whom they monitor [ICRA 2006]. We also developed efficient algorithms for allocating tasks to robots in formation [AAAI 2005].
We developed a unique interface---tested with up to 25 human test subjects---that allows a single human operator to control a team of robots moving in formation. It proved significantly better than previous approaches [ICRA 2006].