Compositional and symbolic synthesis of reactive controllers for multi-agent systems
Compositional and symbolic synthesis of reactive controllers for multi-agent systems
复制标题
DOI：
10.1016/j.ic.2018.02.021
复制
发表时间：
2018-08
期刊：
影响因子：
--
通讯作者：
R. Alur;Salar Moarref;U. Topcu
中科院分区：
文献类型：
--
作者：
R. Alur;Salar Moarref;U. Topcu
我们考虑由一组受控和不受控代理组成的多代理系统的控制器综合问题。受控代理可能需要相互合作并对不受控代理的行为做出反应，以实现其目标。此外，智能体可能是不完美的，即只能部分地观察其环境。我们提出了一种基于组合反应综合的控制器综合框架。我们象征性地实现了这些算法，并将其应用于机器人运动规划案例研究，其中多个机器人被放置在一个带有静态障碍物和其他动态、不受控制和潜在对抗性机器人的网格世界中。我们考虑不同的目标，例如避免碰撞、保持队形和有限可达性。我们证明，通过利用系统的结构，组合合成算法从时间和内存角度都可以显着优于集中式替代算法，并且可以解决集中式算法不可行的问题。
We consider the controller synthesis problem for multi-agent systems that consist of a set of controlled and uncontrolled agents. Controlled agents may need to cooperate with each other and react to actions of uncontrolled agents in order to fulfill their objectives. Moreover, agents may be imperfect, i.e., only partially observe their environment. We propose a framework for controller synthesis based on compositional reactive synthesis. We implement the algorithms symbolically and apply them to a robot motion planning case study where multiple robots are placed on a grid-world with static obstacles and other dynamic, uncontrolled and potentially adversarial robots. We consider different objectives such as collision avoidance, keeping a formation and bounded reachability. We show that by taking advantage of the structure of the system, compositional synthesis algorithm can significantly outperform centralized alternative, both from time and memory perspective, and can solve problems where the centralized algorithm is infeasible.