Transcript 11feb07-icps

Toward Distributed Declarative Control
of Networked Cyber-Physical Systems (NCPS)
Mark-Oliver Stehr, Minyoung Kim, and Carolyn Talcott
Website: http://ncps.csl.sri.com
Accepting International Fellows for 2011 !
1
Key Points
– Partially ordered knowledge-sharing model for
loosely coupled distributed computing
– Distributed logic for declarative control
– Simulation case study: Collaborating team of mobile robots
– Implementation of application framework for NCP
Partially Ordered Knowledge Sharing
New Loosely Coupled Distributed Computing Model
– Inspired by our earlier work on
delay-/disruption-tolerant networking (DTN)
– Minimal assumptions on network
connectivity (can be very unreliable)
– Works with dynamic topologies,
network partitions, and mobile nodes
– Designed for heterogeneous nodes and
heterogeneous networking technologies
– Partial order allows the network to
replace obsolete or subsumed knowledge
– Global consistency is not enforced
(impossible in disruptive environments)
– Avoids strong non-implementable
primitives, e.g. transactions
– Locally each cyber-node uses an
event-based model with local time
– Each cyber-node can have
attached cyber-physical devices
Distributed Declarative Control
Key Problem
- Traditional logics are not designed for distributed reasoning
- Logics are traditionally closed systems, i.e. not interactive
Requirements/Assumptions
- Need to consider the NCPS as a single asset
- Logical theory/specification is available to all nodes
- Nodes contribute resources according to their capabilities
Knowledge is transparently shared
- Knowledge = Facts + Goals
- Facts can represent observations
- Goals can represent control objectives
Distributed logical framework
- Integrates forward and
backward reasoning
- Partial order is essential part
of the distributed logic
Predicates for Distributed Surveillance
Different Flavors of Predicates
– Cyber-facts and cyber-goals serve as interface to environment (user, devices)
– Ordinary facts/goals are used internally by the theory
Sample Theory for Distributed Surveillance
Sample Theory for Distributed Surveillance
Interpretation
– O1: New observations replace old observations
– O2: New control goals replace old goals
– O3 & O4: Solved goals (i.e. facts) replace unsolved subgoals
Sample Execution
Visualization of a Distributed Execution
– Reasoning can occur anywhere in the network
Cyber-Application Framework
Architecture
– Cyber-framework implements partially ordered knowledge-sharing model
– Logical framework is implemented as a cyber-application
– Can coexist and interoperate with conventional code
Cyber-Application Framework
Implementation
– Applications cannot distinguish between simulation and reality
• model-based simulation/analysis mode
• real-world deployment/execution mode
System Implementation
– Simulation vs. Real-world for Physical/Network Layer
– Neighbor Discovery
– Knowledge Dissemination Protocols
– Multi-threaded Execution and Simulation
1. Network/Physical Layer
Core Idea
– Applications cannot distinguish between simulation and reality
• model-based simulation/analysis mode
• real-world deployment/execution mode
Simulation World
– SimNode, SimDevice
– Comm. among cyber-nodes via
• DTN simulator with abstract mobility
• Stage multi-robot simulator with wireless network model
Real World
– RealNode, RealDevice
– Comm. among cyber-hosts via UDP
– Time synchronization
Cyber-framework supports a mechanism that allows
same application code to be used for simulation and deployment.
2. Neighbor Discovery
Core Idea
– To disseminate knowledge via opportunistic links, each cyber-engine needs to
keep track of its immediate neighborhood
– Neighbor list is refreshed between cyber-engines in periodic manner
Implementation
– Hello knowledge is posted periodically between cyber-engines (broadcast)
– Hello knowledge includes:
• Public/private IP address, hop count, engine ID, expiration time
– It is possible to be explicitly define other engine’s address (unicast)
– Multi-hop discovery is supported by forwarding hello knowledge until userdefined maximum hop count reached
– Multi-hop discovery allows some nodes to operate as discovery facilitators
(registry-like service)
Cyber-framework manages up-to-date neighborhood information
to disseminate knowledge via opportunistic links.
3. Knowledge Dissemination Protocol
Optimized Deterministic Flooding
– Disseminates knowledge to all neighbors
that are not (known to be) aware of the
particular unit of knowledge (but only once)
Probabilistic Reflection
– Single message protocol
• Window of opportunity can be small
– Minimal assumptions on network
• Links can be unidirectional or bidirectional
• Error rate can be high
• Only needs eventual weak connectivity
C
B
A
k
k
k
k
k
k
– Periodically, for each knowledge item k and for each outgoing link:
• If potential receiver is not known to be aware of k it will be sent out
• Otherwise k it is sent out with a non-zero probability
defined by a reflection parameter divided by number of outgoing links
The knowledge dissemination layer will replace and discard all
instances of inferior knowledge based on partial order semantics.
4. Multi-threaded Execution
Core Idea
– Local computation is triggered by processing an event from event queue
• Event queue exists per cyber-engine (process)
– The performance can be improved by
Implementations
– Fine-grained parallel execution
• Each cyber-node with its own event queue
• A single shared event with a thread pool
– Coarse-grained parallel execution
• Multiple cooperating cyber-engines
• Can be used at different levels
– On a single host (local communication)
– Hosts on the same subnet (broadcast)
– Beyond subnets (unicast)
Cyber-framework supports various configurations for
parallel execution as well as their arbitrary combinations.
Conclusions
Contributions
–
–
–
–
–
Truly distributed logical framework
Cyber-predicates enable interaction with the physical world
Facts and goals treated on an equal footing
Covers entire spectrum between autonomy and cooperation
Tested with abstract mobility model and Stage multi-robot simulator
Related Work
– Declarative Networking (P2, DTN, XG)
– Modular Robotics (Regiment, Meld)
– Fractionated Software/Systems
Future Work
– Reasoning performance improvements
– Integration with distributed dynamic optimization
– Exploring other applications, e.g. cooperative flight control in
UAV testbed consisting of 10 UAVs and additional ground nodes