论文标题
具有图形时间逻辑规格的多代理系统的分布式策略合成
Distributed Policy Synthesis of Multi-Agent Systems With Graph Temporal Logic Specifications
论文作者
论文摘要
我们研究多代理系统的策略的分布式合成，以执行\ EMPH {时空}任务。我们将合成问题形式化为\ emph {contored}马尔可夫决策过程，约为\ emph {Graph permoal逻辑}规格。每个代理的过渡函数和任务是代理本身及其相邻代理的功能。在这项工作中，我们开发了另一种分布式合成方法，该方法将可伸缩性和运行时提高了两个数量级，与我们的先前工作相比。综合方法将问题分解为一组较小的问题，每种代理一个通过利用模型中的结构和规格。我们表明该方法的运行时间是在代理数量中线性的。每个代理的问题的大小仅在相邻代理的数量中指数级，通常比代理的数量小得多。我们证明了该方法在疾病控制，城市安全以及搜救措施的案例研究中的适用性。数值示例表明，该方法缩放到数百个代理，每个代理具有数百个状态，并且还可以处理比我们先前的工作更大的状态空间。
We study the distributed synthesis of policies for multi-agent systems to perform \emph{spatial-temporal} tasks. We formalize the synthesis problem as a \emph{factored} Markov decision process subject to \emph{graph temporal logic} specifications. The transition function and task of each agent are functions of the agent itself and its neighboring agents. In this work, we develop another distributed synthesis method, which improves the scalability and runtime by two orders of magnitude compared to our prior work. The synthesis method decomposes the problem into a set of smaller problems, one for each agent by leveraging the structure in the model, and the specifications. We show that the running time of the method is linear in the number of agents. The size of the problem for each agent is exponential only in the number of neighboring agents, which is typically much smaller than the number of agents. We demonstrate the applicability of the method in case studies on disease control, urban security, and search and rescue. The numerical examples show that the method scales to hundreds of agents with hundreds of states per agent and can also handle significantly larger state spaces than our prior work.
