摘要翻译:
协作系统的分散控制捕捉了一组共享单一全球目标的决策者的操作。当智能体在运行时缺乏对系统全局状态的完全可观测性时,最优求解这类问题就变得困难。一般问题被证明是NEXP完全的。本文给出了一类复杂度介于NEXP和P之间的分散控制问题,特别是研究了具有独立转移、独立观测和目标函数的分散控制问题。给出了在多项式时间内求解目标分散过程最优有用类的两种算法。本文还研究了决策者之间的信息共享,以提高决策者的绩效。我们区分了Agent交换信息的三种方式:间接通信、直接通信和共享不受Agent控制的状态特征。我们的分析表明,对于我们考虑的每一类问题,引入直接或间接通信并不能改变最坏情况的复杂性。这些结果提供了更好的理解分散控制问题的复杂性,并促进了这些问题的规划算法的发展。
---
英文标题:
《Decentralized Control of Cooperative Systems: Categorization and
Complexity Analysis》
---
作者:
C. V. Goldman, S. Zilberstein
---
最新提交年份:
2011
---
分类信息:
一级分类:Computer Science 计算机科学
二级分类:Artificial Intelligence 人工智能
分类描述:Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域,除了视觉、机器人、机器学习、多智能体系统以及计算和语言(自然语言处理),这些领域有独立的学科领域。特别地,包括专家系统,定理证明(尽管这可能与计算机科学中的逻辑重叠),知识表示,规划,和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要:
Decentralized control of cooperative systems captures the operation of a group of decision makers that share a single global objective. The difficulty in solving optimally such problems arises when the agents lack full observability of the global state of the system when they operate. The general problem has been shown to be NEXP-complete. In this paper, we identify classes of decentralized control problems whose complexity ranges between NEXP and P. In particular, we study problems characterized by independent transitions, independent observations, and goal-oriented objective functions. Two algorithms are shown to solve optimally useful classes of goal-oriented decentralized processes in polynomial time. This paper also studies information sharing among the decision-makers, which can improve their performance. We distinguish between three ways in which agents can exchange information: indirect communication, direct communication and sharing state features that are not controlled by the agents. Our analysis shows that for every class of problems we consider, introducing direct or indirect communication does not change the worst-case complexity. The results provide a better understanding of the complexity of decentralized control problems that arise in practice and facilitate the development of planning algorithms for these problems.
---
PDF链接:
https://arxiv.org/pdf/1107.0047