Transcript Document

Toward a Theory of Protocols for
Communication Through Action
John Baillieul
C.I.S.E. and
Intelligent Mechatonics Laboratory
Boston University
Boston, MA 02215
[email protected]
http://people.bu.edu/johnb
http://iml.bu.edu
http://www.bu.edu/systems
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Integration with Center Themes
Cognitive psychology thrust: The dynamics of choice
among multiple alternatives:
Key problem: Understand the tradeoff between decision time
(DT) (= reaction time, RT) and error rate (ER).
Optimizing the parsimoniousness
of computational effort
Maximum reward rate (RR)(= maximum # of correct task
executions per unit time)
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Prior Work that Informs the Research
From DAAD19-01-1-0465: The Boston University Center for
Communicating Networked Control Systems
G(s)
The Data-Rate Theorem
Theorem: Suppose the system G(s) is controlled using a datarate constrained feedback channel. Suppose, moreover, G has
k right half-plane poles l1,…,lk. Then there is a critical datarate
Rc  log 2 e  (Re( l1) 
 Re( lk ))
such that the system can be stabilized if and only if the
channel capacity R>Rc.

CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Integration with Center Themes
Optimally parsimonious use of resources in control---e.g. speed
vs. accuracy tradeoffs:
G(s)
Air Packets: 17 bytes payload
Bluetooth radio
Air Packets: ≤ 366 bits total
Bluetooth radio
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Prior Work that Informs the Research
Necessary and Sufficient Conditions for Stable Rigidity
with Minimal Sensing
Theorem: (Hendrickx et al., 2006) An acyclic formation
graph correspondingto a stably rigid formation under a
corresponding distributed relative distance control law is
isostatic if and only if
(i) one vertex (the leader) has out-valence 0;
(ii) one vertex (the first-follower) has out-valence 1 and is
adjacent to the leader vertex; and
(iii) all other vertices have out-valence equal to 2
From DAAD19-01-1-0465: The Boston
University Center for Communicating
Networked Control Systems
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Prior Work that Informs the Research
The construction dynamics of
isostatic rigid formations.
JB and Lester McCoy, “The
Combinatorial Graph Theory of
Structured Formations,” CDC, 2007.
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Integration with Center Themes
The search for robustly parsimonious
connection patterns is a big deal in
networked control systems.
See The Technology of Networked
Control Systems: Special Issue of the
Proceedings of the IEEE, Vol. 95:1,
January, 2007
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Problem Statement
Develop a theory of control systems in which primary control
objectives are met while using excess control authority to
communicate among system agents.
QuickTime™ and a
DV/DVCPRO - NTSC decompressor
are needed to see this picture.
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Approach
• Identify classes of controlled dynamical systems where it
seems natural and interesting to design dynamical responses
which achieve a primary control objective while to encoding
additional information that is beyond what is needed to achieve
the primary objective
• Develop theories of action-mediated communication together
with sets of experiments to test and refine those theories.
• Develop approaches to decentralized control in which
controllers communicate with each other through the
performance of a shared task.
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Goals
Design protocols for communication through motions that will
allow teams of humans and robots to:
• Move about as a group in a variety of environments with the
ability to alter motions on the fly based on both sensor
feedback and the relative motions of members of the groups
• Collaborate in the performance of tasks without needing to
communicate over classical communications channels (RF or
optical).
• Understand the tradeoffs between reliability and security in
action-mediated communication
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
The Simplest Communication Through Action Problem
By means of the input u, steer the output y so as to:
1. Achieve an output objective while
2. Simultaneously communicating a message from u to y.
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Two Agents Communicating Through Action Problem
Both agents u and v collaboratively steer the output y so as
to:
1. Achieve a prescribed output objective while
2. Simultaneously communicating messages to each other.
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Multiplexed Communication in Input/Output Networks
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Motivation from Finite Dimensional Linear Systems
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Communication in Terminal Endpoint Linear Control Problems
The null-space of L can be used for communication.
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Terminal Endpoint Control with Communication
steers the system from 0 to x1
and communicates the message
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Control with Communication
Message
Encoder
u
G(s)
yobjective+ysignal
Decoder
Design considerations:
• Consistent with primary control objective Received
• Low energy
message
• Reliability
• Stealth/security
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Reliable Control with Communication
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Double Integrator Example
Choices of Fourier bases:
1.
2.
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Optimal Communication with the Double Integrator
Cosine series with binary coefficients
more reliably encode messages in that
the average Hamming distance is
larger.
Open problems:
1. Reliable coding as the solution of an optimization problem
2. Optimal sampling for reliable decoding
3. Coding for noisy environments (channels)
4. Communication and vehicle motion control problems
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Problems in Communication Complexity
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Wong’s Problem
Alice and Bob use a control process to collaboratively compute
the value f(a,b), with Alice choosing a and Bob choosing b.
Alice
Bob
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
Next Steps
Immediate future research goals:
1. For a variety of control system settings, study the problem of
multiple agents having control inputs u1,u2,… which they
select independently to jointly influence an output y.
2. How does the game change is we try to minimize state or
output excursions while at the same time maintaining a
reliable communication link? (Connection with risk/reward
research.)
3. Infinite horizon games can be considered, but communication costs must be cost per unit time.
4. Redo the receding horizon target seeking game of next
presentation with communication explicitly included.
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
CHARDD Kickoff Meeting, Princeton University, September 13, 2007
CHARDD Kickoff Meeting, Princeton University, September 13, 2007