|
|
Networked
Cyber Physical Systems at SRI |
|
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