Distributed, collaborative agents are promising to play an important role in large-scale
multiagent applications, such as distributed sensors and distributed spacecraft. Since
no single agent can have complete global knowledge in such large scale applications,
conflicts are inevitable even among collaborative agents over shared resources, plans, or
tasks. Fast conflict resolution techniques are required in many multiagent systems under
soft or hard time constraints. In resolving conflicts, we focus on the approaches based
on DCSP (distributed constraint satisfaction problems), a major paradigm in multiagent
conflict resolution. We aim to speed up conflict resolution convergence via developing
efficient DCSP strategies.
We focus on multiagent systems characterized by agents that are collaborative,
homogeneous, arranged in regular networks, and relying on local communication (found
in many multiagent applications). This thesis provides the followings major contributions. First, we develop novel DCSP strategies that significantly speed up conflict resolution convergence. The novel strategies are based on the extra communication of
local information between neighboring agents. We formalize a set of DCSP strategies
which exploit the extra communication: in selecting a new choice of actions, plans,
or resources to resolve conflicts, each agent takes into account how much flexibility is
given to neighboring agents. Second, we provide a new run-time model for performance
measurement of DCSP strategies since a popular existing DCSP performance metric does not consider the extra communication overhead. The run-time model enables us to
evaluate the strategy performance in various computing and networking environments.
Third, the analysis of message processing and communication overhead of the novel
strategies shows that such overhead caused by the novel strategy is not overwhelming.
Thus, despite extra communication, the novel strategies indeed show big speedups in
a significant range of problems (particularly for harder problems). Fourth, we provide
categorization of problem settings with big speedups by the novel strategies Finally,
to select the right strategy in a given domain, we develop performance modeling techniques based on distributed POMDP (Partially Observable Markov Decision Process)
based model where scalability issue is addressed with a new decomposition technique.