SynTM: Synthesis of Teamwork Multi-Agent Systems

Announcement

I am very pleased to announce that I was awarded a VR Starting Grant from the Swedish Resarch Counicl. VR Starting Grants are very competitive with 14% success rate for Year 2020. The aim of the grant is to give junior researchers the opportunity to establish themselves as independent researchrs in Sweden. The Swedish Resarch Council rewards basic research of the highest scientific quality in national competition. The grant is awareded for the project "SynTM: Synthesis of Teamwork Multi-Agent Systems". The purpose of SYNTM is to develop a foundational framework that will enable the automatic production of correct Teamwork MAS from high-level descriptions of desired behaviour. The findings of SYNTM will comprise a significant development of current theories, that are still unable to handle this class of systems. (see project summary).

The project is 4 years long and will be led by Dr. Yehia Abd Alrahman at the University of Gothenburg in Gothenburg, Sweden.


Grant agreement ID: 2020-03401

Overall budget: SEK 4,000,000

Duration: 2021-2024

The Scope of SynTM

Teamwork Multi-Agent Systems (MAS) are emerging as a result of the increasing adoption of robots in industry and the substantial progress in artificial intelligence and robotic hardware. Indeed, recent advances in image recognition and motion control create a pressing demand to define high-level operations (e.g., identify, recruit, turn, etc.) that can be coordinated to fulfill teamwork plans. Currently we can develop single robot systems for particular tasks. We can also develop co-existing robots when they are centrally controlled or they are not required to collaborate, e.g., Amazon Kiva multi-robot system for material handling in a warehouse. However, we do not have techniques to develop robots with joint goals, i.e., teamwork MAS. Such robots are required to collectively interact so that they achieve their goals jointly. Finding ways to design these systems while ensuring their safety and reliability remains a vigorously pursued research goal. Such systems will revolutionize our lives if successfully employed in the development of safety critical systems, e.g., supply chains, smart factories, and autonomous driving.

These systems are a natural evolution of input-enabled (or reactive) systems, where an agent has to additionally collaborate with team members to jointly maintain correct reactions to inputs from the environment. Thus, being reactive requires having strategic plans to always respond to inputs coming from the environment and to the ones triggered by interactions within the team. The major difficulty in designing these systems is that the environment is distributed and partially observed by individuals. Thus, maintaining correct reactions to environmental changes requires coordinating affected agents. Coordination is inevitable as defining reactions to distributed changes is not even expressible in terms of the knowledge of individuals. Agents are usually mobile and have limited resources, the environment is unpredictable and evolves nondeterministically, and thus fixing a communication structure among agents is not feasible.

When considering correct-by-design, reactive synthesis emerges as a viable formal method candidate for developing teamwork MAS. Reactive synthesis enables auto-production of reactive programs from formal descriptions of desired behavior. Correct-by-design means that a decision procedure will algorithmically decide whether the specifications are realizable (i.e., there exists a program implementing them) and synthesize such program when the answer is positive. Thus, the synthesized program, by construction, is guaranteed to satisfy its design goals during execution. Furthermore, unrealizable specifications must necessarily contain contradictions, and are used as early feedback to the designer. However, existing synthesis algorithms cannot deal with distributed systems in general, and their use is limited to single agent systems or co-existing ones that are functionally independent.

The purpose of the SynTM research program is to develop a foundational framework that will enable the automatic production of collaborative Multi-robot systems (or generally Teamwork MAS) from high-level descriptions of desired behavior. The findings of SynTM will comprise a significant development of current theories, that are still unable to handle this class of systems. The theoretical foundations that SynTM promises to develop rely on a major shift of focus in reactive synthesis. They will enable us to mitigate a key difficulty in deciding algorithmically how agents should interact so that each obtains the required information to carry out its functionality. This is done by providing automatic synthesis of additional and minimal strategic interactions among agents that ensure the distributed realizability of the specifications.

News

    The SynTM's Principal investigator

    Dr. Abd Alrahman is the Principal Investigator of the SynTM project at the University of Gothenburg. He investigates a practical reformulation of the distributed synthesis problem , named Teamwork Synthesis. It differs from the current one (Initially introduced by Pnueli and Rosner in 1991) in that it is solvable, i.e., it bypasses the undecidability result of the original one by eliminating the need to fix the interaction architecture among agents. An algorithm will suggest the required interactions to enable distributed realizability. This is in line with the mobility of teamwork MAS where fixing interactions among agents is not feasible. Thus, He aims to generally unlock the automatic production of correct-by-design collaborative multi-robot systems for the first time. More Specifically, his research will focus on the following objectives:
    • Consider a refined representation of the Environment to refer both to the execution context and to the interactions within the team. Thus, the environment is not merely an external entity, but rather is intertwined with the anatomy of the team;
    • to develop a novel specification temporal logic that generalizes the notion of Reactivity to require reacting to both inputs induced by the context and the interaction ;
    • Study compositional analysis of multiplayer games by a reduction to two-player parital infomation ones.

    Current collaborators

    Former collaborators

    The PI is actively collaborating with a number of researchers around the world on topics related to the SynTM project.

    SynTM's Publications