Good algorithmic foundations for flight planning on the scale required for managing dense urban drone traffic we can expect to see in the future are currently still missing. This project provides prototype algorithms for managing this dense drone traffic. The project develops a concept for a coordination system that is able to find collision-free paths for a large number of flying unmanned air vehicles of different size and capability. It uses a hierarchical approach, combining centralized and local coordination, to manage complexity for a large-scale problem. The approach developed here can scale up to handle thousands of drones and lead to conflict free flight. It demonstrates the concept using mixed-reality simulations and using existing helicopter-like robots on a smaller scale. Current multi-robot trajectory-planning algorithms typically operate on a single level (which limits their scalability) and assume holonomic robots that can hover motionlessly (which limits their applicability). The core of the project is the development of a novel hierarchical system that addresses these limitations, combining centralized methods with a divide-and-conquer approach. The hierarchical approach allows the system to negotiate collision-free trajectories on a local level, while ensuring that robots complete their tasks on the global level. Additional research integrates several speed-up techniques into the hierarchical system and generalizes its functionality, for example, to accommodate robots of different priorities (such as drones that deliver blood to hospitals). The research involves not only graduate but also undergraduate students and trains them in cross-disciplinary research.
Complex engineered systems that can adapt to their environments while maintaining safety guarantees are crucial in many applications including Internet-of-Things, transportation, and electric power systems. The primary objective of this project is to develop a scalable design methodology to control very large collections of systems to achieve common objectives despite cyber and physical constraints. As an application, the electric load control problem, in which the goal is to coordinate the power consumption of thousands of small electric loads like air conditioners and refrigerators to help the grid balance supply and demand without inconveniencing electricity consumers and while respecting the physical limitations of the power distribution network, will be considered. The research results will support the integration of more wind and solar power, improving the grid's environmental and health impacts. Education and outreach activities will involve K-12, undergraduate, and graduate students along with stakeholders from local power companies. The key characteristics of the problems considered are a large number of dynamically almost decoupled systems. Each system has their local requirements and constraints and they are coupled through requirements about their collective behavior. A bi-level control architecture will be developed that can handle soft performance requirements and allow adaptability at the upper-level, and that guarantees the satisfaction of hard safety requirements at the lower-level. The lower-level will exploit structural properties symmetries of the systems and requirements, in particular, permutation invariance, to enable highly scalable synthesis methods to ensure safety. The upper-level will leverage adaptation/learning to improve system performance when control inputs are overridden for the purpose of safety.
This project tackles the following question: "Can a network of mutually-distrusting devices perform resilient inference and computation while detecting anomalous behaviors despite heterogeneity in the types of data they sense, the networking technologies they use and their computational capabilities?" The context is the increasingly pervasive Internet of Things (IoT) with low-power end users or sensors relying on edge devices to process their data, and possibly the cloud. However, IoT brings forth a unique challenge, namely, the extreme heterogeneity at multiple levels: data sensed, communication technologies used (WiFi, Bluetooth, Zigbee), and computational capabilities, making it particularly vulnerable to security threats. The goal of this project is to develop a resilient IoT system and applications, with a focus on distributed inference and computing in the presence of threats, from injection of anomalous data to impersonation of the sensors themselves. The system will be demonstrated at scale through a heterogeneous and sensor-rich campus-scale IoT deployment. The proposed testbed offers a rich platform to engage Masters and undergraduate students as well as high-schoolers through outreach programs at the Carnegie Mellon University, e.g., Engineering@CMU, SPARK Saturday, and Project Ignite. Specifically, the project aims to develop novel methodological foundations and a cross-layer system design for secure distributed computing and inference and anomaly detection in the IoT. The proposed approach exploits heterogeneous sensing data at the end-user agents and their interaction with edge devices, to provide resilience to broad classes of Byzantine adversarial scenarios and Sybil attacks. The proposed distributed algorithms yield guarantees on attaining desired computation and inference objectives under broad conditions on the data and sensing models and inter-agent connectivity. To defend against Sybil attacks that violate standard assumptions for Byzantine fault tolerance, the project aims to develop a technology-agnostic wireless fingerprinting based solution to detect anomalous devices and transmissions. The proposed solution involves a novel design of a deep neural network to extract wireless fingerprints cutting across radio technologies.
Nowadays, anyone can buy and put together sensors, actuators, and computation components, but typically only highly trained engineers are able to compose systems that can autonomously perform complex tasks. This project makes the design of cyber-physical systems (CPS) accessible to anyone by creating computational tools that enable people to choose a set of building blocks and define what a system should do. The tools then automatically create a simple and easy to understand description of how to assemble the components and provide the control needed to accomplish the task. If the task cannot be done with a single system, the tools provide either multiple systems that need to be assembled and/or explanations as to why the task cannot be done, for example due to physical constraints. The project includes designing a competition to accelerate the development of design tools, and mentoring of students from underrepresented groups. Inspired by advances in program synthesis, control synthesis and modular CPS, this project (i) defines formal specifications and synthesis processes for CPS whose task requires motion in the physical environment, and (ii) creates automated design tools that synthesize both the structure and control of the CPS and that guarantee either full or partial task satisfaction. The formalisms and tools are based on the Syntax-Guided Synthesis (SyGuS) paradigm where the design space is reduced by considering additional structure and leverages computational methods from satisfiability-modulo-theories (SMT) solvers to program synthesis tools, inverse kinematics solvers, motion planners and design optimization. The tools are evaluated on two physical and two simulated platforms.