Visible to the public CPS: Small: Real-time, Simulation-based Planning and Asynchronous Coordination for Cyber-Physical Systems

Project Details
Lead PI:Kostas Bekris
Performance Period:09/01/09 - 08/31/13
Institution(s):University of Nevada
Sponsor(s):National Science Foundation
Project URL:
Outcomes Report URL:
Award Number:0932423
2268 Reads. Placed 57 out of 803 NSF CPS Projects based on total reads on all related artifacts.
Abstract: The objective of this research is to investigate how to replace human decision-making with computational intelligence at a scale not possible before and in applications such as manufacturing, transportation, power-systems and bio-sensors. The approach is to build upon recent contributions in algorithmic motion planning, sensor networks and other fields so as to identify general solutions for planning and coordination in networks of cyber-physical systems. The intellectual merit of the project lies in defining a planning framework, which integrates simulation to utilize its predictive capabilities, and focuses on safety issues in real-time planning problems. The framework is extended to asynchronous coordination by utilizing distributed constraint optimization protocols and dealing with inconsistent state estimates among networked agents. Thus, the project addresses the frequent lack of well-behaved mathematical models for complex systems, the challenges of dynamic and partially-observable environments, and the difficulties in synchronizing and maintaining a unified, global world state estimate for multiple devices over a large-scale network. The broader impact involves the development and dissemination of new algorithms and open-source software. Research outcomes will be integrated to teaching efforts and undergraduate students will be involved in research. Underrepresented groups will be encouraged to participate, along with students from the Davidson Academy of Nevada, a free public high school for gifted students. At a societal level, this project will contribute towards achieving flexible manufacturing floors, automating the transportation infrastructure, autonomously delivering drugs to patients and mitigating cascading failures of the power network. Collaboration with domain experts will assist in realizing this impact.

The project aims to develop abstractions and general solutions for autonomous planning and coordination in networks of cyber--physical systems. In particular, the following challenges were identified in order to achieve the above objective:

Develop abstractions and sampling-based motion planning algorithms that can be appropriately integrated with simulation tools to utilize their predictive capabilities without requiring detailed or well-behaved mathematical models.

We have developed methods for improving the performance of sampling-based algorithms, which do not depend on the knowledge of a specific model and which can operate given a simulation tool to model the underlying system. In the meanwhile, an important development in the motion planning community has been the proposition of motion planners that provide asymptotic optimality guarantees. These methods, however, have significant computational requirements. We have proposed a series of algorithms that provide asymptotic near-optimality guarantees and which require significantly reduced computational resources.

Address safety issues that arise due to the presence of real-time constraints, such as operating in dynamic and partially-observable environments, and especially given asynchronous coordination protocols between multiple agents towards providing safety guarantees.

We have provided a report that summarizes the state-of-the-art in addressing safety issues in the context of real--time planning. This line of work has been extended to the case of multiple coordinating vehicles that utilize asynchronous communication in order to navigate in a common environment, while achieving safety guarantees. We have also developed methods for the decentralized, collision-free coordination of multiple agents, which involves either no or very limited communication.

Study how inconsistent estimation and partial knowledge among multiple agents of a team affects distributed decision-making and work towards applications in CPS domains.

We have developed methods for computing paths for multiple agents in a decentralized, localized manner on discrete representations by utilizing static sensors, which are able to communicate with the agents. The focus of this work has been on transportation scenarios, which is one of the CPS application domains for this project. A drawback of this type of methods is the lack of completeness guarantees. This motivated the development of methods with completeness guarantees for a broad range of multi-agent path planning instances on discrete representations, which have polynomial complexity. This project has also led into the specification of an open--access, decentralized architecture for the control of the power network, as well as the development of closed-loop methods for the control of medical devices.

Develop and distribute open-source planning and control software which provides appropriate abstraction tools so as to be applied to a variety of CPS applications;

An initial version of the proposed open--source planning and control software has been completed and a related paper will appear to the upcoming Simulation, Modeling and Programming Autonomous Robots conference, which illustrates the capabilities of the platform.