Reactive Synthesis for Robotic Swarms

TitleReactive Synthesis for Robotic Swarms
Publication TypeConference Proceedings
Year of Publication2018
AuthorsMoarref, S, Kress-Gazit, H
Conference NameFormal Modeling and Analysis of Timed Systems
Pagination71--87
Date Published08/2018
PublisherSpringer International Publishing
Conference LocationBeijing, China
ISBN978-3-030-00151-3
Abstract

We consider the problem of reactive synthesis for systems with non-instantaneous actions, i.e., it may take an arbitrary amount of time for the actions of the system to complete, and meanwhile the input from the environment may also change, possibly requiring a different response from the system. The problem can be modeled as a typical reactive synthesis problem by introducing auxiliary propositions and fairness assumptions, at the expense of additional computational complexity. We develop new realizability and synthesis algorithms that address the problem without adding auxiliary propositions or assumptions. We discuss the complexity of both approaches. We then apply our algorithms to synthesize controllers for a swarm robotic system. We implement both approaches and compare them using a specific swarm task.

Citation Key2018