Transcript Robust and Optimal Control of Interconnected Systems

Multi-vehicle Cooperative Control
Raffaello D’Andrea
Mechanical & Aerospace Engineering
Cornell University
OUTLINE
Progress on RoboFlag Test-bed
 MLD approach to Multi-Vehicle Cooperation
 Obstacle Avoidance in Dynamic Environments
 Path Planning with Uncertainty

RoboFlag
An experimental platform for multivehicle cooperative control in
uncertain and adversarial
environments
SYSTEMS OF INTEREST
SENSE
GLOBAL
PROCESSING
SENSING
CENTRAL
CONTROL
HIGH LEVEL
DECISION MAKING
COMMS
COMMS
COMMS
COMMS
COMMUNICATIONS NETWORK
COMMS
COMMS
HUMAN
INTERFACE
COMMS
ACTUATE
COMMS
LOW LEVEL
CONTROL
HIGH LEVEL
CONTROL
SENSE
VEHICLE
What is RoboFlag?
RoboFlag System
Overhead cameras
Vision
computer
Arbiter
Computers
for each entity
RF
transceiver
..
.
..
Leverage RoboCup Technology
SOFTWARE ARCHITECTURE
LOW LEVEL CONTROL INTERFACE
WIRELESS
INTERFACE
LOCAL
MACHINE VISION
BASED
GLOBAL AND
LOCAL SENSING
VEHICLE
HIGH LEVEL
CONTROL
VEHICLE
HIGH LEVEL
CONTROL
GLOBAL
COMMUNICATIONS NETWORK
SIMULATOR
ARBITER
HUMAN
INTERFACE
CENTRAL
CONTROL
VEHICLE
LOW LEVEL
CONTROL
VEHICLE
LOW LEVEL
CONTROL
HARDWARE ARCHITECTURE
HARDWARE PORT
INTERFACE AND
ARBITRATION
COMPUTER
MACHINE VISION
COMPUTER
LOCAL
VEHICLE(S)
HIGH LEVEL
CONTROL
COMPUTER
HARDWARE PORT
WIRELESS
HARDWARE
LOCAL
VEHICLE(S)
HIGH LEVEL
CONTROL
COMPUTER
HUMAN
INTERFACE
COMPUTER
CENTRAL CONTROL
AND
COMMUNICATIONS NETWORK
COMPUTER
HUMAN
INTERFACE
COMPUTER
WIRELESS
HARDWARE
VEHICLE
VEHICLE
SIMPLE COMMUNICATIONS NETWORK MODEL:
U i : communicating subsystem i
Bi , j : maximum bandwidth from U i to U j , data units/frame
Li , j : latency from U i to U j , frames
buffer 0
Ui
Bi,j data units
buffer Li,j -1
Bi,j data units
buffer Li,j
Bi,j data units
Uj
RoboFlag Simulation Environment
Hardware Environment
People
 Michael
Babish (Research Support)
 Andrey Klochko (Programmer)
 JinWoo Lee (Post-Doc)
 30 UG and M.Eng. students
Shared platform with DARPA MICA
The RoboFlag Drill: Matt Earl
Defenders
di  f (di , ui ) ui (t ) U
Attackers
a j  g (a j , v j ) v j (t ) V
Constraints
-defenders cannot enter defense zone
-no collisions
•Defender objective: pick u(t) to minimize number of
attackers within defense zone at time T.
•Attacker objective: pick v(t) to maximize number of
attackers within defense zone at time T.
Problem: Consider the RoboFlag Drill with the
following assumptions
•irrational attackers (drones)
•full and perfect information
•collisions are ok
•simple 2nd order defender
dynamics
Model as a discrete time mixed logical dynamical (MLD)
system (Bemporad & Morari 1999)
•linear dynamics
•logical rules
•inequality constraints
Defenders
dynamics
xi  xi  u xi
yi  yi  u yi
umax  u xi , u yi  umax
constraints (must not enter defense zone)
( xi  b)  ( xi  b)  ( yi  b)  ( yi  b)
intercept region (dotted region in figure above)
Ii (t )  {( x, y) : (c  x  xi  c)  (c  y  yi  c)}
Attackers
auxiliary binary variables
 ij  1  ( x j , y j )  Ii
 j  1  (x j , y j ) G
dynamics
rj (t  1)  rj (t )  v j a j (t )
Optimal control policy
we convert the system into MLD form using HYSDEL
(Torrisi, Bemporad, and Mignone 2000)
Na
min   j (T )
u ,
j 1
x(t  1)  Ax(t )  B1u(t )  B2 (t ), x(0)  xo
E1 x(t )  E2u (t )  E3 (t )  E5
this can be written as a mixed integer linear program
(MILP)
T
min{ f z : Az  b}
z
Results
• MILP problem: 4040 integer variables, 400 continuous
variables,13580 constraints
• CPLEX solves in 244 seconds on Linux PIII 866MHz
Results
Evaluation of this approach for
cooperative control
Good
• easy to model complex systems
• easy to formulate complex tasks via a cost function
to minimize and constraints to be satisfied
• handles very general constraints
• codes available for solving mixed integer programs
• gives optimal strategy
Bad
• computationally intensive
• constraints only enforced at discrete times.
• does not exploit structure
A new approach to reduce computation
Exploit structure of the problem by
considering the discrete and continuous
parts separately.
Form an intercept tree
Exploit motion primitives
- Prune intercept tree
- Find feasible paths within tree
Path Planning under Uncertainty:
Myungsoo Jun
Capture uncertainty in information with a probabilistic
approach
MAIN IDEAS:
• Construction of probability map from available data
• Measurement data
• A priori statistics of environments
• Convert the probability map to a directed graph
• Path planning by solving shortest path problem in
digraph
Probability Map Building
• Measurement update by measured data
sensor characteristics
• Time update by a priori statistics of environment
• Map building
environment statistics
From this can obtain probability distribution that at least one
opponent is at a certain location
Conversion to Digraph
0.015
0.02
0.013
0.02
1
2
0.02
0.015
0.015
0.01
6
0.013
0.013
7
0.015
0.01
5
4
0.013
3
8
9
0.001
0.013
0.001
0.013
0.001
Probability Map
Digraph
Examples
Dynamic Replanning
Case with Multiple Vehicles
Simulation
Contribution and Future Work
Contribution:
• Building a probability map in uncertain dynamic
environments
• Path planning of multiple vehicles in uncertain dynamic
environments based on probability maps
• Integrating map building and path planning
Future Work:
• Consideration of time and velocity in path planning for
multiple vehicles
• Consideration penalty for frequent acceleration and
deceleration
• Improving map building computation for real-time application
Obstacle Avoidance in Dynamic
Environments: Pritam Ganguly
Objective: Computationally fast algorithms for path
planning in multi-agent adversarial environments with delayed
information.
APPROACH
•Game Theoretic: Avoiding a rational adversary in a delayed
environment can be modeled as a non-cooperative imperfect
information game . Trajectory generation is an outcome of
such an approach.
•Randomized Algorithm: This algorithm uses an existing
trajectory generation routine to generate feasible paths in the
presence of obstacles. One way to incorporate the effect of delay
is to associate with each obstacle a reachability regime over the
delayed steps. Frazzoli, Dahleh, and Feron
Randomized Algorithm
Terminology:
•Primary Node:
An equilibrium configuration
belonging to the state-space of the
agent.
•Secondary Node:
An element of the state space of
the agent which lies on the path
from the initial point to a primary
node.
Randomized Algorithm
Main Idea:
(Frazzoli,Dahleh & Feron ‘00)
•The main idea is to search for
random intermediate points
in the state-space which might generate a feasible path to
the destination. A feasible path being the one without any
collisions.
•Among all the feasible paths the one with the lowest cost
(eg. time) is then chosen.
•The underlying assumption in using this algorithm is that
one already has a way of generating trajectories in the
absence of obstacles.
Initialize tree
with starting position
Randomized Algorithm
Randomly generate primary
node and also a start point
from the already generated
tree
Main Idea and Implementation:
•This algorithm is probabilistically
complete: with probability one, it
returns a feasible path if there exists
one.
No
Is Path(start,primary)
feasible
yes
•Instead of using a tree data
structure, use a grid data structure
which takes a large storage space
but has faster access time.
Generate random
secondary points and
add them to the tree
No
Is Path(secondary,
destination) feasible
yes
Feasible Path
found, update
costs
Future Work
• Implement the randomized algorithm framework
for multiple agents in a centralized fashion, which would
be a relatively easy extension to the present
algorithm by increasing the state-space dimension.
• Develop a protocol
enabling the decentralization
of the above computation, and prove that the protocol achieves
the desired objective.
Atif Chaudhry
 Survey
published research on multiple
vehicle control
 Investigating
relationship between
RoboFlag framework and desired
military capabilities of autonomous
vehicles