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.
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
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.
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:
- 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.
Additional information can be found on my agent modeling web page.
- Highly efficient algorithms for plan recognition in multi-agent teams
and when observing a single agent
- Methods for learning the behavior of agents from observations, with no supervision
- Overhearing, a technique for monitoring organizations based on their overheard (observed)
- Techniques for using plan-recognition to detect and diagnose coordination failures
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
- 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].