Min-Time Coverage in Constricted Environments: Problem Formulations and Complexity Analysis

This work deals with the task allocation and robot routing problems that arise in a class of networked mobile robot systems. The defining characteristics of these systems are: 1) the constricting nature of their operational environment and 2) the need to coordinate the robot motion in order to maintain full connectivity of a multihop wireless communication network connecting the robots with each other and a master controller that supervises the entire operation. These two elements give rise to resource allocation structures and traffic dynamics that transcend the state of the art of the corresponding theory and challenge our current understandings and insights for these dynamics and their effective management. We provide: 1) a systematic introduction of the considered problems and of the elements that differentiate them from similar task allocation and traffic scheduling problems already studied in the literature; 2) complete analytical characterizations of these problems in the form of mathematical programming formulations; and 3) a formal analysis of the worst-case computational complexity of these problems and of certain factors that determine this complexity. Furthermore, the presented results define a base for the development of solution approaches to the considered problems able to effectively and systematically manage the identified tradeoff between the operational efficiency of the derived solutions and their computational cost.