The objective of this research is to develop new models of computation for multi-robot systems. Algorithm execution proceeds in a cycle of communication, computation, and motion. Computation is inextricably linked to the physical configuration of the system. Current models cannot describe multi-robot systems at a level of abstraction that is both manageable and accurate. This project will combine ideas from distributed algorithms, computational geometry, and control theory to design new models for multi-robot systems that incorporate physical properties of the systems. The approach is to focus on the high-level problem of exploring an unknown environment while performing designated tasks, and the sub-problem of maintaining network connectivity. Key issues to be studied will include algorithmic techniques for handling ongoing discrete failures, and ways of understanding system capabilities as related to failure rates, geometric assumptions and physical parameters such as robot mobility and communication bandwidth. New metrics will be developed for error rates and robot mobility. Intellectual merit arises from the combination of techniques from distributed algorithms, computational geometry, and control theory to develop and analyze algorithms for multi-robot systems. The project will develop a new class of algorithms and techniques for their rigorous analysis, not only under ideal conditions, but under a variety of error assumptions. The project will test theoretical ideas empirically, on three different multi-robot systems. Broader impacts will include new algorithms for robot coordination, and rigorous understanding of the capabilities of different hardware platforms. Robots are an excellent outreach tool, and provide concrete examples of theory in action.

The objective of this research is to develop new models of computation for multi-robot systems. Algorithm execution proceeds in a cycle of communication, computation, and motion. Computation is inextricably linked to the physical configuration of the system. Current models cannot describe multi-robot systems at a level of abstraction that is both manageable and accurate. This project will combine ideas from distributed algorithms, computational geometry, and control theory to design new models for multi-robot systems that incorporate physical properties of the systems. The approach is to focus on the high-level problem of exploring an unknown environment while performing designated tasks, and the sub-problem of maintaining network connectivity. Key issues to be studied will include algorithmic techniques for handling ongoing discrete failures, and ways of understanding system capabilities as related to failure rates, geometric assumptions and physical parameters such as robot mobility and communication bandwidth. New metrics will be developed for error rates and robot mobility. Intellectual merit arises from the combination of techniques from distributed algorithms, computational geometry, and control theory to develop and analyze algorithms for multi-robot systems. The project will develop a new class of algorithms and techniques for their rigorous analysis, not only under ideal conditions, but under a variety of error assumptions. The project will test theoretical ideas empirically, on three different multi-robot systems. Broader impacts will include new algorithms for robot coordination, and rigorous understanding of the capabilities of different hardware platforms. Robots are an excellent outreach tool, and provide concrete examples of theory in action.

The objective of this research is considering security and timing as primary concerns, re-envisioning computer architecture and network algorithms to provide a robust foundation for CPS. The approach is rethinking the hardware and software divide, providing true process concurrency and isolation. Extending these benefits to the communication network so integral to CPS, multicast and security innovations that consider CPS constraints will be proposed. This project will provide computational and communication foundations for CPS through the following tasks. (1) An open source hardware design will be created. Abandoning the error-prone paradigm of shared memory communication, Precision Timed (PRET) processors for dataflow computations will be extended. (2) The hardware/software interface will be investigated specifically for PRET architectures. (3) A routing algorithm considering the CPS constraints will be investigated. The constraints include efficiency, adaptability, scalability, simplicity, and security. (4) Distributed Source Coding for CPS applications will be studied with focus on challenges from small packet sizes in these applications. This project will engage the community and students in multiple grades and institutions, through the following undertakings. (1) A package for education and research in CPS will be assembled. This package and the material from this project in the form of tutorials, publications, and curriculum will be available to other institutions. (2) New courses will be created integrating research results into education. (3) A diverse group of students including women and minorities will be recruited. (4) Two applications will be implemented in the fields of medical devices and emergency response.

Using the newly introduced idea of a sensor lattice, this project conducts a systematic study of the "granularity'' at which the world can be sensed and how that affects the ability to accomplish common tasks with cyber-physical systems (CPSs). A sensor is viewed as a device that partitions the physical world states into measurement-invariant equivalence classes, and the sensor lattice indicates how all sensors are related. Several distinctive characteristics of the pursued approach are: 1) Virtual sensor models are developed, which correspond to minimal information requirements of common tasks and are independent of particular physical sensor implementations. 2) Uncertainty is decoupled into disturbances and pre-images, the latter of which yields the measurement-invariant equivalence classes and sensor lattice. 3) The development of particular spatial and temporal filters that are based on minimal information requirements of a task. 4) Formally establishing the conditions that enable sensors in a CPS to be interchanged, and then determining the relative complexity tradeoffs. The intellectual merit is to understand how mappings from the physical world to sensor outputs affect the solvability and complexity of commonly occurring tasks. This is a critical step in the development of mathematical and computational CPS foundations. Broader impact is expected by improving design methodologies for CPS solutions to societal problems such as assisted living, environmental monitoring, and automated agriculture. The sensor lattice approach is transformative because it represents a new paradigm with which to address basic sensor-based inference issues, which extend well beyond the traditional academic boundaries.