| Jiaying Shen |
 |
|
Research Statement Jiaying Shen Throughout my graduate research,
I have been excited about deeply understanding interactions between agents
through both formal analysis and experimental evaluation in real world
applications. This understanding applies regardless whether they are software
agents in a multi-agent system (MAS), hardware robots working together in an inhospitable environment, or human
agents interacting in a real society. Until very recently, research on
multi-agent systems has been largely experimental and heuristic. What are
missing are formal models that can explain the behaviors of the agents in the
experiments. These models can also give theoretical guidance for developing new
heuristics in large scale multi-agent systems. The experimental work can
validate the formal models and both are necessary to understand multi-agent
interactions. My research is largely
motivated by my earlier work on distributed sensor networks. I worked in a team
on the DARPA project “Autonomous Negotiating Teams”, where we built
software agents for a distributed sensor network tracking system that identify
objects and negotiate to decide which sensors to track the objects. Our
prototype was tested on hardware demonstration and won the FIPA Software Prototypes
Track Demonstration Award, Honorable mention at the Fifth International Joint
Conference on Autonomous Agents. Through this system building experience I came
to realize that in order to design a suitable complex negotiation protocol for
a real system to work effectively, we need to have a good understanding of how
agents interact with each other. MAS research deals with multiple agents that
interact with each other as well as with the environment. The agents often need
to communicate in order to get more information and to coordinate their
behaviors. Even when there is no communication, an agent’s actions may
affect the other agents’ observations and consequently change their
decisions. It is the existence of these agent interactions that makes multi-agent
systems interesting and at the same time much more complex than single agent
systems. Therefore developing formal models for agent interactions is crucial
to understanding the complexity of multi-agent systems. It is important for the
study of other aspects of multi-agent systems as well. For example, one goal of
organizational design in multi-agent systems is to find the best organizational
structure such that the agents interact efficiently and achieve their goals.
Understanding from a formal perspective how agents interact with each other and
how it affects the system performance is essential in finding an efficient
organizational design for the system. On the other hand, formal study alone is
not enough. Empirical studies are needed to validate the formal models, and
techniques need to be developed to employ the formal models in real world
applications. Current Projects Communication Management
in Distributed Sensor Interpretation -- My
dissertation formalizes the communication management problem in distributed
sensor interpretation (DSI) problems.
DSI has been the subject of considerable research within the MAS
community because advances in sensor technology are leading to the deployment
of large networks of sophisticated sensors. In a DSI system,
data is collected from different sensors and needs to be integrated to produce
the best interpretation. Distributed approaches to DSI emphasize not only
distributed collecting of data, but also distributed processing of data.
However, in virtually all real-world DSI systems the agents have to communicate
as part of their problem solving, exchanging data, local results, and/or other
information among themselves. Unless communication among the agents is
appropriately limited, the cost of communication may negate much of the benefit
of distributed processing. Unfortunately, the state-of-the-art in MAS is such
that there are not yet formal design methods that allow one to evaluate a
potential DSI domain and determine the optimal coordination strategy. I believe
that this is a serious issue that will hinder the deployment of many important
applications of sensor networks. My work is one of the first attempts to address this issue. I formalized
the communication problem in DSI with a Distributed Bayesian Network and solved
the question of what to communicate with a decentralized Markov Decision
Process (DEC-MDP). With this model, one is able to generate a communication
strategy for a given DSI problem such that only minimum communication cost is
needed to achieve a required confidence level in the interpretation task. This
is different from the previous work in this area. Previous work either focuses
on finding the globally optimal solution without taking into consideration the
potentially significant communication cost, or studies the tradeoff between
solution quality and communication cost only from a statistical view. Though general communication can be naturally modeled with a DEC-MDP,
techniques need to be developed to address the complexity issue before the system
can be scaled up. I approach this problem from two perspectives. First, I
proposed an algorithm to automatically generate a set of abstract communication
actions such that when such abstract information is transferred between the
agents, the goal of the system is more likely reached. By allowing only
abstract communication actions in certain states, the expected communication
cost required is shown to be improved, and the time needed to solve the DEC-MDP
is reduced on average. Second, I established that the interactions present
among the agents is the cause of the high complexity of DEC-MDPs. This
understanding is crucial to identifying new and more tractable models as well
as developing appropriate approximations to otherwise intractable problems. I proved
that deciding a distributed MDP whose interaction history contains information
of a size polynomial in the number of states is NP-complete, and that deciding
a non-polynomially encodable distributed MDP is harder than NP. This is the
first time that a well defined condition has been identified that can
distinguish between multi-agent problems in NP and those that are strictly
harder than NP. It is an important step in mapping out the complexity hierarchy
of multi-agent systems. The significance of this theoretical result also has a
more practical side. Most multi-agent systems are provably harder than NP and
solving them optimally is not possible. This work provides theoretical guidance
in understanding how the approximations in a model limit the search space and
reduce the complexity. OAR: A Formal Framework
for Multi-Agent Negotiation -- The other project that I have been actively working on
is building a general framework for multi-agent negotiation. In Multi-Agent systems, agents often need to make decisions about how to
interact with each other when negotiating over task allocations. Traditionally,
research on negotiation is categorized into two general classes: cooperative
negotiation and competitive negotiation. Recent experimental work found that it
is not always beneficial for an agent to cooperate with other agents about
non-local tasks even if its goal is to achieve higher social utility.
Similarly, if an agent is interested only in its own local reward, sometimes it
still should choose to commit to non-local tasks for other agents instead of
its local task. At the same time, researchers look for effective mechanisms to
improve social utility even in competitive negotiation. In a complex distributed
system, the environment often evolves over time. It is virtually impossible for
the agents to always obtain and process all the necessary non-local information
in order to achieve optimal performance, whether their goals are to maximize
the social utility or local reward only. Formally understanding complex
behaviors in multi-agent negotiation is very important for designing
appropriate local mechanisms to achieve optimal performance. In this work, I developed OAR, a formal framework to study different issues
in multi-agent negotiation. There are three components in OAR. Objective
functions specify different goals of the agents involved. Attitude
parameters reflect the negotiation attitude of each agent towards another
agent. Reward splitting specifies how a contractor agent divides the
reward received for finishing the task among itself and the agents who finish
the subtasks. The traditional categorization of self-interested and cooperative
agents is unified by adopting a utility view. Both attitude parameters and
reward splitting can be used as effective local mechanisms for the agents to
realize their goals. I showed that OAR can be used to evaluate different
negotiation strategies. I also presented a closed form statistical analysis of
a small multi agent negotiation to mathematically analyze the interaction
between attitude parameters and reward splitting and their relationship with
different objective functions. To my knowledge, no work has been done that
formally analyzes the interaction among different negotiation parameters. Most
previous work on multi agent negotiation does not make the distinction between
the goal of an agent and the mechanism that an agent may employ to realize its
goal. In OAR, I make this distinction clear by controlling these two related
but distinct concepts with two different parameters: the objective parameter
and the attitude parameter. I demonstrated that this clear distinction is
important and necessary. Additionally, OAR enables us to study agents with
different organizational goals in a unified setting by simply varying their
objective parameters. The uniqueness of OAR lies in the fact that it represents
an agent’s goal and its local negotiation mechanisms formally, which
allows us to model different multi-agent systems with different negotiation
protocols in this framework and understand their performance in various
environments. Future Directions and Interests Building Practical Systems -- One major concern about formal work in MAS is whether it has practical
applications. I believe the answer is yes. My work has shown that formal
analyses can help understand the behaviors of interacting agents in an
uncertain environment and provide theoretical guidance to the design of systems
as well as the development of good approximate algorithms to problems with
inherit high complexity. On the other hand, I am exploring the possibilities of
extending the DSI work to larger sensor networks. The idea is to decompose the
larger network into smaller subnets with only a small number of connections
between them. Abstraction data is used to transfer information efficiently
between the subnets. This is an important step to apply the techniques
developed in my thesis work to a real DSI application. I am also looking into
applying the algorithms to a multi-tier camera sensor network in order to
manage the communication among the agents controlling the camera on the higher
tiers and to decide which cameras to wake up in order to save energy and
minimize delays. Organizational Design -- The organization of a multi-agent system is critical to how agents
interact with each other and therefore has a large impact on the complexity of
the problem. One important question to answer before my DSI solution can be
scaled up to larger networks is how to decompose the network into a number of
loosely coupled subnets. Conversely, in order to decide whether a decomposition
of a network is appropriate, the amount of communication required between the
subnets is a necessary measure. Consequently, organizational design is an
essential component of my future work on the communication management for
larger DSI problems. The organizational design of a multi-agent system also specifies the
roles of the agents in a system and their organizational goals. The objective
function in the OAR framework is a utility definition of the organizational
goal of an agent. By formally defining an agent’s organizational goal, we
are able to study the effects of different local mechanisms on its ability to
realize its goals. One of the next steps in the study of multi-agent
negotiation is to see how agents with different organizational goals should
interact with each other and how local mechanisms may help them realize their
goals. Machine Learning and Game Theory -- Environmental uncertainty is a common feature of the multi-agent systems.
This means that perfect knowledge of the environment where the agents are
situated cannot be assumed, and machine learning techniques can be employed to
learn the model of the agent itself, the other agents it is interacting with
and the environment. Multi-agent Learning is a challenging but exciting area as
the interactions become especially complex when multiple agents are learning
about the environment and each other. In the DSI project, online learning is especially useful when the agents
do not have a complete specification of the problem. It also can be mixed with other
approaches to improve the performance online after an initial joint policy was
developed offline. In the OAR
framework we have already employed a simple learning mechanism where the individual agents can learn the models of the other agents from the past
interactions and adjust their local negotiation parameter accordingly. One
implication of this learning approach and dynamic adjustment of local
parameters is that we need to carefully monitor the agents’ behaviors in
order to avoid system oscillations. I have proved that for the small
cooperative negotiation model, the dynamic adjustment of local attitude
parameters is stable and is guaranteed to converge to a Nash Equilibrium.
However, when the organization gets larger and when the agents have different
organizational goals than to maximize the social welfare, the problem becomes
more interesting. From each individual agent’s perspective, it changes
its local parameters in order to maximize its own objective function. However,
from the system designer’s perspective, the convergence of the multi
agent learning process is desirable. One deeper question is, even when the
process converges what kind of equilibrium it converges to and whether it is
reasonable. I am looking into game theory literature and trying to answer these
questions more satisfactorily. As most other applied sciences,
computer science research involves a lot of team work. I have collaborated with
many excellent researchers. For ANTS project, I worked on a team of postdoc and
graduate students, where close interactions were crucial to the success of the
project. Prof. Norman Carver from To summarize, my research goal
is to understand the interactions between agents from both formal and practical
perspectives. I believe that my experience in both theoretical research and
system building will greatly help me to achieve this goal. |
| jyshen@cs.umass.edu |