Instantaneous Actions vs. Full Asynchronicity: Controlling and Coordinating a Sset of Autonomous Mobile Robots

Over the past fewy ears, the focus of robotic design has been moving from a scenario where few, specialized (and expensive) units were used to solve a variety of tasks, to a scenario where many, general purpose (and cheap) units were used to achieve some common goal. Consequently, part of the focus has been to better understand howto e.ciently coordinate and control a set of such “simpler” mobile units. Studies can be found in di.erent disciplines, from engineering to arti.cial life: a shared feature of the majority of these studies has been the design of algorithms based on heuristics, without mainly being concerned with correctness and termination of such algorithms. Fewst udies have focused on trying to formally model an environment constituted by mobile units, studying which kind of capabilities they must have in order to achieve their goals; in other words, to study the problem from a computational point of view. This paper focuses on two of these studies [1,6,14] (the only ones, to our knowledge, that analyze the problem of coordinating and controlling a set of autonomous, mobile units from this point of view). First, their main features are described. Then, the main di.erences are highlighted, showing the relationship between the class of problems solvable in the two models.