Networked Cyber Physical Systems at SRI






Case Study1

Case Study2

Reading List



To demonstrate the applicability and performance of cyber-framework, we focus on a specific case study in the context of distributed sensing, optimization, and control. In this case study, we assume that various wireless sensors are deployed in space yet isolated in the sense that the sensors cannot communicate directly with each other due to limited energy (e.g., small battery and long lifetime), which requires mobile robots to take the role of data collectors.  This problem is representative of a class of challenging problems, since the network is highly dynamic and in the presence of uncertainties, delays, and failures it requires cooperation among mobile robots to achieve a globally approximate optimal solution. 


We use a mapping into the multiple Traveling Salesman Problem (mTSP), a well-known NP-complete problem. Multiple mobile robots attempt to find the most cost-efficient route assignment visiting all sensor locations and returning to a common starting point.  In our case study, a robot can also encounter other robots on its traversal and exchange up-to-date information about each robot and about the sensors already covered, which leads to a dynamic version of mTSP with opportunistic knowledge sharing.  The algorithm should be executed in a fashion that can adjust load distribution among robots in a fully decentralized manner to cope with failures of all kinds.   


As an approach that can be naturally distributed, we use a quantum evolutionary algorithm (QEA), which is based on the concepts borrowed from quantum computing such as the notions of quantum bit and superposition of states. We modified the distributed QEA to dynamically take into account partial information about the distributed progress by sharing knowledge on the robot's trajectory whenever connectivity is available. When connected, the robots cooperatively recompute a new solution for the reduced instance of mTSP reflecting all available knowledge, i.e., each robot executes the QEA with the union of its assigned but not yet visited cities according to its current solution and with their current positions. Robots return to the starting location after visiting their assigned cities and will repeat the algorithm if not all cities are known to be covered. In this manner, uncertainties (e.g., battery depletion may slow a robot's movement) and runtime failures (e.g., robots are physically damaged) can be reflected in a new solution both during the normal operation and after returning to the starting location. For details, please refer to [1].


1.     M. Kim, M-O. Stehr, J. Kim, S. Ha,

           An Application Framework for Loosely Coupled Networked Cyber Physical Systems

           8th IEEE/IFIP Conference on Embedded and Ubiquitous Computing (EUC'10), Dec. 2010, Hong Kong, China.


The following snapshots illustrate an execution of mTSP on top of Cyber-Framework with the Stage multi-robot simulator.

First, three robots compute initial solutions by solving current instance of mTSP using parallel QEA.

Next, each robot moves based on its current plan.

Sometimes, a robot can fail like in the following snapshot. 

After visiting their assigned cities all robots return to their base position and exchange information about the cities covered.

Now, the remaining cities will be visited by surviving robots.






Last updated: July 12, 2010