Conflict resolution strategies and their performance models for large-scale multiagent systems.

摘要

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.