Transcript Multivehicle Cooperative Control

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

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
..
.
..
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
People
 Michael
Babish (Research Support)
 Andrey Klochko (Programmer)
 JinWoo Lee (Post-Doc)
 30 UG and M.Eng. students
The RoboFlag Drill
Start out simple and work up
(Earl and D’Andrea ‘02)
• Attacking robots are drones
directed toward defense zone
• Defending robots want to
intercept attackers before they
enter the defense zone
• Constraints: defenders must
avoid collisions and must not
enter the defense zone;
defenders have limited control
authority
The RoboFlag Drill: Modeling
Model drill as a mixed logical dynamical system subject to
constraints (MLD system) (Bemporad and Morari ‘99)
Defender dynamics
xD   xD  ux
yD   yD  u y
umax  u x , u y  umax
Constraints
( xD , yD )  defense zone
no collisions
The RoboFlag Drill: Modeling
Attacker dynamics
Constraints
 v if active
r
0 if inactive
 (t )  1  ( xA , y A )  defense zone
and more logical constraints
The RoboFlag Drill: MLD form
Converting logic expressions into inequalities
using HYSDEL (Torrisi et al. ‘00) we can write
system in MLD form
x(t  1)  Ax(t )  B1u (t )  B2 (t )  B3 z (t )
E1 x(t )  E2u (t )  E3 (t )  E4 z (t )  E5
x(0)  x0
x(t )  ( xc , xl ) xc (t ) 
u (t ) 
m
nc
 (t ) {0,1}
n
xl (t ) {0,1}
nl
z (t ) 
nz
The RoboFlag Drill
Strategy synthesis using an optimization approach
(Bemporad and Morari ‘99)
Using this modeling approach the cost can
easily model a wide array of objectives
We take the cost to be the total score of the drill
NA
Total Score    i (T )
i 1
T is the final time and N A is the number of attackers
Objective: Find control input that minimizes the cost
subject to the dynamics and constraints
The RoboFlag Drill: Results
The optimization problem reduces to a mixed integer
linear program (MILP)
• 3 defenders, 8 attackers
• MILP problem:
•4040 integer variables
•400 continuous variables
•13580 constraints
• CPLEX solves in 244 seconds
on Linux PIII 866MHz
The RoboFlag Drill
FUTURE WORK:
• Better modeling to avoid discretization in time
• Speed up solution time
• Perform optimization repeatedly (MPC) to obtain
strategy for dynamically changing and uncertain
environments
• Add more components from the RoboFlag game
(limited sensor footprint, latency and bandwidth
limitations, etc.)
• Decentralization
People
 Matthew
Earl (Graduate Student)
Obstacle Avoidance in Dynamic
Environments
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.
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 that is it returns a feasible
path if there exists one, else it returns
failure, in the probabilistic sense.
No
Is Path(start,primary)
feasible
yes
•Contrary to the tree data structure
that was used by the author to store
the data, we 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
•Implementing 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.
•Developing a protocol
enabling the decentralization
of the above computation. PROVE that the protocol achieves
the desired objective.
People
 Pritam
Ganguly (Graduate Student)
Path Planning under Uncertainty
Motivation:
• Uncertainty in information leads naturally to
probabilistic approach
MAIN IDEAS:
• Construction of probability map from available data
• Measurement data
• A priori statistics
• 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
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
Simulation
Dynamic Replanning
Case with Multiple Vehicles
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 map
Future Works:
• Finding an algorithm to efficiently integrate map building and
path planning
• Consideration of time and velocity in path planning for
multiple vehicles
• Consideration penalty for frequent acceleration and
deceleration
People
 Myungsoo
Jun (Post-Doc)
 Atif Chaudry (Graduate Student)