Formal methods for the design and analysis of robot swarms

Abstract

In my doctoral dissertation, I tackled two of the main open problems in swarm robotics: design and verification. I did so by using model checking. Designing and developing individual-level behaviors to obtain a desired swarm-level goal is, in general, very difficult, as it is difficult to predict and thus design the non-linear interactions of tens or hundreds individual robots that result in the desired collective behavior. In my dissertation, I presented my novel contribution to the top-down design of robot swarms: property-driven design. Property-driven design is based on prescriptive modeling and model checking. Using property-driven design it is possible to design robot swarms in a systematic way, realizing systems that are "correct by design". I demonstrated property-driven design on two case-studies: aggregation and foraging. Developing techniques to analyze and verify a robot swarm is also a necessary step in order to employ swarm robotics in real-world applications. In my dissertation, I explored the use of model checking to analyze and verify the properties of robot swarms. Model checking allows us to formally describe a set of desired properties of a system, in a more powerful and precise way compared to other mathematical approaches, and verify whether a given model of a system satisfies them. I explored two different approaches: the first based on Bio-PEPA and the second based on KLAIM.