Transcript Boulder_SAE Hedrick

Multi-agent
Collaborative Flight
Experiment
Karl Hedrick
UC Berkeley
1
CIRPAS, Camp Roberts, CA
Operated by the Naval Post Graduate School
2
Collaborative UAV Flight Test
GOALS of the August, 2006 Experiment
Thrust 1. Distributed collaboration with limited
communications
a.) multi-vehicle, multi-step task allocation
b.) limited ground-air and air-air com
c.) user task cancellation/reallocation
d.) agent created tasks
e.) task prioritization
f.) no fly zone filter and re-planner
g.) Simple human/UAV team interface
Thrust 2. Vision-based river following.
a.) Ability to identify and search for the desired structure (river).
b.) Ability to accurately track the river once identified.
c.) Ability to accurately map the boundaries of the river.
3
Collaboration Research Goals In
General
Study distributed mechanisms for the collaboration of Unmanned
Aerial Vehicles (UAV)
Generalize a large number of missions under one framework
• Surveillance/Mapping
• Border Patrol
• Search & Rescue
• Convoy Protection, etc.
Emphasis on Robustness rather than Optimization:
• Addition and Deletion of Tasks
• Addition and Removal/Failure of Agents
• Limited and/or Failed communication
4
C3UV Collaboration Software
GOALS
•Transmit desired mission from user to agents
•Provide user with fused information from agents
•Decompose and assign tasks among agents in response to dynamic mission definition
•Accomplish tasks in an efficient and robust manner
Agent in range of user
Mission state est.
Mission state estimate
User
Agent out of range
Command
station
New tasks
Cancel tasks
5
Communication Infrastructure
User
Piccolo
Autopilot
2.4 GHz
ethernet
PC104
New tasks
Cancel tasks
Piccolo
Groundstation
900 MHz
radio
Piccolo
Autopilot
PC104
Command
station
6
The Mission
User defines mission in terms of tasks
Philosophy
“The user specifies what
he or she would like
accomplished.
The system decides how
to do so efficiently.”
7
Mission Commander Interface
8
Graphical User Interface
C:\Documents and
Settings\Sonia\Desktop\CommanderSDK.exe
9
Monitor Area Task
Task details
Goal
Trajectory
Detect any velocity-bounded intruder that cannot leave a defined
box
UAV path depends on maximum speed of intruder; path
becomes a “lawnmower” trajectory if maximum speed is zero
11
Guaranteed Search Task
Task details
Goal
Simulation Result
Detect any intruder traveling from a known start point with a
bounded velocity
500 of 500 intruders detected in simulation
12
Avoiding a no fly zone: active filter
Task
Controller
No fly zone
Visit task
Desired autopilot
command
No Fly
Zone Filter
Safe autopilot
command
Autopilot
18
BLCC- Berkeley “Language” for
Collaborative Control
 Define the mission and communicate it to team members
 Define the “state” of each agent
 Define the mission “state”
 Allow for faults
 Allow for conflict resolution
 Define the information to be communicated between agents.
19
Agents (UAVs)
 AgentID

 Position[ x, y ] 


Velocty[v x , v y ]


k
X  k

ˆ
T

 Plan[ P k ]



Cost ( P k )

 AgentID 


M k  Tˆ k

Cost ( P k )


Transition Logic: Governs
transitions of tasks and subtasks
Communication: Deconflicts plans
and synchronizes information
between agents T k vs. Tˆ k
Planner(ex. path-planner):
calculates cost, generates plan and
chooses “todo”
Low-level Controller (ex. waypoint
tracker)
20
Task-Point List
Every process and each agent communicates primarily through the taskpoint list
A task-point list exists for each task and is manipulated by each process to
generate a desired mode/task/mission
1
2
3
4
21
Real-Time Task Allocation Algorithms
Multiple agents/Multiple Tasks
 Emphasis on real-time computation and robustness to
communication limitations and agent failure.
 Recent progress on optimal and sub-optimal algorithms
22
Task Allocation
Given n UAVs and m tasks, how do we assign tasks to UAVs?
• Assume that each task is simply a point to be visited, with some time spent at that
point.
• Neglect UAV turn rate constraints – assume constant velocity
• For each UAV, let a tour be an ordered set of targets that it will visit
• Let the cost of tour be the total time required to complete. For a constant velocity
UAV with no turn rate constraint, this time corresponds to distance.
Often this is posed as an instance of the multiple traveling salesman problem
24
Multiple Traveling Salesman
The Multiple Traveling Salesman Problems focuses on minimizing
total cost. For n UAVs, with the cost of a tour for UAV j = Tj
Our problem differs: we should focus on minimizing the max cost of
any tour
• Given that we’re working with constant velocity UAVs, the cost in fuel of
having a UAV circle is the same as having it do some work.
• For our problem, this corresponds to a minimum clock time problem. This
problem is often referred to as the min-max Vehicle Routing Problem.
25
Min-Max Vehicle Routing
The min-max Vehicle Routing Problem is NP hard. There is no
polynomial time solution.
We’d like to develop algorithms find near-optimal solutions to the minmax problem.
In practice, we’d like to build algorithms that are robust to
communication losses; with perfect communication, we’d like these
algorithms to achieve near optimal performance.
26
The Greedy Algorithm
In constructing a tour, let the UAV with the lowest cost function for its partial
tour choose the next task.
This algorithm leads to balanced tours among UAVs: all UAVs perform tours
of roughly equal cost.
• For the min-max VRP, optimal solutions will contain tours balanced to within the
maximum distance between any two tasks.
This is a fast algorithm that creates balanced tours
Sub-optimal
2 questions:
• How well does this work?
• How do we implement this in a distributed system with limited communication?
27
Approximate Multi-step Distributed
Min-Max Vehicle Routing Algorithm
0 Communication and 1 Computation
28
Example continued…
1 Communication and 1 Computation
29
Example continued…
1 Communication and 2 Computation
30
Example continued…
2 Communication and 2 Computation
31
Collaboration Architecture
Communication
Integrates
MSEA and
MSEB
Retains most
up-to-date
information
Information Base
Internal
State
ISA
Mission
State
Estimate
MSEA
MSEB
Receive
MSEA
Computation
Decision
Functions
Complete
Redo
Fault
Choose
Task Execution
Agent A
Broadcast
User Plan
32
How we implement in software
Collaboration
Sensors
Mission
Plan
Piccolo
Interface
Sensor
Data
Aircraft
Commands
Telemetry
Datahub
Collaboration
info
A2A
Wireless
Mission
AC
Plan
User
High Level Commands
Commands Telemetry
Payload
Interface
Task
Execution
Safe Flight
Controller
Controllers
33
Sig Rascal 110 airframe
Balsa frame remote control aircraft kit with 110” wingspan
Modifications:
•32 cc gasoline engine with vibration isolation mounts
•Dual fuel tanks for 60 min flight time
•Carbon fiber reinforcement to support payload
•26 lb takeoff weight
•Piccolo avionics system
34
Berkeley Air Force
35
PC104 stack and payload tray
•PC104 with 700 MHz Pentium III processor
•2 GB flash memory (16 GB on vision plane)
•Bidirectional 1 Watt amplifier for 802.11b communication
•Vibration isolating suspension
•Wireless analog video transmitter
36
UC Berkeley UAV Platform: Autopilot, HIL Sim
 Low Level Guidance and Control Provided by Cloud Cap Technology’s Piccolo Avionics Module and
Corresponding Ground Station System
 Capable of operating multiple vehicles. C3UV has successfully flown four vehicles simultaneously.
Piccolo
Avionics
Ground Station
Wireless Link
Actuators and
Sensors Signals
Simulated
States
Ground Station
Computer
Manual Control
Console
Hardware In Loop
(HIL) Simulation
Computer
38
UC Berkeley UAV Platform: Communications
Three Communications Channels:
 Autopilot Avionics and Ground station: 900 MHz
Ground Station
 Plane to Plane communication: 2.4 GHz
 Video downlink: 1.2 GHz
39
Piccolo avionics system
Piccolo
Piccolo
900 MHz UHF radio
“Piccolo channel”
Autopilot commands and telemetry
Piccolo Operator Interface
•Send waypoint commands
•Monitor aircraft physical state
Piccolo
Ground station
40
User interfaces and Piccolo payload
channel
Piccolo
PC104
PC104
900 MHz UHF radio
“Piccolo channel”
Autopilot commands and telemetry
“Payload channel”
Communication between
PC104s and GUIs
Piccolo Operator Interface
•Send waypoint commands
•Monitor aircraft physical state
Piccolo
Piccolo
Ground station
Mission Commander Interface
•Create tasks
•Monitor status of tasks and
UAVs
Process Monitor Interface
•Activate or idle processes
•Monitor process states
41
Aircraft to aircraft communication
Piccolo
PC104
Piccolo
PC104
Piccolo
PC104
2.4 GHz 802.11b ad-hoc wireless ethernet
Mission state estimates
Task allocation data
42
Preview of collaboration experiment Logistics
Mission Commander Tent
Status Monitor Tent
Mission Commander Interface
Video downlink from aircraft
Piccolo Operator Interface
Read-only display of Mission Commander Interface
Process Monitor Interface
Aircraft launch process
1.
Aircraft takes off under manual control
2.
Pilot gives control to Piccolo autopilot- aircraft flies on preloaded waypoint loop
3.
Onboard software is activated using Process Monitor Interface
** At this point the aircraft is controlled only via the Mission Commander Interface.
All other personnel serve only as monitors.**
43
UC Berkeley UAV Platform: All Together
GPS Ant.
Analog Video TX’s
Wing-Mounted
Camera
Air-Ground
UHF Ant.
Onboard computer and wireless communication radio
47
August ONR Demonstration
59
LESSONS LEARNED
Initially Air-Air com was so bad that mission performance was
unacceptable.
Improved amplifier/antenna combined with robust architecture allowed
us to accomplish complex missions successfully.
Ground-Air link needs to have a higher bandwidth for human/UAV
interaction.
Required computation including task allocation and vision processing
can be done on a Pentium III.
3 UAV’s with 4-5 tasks is already too complex for humans without
autonomy software.
Complex interaction between task allocation and priority system
needs further analysis.
60
The End
61